Curs 1

Sets. Relations. Equivalence relations. Factor set. Order relations. Functional relations Sets

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

1 / 67

Sets. Relations. Equivalence relations. Factor set. Order relations. Functional relations Sets In order to avoid paradoxes, we shall consider that all the elements of the sets which are considered belong to a certain universal or total set T . Also, we consider the empty set, which may be defined as ∅ := {x ∈ T |x 6= x} .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

1 / 67

Sets. Relations. Equivalence relations. Factor set. Order relations. Functional relations Sets In order to avoid paradoxes, we shall consider that all the elements of the sets which are considered belong to a certain universal or total set T . Also, we consider the empty set, which may be defined as ∅ := {x ∈ T |x 6= x} .

Remark Using the property of the logical operation of implication, according to which ”False implies anything”, any statement made about the elements of the empty set is automatically true!

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

1 / 67

Sets. Relations. Equivalence relations. Factor set. Order relations. Functional relations Sets In order to avoid paradoxes, we shall consider that all the elements of the sets which are considered belong to a certain universal or total set T . Also, we consider the empty set, which may be defined as ∅ := {x ∈ T |x 6= x} .

Remark Using the property of the logical operation of implication, according to which ”False implies anything”, any statement made about the elements of the empty set is automatically true!

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

1 / 67

Relations between sets Definition Let A and B be two sets. We call the two sets equal, and write A = B, if for any element x ∈ T of the total set the following equivalence holds x ∈ A ⇐⇒ x ∈ B .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

2 / 67

Relations between sets Definition Let A and B be two sets. We call the two sets equal, and write A = B, if for any element x ∈ T of the total set the following equivalence holds x ∈ A ⇐⇒ x ∈ B .

Proposition For any sets A, B, and C the following properties hold: A=A A = B ∧ B = C =⇒ A = C A = B =⇒ B = A

Lect.dr. M.Chi¸s ()

Lecture 1

(reflexivity) (transitivity) (simmetry)

6.X.2008

2 / 67

Relations between sets Definition Let A and B be two sets. We call the two sets equal, and write A = B, if for any element x ∈ T of the total set the following equivalence holds x ∈ A ⇐⇒ x ∈ B .

Proposition For any sets A, B, and C the following properties hold: A=A A = B ∧ B = C =⇒ A = C A = B =⇒ B = A

Lect.dr. M.Chi¸s ()

Lecture 1

(reflexivity) (transitivity) (simmetry)

6.X.2008

2 / 67

Definition Let A and B be two sets. We say that the set A is included in the set B, and write A ⊆ B, if for any element x ∈ T of the total set the following implication holds x ∈ A =⇒ x ∈ B . In this case we call the set A a subset of the set B, respectively the set B a superset of the set A.

Proposition For any sets A, B, and C the following properties hold: A⊆A A ⊆ B ∧ B ⊆ C =⇒ A ⊆ C A ⊆ B ∧ B ⊆ A =⇒ A = B

Lect.dr. M.Chi¸s ()

Lecture 1

(reflexivity) (transitivity) (antisimmetry)

6.X.2008

3 / 67

Definition Let A and B be two sets. We say that the set A is included in the set B, and write A ⊆ B, if for any element x ∈ T of the total set the following implication holds x ∈ A =⇒ x ∈ B . In this case we call the set A a subset of the set B, respectively the set B a superset of the set A.

Proposition For any sets A, B, and C the following properties hold: A⊆A A ⊆ B ∧ B ⊆ C =⇒ A ⊆ C A ⊆ B ∧ B ⊆ A =⇒ A = B

Lect.dr. M.Chi¸s ()

Lecture 1

(reflexivity) (transitivity) (antisimmetry)

6.X.2008

3 / 67

Operations with sets We shall consider T to be a fixed total set, such that all the sets which are considered are subsets of the set T . We shall denote by Set(T ) the class of all sets included in the total set T .

Definition Complementation is the unary operation CT : Set(T ) −→ Set(T ) , by which we associate to any set A the complementary set of the set A with respect to the total set T , denoted CT (A)(or sometimes, if the set T is implicit, simply A), which is formed by exactly those elements of the total set not belonging to the set A: CT (A) = {x ∈ T | x 6∈ A} .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

4 / 67

Operations with sets We shall consider T to be a fixed total set, such that all the sets which are considered are subsets of the set T . We shall denote by Set(T ) the class of all sets included in the total set T .

Definition Complementation is the unary operation CT : Set(T ) −→ Set(T ) , by which we associate to any set A the complementary set of the set A with respect to the total set T , denoted CT (A)(or sometimes, if the set T is implicit, simply A), which is formed by exactly those elements of the total set not belonging to the set A: CT (A) = {x ∈ T | x 6∈ A} .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

4 / 67

Proposition For any set A ∈ Set(T ) the equality CT (CT (A)) = A(or A = A) is true.

Proposition Let A and B be two arbitrary sets. Then A ⊆ B if and only if CT (B) ⊆ CT (A)(or B ⊆ A).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

5 / 67

Proposition For any set A ∈ Set(T ) the equality CT (CT (A)) = A(or A = A) is true.

Proposition Let A and B be two arbitrary sets. Then A ⊆ B if and only if CT (B) ⊆ CT (A)(or B ⊆ A).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

5 / 67

Definition Intersection is the binary operation ∩ : Set(T ) × Set(T ) −→ Set(T ) , by which to any two sets A and B one asocciates a new set A ∩ B, called their intersection, formed by the common elements of the two sets: A ∩ B = {x ∈ T |(x ∈ A) ∧ (x ∈ B)} .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

6 / 67

Proposition The intersection operation has the following properties: −idempotence: −associativity: −commutativity: −unit element: −absorbant element:

A ∩ A = A, (∀)A ∈ Set(T ) ; (A ∩ B) ∩ C = A ∩ (B ∩ C ), (∀)A, B, C ∈ Set(T ) ; A ∩ B = B ∩ A, (∀)A, B ∈ Set(T ) ; A ∩ T = T ∩ A = A, (∀)A ∈ Set(T ) ; A ∩ ∅ = ∅ ∩ A = ∅, (∀)A ∈ Set(T ) .

Remark The operation of intersection can be extended from two sets to arbitrary families of sets. If {Ai }i∈I is a family of stes included in the total set T , where I is some index set, the intersection of the family is given by \ Ai = {x ∈ T |(∀i ∈ I )x ∈ Ai } . i∈I

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

7 / 67

Proposition The intersection operation has the following properties: −idempotence: −associativity: −commutativity: −unit element: −absorbant element:

A ∩ A = A, (∀)A ∈ Set(T ) ; (A ∩ B) ∩ C = A ∩ (B ∩ C ), (∀)A, B, C ∈ Set(T ) ; A ∩ B = B ∩ A, (∀)A, B ∈ Set(T ) ; A ∩ T = T ∩ A = A, (∀)A ∈ Set(T ) ; A ∩ ∅ = ∅ ∩ A = ∅, (∀)A ∈ Set(T ) .

Remark The operation of intersection can be extended from two sets to arbitrary families of sets. If {Ai }i∈I is a family of stes included in the total set T , where I is some index set, the intersection of the family is given by \ Ai = {x ∈ T |(∀i ∈ I )x ∈ Ai } . i∈I

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

7 / 67

Definition Union is the binary operation ∪ : Set(T ) × Set(T ) −→ Set(T ) , by which to any two sets A and B one associates a new set A ∪ B, called their union, formed by the elements which belong to at least one of the two sets: A ∪ B = {x ∈ T |(x ∈ A) ∨ (x ∈ B)} .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

8 / 67

Proposition The operation of union has the following properties: −idempotence: −associativity: −commutativity: −unit element: −absornant element:

A ∪ A = A, (∀)A ∈ Set(T ) ; (A ∪ B) ∪ C = A ∪ (B ∪ C ), (∀)A, B, C ∈ Set(T ) ; A ∪ B = B ∪ A, (∀)A, B ∈ Set(T ) ; A ∪ ∅ = ∅ ∪ A = A, (∀)A ∈ Set(T ) ; A ∪ T = T ∪ A = T , (∀)A ∈ Set(T ) .

