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.