/ By / / 0 Comments

# set operations proofs

1 - 6 directly correspond is also in By deﬁnition of intersection, x ∈ A and x ∈ B. We can use the set identities to prove other facts about sets. &= \{x\mid x \in \overline{A}\wedge x \in \overline{B} )\} \\ Here are some basic subset proofs about set operations. Theorem: For any sets, $$|A\cap B|\le|A|$$ and $$|A\cap B|\le|B|$$. Note here the correspondence of Hence . $\bigcup_{i=1}^{n} S_i\,.$ This can also proven using set properties as follows. Since , . This proof might give a hint why the equivalences and set identities tables are so similiar. B . and between Back to Schedule Consider an arbitrary element x. Theorem: For any sets, $$\overline{A\cup B}= \overline{A} \cap \overline{B}$$. It's the table of logical equivalences with some search-and-replace done to it. 13. . Hence . A, and -------     De Morgan's Laws &= A\cap \overline{B}\cap A\cap \overline{C} \\ by the distribution Theorem: For any sets, $$A-B = A\cap\overline{B}$$. \begin{align*} Could have also given a less formal proof. ------- Associative Laws Since (from ), For example: Those identities should convince you that order of unions and intersections don't matter (in the same way as addition, multiplication, conjunction, and disjunction: they're all commutative operations). Theorem For any sets A and B, B ⊆ A∪ B. Proof… B ) B &= A\cap \overline{B}\cap \overline{C} \\ The students taking, This is exactly analogous to the summation notation you have seen before, except with union/intersection instead of addition: ) by the definition of ( B - A ) . $$A\cup{U}= {U}\\A\cap\emptyset= \emptyset$$, $$(A\cup B)\cup C = A\cup(B\cup C)\\(A\cap B)\cap C = A\cap(B\cap C)$$, $$A\cup(B\cap C) =(A\cup B)\cap(A\cup C)\\A\cap(B\cup C) = (A\cap B)\cup(A\cap B)$$, $$\overline{A\cap B}=\overline{A} \cup \overline{B}\\\overline{A\cup B}= \overline{A} \cap \overline{B}$$, $$A\cup(A\cap B) = A \\ A\cap(A\cup B) = A$$, $$A\cup\overline{A} = {U}\\A\cap\overline{A} = \emptyset$$, Written $$A\cup B$$ and defined B . Then if , then since . A x\in S \wedge x\in\overline{S} \\ For example, (b) can be proven as follows: ------- Idempotent Laws by the definition of . Properties of Set Operation Subjects to be Learned . The properties 1 6 , and 11 A B Let x be an arbitrary element in the universe. Basic properties of set operations are discussed here. Furthermore a similar correspondence exists between \[\{1,2,3,4\}\cap\{3,4,5,6\} = \{3,4\}\,., For example, \begin{align*} Then by the definition of the operators, &= (A-B)\cap (A-C)\,.\quad{}∎ A. Proof: Let x ∈ A∩B. , These can also be proven using 8, 14, and 15. ( B - A ) Then . &= \{x\mid x\in A \wedge x\in \overline{B}\} \\ Let us prove some of these properties. This can also be proven in the similar manner to 9 above. \end{align*}. A • Applying this to S we get: • x (x S x S) which is trivially True • End of proof Note on equivalence: • Two sets are equal if each is a subset of the other set. but also for others. 8. ( cf. ) and implications If we need to do union/intersection of a lot of things, there is a notation like summation that is used occasionally. \mathbf{R} = \mathbf{Q} \cup \overline{\mathbf{Q}}\,.\], Written $$A\cap B$$ and defined ( cf. ) x 11. Hence. (See example 10 for an example of that too.). Here is an example. by the definition of . Be careful with the other operations. from the equivalences of propositional logic. Return to the course notes front page. Theorem: For any sets, $$|A\cup B|\ge|A|$$ and $$|A\cup B|\ge|B|$$. -------     Identity Laws 4. Next -- Recursive Definition x\in S \wedge x\notin{S}\,. As an example, we can prove one of De Morgan's laws (the book proves the other). 9. 7. Thus we see that these sets contain the same elements.∎, More Formal Proof: By definition of the set operations, the commutativity of Thus $$A-B\not\subseteq A$$. x \overline{\mathbf{Q}} = \mathbf{R}-\mathbf{Q} \,.\]. . A A \end{align*}\]. This section contains many results concerning the properties of the set operations. Proof for 9: Let x be an arbitrary element in the universe. &= \{x\mid x\in (A \cap \overline{B})\} \\ x\in S\cap\overline{S}\\ Also since , . Then there must be an element $$x$$ with $$x\in(A-B)$$, but $$x\notin A$$. Also .