Remark The operation of union can also be extended to arbitrary families of sets. If {Ai }i∈I is a family of sets included in the total set T , where I is an index set, the union of the family is given by [ Ai = {x ∈ T |(∃i ∈ I )x ∈ Ai } . i∈I

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

9 / 67

Proposition The operation of union has the following properties: −idempotence: −associativity: −commutativity: −unit element: −absornant element:

A ∪ A = A, (∀)A ∈ Set(T ) ; (A ∪ B) ∪ C = A ∪ (B ∪ C ), (∀)A, B, C ∈ Set(T ) ; A ∪ B = B ∪ A, (∀)A, B ∈ Set(T ) ; A ∪ ∅ = ∅ ∪ A = A, (∀)A ∈ Set(T ) ; A ∪ T = T ∪ A = T , (∀)A ∈ Set(T ) .

Remark The operation of union can also be extended to arbitrary families of sets. If {Ai }i∈I is a family of sets included in the total set T , where I is an index set, the union of the family is given by [ Ai = {x ∈ T |(∃i ∈ I )x ∈ Ai } . i∈I

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

9 / 67

Proposition For any sets A, B, C ∈ Set(T ) the following properties hold: −absorbtion:

A ∩ (A ∪ B) = A , A ∪ (A ∩ B) = A ; −distributivity: A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) , A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C ) ; −modularity: A ⊆ C =⇒ (A ∪ B) ∩ C = A ∪ (B ∩ C ) ; −the laws of the complementary: A ∩ A = ∅ , A∪A=T ; −de Morgan’s laws: (A ∩ B) = A ∪ B , (A ∪ B) = A ∩ B .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

10 / 67

Remark The distributivity properties and de Morgan’s laws can be extended to arbitrary families of sets:     T S T S Ai ∪ B = (Ai ∪ B) , Ai ∩ B = (Ai ∩ B) ; i∈I

i∈I

i∈I



 T

i∈I

Lect.dr. M.Chi¸s ()

Ai

i∈I

 =

S

 S

Ai ,

i∈I

i∈I

Lecture 1

Ai

=

T

Ai .

i∈I

6.X.2008

11 / 67

Definition Difference is the binary operation \ : Set(T ) × Set(T ) −→ Set(T ) , by which to any two sets A and B one associates a new set, denoted A \ B(or A − B), called their difference, formed by the elements which belong to the first set, A, but not also to the second set, B: A \ B = {x ∈ T |(x ∈ A) ∨ (x 6∈ B)} .

Remark A \ B = A ∩ CT (B), (∀)A, B ∈ Set(T ).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

12 / 67

Definition Difference is the binary operation \ : Set(T ) × Set(T ) −→ Set(T ) , by which to any two sets A and B one associates a new set, denoted A \ B(or A − B), called their difference, formed by the elements which belong to the first set, A, but not also to the second set, B: A \ B = {x ∈ T |(x ∈ A) ∨ (x 6∈ B)} .

Remark A \ B = A ∩ CT (B), (∀)A, B ∈ Set(T ).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

12 / 67

Proposition For any sets A, B, C ∈ Set(T ) the following relations are true: A \ A = ∅; (A \ B) \ C = A \ (B ∪ C ) = (A \ C ) \ B ; A \ (B \ C ) = (A \ B) ∪ (A ∩ C ) ; A \ (B ∩ C ) = (A \ B) ∪ (A \ C ) ; A \ (B ∪ C ) = (A \ B) ∩ (A \ C ) ; (A ∩ B) \ C = (A \ C ) ∩ (B \ C ) ; (A ∪ B) \ C = (A \ C ) ∪ (B \ C ) .

Remark Diference is not a commutative operation. Moreover, for any two sets A and B we have (A \ B) ∩ (B \ A) = ∅ .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

13 / 67

Proposition For any sets A, B, C ∈ Set(T ) the following relations are true: A \ A = ∅; (A \ B) \ C = A \ (B ∪ C ) = (A \ C ) \ B ; A \ (B \ C ) = (A \ B) ∪ (A ∩ C ) ; A \ (B ∩ C ) = (A \ B) ∪ (A \ C ) ; A \ (B ∪ C ) = (A \ B) ∩ (A \ C ) ; (A ∩ B) \ C = (A \ C ) ∩ (B \ C ) ; (A ∪ B) \ C = (A \ C ) ∪ (B \ C ) .

Remark Diference is not a commutative operation. Moreover, for any two sets A and B we have (A \ B) ∩ (B \ A) = ∅ .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

13 / 67

Definition Symmetric difference is the binary operation 4 : Set(T ) × Set(T ) −→ Set(T ) , by which to any two sets A and B one associates a new set, denoted A 4 B, called the symmetrice difference of the sets A and B, formed of those elements which belong to exactly one of the two sets: A 4 B := {x ∈ T |(x ∈ A ∧ x 6∈ B) ∨ (x 6∈ A ∧ x ∈ B)} .

Remark From the definition follows immediately that A 4 B = (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B) .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

14 / 67

Definition Symmetric difference is the binary operation 4 : Set(T ) × Set(T ) −→ Set(T ) , by which to any two sets A and B one associates a new set, denoted A 4 B, called the symmetrice difference of the sets A and B, formed of those elements which belong to exactly one of the two sets: A 4 B := {x ∈ T |(x ∈ A ∧ x 6∈ B) ∨ (x 6∈ A ∧ x ∈ B)} .

Remark From the definition follows immediately that A 4 B = (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B) .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

14 / 67

Proposition The operation of symmetric difference has the following properties: −asociativity: −commutativity: −unit element: −symmetric elements:

Lect.dr. M.Chi¸s ()

(A 4 B) 4 C = A 4 (B 4 C ) , (∀)A, B, C ∈ Set(T ) A 4 B = B 4 A , (∀)A, B ∈ Set(T ) ; A 4 ∅ = ∅ 4 A = A , (∀)A ∈ Set(T ) ; A 4 A = ∅ , (∀)A ∈ Set(T ) .

Lecture 1

6.X.2008

15 / 67

Definition If A ∈ Set(T ) is a set, we denote by P(A), and call the set of subsets(or parts) of A the set whose elements are the subsets of the set A: P(A) := {X ∈ Set(T )|X ⊆ A} .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

16 / 67

Definition Let n ∈ N∗ be an arbitrary nonzero natural number such that n ≥ 2, and a1 , a2 , . . . , an ∈ T arbitrary elements. The ordered system (a1 , a2 , . . . , an ) is defined by recursion in the following way: (a1 , a2 ) := {{a1 }, {a1 , a2 }} , (a1 , a2 , . . . , an ) := {(a1 , a2 , . . . , an−1 ), {a1 , a2 , . . . , an−1 , an }} .

Definition Let n ∈ N∗ be a nonzero natural number such that n ≥ 2, and A1 , A2 , . . . , An ∈ Set(T ) arbitrary sets. The cartesian product of the sets A1 , A2 , . . . , An is the set A1 × A2 × . . . × An := {(a1 , a2 , . . . , an )|ai ∈ Ai , (∀)i = 1, n} .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

17 / 67

Definition Let n ∈ N∗ be an arbitrary nonzero natural number such that n ≥ 2, and a1 , a2 , . . . , an ∈ T arbitrary elements. The ordered system (a1 , a2 , . . . , an ) is defined by recursion in the following way: (a1 , a2 ) := {{a1 }, {a1 , a2 }} , (a1 , a2 , . . . , an ) := {(a1 , a2 , . . . , an−1 ), {a1 , a2 , . . . , an−1 , an }} .

Definition Let n ∈ N∗ be a nonzero natural number such that n ≥ 2, and A1 , A2 , . . . , An ∈ Set(T ) arbitrary sets. The cartesian product of the sets A1 , A2 , . . . , An is the set A1 × A2 × . . . × An := {(a1 , a2 , . . . , an )|ai ∈ Ai , (∀)i = 1, n} .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

17 / 67

Relations

Definition Let n ∈ N∗ be a nonzero natural number and A1 , A2 , . . . , An n sets.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

18 / 67

Relations

Definition Let n ∈ N∗ be a nonzero natural number and A1 , A2 , . . . , An n sets. An n−ary relation between the elements of the sets A1 , A2 , . . . , An (in this order) is an ordered system R = (A1 , A2 , . . . , An , G ) formed by the n sets and a subset G of the cartesian product A1 × A2 × . . . × An , called the graph of the relation. The product A1 × A2 × . . . × An is called the domain of the relation R.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

18 / 67

Relations

Definition Let n ∈ N∗ be a nonzero natural number and A1 , A2 , . . . , An n sets. An n−ary relation between the elements of the sets A1 , A2 , . . . , An (in this order) is an ordered system R = (A1 , A2 , . . . , An , G ) formed by the n sets and a subset G of the cartesian product A1 × A2 × . . . × An , called the graph of the relation. The product A1 × A2 × . . . × An is called the domain of the relation R. If (a1 , a2 , . . . , an ) ∈ G , we write R(a1 , a2 , . . . , an ) and say that a1 , a2 , . . . , an are related by the relation R, or that a1 , a2 , . . . , an satisfy the relation R.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

18 / 67

Relations

Definition Let n ∈ N∗ be a nonzero natural number and A1 , A2 , . . . , An n sets. An n−ary relation between the elements of the sets A1 , A2 , . . . , An (in this order) is an ordered system R = (A1 , A2 , . . . , An , G ) formed by the n sets and a subset G of the cartesian product A1 × A2 × . . . × An , called the graph of the relation. The product A1 × A2 × . . . × An is called the domain of the relation R. If (a1 , a2 , . . . , an ) ∈ G , we write R(a1 , a2 , . . . , an ) and say that a1 , a2 , . . . , an are related by the relation R, or that a1 , a2 , . . . , an satisfy the relation R. If A1 = A2 = · · · = An = A, we call R a (homogenous) n−ary relation on the set A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

