A (binary) relation R from a set X to a set Y is a subset of XxY.

If (x, y)∈R, we write xRy and say that x is relation to y.

If X=Y, we call R a (binary) relation on X.

domain of R is Dom(R) = { x∈X| (x, y)∈R for some y∈Y}.

range of R is Rng(R) = { y∈Y|(x,y)∈R for some x∈X}

① draw dots to represent the elements of X.

② If the element (x,y) is in R, draw an arrow from x to y.

- reflexive             xRx for all x∈X.

- symmetric           if xRy, then yRx.

- anti-symmetric    if xRy and yRx, then x=y.

- transitive            if xRy  and yRz, then xRz.

- If R is reflexive, anti-symmetric, transitive, then R is a partial order. and If (x, y) or (y, x)∈R for      every pair of elements in X, then R is total order.

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}

Let R1 be a relation from X to Y and R2 be a relation from Y to Z.

the composition of R1 and R2, denote R2∘R1, is the relation from X to Z defined by

R2∘R1 = { (x, z)| (x, y)∈R1 and (y, z)∈R2 for some y∈Y}.

R is an equivalence relation if R is reflexive, symmetric and transitive.

Let S be a partition of a set X. if for some set T in S, x, y are in T, Define xRy on X. Then R is an equivalence relation on X. 

Let R be an equivalence relation on a set X. For each a∈X, let

[a] = { x∈X | xRa }

then 

S = { [a] | a∈X}

is a partition of X.

the sets [a] are called the equivalence classes of X given by the relation R.

Let X,Y be sets and R a relation from X to Y.

Write the matrix A of the relation R as follows:

- Rows of A = elements of X

- Columns of A = elements of Y

- Element a(ij) = if the element of X in low i and the element of Y in column j are related, it is 1 else 0.

Let R1 be the relation from X to Y and let R2 be the relation from Y to Z.

Let A1 be the matrix of R1 and let A2 be the matrix of R2.

The product of these matrices is A1A2.

if the (i,k)th entry in A1A2 is nonzero, then (Xi, Zk)∈R2∘R1.

Let A be the square matrix of a relation R from X to itself.

Let A^2 is the matrix product AA.

- R is reflexive if and only if all terms a(ii) in the main diagonal of A are 1.

- R is symmetric if and only if a(ij) = a(ji) for all i and j.

- R is transitive if A^2=A(whenever c(ij) in C = A^2 in nonzero then entry a(ij) is A is also nonzero.).

we call (x, y) on ordered pair.

(x1, x2)=(y1, y2) if and only if x1=y1, and x2=y2.

X x Y = { (x, y) | x∈X and y∈Y} 

A sequence is an ordered list.

S or {Sn} is a sequence named S, the entire sequence.

Sn is single element of the sequence S at index n.

A sub-sequence {Snk} is a sequence that consist of certain element of {Sn} retained in the original order in S.

A string over a set X is a finite sequence of elements from X.

an unordered collection of object.

A = {1, 3, 5, 7}

B = { n | n is a prime number} which we read as 'the set of all n such that n is a prime number'.

Two sets X and Y equal if ((x∈X -> x∈Y) ^ (x∈Y -> x∈X)).

cadinality, denoted by |X|, is the number of elements in a set X.(size)

We write X⊆Y to mean that any member of X is also in Y, and say that X is a subset.

X is proper subset if X ⊆ Y and X≠Y. 

The set of all subsets of X is called its power set P(X). Thus

P(X) =  { Y | Y⊆X}

A partition S on a set X is a familly {A1, A2, ... , An} of subsets of X, such that

S = {A| (A⊆X) ^ (Aj∩Ak = ø. for every j, k) ^ ( A1∪A2∪ ... ∪ An = X)

①union

X∪Y = { x| x∈X or x∈Y}

② intersection

X∩Y = { x| x∈X and x∈Y}

Two sets X and Y are disjoint if X∩Y = ø.

A collection of sets S is said to be pairwise disjoint if whenever X and Y are distinct sets in S, X and Y are disjoint. 

③ difference

X - Y = { x| x∈X and x∉Y}

④ complement

X^￣ = U - X

⑤ Other Notation

Let S = {A1, A2, A3, ... , An}

∪S = { x|x∈X for some X∈S} = A1∪A2∪ ... ∪An

∩S = { x|x∈X for all X∈S} = A1∩A2∩ ... ∩An