Hence . ------- Domination Laws \] Proof for 12: (a) ? Proof: Let x ∈ A∩B. We have used the choose-an-element method to prove Propositions 5.7, 5.11, and 5.14. &= A\cap \overline{B\cup C} \\ of propositional logic, and 7 - 11 also follow immediately from them as illustrated below. \[\{1,2,3,4\}\cap\{3,4,5,6\} = \{3,4\}\,.\], For example, Hence . A Could have also given a less formal proof. The others can also be proven similarly by going to logic, x\in S \wedge x\in\overline{S} \\ We are going to prove this by showing that every element that is in B . Then if , then since . B ) A Let x be an arbitrary element in the universe. by the distribution ( A (b) Similarly for . Here the only if part is going to be proven. B \overline{\mathbf{Q}} = \mathbf{R}-\mathbf{Q} \,.\]. Copyright © 2013, Greg Baker. Since we're doing the same manipulations, we ended up with the same tables. Hence . Consider an arbitrary element x. For example, suppose there are \(n\) courses being offered at ZJU this semester. B Proof: Suppose not, that \(|A-B|>|A|\). This can also be proven in the similar manner to 9 above. Using set-builder notation, we can define a number of common sets and operations. to identities by 1. &= \overline{A}\cap\overline{B}\,.\quad{}∎ x\in S \wedge x\notin{S}\,. A A A Since A Then &= \{x\mid \neg(x \in A)\wedge \neg(x\in B )\} \\ Proofs involving sets that use this method are sometimes referred to aselement-chasing proofs. but also for others. • Any set S is a subset of itself Proof: • the definition of a subset says: all elements of a set A must be also elements of B: x (x A x B). B A If we need to do union/intersection of a lot of things, there is a notation like summation that is used occasionally. Since (from ), Then since Set. Then A \mathbf{Q} \cap \overline{\mathbf{Q}}=\emptyset\,.\], For example, Theorem: For any sets, \(|A\cap B|\le|A|\) and \(|A\cap B|\le|B|\). Then there is an element x that is in , i.e. The students taking, This is exactly analogous to the summation notation you have seen before, except with union/intersection instead of addition: A Thus \(A-B\not\subseteq A\). Let the sets \(S_1,S_2,\ldots ,S_n\) be the students in each course. when we're working with real numbers, probably \(U=\mathbf{R}\). \[\begin{align*} This correspondence holds not just for the commutativity Proof for 8: (a) If then . B . Since (use "addition" rule), if and only if ( cf. ) equalities involving set operations intersection of sets subset relations proofs of equalities proofs of subset relations Contents . 11. Proof for 10: Suppose . That is, \(A\cap\overline{B}\) is the \(A\) with all of the values from \(B\) removed. Be careful with the other operations. \overline{A\cup B} &= \{x\mid x\in (A \cap \overline{B})\} \\ &= \{x\mid x \in (\overline{A}\cap\overline{B}) )\} \\ \[\bigcup_{i=1}^{n} S_i\,.\] Hence. x A can be proven using equivalences of propositional logic. Since , since . of . Theorem For any sets A and B, A∩B ⊆ A. if and only if x\in S\cap\overline{S}\\ \[\{1,2,3,4\}-\{3,4,5,6\} = \{1,2\}\,\\ = ( A B Proof for 9: Let x be an arbitrary element in the universe. ------- Associative Laws ) by the definition of ( B - A ) . A , A though they can be proven also using some of these properties (after those properties are proven, needless to say). Proof for 6: By the definition of the equality of sets, we need to prove that &= \{x\mid x\in A \wedge x\in \overline{B}\} \\ A Additional properties: It's the table of logical equivalences with some search-and-replace done to it. This name is used since the basic method is to choose an arbitrary element from one set and “chase it” until you prove it must be in another set. Furthermore a similar correspondence exists between and vice versa. Proof for 13: Since , . A-(B\cup C) &= A\cap\overline{B}\,.\quad{}∎ Thus, in particular, x ∈ A is true. is also in 8. x As an example, we can prove one of De Morgan's laws (the book proves the other). ------- Idempotent Laws A But from the definition of set difference, we see that A, and A Notice the similarity between the corresponding set and logical operators: \(\vee,\cup\) and \(\wedge,\cap\) and \(\overline{\mbox{S}},\neg\). \end{align*}\]. by the definition Basic properties of set operations are discussed here. Hence . A Like the domain for quantifiers, it's the set of all possible values we're working with. Less Formal Proof: The set \(A-B\) is the values from \(A\) with any values from \(B\) removed. \[\begin{align*} &= \{x\mid \neg(x \in A\vee x\in B )\} \\ 12. if and only if and Properties of Set Operation Subjects to be Learned . A = A by 3, Alternative proof These can also be proven using 8, 14, and 15. &= A\cap \overline{B}\cap \overline{C} \\ 6. We'll be careful for this one and manipulate the set builder notation. We have already proved some of the results. Hence . B and that of Theorem: For any sets, \(\overline{A\cup B}= \overline{A} \cap \overline{B}\). For that we need to show that for an arbitrary element in the universe x, Theorem: For any sets, \(A-B = A\cap\overline{B}\). ------- Distributive Laws Others will be proved in this section or in the exercises. Then . 5. by the definition of set union. x Since we're doing the same manipulations, we ended up with the same tables. Proof: For sets \(A,B,C\) from the above theorem, we have, B Just because it worked for these, doesn't mean you can assume everything is the same. For any one of the set operations, we can expand to set builder notation, and then use the logical equivalences to manipulate the conditions. and If , then . B ) By deﬁnition of intersection, x ∈ A and x ∈ B. Theorem: \(A-(B\cup C)= (A-B)\cap(A-C)\). ------- Identity Laws Then there must be an element \(x\) with \(x\in(A-B)\), but \(x\notin A\). by the commutativity of 4. With similar proofs, we could prove these things: When doing set operations we often need to define a. x 10. 1 - 6 directly correspond Next -- Recursive Definition Let us prove some of these properties.