18 / 67

Relations

Definition Let n ∈ N∗ be a nonzero natural number and A1 , A2 , . . . , An n sets. An n−ary relation between the elements of the sets A1 , A2 , . . . , An (in this order) is an ordered system R = (A1 , A2 , . . . , An , G ) formed by the n sets and a subset G of the cartesian product A1 × A2 × . . . × An , called the graph of the relation. The product A1 × A2 × . . . × An is called the domain of the relation R. If (a1 , a2 , . . . , an ) ∈ G , we write R(a1 , a2 , . . . , an ) and say that a1 , a2 , . . . , an are related by the relation R, or that a1 , a2 , . . . , an satisfy the relation R. If A1 = A2 = · · · = An = A, we call R a (homogenous) n−ary relation on the set A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

18 / 67

Definition Let A1 , A2 , . . . , An be n arbitrary fixed sets. The empty relation associated with the sets A1 , A2 , . . . , An is the relation ∅A1 ,A2 ,...,An = (A1 , A2 , . . . , An , ∅) , whose graph is the empty set.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

19 / 67

Definition Let A1 , A2 , . . . , An be n arbitrary fixed sets. The empty relation associated with the sets A1 , A2 , . . . , An is the relation ∅A1 ,A2 ,...,An = (A1 , A2 , . . . , An , ∅) , whose graph is the empty set. The total relation associated with the sets A1 , A2 , . . . , An is the relation TA1 ,A2 ,...,An = (A1 , A2 , . . . , An , A1 × A2 × . . . × An ) , whose graph is the cartesian product A1 × A2 × . . . × An .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

19 / 67

Definition Let A1 , A2 , . . . , An be n arbitrary fixed sets. The empty relation associated with the sets A1 , A2 , . . . , An is the relation ∅A1 ,A2 ,...,An = (A1 , A2 , . . . , An , ∅) , whose graph is the empty set. The total relation associated with the sets A1 , A2 , . . . , An is the relation TA1 ,A2 ,...,An = (A1 , A2 , . . . , An , A1 × A2 × . . . × An ) , whose graph is the cartesian product A1 × A2 × . . . × An .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

19 / 67

Definition We call two relations R = (A1 , A2 , . . . , An , G ) and R0 = (B1 , B2 , . . . , Bn , G 0 ) equal if Ai = Bi , (∀)i = 1, n and G = G 0 . In this case, we write R = R0 . We say that the relation R implies the relation R0 , or that R is included in R0 , and write R ⊆ R0 , if Ai ⊆ Bi , (∀)i = 1, n and G ⊆ G 0 (which reduces to the validity of the implication R(a1 , a2 , . . . , an ) =⇒ R0 (a1 , a2 , . . . , an )).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

20 / 67

Definition We call two relations R = (A1 , A2 , . . . , An , G ) and R0 = (B1 , B2 , . . . , Bn , G 0 ) equal if Ai = Bi , (∀)i = 1, n and G = G 0 . In this case, we write R = R0 . We say that the relation R implies the relation R0 , or that R is included in R0 , and write R ⊆ R0 , if Ai ⊆ Bi , (∀)i = 1, n and G ⊆ G 0 (which reduces to the validity of the implication R(a1 , a2 , . . . , an ) =⇒ R0 (a1 , a2 , . . . , an )).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

20 / 67

Definition Let A1 = A2 = · · · = An = A. The relation ∆nA with the domain An and the graph diag (An ) = {(a, a, . . . , a) ∈ An | a ∈ A} is called the n−ary diagonal relation on the set A. In case n = 2, we denote ∆2A by idA , and call it the identical relation(or the identity) on the set A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

21 / 67

Definition Let A1 = A2 = · · · = An = A. The relation ∆nA with the domain An and the graph diag (An ) = {(a, a, . . . , a) ∈ An | a ∈ A} is called the n−ary diagonal relation on the set A. In case n = 2, we denote ∆2A by idA , and call it the identical relation(or the identity) on the set A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

21 / 67

To most of the set operations correspond operations between relations. For simplicity, we shall consider only operations with relations on the same domain.

Definition Let R = (A1 , A2 , . . . , An , G ) be a relation. The opposite(or complementary) of the relation R is the relation R = (A1 , A2 , . . . , An , A1 × A2 × . . . × An \ G ) .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

22 / 67

To most of the set operations correspond operations between relations. For simplicity, we shall consider only operations with relations on the same domain.

Definition Let R = (A1 , A2 , . . . , An , G ) be a relation. The opposite(or complementary) of the relation R is the relation R = (A1 , A2 , . . . , An , A1 × A2 × . . . × An \ G ) .

Remark For (a1 , a2 , . . . , an ) ∈ A1 × A2 × . . . × An we have R(a1 , a2 , . . . , an ) ⇐⇒ R(a1 , a2 , . . . , an ) .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

22 / 67

To most of the set operations correspond operations between relations. For simplicity, we shall consider only operations with relations on the same domain.

Definition Let R = (A1 , A2 , . . . , An , G ) be a relation. The opposite(or complementary) of the relation R is the relation R = (A1 , A2 , . . . , An , A1 × A2 × . . . × An \ G ) .

Remark For (a1 , a2 , . . . , an ) ∈ A1 × A2 × . . . × An we have R(a1 , a2 , . . . , an ) ⇐⇒ R(a1 , a2 , . . . , an ) .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

22 / 67

Definition Let R1 = (A1 , A2 , . . . , An , G1 ) and R2 = (A1 , A2 , . . . , An , G2 ) be two relations on the domain A1 × A2 × . . . × An . The intersection of the relations R1 and R2 is the relation R1 ∩ R2 = (A1 , A2 , . . . , An , G1 ∩ G2 ) . The union of the relations R1 and R2 is the relation R1 ∪ R2 = (A1 , A2 , . . . , An , G1 ∪ G2 ) .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

23 / 67

Definition Let R1 = (A1 , A2 , . . . , An , G1 ) and R2 = (A1 , A2 , . . . , An , G2 ) be two relations on the domain A1 × A2 × . . . × An . The intersection of the relations R1 and R2 is the relation R1 ∩ R2 = (A1 , A2 , . . . , An , G1 ∩ G2 ) . The union of the relations R1 and R2 is the relation R1 ∪ R2 = (A1 , A2 , . . . , An , G1 ∪ G2 ) .

