集合

1 .Sets 2/10/12 1

2 .What is a Set? Informally, a collection of objects, determined by its members, treated as a single mathematical object Not a real definition: What’s a collection?? 2/10/12 2

3 .Some sets 𝒁 = the set of integers 𝐍 = the set of nonnegative integers R = the set of real numbers {1, 2, 3} { {1}, {2}, {3} } {Z} ∅ = the empty set P ( {1,2} ) = the set of all subsets of {1,2} = {∅, {1}, {2}, {1,2}} P(𝒁) = the set of all sets of integers (“the power set of the integers”) 2/10/12 3

4 .“Determined by its members” {7, “Sunday”, π } is a set containing three elements {7, “Sunday”, π } = { π , 7, “Sunday”, π , 14/2} 2/10/12 4

5 .Set Membership Let A = {7, “Sunday”, π } Then 7 ∈A 8 ∉ A N ∈ P(Z) 2/10/12 5

6 .Subset: ⊆ A ⊆ B is read “A is a subset of B” or “A is contained in B” (∀ x ) ( x∈A ⇒ x∈B ) N ⊆ Z, {7} ⊆ {7, “Sunday”, π } ∅ ⊆ A for any set A (∀ x ) ( x ∈ ∅ ⇒ x∈A ) A ⊆ A for any set A To be clear that A ⊆ B but A ≠ B, write A ⊊ B “Proper subset” (I don’t like “⊂”) 2/10/12 6

7 .Finite and Infinite Sets A set is finite if it can be counted using some initial segment of the integers {∅, {1}, {2}, {1,2}} 1 2 3 4 Otherwise infinite N, Z {0, 2, 4, 6, 8, …} (to be continued …} 2/10/12 7

8 .Set Constructor The set of elements of A of which P is true: { x ∈A: P(x )} or { x ∈A | P(x )} E.g. the set of even numbers is { n∈Z : n is even} = { n∈Z : (∃ m∈Z ) n = 2m} E. g . A×B = {( a,b ): a∈A and b∈B } Ordered pairs also written 〈 a ,b〉 2/10/12 8

9 .Size of a Finite Set |A| is the number of elements in A |{2,4,6}| = ? 2/10/12 9

10 .Size of a Finite Set |A| is the number of elements in A |{2,4,6}| = 3 | { {2,4,6} } | = ? 2/10/12 10

11 .Size of a Finite Set |A| is the number of elements in A |{2,4,6}| = 3 | { {2,4,6} } | = 1 | { N } | = ? 2/10/12 11

12 .Size of a Finite Set |A| is the number of elements in A |{2,4,6}| = 3 | { {2,4,6} } | = 1 | { N } | = 1 (a set containing only one thing, which happens to be an infinite set) 2/10/12 12

13 .Operators on Sets Union: x∈A∪B iff x∈A or x∈B Intersection: x∈A∩B iff x∈A and x∈B Complement: x∈B iff x ∉ B x∈A -B iff x∈A and x ∉ B A-B = A\B = A∩B 2/10/12 13

14 .Proof that A ∪ (B∩C) = ( A∪ B )∩ (A∪C ) x∈A∪(B∩C ) iff x∈A or x∈B∩C ( defn of ∪) iff x∈A or ( x∈B and x∈C ) ( defn of ∩) Let p := “ x∈A ”, q := “ x∈B ”, r := x∈C Then p ∨ ( q ⋀ r ) ≡ ( p ∨ q ) ⋀ ( p ∨ r ) ≡ ( x∈A or x∈B ) and ( x∈A or x∈C ) iff ( x∈A∪B ) and ( x∈A∪C ) iff x∈(A∪B)∩(A∪C ) 2/10/12 14