Relations Equivalence relations
Definition : A (binary) relation R from a set X to a set Y is a subset of the Cartesian product X ´ Y. If (x,y) Î R, we write xRy and say that x is related to y. In case of X = Y, we call R a (binary) relation on X.
The set {x Î X | (x,y) Î R for some y Î Y} is called the domain of R.
The set { y Î Y | (x,y) Î R for x Î X } is called the range of R.
Definition : A relation R on a set X is called reflexive if for all x Î X,
(x,x) Î R .
Definition : A relation R on a set X is called symmetric if for all x,y Î X, if
(x,y) Î R , then (y,x) Î R.
Definition : A relation R on a set X is called antisymmetric if for all x,y Î X, if (x,y) Î R and x ¹ y then (y,x) Ï R.
Definition : A relation R on a set X is called transitive if for all x,y,z Î X, if
(x,y) Î R and ( y,z) Î R then (x,z) Î R.
Definition : A relation R on a set X is called a partial order if R is reflexive, antisymmetric and transitive.
Definition : Given a partial order R on a set X, if x , y Î X and either (x,y) Î R or (y,x) Î R, then we say x and y are comparable. If every pair of elements in C is comparable, then R is called a total order.
Definition : Let R be a relation from X to Y. The inverse of R , denoted R-1, is the relation from Y to X defined by
R-1 = { (y,x) | (x,y) Î R }
Definition : Let R1 be a relation from X to Y and R2 be a relation from Y to Z. The composition of R1 and R2 , denoted R2 o R1 , is the relation from X to Z defined by
R2 o R1 = { (x,z) | (x,y) Î R1 and (y,z) Î R2 for some y Î Y }.
Definition :
A relation that is reflexive, symmetric and transitive on a set X is called an equivalence relation on X.
Given R be an equivalence relation on X, and for each a Î X let
[a] = { x Î X | x R a } , [a] is called the equivalence class of X with respect to R.
A collection S of non-empty subsets of X is said to be a partition of the set X if every element in X belongs to exactly one member of S.
Theorem : Let R be an equivalence relation on a set X, then the equivalence classes S = { [a] | a Î X } is a partition of X.
Theorem : Given a partition of a set X, we can define an equivalence relation R on X such that each member of the partition is an equivalence class of X with respect to R .
Functions :
Definition : A function f is a special kind of relation. In order for a relation f from X to Y to be a function, its domain must equal to X and if (x,y) and (x,y') Î f , we must have y = y' .
Examples :
Definition : If f is a function from X to Y is said to be one-to-one (or injective ) if for each y Î Y, there is at most one x Î X with f(x)= y
Definition : If f is a function from X to Y and the range of f is Y, then f is said to be onto Y (or an onto function or a surjective function.)
Definition : A function is both one-to-one and onto is called a bijection.