Remark For (a1 , a2 , . . . , an ) ∈ A1 × A2 × . . . × An we have (R1 ∩ R2 )(a1 , a2 , . . . , an ) ⇐⇒ (R1 (a1 , a2 , . . . , an ) ∧ (R1 (a1 , a2 , . . . , an ) ; (R1 ∪ R2 )(a1 , a2 , . . . , an ) ⇐⇒ (R1 (a1 , a2 , . . . , an ) ∨ (R1 (a1 , a2 , . . . , an ) . Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

23 / 67

Definition Let R1 = (A1 , A2 , . . . , An , G1 ) and R2 = (A1 , A2 , . . . , An , G2 ) be two relations on the domain A1 × A2 × . . . × An . The intersection of the relations R1 and R2 is the relation R1 ∩ R2 = (A1 , A2 , . . . , An , G1 ∩ G2 ) . The union of the relations R1 and R2 is the relation R1 ∪ R2 = (A1 , A2 , . . . , An , G1 ∪ G2 ) .

Remark For (a1 , a2 , . . . , an ) ∈ A1 × A2 × . . . × An we have (R1 ∩ R2 )(a1 , a2 , . . . , an ) ⇐⇒ (R1 (a1 , a2 , . . . , an ) ∧ (R1 (a1 , a2 , . . . , an ) ; (R1 ∪ R2 )(a1 , a2 , . . . , an ) ⇐⇒ (R1 (a1 , a2 , . . . , an ) ∨ (R1 (a1 , a2 , . . . , an ) . Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

23 / 67

Binary relations

Definition A relation R = (A, B, G ) is called a binary relation between the elements of the sets A and B. Generaly, in the case of a binary relation we write aRb in stead of R(a, b).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

24 / 67

Binary relations

Definition A relation R = (A, B, G ) is called a binary relation between the elements of the sets A and B. Generaly, in the case of a binary relation we write aRb in stead of R(a, b). In case of a binary relation R = (A, B, G ), the set A is called the domain of the relation R, denoted dom(R), respectively B is called the codomain of the relation, denoted codom(R).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

24 / 67

Binary relations

Definition A relation R = (A, B, G ) is called a binary relation between the elements of the sets A and B. Generaly, in the case of a binary relation we write aRb in stead of R(a, b). In case of a binary relation R = (A, B, G ), the set A is called the domain of the relation R, denoted dom(R), respectively B is called the codomain of the relation, denoted codom(R).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

24 / 67

For binary relations there exist the following operations, which are not defined for general n−ary relations:

Definition Let R = (A, B, G ) be a binary relation. The inverse(or symmetric) of R is the relation R−1 = (B, A, G −1 ) , where G −1 = {(b, a) ∈ B × A| (a, b) ∈ G } .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

25 / 67

For binary relations there exist the following operations, which are not defined for general n−ary relations:

Definition Let R = (A, B, G ) be a binary relation. The inverse(or symmetric) of R is the relation R−1 = (B, A, G −1 ) , where G −1 = {(b, a) ∈ B × A| (a, b) ∈ G } .

Definition Let R = (A, B, G ) and S = (B, C , H) be two binary relations, with the property that codom(R) = dom(S). The composite of the two relations is the relation R · S = (A, C , G · H) , where G · H = {(a, c) ∈ A × C |(∃)b ∈ B : (a, b) ∈ G ∧ (b, c) ∈ H} .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

25 / 67

For binary relations there exist the following operations, which are not defined for general n−ary relations:

Definition Let R = (A, B, G ) be a binary relation. The inverse(or symmetric) of R is the relation R−1 = (B, A, G −1 ) , where G −1 = {(b, a) ∈ B × A| (a, b) ∈ G } .

Definition Let R = (A, B, G ) and S = (B, C , H) be two binary relations, with the property that codom(R) = dom(S). The composite of the two relations is the relation R · S = (A, C , G · H) , where G · H = {(a, c) ∈ A × C |(∃)b ∈ B : (a, b) ∈ G ∧ (b, c) ∈ H} .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

25 / 67

Remark With the notations from the previous definitions, for a ∈ A, b ∈ B, c ∈ C , the properties which define the inverse relation, respectively the composite relation are: bR−1 a ⇐⇒ aRb ; a(R · S)c ⇐⇒ (∃)b ∈ B : aRb ∧ bSc .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

26 / 67

Proposition Let R = (A, B, G ), S = (B, C , H), R0 = (A, B, G 0 ), S 0 = (B, C , H 0 ) and T = (C , D, K ) be arbitrary binary relations such that codom(R) = codom(R0 ) = dom(S) = dom(S 0 ) and codom(S) = dom(T ). Then the following properties are true:
−1 = R; R−1 −1 R = (R)−1 ; R ⊆ R0 ⇐⇒ R−1 ⊆ R0−1 ; (R ∩ R0 )−1 = R−1 ∩ R0−1 ; (R ∪ R0 )−1 = R−1 ∪ R0−1 ;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

27 / 67

Proposition (sequel) idA · R = R · idB = R R ⊆ R0 =⇒ R · S ⊆ R0 · S ; S ⊆ S 0 =⇒ R · S ⊆ R · S 0 ; (R ∩ R0 ) · S ⊆ (R · S) ∩ (R0 · S) ; (R ∪ R0 ) · S = (R · S) ∪ (R0 · S) ; R · (S ∩ S 0 ) ⊆ (R · S) ∩ (R · S 0 ) ; R · (S ∪ S 0 ) = (R · S) ∪ (R · S 0 ) ; (R · S)−1 = S −1 · R−1 ; (R · S) · T = R · (S · T ) ; R ⊆ R · R−1 · R .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

28 / 67

Definition Let R = (A, B, G ) be a binary relation and x ∈ A. The set xR := {y ∈ B| xRy } is called the section of the relation R at the point x. If X ⊆ A, [ X R := xR x∈X

is called the section of the relation R with respect to the subset X .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

29 / 67

Definition Let R = (A, B, G ) be a binary relation and x ∈ A. The set xR := {y ∈ B| xRy } is called the section of the relation R at the point x. If X ⊆ A, [ X R := xR x∈X

is called the section of the relation R with respect to the subset X . The section AR is called the second projection of the relation R, denoted pr2 (R), respectively the section BR−1 is called the first projection of the relation R and is denoted pr1 (R).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

29 / 67

Definition Let R = (A, B, G ) be a binary relation and x ∈ A. The set xR := {y ∈ B| xRy } is called the section of the relation R at the point x. If X ⊆ A, [ X R := xR x∈X

is called the section of the relation R with respect to the subset X . The section AR is called the second projection of the relation R, denoted pr2 (R), respectively the section BR−1 is called the first projection of the relation R and is denoted pr1 (R).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

29 / 67

Proposition Let R = (A, B, G ), S = (B, C , H), R0 = (A, B, G 0 ) be binary relations, and X , X1 , X2 ⊆ A. Then the following properties hold: 1) (X1 ∪ X2 )R = (X1 R) ∪ (X2 R); 2) (X1 ∩ X2 )R ⊆ (X1 R) ∩ (X2 R); 3) X (R ∪ R0 ) = (X R) ∪ (X R0 ); 4) X (R ∩ R0 ) ⊆ (X R) ∩ (X R0 ); 5) X (R · S) = (X R)S.

Proposition Let R = (A, B, G ) be a binary relation, X ⊆ A and Y ⊆ B. Then X ⊆ pr1 (R) ⇐⇒ X ⊆ (X R)R−1 Y ⊆ pr2 (R) ⇐⇒ Y ⊆ (Y R−1 )R

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

30 / 67

Proposition Let R = (A, B, G ), S = (B, C , H), R0 = (A, B, G 0 ) be binary relations, and X , X1 , X2 ⊆ A. Then the following properties hold: 1) (X1 ∪ X2 )R = (X1 R) ∪ (X2 R); 2) (X1 ∩ X2 )R ⊆ (X1 R) ∩ (X2 R); 3) X (R ∪ R0 ) = (X R) ∪ (X R0 ); 4) X (R ∩ R0 ) ⊆ (X R) ∩ (X R0 ); 5) X (R · S) = (X R)S.

Proposition Let R = (A, B, G ) be a binary relation, X ⊆ A and Y ⊆ B. Then X ⊆ pr1 (R) ⇐⇒ X ⊆ (X R)R−1 Y ⊆ pr2 (R) ⇐⇒ Y ⊆ (Y R−1 )R

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

30 / 67

Functional relations. Functions

Definition A relation R = (A, B, G ) is called a functional relation if R−1 · R ⊆ idB .

Remark A relation R = (A, B, G ) is a functional relation if and only if for any a ∈ A there is at most one element b ∈ B such that aRb.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

31 / 67

Functional relations. Functions

Definition A relation R = (A, B, G ) is called a functional relation if R−1 · R ⊆ idB .

Remark A relation R = (A, B, G ) is a functional relation if and only if for any a ∈ A there is at most one element b ∈ B such that aRb.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

31 / 67

Definition A relation R = (A, B, G ) is called a function, mapping or application if R−1 · R ⊆ idB and idA ⊆ R · R−1 .

Remark A relation R = (A, B, G ) is a function if and only if for any a ∈ A there is exactly one element b ∈ B such that aRb.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

32 / 67

Definition A relation R = (A, B, G ) is called a function, mapping or application if R−1 · R ⊆ idB and idA ⊆ R · R−1 .

Remark A relation R = (A, B, G ) is a function if and only if for any a ∈ A there is exactly one element b ∈ B such that aRb.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

32 / 67

Definition Let R = (A, B, G ) be a function and a ∈ A an arbitrary fixed element. The uniquely determined element b ∈ B with the property that aRb is called the image of the element a and is denoted b = aR .

Definition Let R = (A, B, G ) be a function and X ⊆ A. The section X R is then the set X R = {aR | a ∈ X } and is called the image of the set X with respect to the function R. In particular, AR is called the image of the function R and is denoted Im(R).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

33 / 67

Definition Let R = (A, B, G ) be a function and a ∈ A an arbitrary fixed element. The uniquely determined element b ∈ B with the property that aRb is called the image of the element a and is denoted b = aR .

Definition Let R = (A, B, G ) be a function and X ⊆ A. The section X R is then the set X R = {aR | a ∈ X } and is called the image of the set X with respect to the function R. In particular, AR is called the image of the function R and is denoted Im(R).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

33 / 67

Remark If R = (A, B, G ) is a function, we generally write R : A −→ B in stead of R = (A, B, G ) and usually indicate a rule to compute the images aR of the elements a ∈ A, in stead of specifying the graph G . This graph is most often denoted GR .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

34 / 67

Surjective, injective, bijective functions. Cardinal numbers Let f : A −→ B be a function. To any element x ∈ A corresponds a unique element y ∈ B such that y = x f . On the other hand, to an element y ∈ B may correspond either one, none, or more than one element x ∈ A such that y = x f .

Definition A function f : A −→ B is called surjective if for any y ∈ B the equation x f = y has at least one solution x ∈ A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

35 / 67

Surjective, injective, bijective functions. Cardinal numbers Let f : A −→ B be a function. To any element x ∈ A corresponds a unique element y ∈ B such that y = x f . On the other hand, to an element y ∈ B may correspond either one, none, or more than one element x ∈ A such that y = x f .

Definition A function f : A −→ B is called surjective if for any y ∈ B the equation x f = y has at least one solution x ∈ A.

Definition A function f : A −→ B is called injective if for any y ∈ B the equation x f = y has at most one solution x ∈ A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

35 / 67

Surjective, injective, bijective functions. Cardinal numbers Let f : A −→ B be a function. To any element x ∈ A corresponds a unique element y ∈ B such that y = x f . On the other hand, to an element y ∈ B may correspond either one, none, or more than one element x ∈ A such that y = x f .

Definition A function f : A −→ B is called surjective if for any y ∈ B the equation x f = y has at least one solution x ∈ A.

Definition A function f : A −→ B is called injective if for any y ∈ B the equation x f = y has at most one solution x ∈ A.

Definition A function f : A −→ B is called bijective if for any y ∈ B the equation x f = y has exactly one solution x ∈ A. Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

35 / 67

Surjective, injective, bijective functions. Cardinal numbers Let f : A −→ B be a function. To any element x ∈ A corresponds a unique element y ∈ B such that y = x f . On the other hand, to an element y ∈ B may correspond either one, none, or more than one element x ∈ A such that y = x f .

Definition A function f : A −→ B is called surjective if for any y ∈ B the equation x f = y has at least one solution x ∈ A.

Definition A function f : A −→ B is called injective if for any y ∈ B the equation x f = y has at most one solution x ∈ A.

Definition A function f : A −→ B is called bijective if for any y ∈ B the equation x f = y has exactly one solution x ∈ A. Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

35 / 67

Remark A function is bijective if and only if it is surjective and injective.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

36 / 67

Proposition Let f : A −→ B and g : B −→ C be two functions. Then the following properties hold: 1) If f and g are surjective, then the function f · g is surjective. 2) If f and g are injective, then the function f · g is injective. 3) If f and g are bijective, then the function f · g is bijective.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

