Comparing N and set of all subsets of N

(1)

CS 207m: Discrete Structures (Minor)

Instructor : S. Akshay

Jan 19, 2018 Lecture 05 – relations

1

(2)

Recap: Countable and countably infinite sets

Definition

I For a given set C, if there is a bijection from C toN, then C is calledcountably infinite. A set iscountableif it is finite or countably infinite.

I Examples: Z,N×N,Q.

I Properties: Closure under (countable) unions and (finite) products.

Are all sets countable?

(3)

Comparing N and set of all subsets of N

Theorem (Cantor, 1891)

There is no bijection betweenNand the set of all subsets ofN.

3

(4)

Comparing N and set of all subsets of N

I Proving existence just needs one to exhibit a function

I But how do we prove non-existence?

(5)

Comparing N and set of all subsets of N

I Proving existence just needs one to exhibit a function

I But how do we prove non-existence? Try contradiction.

3

(6)

Comparing N and set of all subsets of N

There is no bijection betweenNand the set of all subsets ofN. Proof by contradiction: Suppose there is such a bijection, sayf. This would imply that eachi∈N maps to some setf(i)⊆N.

0 1 2 3 . . .

f(0) X × × × . . .

f(1) X × X X . . .

f(2) × × × × . . .

f(3) × X × X . . .

(7)

Comparing N and set of all subsets of N

0 1 2 3 . . .

f(0) X/× × × × . . . f(1) X ×/X X X . . . f(2) × × ×/X × . . . f(3) × X × X/× . . .

I Consider the setS ⊆Nobtained by switching the diagonal elements, i.e., S={i∈N|i6∈f(i)}.

3

(8)

Comparing N and set of all subsets of N

0 1 2 3 . . .

f(0) X/× × × × . . . f(1) X ×/X X X . . . f(2) × × ×/X × . . . f(3) × X × X/× . . .

I Asf is bij,∃j∈N, f(j) =S.

(9)

Comparing N and set of all subsets of N

0 1 2 3 . . .

f(0) X/× × × × . . . f(1) X ×/X X X . . . f(2) × × ×/X × . . . f(3) × X × X/× . . .

I S andf(j) differ at position j, for anyj.

3

(10)

Comparing N and set of all subsets of N

Proof by contradiction: Suppose there is such a bijection, sayf. This would imply that eachi∈N maps to some setf(i)⊆N.

0 1 2 3 . . .

f(0) X/× × × × . . . f(1) X ×/X X X . . . f(2) × × ×/X × . . . f(3) × X × X/× . . .

I S andf(j) differ at position j, for anyj.

I Thus,S 6=f(j) for allj ∈N, which is a contradiction!

(11)

Summary and moving on...

I Finite and infinite sets.

I Using functions to compare sets: focus on bijections.

I Countable, countably infinite and uncountable sets.

I Cantor’s diagonalization argument (A new powerful proof technique!).

Next: Basic Mathematical Structures – Relations

4

(12)

Summary and moving on...

I Finite and infinite sets.

I Using functions to compare sets: focus on bijections.

I Countable, countably infinite and uncountable sets.

I Cantor’s diagonalization argument (A new powerful proof technique!).

Next: Basic Mathematical Structures – Relations

(13)

Relations

Definition: Function

LetA,B be two sets. Afunctionf from A toB is a subset R ofA×B such that

(i) ∀a∈A,∃b∈B such that (a, b)∈R, and (ii) if (a, b)∈R and (a, c)∈R, thenb=c.

I Now, suppose Ais the set of all Btech students andB is the set of all courses. Clearly, we can assign to each student the set of courses he/she is taking. Is this a function?

I By removing the two extra assumptions in the defn, we get: Definition: Relation

I A relationR from AtoB is a subset of A×B. If (a, b)∈R, we also write this asa R b.

I Thus, a relation is a way to relate the elements of two (not necessarily different) sets.

5

(14)

Relations

Definition: Function

LetA,B be two sets. Afunctionf from A toB is a subset R ofA×B such that

(i) ∀a∈A,∃b∈B such that (a, b)∈R, and (ii) if (a, b)∈R and (a, c)∈R, thenb=c.

