Report

Discrete Structures Chapter 6: Set Theory 6.1 Set Theory: Definitions and the Element Method of Proof The introduction of suitable abstractions is our only mental aid to organize and master complexity. – E. W. Dijkstra, 1930 – 2002 Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 1 Subsets • Let’s write what it means for a set A to be a subset of a set B as a formal universal conditional statement: A B x, if x A then x B. Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 2 Subsets • The negation is existential A Erickson B x, if x A and x B. 6.1 Set Theory - Definitions and the Element Method of Proof 3 Subsets • A proper subset of a set is a subset that is not equal to its containing set. A is a proper subset of B 1. A B, and 2. there is at least one element in B that is not in A. Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 4 Element Argument • Let sets X and Y be given. To prove that X Y, 1. Suppose that x is a particular but arbitrarily chosen element of X, 2. Show that x is an element of Y. Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 5 Example – pg. 350 # 4 • Let A = {n | n = 5r for some integer r} and B = {m | m = 20s for some integer s}. a. Is A B? Explain. b. Is B A? Explain. Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 6 Set Equality • Given sets A and B, A equals B, written A = B, iff every element of A is in B and every element of B is in A. Symbolically, A = B A B and B A Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 7 Operations on Sets • Let A and B be subsets of a universal set U. 1. The union of A and B denoted A B, is the set of all elements that are in at least one of A or B. Symbolically: A B = {x U | x A or x B} Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 8 Operations on Sets • Let A and B be subsets of a universal set U. 2. The intersection of A and B denoted A B, is the set of all elements that are common to both A or B. Symbolically: A B = {x U | x A and x B} Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 9 Operations on Sets • Let A and B be subsets of a universal set U. 3. The difference of B minus A (or relative complement of A in B) denoted B – A, is the set of all elements that are in B but not A. Symbolically: B – A = {x U | x B and x A} Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 10 Operations on Sets • Let A and B be subsets of a universal set U. 4. The complement of A denoted Ac, is the set of all elements in U that are not A. Symbolically: Ac = {x U | x A} Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 11 Example – pg. 350 # 11 • Let the universal set be the set R of all real numbers and let A = {x R | 0 < x 2}, B = {x R | 1 x < 4}, and C = {x R | 3 x < 9}. Find each of the following: a. A B d. A C g. Ac Bc j. (A B)c Erickson b. A e. A B C h. Ac c. Ac f. Bc Bc 6.1 Set Theory - Definitions and the Element Method of Proof i. (A B)c 12 Unions and Intersections of an Indexed Collection of Sets Given sets A0, A1, A2, … that are subsets of a universal set U and given a nonnegative integer n, n Ai x U | x Ai for at least one i 0,1, 2, ..., n i0 Ai x U | x Ai for at least one nonnegative integer i i0 n Ai x U | x Ai for all i 0,1, 2, ..., n i0 Ai x U | x Ai for all nonnegative integers i i0 Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 13 Definitions • Empty Set A set with no elements is called the empty set (or null set) and denoted by the symbol . • Disjoint Two sets are called disjoint iff they have no elements in common. Symbolically: A and B are disjoint A B = Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 14 Definitions • Mutually Disjoint Sets A1, A2, A3, … are mutually disjoint (or pairwise disjoint or nonoverlapping) iff no two sets Ai and Aj with distinct subscripts have any elements in common. More precisely, for all i, j = 1, 2, 3, … Ai Aj = whenever i j. Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 15 Example – pg. 305 # 23 Let Vi x 1 1 1 | x , i i i i 1 for all positive integers i. 4 4 Vi ? a. Vi ? b. i 1 i 1 c. A re V1 , V 2 , V 3 , ... m utually disjoint? E xplain. n n Vi ? d. i 1 i 1 Vi ? f. i 1 Erickson Vi ? e. Vi ? g. i 1 6.1 Set Theory - Definitions and the Element Method of Proof 16 Definition • Partition A finite or infinite collection of nonempty sets {A1, A2, A3, …} is a partition of a set A iff, 1. A is the union of all the Ai 2. The sets A1, A2, A3, …are mutually disjoint. Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 17 Example – pg. 351 # 27 b. Is w , x , v , u , y , q , p , z a partition of p, q, u , v, w, x, y, z ? c. Is 5, 4 , 7, 2 , 1, 3, 4 , 6, 8 a partition of 1, 2, 3, 4, 5, 6, 7, 8 ? e. Is 1, 5 , 4, 7 , 2, 8, 6, 3 a partition of 1, 2, 3, 4, 5, 6, 7, 8 ? Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 18 Definition • Power Set Given a set A, the power set of A is denoted (A), is the set of all subsets of A. Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 19 Example – pg. 351 # 31 • Suppose A = {1, 2} and B = {2, 3}. Find each of the following: a. A B b. A c. A B d. A B Erickson 6.1 Set Theory - Definitions and the Element Method of Proof 20