37 / 67

Proposition Let f : A −→ B and g : B −→ C be two functions. Then the following properties hold: 1) If f and g are surjective, then the function f · g is surjective. 2) If f and g are injective, then the function f · g is injective. 3) If f and g are bijective, then the function f · g is bijective. 4) If f · g is surjective, then the function g is surjective. 5) If f · g is injective, then the function f is injective. 6) If f · g is bijective, then g is surjective, and f injective.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

37 / 67

Proposition Let f : A −→ B and g : B −→ C be two functions. Then the following properties hold: 1) If f and g are surjective, then the function f · g is surjective. 2) If f and g are injective, then the function f · g is injective. 3) If f and g are bijective, then the function f · g is bijective. 4) If f · g is surjective, then the function g is surjective. 5) If f · g is injective, then the function f is injective. 6) If f · g is bijective, then g is surjective, and f injective.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

37 / 67

Definition A function f : A −→ B is called invertible if there is a function g : B −→ A such that f · g = idA and g · f = idB . In this case, the function g is called the inverse of the function f and is denoted f −1 .

Proposition A function f : A −→ B is invertible if and only if it is bijective.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

38 / 67

Definition A function f : A −→ B is called invertible if there is a function g : B −→ A such that f · g = idA and g · f = idB . In this case, the function g is called the inverse of the function f and is denoted f −1 .

Proposition A function f : A −→ B is invertible if and only if it is bijective.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

38 / 67

Remark 1) For a bijective(hence invertible) function f : A −→ B, the inverse function f −1 : B −→ A represents ”the solving formula of the equation x f = y with respect to the unknown x ∈ A, in terms of the parameter y ∈ B”. 2) The inverse of a bijective function is also bijective.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

39 / 67

Remark 1) For a bijective(hence invertible) function f : A −→ B, the inverse function f −1 : B −→ A represents ”the solving formula of the equation x f = y with respect to the unknown x ∈ A, in terms of the parameter y ∈ B”. 2) The inverse of a bijective function is also bijective.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

39 / 67

Definition Let A and B be two sets. We say that A is equipotent or cardinal equivalent with B, and write A ∼ B, if there is a bijective function f : A −→ B.

Remark 1) Since for any set A, the function idA : A −→ A is bijective, we find that A ∼ A for any set A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

40 / 67

Definition Let A and B be two sets. We say that A is equipotent or cardinal equivalent with B, and write A ∼ B, if there is a bijective function f : A −→ B.

Remark 1) Since for any set A, the function idA : A −→ A is bijective, we find that A ∼ A for any set A. 2) If A, B, and C are sets such that A ∼ B and B ∼ C , then there are bijective functions f : A −→ B and g : B −→ C . Their composite f · g : A −→ C is then also bijective, hence A ∼ C .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

40 / 67

Definition Let A and B be two sets. We say that A is equipotent or cardinal equivalent with B, and write A ∼ B, if there is a bijective function f : A −→ B.

Remark 1) Since for any set A, the function idA : A −→ A is bijective, we find that A ∼ A for any set A. 2) If A, B, and C are sets such that A ∼ B and B ∼ C , then there are bijective functions f : A −→ B and g : B −→ C . Their composite f · g : A −→ C is then also bijective, hence A ∼ C . 3) If A and B are sets such that A ∼ B, then there is a bijection f : A −→ B. Its inverse f −1 : B −→ A is then aslo bijective, so that B ∼ A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

40 / 67

Definition Let A and B be two sets. We say that A is equipotent or cardinal equivalent with B, and write A ∼ B, if there is a bijective function f : A −→ B.

Remark 1) Since for any set A, the function idA : A −→ A is bijective, we find that A ∼ A for any set A. 2) If A, B, and C are sets such that A ∼ B and B ∼ C , then there are bijective functions f : A −→ B and g : B −→ C . Their composite f · g : A −→ C is then also bijective, hence A ∼ C . 3) If A and B are sets such that A ∼ B, then there is a bijection f : A −→ B. Its inverse f −1 : B −→ A is then aslo bijective, so that B ∼ A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

40 / 67

Definition The cardinal number or cardinal of a set A is the class of all sets which are equipotent with A, denoted |A| or card(A): |A| = card(A) := {B| B − set, B ∼ A} .

Remark A ∼ B ⇐⇒ |A| = |B| .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

41 / 67

Definition The cardinal number or cardinal of a set A is the class of all sets which are equipotent with A, denoted |A| or card(A): |A| = card(A) := {B| B − set, B ∼ A} .

Remark A ∼ B ⇐⇒ |A| = |B| .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

41 / 67

Definition Let A and B be two sets. We say that the cardinal of the set A is less or equal then the cardinal of the set B, and denote |A| ≤ |B|, if there is an injective function f : A −→ B.

Remark 1) |A| = |B| =⇒ |A| ≤ |B|.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

42 / 67

Definition Let A and B be two sets. We say that the cardinal of the set A is less or equal then the cardinal of the set B, and denote |A| ≤ |B|, if there is an injective function f : A −→ B.

Remark 1) |A| = |B| =⇒ |A| ≤ |B|. 2) |A| ≤ |A|, for any set A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

42 / 67

Definition Let A and B be two sets. We say that the cardinal of the set A is less or equal then the cardinal of the set B, and denote |A| ≤ |B|, if there is an injective function f : A −→ B.

Remark 1) |A| = |B| =⇒ |A| ≤ |B|. 2) |A| ≤ |A|, for any set A. 3) If A, B, and C are sets such that |A| ≤ |B| and |B| ≤ |C |, then there are injective functions f : A −→ B and g : B −→ C . Their composite f · g : A −→ C is then also injective, hence |A| ≤ |C |.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

42 / 67

Definition Let A and B be two sets. We say that the cardinal of the set A is less or equal then the cardinal of the set B, and denote |A| ≤ |B|, if there is an injective function f : A −→ B.

Remark 1) |A| = |B| =⇒ |A| ≤ |B|. 2) |A| ≤ |A|, for any set A. 3) If A, B, and C are sets such that |A| ≤ |B| and |B| ≤ |C |, then there are injective functions f : A −→ B and g : B −→ C . Their composite f · g : A −→ C is then also injective, hence |A| ≤ |C |.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

42 / 67

Lemma Let A be a set, and B ⊆ A a subset of A such that there is an injective function f : A −→ B. Then |A| = |B|.

Proposition (Cantor-Bernstein’s theorem) Let A and B be two sets such that |A| ≤ |B| and |B| ≤ |A|. Then |A| = |B|.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

43 / 67

Lemma Let A be a set, and B ⊆ A a subset of A such that there is an injective function f : A −→ B. Then |A| = |B|.

Proposition (Cantor-Bernstein’s theorem) Let A and B be two sets such that |A| ≤ |B| and |B| ≤ |A|. Then |A| = |B|.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

43 / 67

Definition A set A is called (Dedekind-)infinite if there is a proper subset B ⊂ A such that |A| = |B|.