I Now, suppose Ais the set of all Btech students andB is the set of all courses. Clearly, we can assign to each student the set of courses he/she is taking. Is this a function?

I By removing the two extra assumptions in the defn, we get:

Definition: Relation

I A relationR from AtoB is a subset of A×B. If (a, b)∈R, we also write this as a R b.

I Thus, a relation is a way to relate the elements of two (not necessarily different) sets.

(15)

Examples and representations of relations

We writeR(A, B) for a relation fromA toB and justR(A) if A=B. Also if Ais clear from context, we just write R.

Examples of relations

I All functions are relations.

I R₁(Z) ={(a, b)|a, b∈Z, a−b is even }.

I R2(Z) ={(a, b)|a, b∈Z, a≤b}.

I Let S be a set,R3(P(S)) ={(A, B)|A, B⊆S, A⊆B}.

I Relational databases are practical examples.

Representations of a relation from A toB.

I As a set ofordered pairs of elements, i.e., subset ofA×B.

I As a directed graph.

I As a (database) table.

6

(16)

Examples and representations of relations

We writeR(A, B) for a relation fromA toB and justR(A) if A=B. Also if Ais clear from context, we just write R.

Examples of relations

I All functions are relations.

I R₁(Z) ={(a, b)|a, b∈Z, a−b is even }.

I R2(Z) ={(a, b)|a, b∈Z, a≤b}.

I Let S be a set,R3(P(S)) ={(A, B)|A, B⊆S, A⊆B}.

I Relational databases are practical examples.

Representations of a relation from A toB.

I As a set ofordered pairs of elements, i.e., subset ofA×B.

I As a directed graph.

I As a (database) table.

(17)

Use of relations

Practical application in relational databases: IMDB, university records, etc.

But, why study relations in this course?

I Functions were special kinds of relations that were useful to compare sets.

I Are there otherspecialrelations?What are they useful for?

I Equivalence relations

I Partial orders

7

(18)

Use of relations

I Partial orders

(19)

Use of relations

I Partial orders

7

(20)

Use of relations

I Partial orders

(21)

Partitions of a set – grouping “like” elements

Examples

I Natural numbers are partitioned into even and odd.

I This class is partitioned into set of all those who are taking thesameset of courses.

How do you define a partition?

Definition

A partition of a setS is a setP of its subsets such that

I ifS⁰ ∈P, then S⁰ 6=∅.

I S

S⁰∈P

S⁰ =S : its union covers entire set S.

I If S1, S2 ∈P, thenS1∩S2=∅: sets are disjoint.

Can you think of two trivial partitions that any set must have?

8

(22)

Partitions of a set – grouping “like” elements

Examples

Definition

I ifS⁰ ∈P, thenS⁰ 6=∅.

I S

S⁰∈P

(23)

Partitions of a set – grouping “like” elements

Examples

Definition

I S

S⁰∈P

8

(24)

Interpreting partitions as relations

Thus, a partition dividesS into subsets that each contain (only) elements that share some common property. e.g.,

I Evenness or oddness (formally, remainder modulo 2!).

I Same set of courses...

I But, this sounds like relation, right? Which one? Relation generated by a partition

I Clearly all elements in a set of the partition are related by the “sameness” or “likeness” property.

I So can we define this as a relation? aRbifais “like” b.

I Formally, we define R(S) byaRb ifaand bbelong to the same set in the partition of S.

What properties does this relation have?

(25)

Interpreting partitions as relations

I But, this sounds like relation, right? Which one? Relation generated by a partition

9

(26)

Interpreting partitions as relations

I But, this sounds like relation, right? Which one?

Relation generated by a partition

(27)

Interpreting partitions as relations

I So can we define this as a relation?

aRbifais “like” b.

9

(28)

Interpreting partitions as relations

(29)

Interpreting partitions as relations

9

(30)

Interpreting partitions as relations

(31)

Properties of a relation generated by a partition

1. All elements must be related to themselves (why?)

I A relationR(S) is calledreflexiveif for alla∈S,aRa. 2. If ais “like” b, thenbmust be “like” a.

I A relationR(S) is calledsymmetricif for all a, b∈S, we haveaRbimpliesbRa.

