# 集合之间的关系

1.Relations Between S ets 2/13/12 1

2.Relations 2/13/12 2 Sam Mary CS20 EC 10 Students Courses The “is-taking” relation A relation is a set of ordered pairs: {(Sam,Ec10), (Sam, CS20), (Mary, CS20)}

3.Function: A → B 2/13/12 3 A B Each element of A is associated with at most one element of B. a ⟼ b f(a ) = b f AT MOST ONE ARROW OUT OF EACH ELEMENT OF A domain codomain

4.Total Function: A → B 2/13/12 4 A B Each element of A is associated with ONE AND ONLY one element of B. a ⟼ b f(a ) = b f EXACTLY ONE ARROW OUT OF EACH ELEMENT OF A domain codomain

5.A Function that is “Partial,” Not Total 2/13/12 5 R×R R f : R ×R → R f (x,y ) = x/y Defined for all pairs ( x,y ) except when y =0! f domain codomain

6.A Function that is “Partial,” Not Total 2/13/12 6 R×R R f : R ×R → R f (x,y ) = x/y Defined for all pairs ( x,y ) except when y =0! Or: f is a total function: R×(R-{0})→R f domain codomain

7.Injective Function 2/13/12 7 A B f domain codomain “at most one arrow in” (∀b∈B)(∃ ≤1 a∈A) f(a )= b

8.Surjective Function 2/13/12 8 A B f domain codomain “at least one arrow in” (∀b∈B)(∃ ≥1 a∈A) f(a )= b

9.Bijection = Total + Injective + Surjective 2/13/12 9 A B f domain codomain “exactly one arrow out of each element of A a nd exactly one arrow in to each element of B” ( ∀ a∈A ) f(a ) is defined and ( ∀ b∈B )(∃ =1 a∈A) f(a )= b

10.Cardinality or “Size” 2/13/12 10 A B f domain codomain For finite sets, a bijection exists iff A and B have the same number of elements

11.Cardinality or “Size” 2/13/12 11 Use the same as a definition of “same size” for infinite sets: Sets A and B have the same size iff there is a bijection between A and B Theorem: The set of even integers has the same size as the set of all integers [f(2n) = n ] …, -4, -3, -2, -1, 0, 1, 2, 3, 4 … …, -8, -6, -4, -2, 0, 2, 4, 6, 8 …

12.Cardinality or “Size” 2/13/12 12 There are as many natural numbers as integers 0 1 2 3 4 5 6 7 8 … 0, -1, 1, -2, 2, -3, 3, -4, 4 … f(n ) = n/2 if n is even, -(n+1)/2 if n is odd Defn : A set is countably infinite if it has the same size as the set of natural numbers

13.An Infinite Set May Have the Same Size as a Proper Subset! 2/13/12 13 0 1 2 3 4 5 0 1 2 3 4 5 Hilton Sheraton Every room of both hotels is full! Suppose the Sheraton has to be evacuated ⋮ ⋮

14.An Infinite Set May Have the Same Size as a Proper Subset! 2/13/12 14 0 1 2 3 4 5 0 1 2 3 4 5 Hilton Sheraton Step 1: Tell the resident of room n in the Hilton to go to room 2n This leaves all the odd-numbered rooms of the Hilton unoccupied ⋮ ⋮

15.An Infinite Set May Have the Same Size as a Proper Subset! 2/13/12 15 0 1 2 3 4 5 0 1 2 3 4 5 Hilton Sheraton Step 2: Tell the resident of room n in the Sheraton to go to room 2n+1 of the Hilton. Everyone gets a room! ⋮ ⋮