Definition A set is called finite if it is not infinite.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

44 / 67

Definition A set A is called (Dedekind-)infinite if there is a proper subset B ⊂ A such that |A| = |B|.

Definition A set is called finite if it is not infinite.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

44 / 67

Remark 1) A set A is finite if and only if there is some natural number n ∈ N such that A ∼ {1, . . . , n}. In this case we write |A| = n and call n the number of elements of the set A. 2) Any finite union of finite sets is finite.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

45 / 67

Remark 1) A set A is finite if and only if there is some natural number n ∈ N such that A ∼ {1, . . . , n}. In this case we write |A| = n and call n the number of elements of the set A. 2) Any finite union of finite sets is finite.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

45 / 67

Definition A set is called countable or countably infinite if it is equipotent to the set N of natural numbers. A set is called at most countable if it is finite or countably infinite.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

46 / 67

Homogenous binary relations

Definition Let R = (A, A, G ) be a homogenous binary relation on a set A. We call the relation R def - reflexive ⇐⇒ idA ⊆ R;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

47 / 67

Homogenous binary relations

Definition Let R = (A, A, G ) be a homogenous binary relation on a set A. We call the relation R def - reflexive ⇐⇒ idA ⊆ R; def - transitive ⇐⇒ R · R ⊆ R;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

47 / 67

Homogenous binary relations

Definition Let R = (A, A, G ) be a homogenous binary relation on a set A. We call the relation R def - reflexive ⇐⇒ idA ⊆ R; def - transitive ⇐⇒ R · R ⊆ R; def - symmetric ⇐⇒ R ⊆ R−1 ;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

47 / 67

Homogenous binary relations

Definition Let R = (A, A, G ) be a homogenous binary relation on a set A. We call the relation R def - reflexive ⇐⇒ idA ⊆ R; def - transitive ⇐⇒ R · R ⊆ R; def - symmetric ⇐⇒ R ⊆ R−1 ; def - antisymmetric ⇐⇒ R ∩ R−1 ⊆ idA ;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

47 / 67

Homogenous binary relations

Definition Let R = (A, A, G ) be a homogenous binary relation on a set A. We call the relation R def - reflexive ⇐⇒ idA ⊆ R; def - transitive ⇐⇒ R · R ⊆ R; def - symmetric ⇐⇒ R ⊆ R−1 ; def - antisymmetric ⇐⇒ R ∩ R−1 ⊆ idA ; def - a preorder relation ⇐⇒ R is reflexive and transitive;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

47 / 67

Homogenous binary relations

Definition Let R = (A, A, G ) be a homogenous binary relation on a set A. We call the relation R def - reflexive ⇐⇒ idA ⊆ R; def - transitive ⇐⇒ R · R ⊆ R; def - symmetric ⇐⇒ R ⊆ R−1 ; def - antisymmetric ⇐⇒ R ∩ R−1 ⊆ idA ; def - a preorder relation ⇐⇒ R is reflexive and transitive; def - an equivalence relation ⇐⇒ R is a symmetric preorder relation;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

47 / 67

Homogenous binary relations

Definition Let R = (A, A, G ) be a homogenous binary relation on a set A. We call the relation R def - reflexive ⇐⇒ idA ⊆ R; def - transitive ⇐⇒ R · R ⊆ R; def - symmetric ⇐⇒ R ⊆ R−1 ; def - antisymmetric ⇐⇒ R ∩ R−1 ⊆ idA ; def - a preorder relation ⇐⇒ R is reflexive and transitive; def - an equivalence relation ⇐⇒ R is a symmetric preorder relation; def - an order relation ⇐⇒ R is a symmetric preorder relation.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

47 / 67

Homogenous binary relations

Definition Let R = (A, A, G ) be a homogenous binary relation on a set A. We call the relation R def - reflexive ⇐⇒ idA ⊆ R; def - transitive ⇐⇒ R · R ⊆ R; def - symmetric ⇐⇒ R ⊆ R−1 ; def - antisymmetric ⇐⇒ R ∩ R−1 ⊆ idA ; def - a preorder relation ⇐⇒ R is reflexive and transitive; def - an equivalence relation ⇐⇒ R is a symmetric preorder relation; def - an order relation ⇐⇒ R is a symmetric preorder relation.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

47 / 67

Remark Let R = (A, A, G ) be a homogenous binary relation on a set A. Then R is - reflexive ⇐⇒ [(∀)a ∈ A =⇒ aRa];

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

48 / 67

Remark Let R = (A, A, G ) be a homogenous binary relation on a set A. Then R is - reflexive ⇐⇒ [(∀)a ∈ A =⇒ aRa]; - transitive ⇐⇒ [(∀)a, b, c ∈ A : aRb ∧ bRc =⇒ aRc];

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

48 / 67

Remark Let R = (A, A, G ) be a homogenous binary relation on a set A. Then R is - reflexive ⇐⇒ [(∀)a ∈ A =⇒ aRa]; - transitive ⇐⇒ [(∀)a, b, c ∈ A : aRb ∧ bRc =⇒ aRc]; - symmetric ⇐⇒ [(∀)a, b ∈ A : aRb =⇒ bRa];

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

48 / 67

Remark Let R = (A, A, G ) be a homogenous binary relation on a set A. Then R is - reflexive ⇐⇒ [(∀)a ∈ A =⇒ aRa]; - transitive ⇐⇒ [(∀)a, b, c ∈ A : aRb ∧ bRc =⇒ aRc]; - symmetric ⇐⇒ [(∀)a, b ∈ A : aRb =⇒ bRa]; - antisymmetric ⇐⇒ [(∀)a, b ∈ A : aRb ∧ bRa =⇒ a = b].

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

48 / 67

Remark Let R = (A, A, G ) be a homogenous binary relation on a set A. Then R is - reflexive ⇐⇒ [(∀)a ∈ A =⇒ aRa]; - transitive ⇐⇒ [(∀)a, b, c ∈ A : aRb ∧ bRc =⇒ aRc]; - symmetric ⇐⇒ [(∀)a, b ∈ A : aRb =⇒ bRa]; - antisymmetric ⇐⇒ [(∀)a, b ∈ A : aRb ∧ bRa =⇒ a = b].

Notation If A is a nonempty set, we denote by Eq(A) the set of equivalence relations defined on the set A, respectively by Ord(A) the set of order relations defined on A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

48 / 67

Remark Let R = (A, A, G ) be a homogenous binary relation on a set A. Then R is - reflexive ⇐⇒ [(∀)a ∈ A =⇒ aRa]; - transitive ⇐⇒ [(∀)a, b, c ∈ A : aRb ∧ bRc =⇒ aRc]; - symmetric ⇐⇒ [(∀)a, b ∈ A : aRb =⇒ bRa]; - antisymmetric ⇐⇒ [(∀)a, b ∈ A : aRb ∧ bRa =⇒ a = b].

Notation If A is a nonempty set, we denote by Eq(A) the set of equivalence relations defined on the set A, respectively by Ord(A) the set of order relations defined on A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

48 / 67

Equivalence relations. Partitions. Factor sets Definition Let A be a nonempty set, ρ = (A, A, G ) an equivalence relation on A, and a ∈ A an arbitrary fixed element. The set [a]ρ := {b ∈ A| aρb} is called the equivalence class of the element a with respect to the equivalence relation ρ.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

49 / 67

Equivalence relations. Partitions. Factor sets Definition Let A be a nonempty set, ρ = (A, A, G ) an equivalence relation on A, and a ∈ A an arbitrary fixed element. The set [a]ρ := {b ∈ A| aρb} is called the equivalence class of the element a with respect to the equivalence relation ρ.

Proposition If ρ = (A, A, G ) is an equivalence relation on the nonempty set A, then 1) a ∈ [a]ρ , (∀)a ∈ A ; 2) b ∈ [a]ρ ⇐⇒ a ∈ [b]ρ ⇐⇒ [a]ρ = [b]ρ ; 3) [a] 6 [b]ρ =⇒ [a]ρ ∩ [b]ρ = ∅ ; Sρ = 4) [a]ρ = A . a∈A Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

49 / 67

Equivalence relations. Partitions. Factor sets Definition Let A be a nonempty set, ρ = (A, A, G ) an equivalence relation on A, and a ∈ A an arbitrary fixed element. The set [a]ρ := {b ∈ A| aρb} is called the equivalence class of the element a with respect to the equivalence relation ρ.

Proposition If ρ = (A, A, G ) is an equivalence relation on the nonempty set A, then 1) a ∈ [a]ρ , (∀)a ∈ A ; 2) b ∈ [a]ρ ⇐⇒ a ∈ [b]ρ ⇐⇒ [a]ρ = [b]ρ ; 3) [a] 6 [b]ρ =⇒ [a]ρ ∩ [b]ρ = ∅ ; Sρ = 4) [a]ρ = A . a∈A Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

49 / 67