3. If ais “like” band bis “like” c, then amust be “like”c.

I A relationR(S) calledtransitiveif for alla, b, c∈S, we haveaRbandbRc impliesaRc.

Any other defining properties?

We will see that any relation that satisfies these three properties defines a partition!

Definition

A relation which satisfies all these three properties is called an equivalence relation.

10

(32)

Properties of a relation generated by a partition

I A relationR(S) is calledreflexiveif for alla∈S,aRa.

2. If ais “like” b, thenbmust be “like” a.

Definition

(33)

Properties of a relation generated by a partition

2. If ais “like” b, thenbmust be “like”a.

Definition

10

(34)

Properties of a relation generated by a partition

Definition

(35)

Properties of a relation generated by a partition

3. If ais “like” band bis “like” c, thena must be “like”c.

Definition

10

(36)

Properties of a relation generated by a partition

Definition

(37)

Properties of a relation generated by a partition

Definition

10

(38)

Properties of a relation generated by a partition

Definition

(39)

Properties of a relation generated by a partition

Definition

10

(40)

Examples

I Reflexive: ∀a∈S,aRa.

I Symmetric: ∀a, b∈S,aRb impliesbRa.

I Transitive: ∀a, b, c∈S,aRb, bRc impliesaRc.

I Equivalence: Reflexive, Symmetric and Transitive.

Relation Refl. Sym. Trans. Equiv.

aR₂b if students a and b take same set of courses

X X X X

aR1bif student atakes courseb {(a, b)|a, b∈Z,(a−b) mod 2 = 0}

{(a, b)|a, b∈Z, a≤b} {(a, b)|a, b∈Z, a < b} {(a, b)|a, b∈Z, a|b} {(a, b)|a, b∈R,|a−b|<1} {((a, b),(c, d)) | (a, b),(c, d) ∈ Z×(Z\ {0}),(ad=bc)}

(41)

Examples

I Reflexive: ∀a∈S,aRa.

I Symmetric: ∀a, b∈S,aRb impliesbRa.

I Transitive: ∀a, b, c∈S,aRb, bRc impliesaRc.

I Equivalence: Reflexive, Symmetric and Transitive.

Relation Refl. Sym. Trans. Equiv.

aR₂b if students a and b take same set of courses

X X X X

aR1bif student atakes courseb {(a, b)|a, b∈Z,(a−b) mod 2 = 0}

{(a, b)|a, b∈Z, a≤b}

{(a, b)|a, b∈Z, a < b}

{(a, b)|a, b∈Z, a|b}

{(a, b)|a, b∈R,|a−b|<1}

{((a, b),(c, d)) | (a, b),(c, d) ∈ Z×(Z\ {0}),(ad=bc)}

11

(42)

Partitions of a set – grouping “like” elements

Definition

I S

S⁰∈P

Example: natural numbers partitioned into even and odd...

Theorem

Every partition of setS gives rise to a canonical equivalence relationR onS, namely,

I aRb ifaand bbelong to the same set in the partition ofS.

Is the converse true? Can we generate a partition from every equivalence relation?

(43)

Partitions of a set – grouping “like” elements

Definition

I S

S⁰∈P

Example: natural numbers partitioned into even and odd...

Theorem

Every partition of setS gives rise to a canonical equivalence relationR onS, namely,

I aRb ifaand bbelong to the same set in the partition ofS.

Is the converse true? Can we generate a partition from every equivalence relation?

12

(44)

Equivalence classes

Definition

I Let R be an equivalence relation on setS, and let a∈S.

I Then the equivalence classof a, denoted [a], is the set of all elements related to it, i.e., [a] ={b∈S |(a, b)∈R}.

InR={(a, b)∈Z×Z|(a−b) mod 5 = 0}, what are [0], [1]? Lemma

LetR be an equivalence relation onS. Leta, b∈S. Then, the following statements are equivalent:

1. aRb 2. [a] = [b] 3. [a]∩[b]6=∅.

Proof Sketch: (1) to (2) symm and trans, (2) to (3) refl, (3) to (1) symm and trans. (H.W.: Do the proof formally.)

(45)

