(New page: Category:ECE600 Category:Set Theory Category:Math == Theorem == Union is distributive over intersection ,i.e. <br/> <math>A\cup (B\cap C) = (A\cup B)\cap (A\cup C</math> <br...) |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 7: | Line 7: | ||
Union is distributive over intersection ,i.e. <br/> | Union is distributive over intersection ,i.e. <br/> | ||
| − | <math>A\cup (B\cap C) = (A\cup B)\cap (A\cup C</math> <br/> | + | <math>A\cup (B\cap C) = (A\cup B)\cap (A\cup C)</math> <br/> |
| − | where <math>A</math>, <math>B</math> and <math>C</math> are | + | where <math>A</math>, <math>B</math> and <math>C</math> are sets. |
| Line 16: | Line 16: | ||
Let x ∈ A ∪ (B ∩ C). Then, x ∈ A or x ∈ (B ∩ C), or both. <br/> | Let x ∈ A ∪ (B ∩ C). Then, x ∈ A or x ∈ (B ∩ C), or both. <br/> | ||
| − | If x ∈ A, then x ∈ (A ∪ B), since A ⊂ (A ∪ B). <br/> | + | If x ∈ A, then x ∈ (A ∪ B), since A ⊂ (A ∪ B) ([[Union_and_intersection_subsets_mh|proof]]). <br/> |
Similarly, we can argue that x ∈ A ⇒ x ∈ (A ∪ C), since A ⊂ (A ∪ C). | Similarly, we can argue that x ∈ A ⇒ x ∈ (A ∪ C), since A ⊂ (A ∪ C). | ||
Therefore, x ∈ A ⇒ x ∈ (A ∪ B) and x ∈ (A ∪ C) ⇒ x ∈ (A ∪ B) ∩ (A ∪ C).<br/> | Therefore, x ∈ A ⇒ x ∈ (A ∪ B) and x ∈ (A ∪ C) ⇒ x ∈ (A ∪ B) ∩ (A ∪ C).<br/> | ||
| − | If, instead, x ∈ (B ∩ C), then x ∈ B ⇒ x ∈ (A ∪ B), since B ⊂ (A ∪ B). <br/> | + | If, instead, x ∈ (B ∩ C), then x ∈ B ⇒ x ∈ (A ∪ B), since B ⊂ (A ∪ B) ([[Union_and_intersection_subsets_mh|proof]]). <br/> |
x ∈ (B ∩ C) also implies that x ∈ C ⇒ x ∈ (A ∪ C), since C ⊂ (A ∪ C). <br/> | x ∈ (B ∩ C) also implies that x ∈ C ⇒ x ∈ (A ∪ C), since C ⊂ (A ∪ C). <br/> | ||
Therefore, x ∈ (A ∪ B) and x ∈ (A ∪ C) ⇒ x ∈ (A ∪ B) ∩ (A ∪ C). <br/> | Therefore, x ∈ (A ∪ B) and x ∈ (A ∪ C) ⇒ x ∈ (A ∪ B) ∩ (A ∪ C). <br/> | ||
| Line 25: | Line 25: | ||
Next, assume that x ∈ (A ∪ B) ∩ (A ∪ C) ⇒ x ∈ (A ∪ B) and x ∈ (A ∪ C) ⇒ (x ∈ A or x ∈ B) and (x ∈ A or x ∈ C) ⇒ x ∈ A or (x ∈ B and x ∈ C) ⇒ x ∈ A or x ∈ (B ∩ C) ⇒ x ∈ A ∪ (B ∩ C). <br/> | Next, assume that x ∈ (A ∪ B) ∩ (A ∪ C) ⇒ x ∈ (A ∪ B) and x ∈ (A ∪ C) ⇒ (x ∈ A or x ∈ B) and (x ∈ A or x ∈ C) ⇒ x ∈ A or (x ∈ B and x ∈ C) ⇒ x ∈ A or x ∈ (B ∩ C) ⇒ x ∈ A ∪ (B ∩ C). <br/> | ||
| − | And we have that x ∈ (A ∪ B) ∩ (A ∪ C) ⇒ x ∈ A ∪ (B ∩ C), i.e. (A ∪ B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C) | + | And we have that x ∈ (A ∪ B) ∩ (A ∪ C) ⇒ x ∈ A ∪ (B ∩ C), i.e. (A ∪ B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C). |
Since A ∪ (B ∩ C) ⊂ (A ∪ B) ∩ (A ∪ C) and (A ∪ B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C), we have that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).<br/> | Since A ∪ (B ∩ C) ⊂ (A ∪ B) ∩ (A ∪ C) and (A ∪ B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C), we have that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).<br/> | ||
Latest revision as of 10:24, 1 October 2013
Theorem
Union is distributive over intersection ,i.e.
$ A\cup (B\cap C) = (A\cup B)\cap (A\cup C) $
where $ A $, $ B $ and $ C $ are sets.
Proof
Let x ∈ A ∪ (B ∩ C). Then, x ∈ A or x ∈ (B ∩ C), or both.
If x ∈ A, then x ∈ (A ∪ B), since A ⊂ (A ∪ B) (proof).
Similarly, we can argue that x ∈ A ⇒ x ∈ (A ∪ C), since A ⊂ (A ∪ C).
Therefore, x ∈ A ⇒ x ∈ (A ∪ B) and x ∈ (A ∪ C) ⇒ x ∈ (A ∪ B) ∩ (A ∪ C).
If, instead, x ∈ (B ∩ C), then x ∈ B ⇒ x ∈ (A ∪ B), since B ⊂ (A ∪ B) (proof).
x ∈ (B ∩ C) also implies that x ∈ C ⇒ x ∈ (A ∪ C), since C ⊂ (A ∪ C).
Therefore, x ∈ (A ∪ B) and x ∈ (A ∪ C) ⇒ x ∈ (A ∪ B) ∩ (A ∪ C).
So we have that x ∈ A ∪ (B ∩ C) ⇒ x ∈ (A ∪ B) ∩ (A ∪ C), or equivalently, that A ∪ (B ∩ C) ⊂ (A ∪ B) ∩ (A ∪ C).
Next, assume that x ∈ (A ∪ B) ∩ (A ∪ C) ⇒ x ∈ (A ∪ B) and x ∈ (A ∪ C) ⇒ (x ∈ A or x ∈ B) and (x ∈ A or x ∈ C) ⇒ x ∈ A or (x ∈ B and x ∈ C) ⇒ x ∈ A or x ∈ (B ∩ C) ⇒ x ∈ A ∪ (B ∩ C).
And we have that x ∈ (A ∪ B) ∩ (A ∪ C) ⇒ x ∈ A ∪ (B ∩ C), i.e. (A ∪ B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C).
Since A ∪ (B ∩ C) ⊂ (A ∪ B) ∩ (A ∪ C) and (A ∪ B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C), we have that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
$ \blacksquare $
