Overview

# equivalence relation

Results | All related links for this item | 1-15 of 15 results for:

Overview x clear all

Show only full text

## biconnected graph

Overview page. Subjects: Computing.

A graph G, either directed or undirected, with the property that for every three distinct vertices u, v, and w there is a path from u to w not containing v. For an undirected graph, this is...

## common denominator

Overview page. Subjects: Mathematics.

An integer that is exactly divisible by all the denominators of a group of fractions. Used in adding or subtracting where the first step is to express each fraction as an equivalent...

## component

Overview page. Subjects: Mathematics.

(of a graph)

A graph may be ‘in several pieces’ and these are called its components: two vertices are in the same component if and only if there is a path from one to the other. A...

## congruence

Overview page. Subjects: Mathematics.

(modulo n)

For each positive integer n, the relation of congruence between integers is defined as follows: a is congruent to b modulo n if ab is a multiple of n. This is written anull...

## congruence relation

Overview page. Subjects: Computing.

1 An equivalence relation defined on the integers in the following manner. Let m be some given but fixed positive integer and let a and b be arbitrary integers. Then a is...

## equivalence class

Overview page. Subjects: Computing.

A subset of a set S (on which an equivalence relation is defined) that consists of all the elements of S that are equivalent to each other, and to no other elements of S. An equivalence...

## Myhill equivalence

Overview page. Subjects: Computing.

An equivalence relation arising in formal language theory. If L is a language over alphabet Σ (see word) then its Myhill equivalence is the relation =M on Σ* defined as follows:

null...

## Nerode equivalence

Overview page. Subjects: Computing.

An equivalence relation, =N, arising in formal language theory. It is defined analogously to the Myhill equivalence by the weaker properties:

for a language L over Σ, u =Nnull...

## ordering relation

Overview page. Subjects: Philosophy.

A partial ordering on a set is a relation < that is transitive and reflexive and antisymmetric. That is, (i) x < y & y < zx < z; (ii) x < x; (iii) x < null...

## partition

Overview page. Subjects: Mathematics.

(of a positive integer)

A partition of the positive integer n is obtained by writing n=n 1+n 2+…+n k , where nnull...

## rational number

Overview page. Subjects: Mathematics.

Any number that can be expressed as the ratio of two integers. For example, 0.3333… is rational because it can be written as 1/3. √2, however, is an irrational number.

## relation

Overview page. Subjects: Computing.

A relation on a set S is usually a binary relation on S, though the notion can be extended to involve more than two elements. An example of a ternary relation, involving three elements, is ‘null...

## relation

Overview page. Subjects: Philosophy.

Philosophically relations are interesting because of the historic prejudice, given its most forceful expression by Leibniz, that they are somehow ‘unreal’ compared to the intrinsic, monadic...

## representative

Overview page. Subjects: Mathematics.

Given an equivalence relation on a set, any one of the equivalence classes can be specified by giving one of the elements in it. The particular element a used can be called a representative...

## residue class

Overview page. Subjects: Mathematics.

(modulo n)

An equivalence class for the equivalence relation of congruence modulo n. So, two integers are in the same class if they have the same remainder upon division by n. If [anull...