x) xσx

( " x ) ( " y ) (xσ y è yσ x)

( " x ) ( " y ) ( " z ) (xσ y and yσ zè xσ z)

The inverse statement is also true: each equivalence σ defined an a set A corresponds to some partition of the set A.

Properties of relations (another variant of explanation):

Let A be a set, relation R A × A.

1. Relation R is reflexive “if (a, a) R for every a A” (if every element in A is related to itself).

1.a) Relation R A × A is not reflexive if “There exists a A such that

(a, a) R”.

Ex: Let A = {1, 2, 3}.

2. R is symmetric if (a, b) R implies (b, a) R (if a is related to b then b is also related to a).

2.a) R is not symmetric if there exists (a, b) R such that (b, a) Ï R.

Ex: A = {1, 2, 3}

Relations represented by matrixes (3), (4), (5), (6) are symmetric.

Relations represented by matrixes (7), (8), (9) are not symmetric.

3. R is antisymmetric if (a, b) R and (b, a) R implies a = b, (if a b then possibly a is related to b or possibly b is related to a, but never both).

3.a) R is not antisymmetric if there exist distinct elements a and b such that

(a, b) R and (b, a) R.

Ex: A = {1, 2, 3}. Relations (10), (11), (12), (13), (14) are antisymmetric.

Note: a relation can be symmetric and antisymmetric at the same time. See relations (6) and (13).

Relations (15), (16) are not antisymmetric.

Here (2, 1) R and (1, 2) R and (1 2).

4. R is transitive if (a, b) R and (b, c) R (a, c) R.

4.a) R is not transitive if there exist (a, b) R and (b, c) R such that (a, c) R

Relations (17), (18) are transitive.

(1, 3) R and (3, 1) R (1, 1) R (1, 1) R and (1, 2) R (1, 2) R (1, 1) R and (1, 3) R (1, 3) R

transitive

(1, 1)& (1, 1) (1, 1) It is transitive for the same reason why it is antisymmetric. (See relation (14)): (1, 1)& (1, 1) (1 = 1); In the condition part we can use the same 2-tuple from the main diagonal two times.

Relations (19), (20) are not transitive.

(1, 2) R and (2, 3) R but (1, 3) R

(1, 2) R and (1, 3) R. We have not a pair with 2 in the first position. So, it is a wrong condition for transitivity.

General types of relations

1. Relation R is equivalence relation if it is reflexive, symmetric and transitive.

Ex: Relations (21), (22), (23) are equivalences.

Relations (24), (25), (26) are not equivalences.

reflexive, symmetric, but not transitive: (1, 2) R and (2, 3) R but (1, 3) R

not reflexive: (1, 1) R, symmetric, not transitive: (1, 3) R and (3, 1) R but (1, 1) R.

.

reflexive, not symmetric: (1, 3) R but (3, 1) R, not transitive: (3, 1) R and (1, 1) R but (3, 1) R.

H/a. Given a set of table tennis players P = {Bob, Sam, Tom, Paul}.

Define a relation “to play in the same team in doubles” by a matrix. Check the properties of the relation.

Topic: Order relation

A finite relation O is called a partial order if it is reflexive, transitive and antisymmetric. The partial order is often denoted by ≤.

Example: Let P(U) denote a system of subsets of the universal set U. Then the relation of inclusion of subsets A_i ⊆ A_j is a relation of partial order on P(U). Note: A_i , A_j ⊆ U, same: A_i , A_j Î P(U).

A binary relation S is called a strict (irreflexive, antireflexive) order if it is antireflexive, antisymmetric; and transitive. It is often denoted by <.

Elements a and b are called comparable on the basis of the order relation R if aRb or bRa is true. A set A with the relation order (strict or partial order) defined on it is called completely ordered if any two elements of A are comparable on the basis of R.

Examples: numbers on the number axis are completely ordered on the basis of the relation “more-less”. The relation “not heavier” between the weights of different objects is an example of the partial order.

A binary relation T is called tolerance on set A if it is reflexive, symmetric and nontransitive.

Example: Let A be a set of 4-letter arrangements.

A = {aaaa, aaab, …, яяяю, яяяя}. A relation of tolerance is defined on this set of arrangements. An arrangement x is tolerant to arrangement y if it differs from y only by one symbol in a corresponding position. Then in the following sequence of 4-letter arrangements, each two neighboring arrangements are linked by the relation of tolerance (note: only neighboring arrangements):

муха, мура, тура, тара, кара, каре, кафе, кафр, каюр, каюк, крюк, крок, срок, сток, стон, слон.

Tolerance is a formal substitution for the intuitive idea of resemblance and similarity, likeness. If the first object is like some second object and the second is like a third one, it does not mean that the first and the third objects are also similar.

h/t: G ive an example of а tolerance relation. Check the properties of this relation.

Topic: Functions

A function is a special relation.

Def: a function consists of 3 things:

1. a nonempty set A, called the domain of the function.

2. a nonempty set B, called the range of the function.

3. a rule that assigns to each element of A one, and only one element of B.

Notation: A è B; (read “ f is a function from A to B”).

If a ∈ A, then f(a) is the image of a under the function f.

f(a) ∈ B is assigned to a the rule f.

Simple pictures:

Ex: Let A={…, -2, -1, 0, 1, 2, …}, B={0, 1, 2, …}.

We can define a function f: Aè B by the formula

f(x)= (here we specify the rule f).

Ex: Let S be any finite set. Let P(S) be a power set. Then we can define a function f: P(S) è N by the rule: f(A)=|A| for each subset A of S. In words, f(A) is the size of A.

General types of functions.

Def: f: Aè B is called is surjective if for every element bÎ B there is at least one element aÎ A for which f(a) = b.

Ex:

f(x)=1, f(b)=1, f(c)=1, f(d)=2.

The function is surjective.

Ex.: A={b, c, d, x}, B={1, 2};

g(b)=1, g(c)=1, g(d)=1, d(x)=1

g(a) is not a surjective function: there is no such aÎ A, such that g(a)=2.

Def: a function f: Aè B is called injective if ≠ then f( f(

It is a one-to-one function.

Ex:

Here f(a) is an injective function.

Ex.: g: Nè N, where g(n)= is also injective because g(i)= ≠ g(i)= , for all j≠ i.

On the other hand g: Zè N, g(i)= is not injective.

Z={…, -2, -1, 0, 1, 2, …}, N={0, 1, 2, …}

-2≠ 2 but g(-2)=g(2)=4

Def: f: Aè B is called bijective if it is both injective and surjective. (It is a one-to-one correspondence between the elements of A and the elements of B).

f: {set of 256 symbols} è {0, 1, …, 255}

f(‘c’) = 67, f(‘d’) = 100, etc

f(NUL) = 0 (nonvisible).