Definition If ρ = (A, A, G ) is an equivalence relation defined on the nonempty set A, the set denoted A/ρ of all equivalence classes with respect to the equivalence relation ρ is called the factor set(or quotient set) of A with respect to the equivalence relation ρ.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

50 / 67

Definition Let A be a nonempty set and Π ⊆ P(A) a family of subsets of A. Π is called a partition of the set A if it satisfies the following conditions: 1) M 6= ∅, (∀)M ∈ Π ; 2) LS ∩ M, (∀)L, M ∈ Π, L 6= M ; 3) M = A. M∈Π

We denote by Part(A) the set of all partitions of a nonempty set A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

51 / 67

Definition Let A be a nonempty set and Π ⊆ P(A) a family of subsets of A. Π is called a partition of the set A if it satisfies the following conditions: 1) M 6= ∅, (∀)M ∈ Π ; 2) LS ∩ M, (∀)L, M ∈ Π, L 6= M ; 3) M = A. M∈Π

We denote by Part(A) the set of all partitions of a nonempty set A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

51 / 67

Proposition Let A be a nonempty set, and ρ = (A, A, G ) an equivalence relation defined on A. The set Πρ := A/ρ is then a partition of the set A.

Proposition Let A be a nonempty set, andSΠ ∈ Part(A) a partition of the set A. The binary relation ρΠ := (A, A, M × M) is then an equivalence relation on M∈Π

the set A.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

52 / 67

Proposition Let A be a nonempty set, and ρ = (A, A, G ) an equivalence relation defined on A. The set Πρ := A/ρ is then a partition of the set A.

Proposition Let A be a nonempty set, andSΠ ∈ Part(A) a partition of the set A. The binary relation ρΠ := (A, A, M × M) is then an equivalence relation on M∈Π

the set A.

Proposition Let A be a nonempty set. The applications ρ 7−→ Πρ : Eq(A) −→ Part(A) and Π 7−→ ρΠ : Part(A) −→ Eq(A) are then bijective and inverse to each other.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

52 / 67

Proposition Let A be a nonempty set, and ρ = (A, A, G ) an equivalence relation defined on A. The set Πρ := A/ρ is then a partition of the set A.

Proposition Let A be a nonempty set, andSΠ ∈ Part(A) a partition of the set A. The binary relation ρΠ := (A, A, M × M) is then an equivalence relation on M∈Π

the set A.

Proposition Let A be a nonempty set. The applications ρ 7−→ Πρ : Eq(A) −→ Part(A) and Π 7−→ ρΠ : Part(A) −→ Eq(A) are then bijective and inverse to each other.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

52 / 67

Definition Let A be a nonempty set and ρ = (A, A, G ) ∈ Eq(A). The function πρ : A −→ A/ρ : a 7−→ [a]ρ is called the canonical projection of the set A onto the factor set A/ρ.

Remark aρb ⇐⇒ [a]ρ = [b]ρ ⇐⇒ aπρ = b πρ .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

53 / 67

Definition Let A be a nonempty set and ρ = (A, A, G ) ∈ Eq(A). The function πρ : A −→ A/ρ : a 7−→ [a]ρ is called the canonical projection of the set A onto the factor set A/ρ.

Remark aρb ⇐⇒ [a]ρ = [b]ρ ⇐⇒ aπρ = b πρ .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

53 / 67

Proposition Let f : A −→ B be a function and ρ = (B, B, G ) ∈ Eq(B) an equivalence relation on the set B. The relation ρf = f · ρ · f −1 is then an equivalence relation on the set A.

Definition The relation ρf defined in the previous proposition is called the relation induced by ρ on A through the function f , or the preimage of the relation ρ through f .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

54 / 67

Proposition Let f : A −→ B be a function and ρ = (B, B, G ) ∈ Eq(B) an equivalence relation on the set B. The relation ρf = f · ρ · f −1 is then an equivalence relation on the set A.

Definition The relation ρf defined in the previous proposition is called the relation induced by ρ on A through the function f , or the preimage of the relation ρ through f .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

54 / 67

Definition If f : A −→ B is a function, the preimage (idB )f of the identical relation idB through f is called the kernel of the function f and is denoted ker (f ).

Remark 1) (∀)a, a0 ∈ A, a ker (f )a0 ⇐⇒ af = a0f ;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

55 / 67

Definition If f : A −→ B is a function, the preimage (idB )f of the identical relation idB through f is called the kernel of the function f and is denoted ker (f ).

Remark 1) (∀)a, a0 ∈ A, a ker (f )a0 ⇐⇒ af = a0f ; 2) ker (f ) = f · f −1 .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

55 / 67

Definition If f : A −→ B is a function, the preimage (idB )f of the identical relation idB through f is called the kernel of the function f and is denoted ker (f ).

Remark 1) (∀)a, a0 ∈ A, a ker (f )a0 ⇐⇒ af = a0f ; 2) ker (f ) = f · f −1 .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

55 / 67

Proposition Let R = (A, A, G ) be a preorder relation on the set A. The relation ρR = R ∩ R−1 is then an equivalence relation on the set A.

Definition The relation ρR defined in the previous proposition is called the association relation with respect to R.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

56 / 67

Proposition Let R = (A, A, G ) be a preorder relation on the set A. The relation ρR = R ∩ R−1 is then an equivalence relation on the set A.

Definition The relation ρR defined in the previous proposition is called the association relation with respect to R.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

56 / 67

Order relations

Definition Let A be a set and R = (A, A, G ) an order relation on A. The pair (A, R) is called an ordered set.

Remark Let A be a set and R = (A, A, G ) an order relation on A. The inverse R−1 of the relation R is then also an order relation.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

57 / 67

Order relations

Definition Let A be a set and R = (A, A, G ) an order relation on A. The pair (A, R) is called an ordered set.

Remark Let A be a set and R = (A, A, G ) an order relation on A. The inverse R−1 of the relation R is then also an order relation.

Notation Generally we shall denote by ≤ an order relation on a set, respectively by ≥ the inverse ≤−1 of the relation ≤.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

57 / 67

Order relations

Definition Let A be a set and R = (A, A, G ) an order relation on A. The pair (A, R) is called an ordered set.

Remark Let A be a set and R = (A, A, G ) an order relation on A. The inverse R−1 of the relation R is then also an order relation.

Notation Generally we shall denote by ≤ an order relation on a set, respectively by ≥ the inverse ≤−1 of the relation ≤.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

57 / 67

Definition Let(A, ≤) be an ordered set and M ⊆ A a subset of A. An element m ∈ M is called def - the least element(or minimum, or first element)of M ⇐⇒ m ≤ x, (∀)x ∈ M;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

58 / 67

Definition Let(A, ≤) be an ordered set and M ⊆ A a subset of A. An element m ∈ M is called def - the least element(or minimum, or first element)of M ⇐⇒ m ≤ x, (∀)x ∈ M; def

- the greatest element(or maximum, or last element)of M ⇐⇒ x ≤ m, (∀)x ∈ M;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

58 / 67

Definition Let(A, ≤) be an ordered set and M ⊆ A a subset of A. An element m ∈ M is called def - the least element(or minimum, or first element)of M ⇐⇒ m ≤ x, (∀)x ∈ M; def

- the greatest element(or maximum, or last element)of M ⇐⇒ x ≤ m, (∀)x ∈ M; def

- a minimal element of M ⇐⇒ x ∈ M ∧ x ≤ m =⇒ x = m;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

58 / 67

Definition Let(A, ≤) be an ordered set and M ⊆ A a subset of A. An element m ∈ M is called def - the least element(or minimum, or first element)of M ⇐⇒ m ≤ x, (∀)x ∈ M; def

- the greatest element(or maximum, or last element)of M ⇐⇒ x ≤ m, (∀)x ∈ M; def

- a minimal element of M ⇐⇒ x ∈ M ∧ x ≤ m =⇒ x = m; def - a maximal element of M ⇐⇒ x ∈ M ∧ m ≤ x =⇒ x = m.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

58 / 67

Definition Let(A, ≤) be an ordered set and M ⊆ A a subset of A. An element m ∈ M is called def - the least element(or minimum, or first element)of M ⇐⇒ m ≤ x, (∀)x ∈ M; def

- the greatest element(or maximum, or last element)of M ⇐⇒ x ≤ m, (∀)x ∈ M; def

- a minimal element of M ⇐⇒ x ∈ M ∧ x ≤ m =⇒ x = m; def - a maximal element of M ⇐⇒ x ∈ M ∧ m ≤ x =⇒ x = m.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

58 / 67

Remark 1) If the set M contains a minimum, respectively a maximum, then this is unique and is denoted min(M), respectively max(M). 2) A set M may contain one, none, or more than one minimal, respectively maximal elements.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

59 / 67