Equivalence classes

Definition

InR={(a, b)∈Z×Z|(a−b) mod 5 = 0}, what are [0], [1]?

Lemma

1. aRb 2. [a] = [b] 3. [a]∩[b]6=∅.

13

(46)

Equivalence classes

Definition

Lemma

1. aRb 2. [a] = [b]

3. [a]∩[b]6=∅.

(47)

Equivalence classes

Definition

Lemma

1. aRb 2. [a] = [b]

3. [a]∩[b]6=∅.

13

(48)

From equivalence relations to partitions

Theorem

1. Let R be an equivalence relation onS. Then,the equivalence classes ofR form a partition of S.

2. Conversely, given a partition P of S, there is an equivalence relation R whose equivalence classes are exactly the sets ofP.

Proof sketch of (1): Union, non-emptiness follows from reflexivity. The rest (pairwise disjointness) follows from the previous lemma.

(H.W.): Write the formal proofs of (1) and (2).

(49)

From equivalence relations to partitions

Theorem

14

(50)

From equivalence relations to partitions

Theorem

(51)

More “applications” of equivalence relations

Defining new objects using equivalence relations Consider

R={((a, b),(c, d))|(a, b),(c, d)∈Z×(Z\ {0}),(ad=bc)}.

I Then the equivalence classes ofR define the rational numbers.

I e.g.,₁

2

=₂

4

are two names for the same rational number.

I Indeed, when we write ^p_q we implicitly mean h

p q

i .

I With this definition, why are addition and multiplication

“well-defined”?

I addition: [(a, b)] + [(c, d)] = [(ad+bc, bd)]

I multiplication: [(a, b)]·[(c, d)] = [(ac, bd)]

Can we defineintegers and real numbers starting from naturals by using equivalence classes?

15

(52)

More “applications” of equivalence relations

I e.g.,₁

2

=₂

4

p q

i .

“well-defined”?

(53)

More “applications” of equivalence relations

I e.g.,₁

2

=₂

4

p q

i .

“well-defined”?

15

(54)

More “applications” of equivalence relations

I e.g.,₁

2

=₂

4

p q

i .

“well-defined”?

(55)

Geometrical objects using equivalence relations

Cut-and-paste

Consider the relationR([0,1]) ={aRb|a, b∈[0,1], eithera=b ora= 1, b= 0, or a= 0, b= 1}.

I Is R an equivalence relation? What does it define?

I This is [0,1] in which the end-points have been related to each other.

I So the equivalence classes form a “loop”, since end-points are joined. If we imagine [0,1] as a 1-length string, we have glued its ends!

16

(56)

Geometrical objects using equivalence relations

Cut-and-paste

Consider the relationR([0,1]) ={aRb|a, b∈[0,1], eithera=b ora= 1, b= 0, or a= 0, b= 1}.

I Is R an equivalence relation? What does it define?

I This is [0,1] in which the end-points have been related to each other.

I So the equivalence classes form a “loop”, since end-points are joined. If we imagine [0,1] as a 1-length string, we have glued its ends!

(57)

Geometrical objects using equivalence relations

Forming 2D objects

Consider a rectangular piece of the real plane, [0,1]×[0,1].

I Define R1([0,1]×[0,1]) by (a, b)R1(c, d) if

I (a, b) = (c, d) or

I b=d,a= 0, c= 1 or

I b=d,c= 0,a= 1.

Is R1 an equivalence relation? What do its equivalence classes define?

I (a, b) = (c, d) or

I a, b, c, d∈ {0,1}.

Is R2 an equivalence relation? What does it define? Can you build even more interesting “shapes”? Torus? Mobius strip?!

17

(58)

Geometrical objects using equivalence relations

Forming 2D objects

Consider a rectangular piece of the real plane, [0,1]×[0,1].

I (a, b) = (c, d) or

I b=d,a= 0, c= 1 or

I b=d,c= 0,a= 1.

Is R1 an equivalence relation? What do its equivalence classes define?

I (a, b) = (c, d) or

I a, b, c, d∈ {0,1}.

Is R2 an equivalence relation? What does it define?

Can you build even more interesting “shapes”? Torus? Mobius strip?!