Relations

RELATIONS

Please note that the material on this website is not intended to be exhaustive.
This is intended as a summary and supplementary material to the required textbook.

Relation: R on a set S is a subset of the cartesian product S x S, i.e. R consists of ordered pairs (x, y) such that x and y both belong to S, i.e.
R Í S x S = { (x, y) | x Î S /\ y Î S }.

Reflexive Relation: A relation R on a set S is reflexive if for all x belonging to S, every ordered pair (x, x) belongs to R, i.e.
R Í S x S is reflexive if " x Î S Þ (x, x) Î R.

Irreflexive Relation: A relation R on a set S is irreflexive if for all x belonging to S, the ordered pair (x, x) does not belong to R, i.e.
R Í S x S is irreflexive if " x Î S Þ (x, x) Ï R.

Symmetric Relation: A relation R on a set S is symmetric if for every ordered pair (x, y) belonging to R it implies that (y, x) belongs to R for all elements x and y belonging S, i.e.
R Í S x S is symmetric if " (x, y) Î R Þ (y, x) Î R, for x, y Î S.

Antisymmetric Relation: A relation R on a set S is antisymmetric if for every ordered pair (x, y) belonging to R where x is not equal to y it implies that ordered pair (y, x) does not belong to R, i.e.
R Í S x S is antisymmetric if " (x, y) Î R, where x ¹ y, Þ (y, x) Ï R, for x, y Î S.

Asymmetric Relation: A relation R on a set S is asymmetric if (x, y) belongs to R implies that (y, x) does not belong to R for x and y belonging to S, i.e.
R Í S x S is asymmetric if (x, y) Î R Þ (y, x) Ï R, for x, y Î S.

Transitive Relation: A relation R on a set S is transitive if for every ordered pairs (x, y) and (y, z) belonging to R it implies that (x, z) belongs to R, for x, y, and x belonging to S, i.e.
R Í S x S is transitive if " (x, y) Î R /\ (y, z) Î R Þ (x, z) Î R, for x, y, z Î S.

Partial Order

is a relation R on a set S where R is reflexive, antisymmetric, and transitive, i.e. " x, y, z Î S

x £ x

x £ y /\ y £ x Þ x = y

x £ y /\ y £ z Þ x £ z

Partially Ordered Set or Poset: is a pair (S, R), where S is a set and R is a partial order on S.

N–Cube: The poset (P(S), Í) where S = {1, 2, ..., n}.

Example:	The following are partial orders.
	·	If S is any set and P(S) is its power set, then the relation of Í is a partial ordering of P(S).
	·	If S = { 1, 2, . . . , n }, then the poset (P(S), Í) is called the n-cube.
	·	Div (n) is the set of positive integers which divide n. The relation of divisibility is a partial order on the set S = Div (n).

Comparable Elements: Two elements x and y of a relation R are comparable if x £ y or y £ x.

Chain: is a subset T of a poset S where each pair of elements of T are comparable.

Antichain: is a subset T of a poset S where no pair of elements of T are comparable.

(See example.)

Total Order: is a relation R where every pair of elements is comparable.

Equivalence Relation: is a relation R on a set S where R is reflexive, symmetric, and transitive.

Equivalence Class: If S is a set, R is an equivalence relation on S, and x is an element of S, then the equivalence class of x is the set of elements y such that xRy and where y is an element of S, i.e.
[x] = { y | xRy ' x, y Î S }.

NOTE:

If n is a positive integer, then two integers a and b are congruent modulo n if n | (a – b), i.e. if n divides a – b and it is denoted by a º b (mod n). We can also say that a is congruent to b modulo n.

Example:	The following are equivalence relations:
	·	If S is any set, then the relation "a = b" is an equivalence relation on S.
	·	If n ÎZ ⁺, then the relation "a is congruent to b (mod n)" is an equivalence relation.
		NOTE:	The equivalence classes of the relation "congruence module n" are called the congruence classes modulo n.

Binary Relation: If S and T are sets, then the binary relation R from set S to set T is a subset of the cartesian product S x T, i.e. R consists of ordered pairs (s, t) such that s belongs to S and t belongs to T, i.e.
R Í S x T = { (s, t) | s Î S /\ t Î T }.
The set S is said to be the domain of R while the set T is said to be the range of R.

N–ary Relation: R between the elements of n sets S₁, S₂, ¼, S_n is a subset of the Cartesian product of those n sets, i.e.
R Í S₁ x S₂ x ¼ x S_n = { (x₁, x₂, ¼ , x_n) | x₁ Î S₁, x₂ Î S₂, ¼, x_n Î S_n }.

Hasse Diagram

of a poset (S, R) is the graph G where

S consists of the nodes or vertices of G, i.e. V(G) = S
if x, y Î S, then {x, y} Î E(G) if xRy where x ¹ y, and there does not exist an element z Î S, ' x ¹ z, y ¹ z /\ xRz, zRy.

ASSIGNMENT

RELATIONS

Please note that the material on this website is not intended to be exhaustive. This is intended as a summary and supplementary material to the required textbook.

© 2000-07-05 cpsm ; last update 2007-08-20 20:26

Please note that the material on this website is not intended to be exhaustive.
This is intended as a summary and supplementary material to the required textbook.