Remark 1) If the set M contains a minimum, respectively a maximum, then this is unique and is denoted min(M), respectively max(M). 2) A set M may contain one, none, or more than one minimal, respectively maximal elements. 3) If a set M has a minimum, respectively a maximum, then min(M) is the unique minimal element, respectively max(M) is the unique maximal element of M.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

59 / 67

Remark 1) If the set M contains a minimum, respectively a maximum, then this is unique and is denoted min(M), respectively max(M). 2) A set M may contain one, none, or more than one minimal, respectively maximal elements. 3) If a set M has a minimum, respectively a maximum, then min(M) is the unique minimal element, respectively max(M) is the unique maximal element of M.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

59 / 67

Definition Let (A, ≤) be an ordered set, M ⊆ A a subset of A, and a ∈ A an element of A. The element a is called def - a minorant of M ⇐⇒ a ≤ x, (∀)x ∈ M;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

60 / 67

Definition Let (A, ≤) be an ordered set, M ⊆ A a subset of A, and a ∈ A an element of A. The element a is called def - a minorant of M ⇐⇒ a ≤ x, (∀)x ∈ M; def

- a majorant of M ⇐⇒ x ≤ a, (∀)x ∈ M;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

60 / 67

Definition Let (A, ≤) be an ordered set, M ⊆ A a subset of A, and a ∈ A an element of A. The element a is called def - a minorant of M ⇐⇒ a ≤ x, (∀)x ∈ M; def

- a majorant of M ⇐⇒x ≤ a, (∀)x ∈ M; a ≤ x, (∀)x ∈ M , def - the infimum M ⇐⇒ (∀)b ∈ A : b ≤ x, (∀)x ∈ M =⇒ b ≤ a ;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

60 / 67

Definition Let (A, ≤) be an ordered set, M ⊆ A a subset of A, and a ∈ A an element of A. The element a is called def - a minorant of M ⇐⇒ a ≤ x, (∀)x ∈ M; def

- a majorant of M ⇐⇒x ≤ a, (∀)x ∈ M; a ≤ x, (∀)x ∈ M , def - the infimum M ⇐⇒ (∀)b ∈ A : b ≤ x, (∀)x ∈ M =⇒ b ≤ a ;  x ≤ a, (∀)x ∈ M , def - the supremum of M ⇐⇒ (∀)b ∈ A : x ≤ b, (∀)x ∈ M =⇒ a ≤ b ;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

60 / 67

Definition Let (A, ≤) be an ordered set, M ⊆ A a subset of A, and a ∈ A an element of A. The element a is called def - a minorant of M ⇐⇒ a ≤ x, (∀)x ∈ M; def

- a majorant of M ⇐⇒x ≤ a, (∀)x ∈ M; a ≤ x, (∀)x ∈ M , def - the infimum M ⇐⇒ (∀)b ∈ A : b ≤ x, (∀)x ∈ M =⇒ b ≤ a ;  x ≤ a, (∀)x ∈ M , def - the supremum of M ⇐⇒ (∀)b ∈ A : x ≤ b, (∀)x ∈ M =⇒ a ≤ b ;

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

60 / 67

Remark 1) If a set M has an infimum, respectively a supremum, then this is unique and is denoted inf (M), respectively sup(M). 2) a = inf (M) ⇐⇒ a is the greatest minorant of M.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

61 / 67

Remark 1) If a set M has an infimum, respectively a supremum, then this is unique and is denoted inf (M), respectively sup(M). 2) a = inf (M) ⇐⇒ a is the greatest minorant of M. 3) a = sup(M) ⇐⇒ a is the least majorant of M.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

61 / 67

Remark 1) If a set M has an infimum, respectively a supremum, then this is unique and is denoted inf (M), respectively sup(M). 2) a = inf (M) ⇐⇒ a is the greatest minorant of M. 3) a = sup(M) ⇐⇒ a is the least majorant of M. 4) If there exists min(M)(respectively max(M)), then inf (M)(respectively sup(M)) also exists and inf (M) = min(M)(respectively sup(M) = max(M)).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

61 / 67

Remark 1) If a set M has an infimum, respectively a supremum, then this is unique and is denoted inf (M), respectively sup(M). 2) a = inf (M) ⇐⇒ a is the greatest minorant of M. 3) a = sup(M) ⇐⇒ a is the least majorant of M. 4) If there exists min(M)(respectively max(M)), then inf (M)(respectively sup(M)) also exists and inf (M) = min(M)(respectively sup(M) = max(M)).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

61 / 67

Definition An ordered set (A, ≤) is called totally(or linearly) ordered if for any x, y ∈ A one has either x ≤ y or y ≤ x.

Definition An ordered set (A, ≤) is called well ordered if any nonempty subset of A has a least element.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

62 / 67

Definition An ordered set (A, ≤) is called totally(or linearly) ordered if for any x, y ∈ A one has either x ≤ y or y ≤ x.

Definition An ordered set (A, ≤) is called well ordered if any nonempty subset of A has a least element.

Remark Any well ordered set is totally ordered.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

62 / 67

Definition An ordered set (A, ≤) is called totally(or linearly) ordered if for any x, y ∈ A one has either x ≤ y or y ≤ x.

Definition An ordered set (A, ≤) is called well ordered if any nonempty subset of A has a least element.

Remark Any well ordered set is totally ordered.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

62 / 67

Proposition (Zermelo’s axiom) Any set may be well ordered(i.e., for any set A there exists some order relation ≤ on A, such that (A, ≤) is well ordered).

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

63 / 67

Remark As a consequence of Zermelo’s axiom, the method of mathematical induction may be used as a proof method for statements obtained by universal cuantification of some predicat over any set in the following way: Let A be a set, which we may assume well ordered with respect to some order relation ≤ defined on A. Also, let P be a predicat defined on A. If M = {x ∈ A| P(x)},

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

64 / 67

Remark As a consequence of Zermelo’s axiom, the method of mathematical induction may be used as a proof method for statements obtained by universal cuantification of some predicat over any set in the following way: Let A be a set, which we may assume well ordered with respect to some order relation ≤ defined on A. Also, let P be a predicat defined on A. If M = {x ∈ A| P(x)}, the statement (∀x ∈ A)P(x) is true(i.e., M = A) if and only if  (V) min(A) ∈ M , (I) (∀a ∈ A)(x ≤ a =⇒ x ∈ M) =⇒ a ∈ M .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

64 / 67

Remark As a consequence of Zermelo’s axiom, the method of mathematical induction may be used as a proof method for statements obtained by universal cuantification of some predicat over any set in the following way: Let A be a set, which we may assume well ordered with respect to some order relation ≤ defined on A. Also, let P be a predicat defined on A. If M = {x ∈ A| P(x)}, the statement (∀x ∈ A)P(x) is true(i.e., M = A) if and only if  (V) min(A) ∈ M , (I) (∀a ∈ A)(x ≤ a =⇒ x ∈ M) =⇒ a ∈ M . Indeed, the necesity of this condition is obvious, whereas to prove sufficiency we can observe that from the given condition follows that there is no min(CA (M)). Since A is well ordered, this means that CA (M) = ∅, hence M = A. Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

64 / 67

Remark As a consequence of Zermelo’s axiom, the method of mathematical induction may be used as a proof method for statements obtained by universal cuantification of some predicat over any set in the following way: Let A be a set, which we may assume well ordered with respect to some order relation ≤ defined on A. Also, let P be a predicat defined on A. If M = {x ∈ A| P(x)}, the statement (∀x ∈ A)P(x) is true(i.e., M = A) if and only if  (V) min(A) ∈ M , (I) (∀a ∈ A)(x ≤ a =⇒ x ∈ M) =⇒ a ∈ M . Indeed, the necesity of this condition is obvious, whereas to prove sufficiency we can observe that from the given condition follows that there is no min(CA (M)). Since A is well ordered, this means that CA (M) = ∅, hence M = A. Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

64 / 67

Definition An ordered set (A, ≤) is called inductively ordered if any totally ordered subset of A has a majorant.

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

65 / 67

Proposition (Zorn’s lemma) Any nonempty inductively ordered set has at least a maximal element.

Proposition (Zorn’s lemma - ”strong variation”) Let (A, ≤) be a nonempty inductively ordered set and a ∈ A an element of A. Then there is a maximal element ma ∈ A such that a ≤ ma .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

66 / 67

Proposition (Zorn’s lemma) Any nonempty inductively ordered set has at least a maximal element.

Proposition (Zorn’s lemma - ”strong variation”) Let (A, ≤) be a nonempty inductively ordered set and a ∈ A an element of A. Then there is a maximal element ma ∈ A such that a ≤ ma .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

66 / 67

Proposition Let R = (A, A, G ) be a preorder relation defined on a set A, and ρR the association relation with respect to R. The relation R defined on the factor set A/ρR by [a]ρR R[b]ρR ⇐⇒ aRb is then well defined and represents an order relation on A/ρR .

Lect.dr. M.Chi¸s ()

Lecture 1

6.X.2008

67 / 67