Properties of Set Operation

Subjects to be Learned


Basic properties of set operations are discussed here. 1 - 6 directly correspond to identities and implications of propositional logic, and 7 - 11 also follow immediately from them as illustrated below. If you widh to review them as well as inference rules click here.

1. $A \cup \emptyset = A$
    $A \cap U = A$
            -------     Identity Laws

2. $A \cup U = U$
    $A \cap \emptyset = \emptyset$
            -------     Domination Laws

3. $A \cup A = A$
    $A \cap A = A$
            -------     Idempotent Laws

4. tex2html_wrap_inline233
            -------     Commutative Laws

5. tex2html_wrap_inline237
            -------     Associative Laws

6. tex2html_wrap_inline241
            -------     Distributive Laws

7. If tex2html_wrap_inline185 and tex2html_wrap_inline247 , then tex2html_wrap_inline249 , and tex2html_wrap_inline251 .
8. If tex2html_wrap_inline185 , then tex2html_wrap_inline255 and tex2html_wrap_inline257 .
9. tex2html_wrap_inline259
10. tex2html_wrap_inline261
11. tex2html_wrap_inline263        ( cf. tex2html_wrap_inline265 )
      tex2html_wrap_inline267        ( cf. tex2html_wrap_inline269 )
            -------     De Morgan's Laws

12. tex2html_wrap_inline271 if and only if tex2html_wrap_inline273 and tex2html_wrap_inline275
13. tex2html_wrap_inline277 .

Additional properties:

14. A A B
15. A B A

The properties 1 tex2html_wrap_inline279 6 , and 11 can be proven using equivalences of propositional logic. The others can also be proven similarly by going to logic, though they can be proven also using some of these properties (after those properties are proven, needless to say). Let us prove some of these properties.

Proof for 4: tex2html_wrap_inline233
We are going to prove this by showing that every element that is in A B is also in B A and vice versa.
Consider an arbitrary element x. Then by the definition of set union
x A B x A x B
x A x B   by the commutativity of
x B A   by the definition of set union.
Hence by Universal Generalization, every element is in A B is also in B A .
Hence tex2html_wrap_inline233 .

Note here the correspondence of the commutativity of and that of This correspondence holds not just for the commutativity but also for others.
Furthermore a similar correspondence exists between and , and between and .

Proof for 6: By the definition of the equality of sets, we need to prove that tex2html_wrap_inline281 if and only if tex2html_wrap_inline283
For that, considering the Univesal Generalization rule, we need to show that for an arbitrary element in the universe x,
tex2html_wrap_inline287 if and only if tex2html_wrap_inline289
Here the only if part is going to be proven. The if part can be proven similarly. tex2html_wrap_inline291 by the definition of tex2html_wrap_inline293 .
tex2html_wrap_inline295 by the definition of tex2html_wrap_inline297 .
tex2html_wrap_inline299 by the distribution from the equivalences of propositional logic.
tex2html_wrap_inline301 by the definition of tex2html_wrap_inline293 .
tex2html_wrap_inline305 by the definition of tex2html_wrap_inline297 .

Proof for 8: (a) If tex2html_wrap_inline185 then tex2html_wrap_inline255 .
Let x be an arbitrary element in the universe.
Then tex2html_wrap_inline315 .
Since tex2html_wrap_inline185 , tex2html_wrap_inline219 .
Also tex2html_wrap_inline321 .
Hence tex2html_wrap_inline323 .
Hence tex2html_wrap_inline325 .
Since tex2html_wrap_inline327 (use "addition" rule), tex2html_wrap_inline255 follows.
(b) Similarly for tex2html_wrap_inline257 .

Alternative proof:

These can also be proven using 8, 14, and 15. For example, (b) can be proven as follows:
First by 15 A B A.
Then since A A, and A B, by 7 A A A B .
Since A A = A by 3, A A B .

Proof for 9: Let x be an arbitrary element in the universe.
Then tex2html_wrap_inline335
Hence tex2html_wrap_inline259 .

Alternative proof

This can also proven using set properties as follows.

A ( B - A ) = A ( B ) by the definition of ( B - A ) .
= ( A B ) ( A ) by the distribution.
= ( A B ) U
= ( A B )
by 1.

Proof for 10: Suppose tex2html_wrap_inline345 .
Then there is an element x that is in tex2html_wrap_inline349 , i.e.
Hence tex2html_wrap_inline345 does not hold.
Hence tex2html_wrap_inline261 .

This can also be proven in the similar manner to 9 above.

Proof for 11: Let x be an arbitrary element in the universe.
Then tex2html_wrap_inline365 tex2html_wrap_inline367
Hence tex2html_wrap_inline263

Proof for 12: (a) tex2html_wrap_inline379 ?
Try to prove tex2html_wrap_inline381 and tex2html_wrap_inline383 .
Let x be an arbitrary element in the universe.
Then if tex2html_wrap_inline387 , then tex2html_wrap_inline389 since tex2html_wrap_inline275 . Hence tex2html_wrap_inline393 .
Hence tex2html_wrap_inline381 .
If tex2html_wrap_inline393 , then tex2html_wrap_inline389 . Since tex2html_wrap_inline401 (from tex2html_wrap_inline273 ), tex2html_wrap_inline387 must hold. Hence tex2html_wrap_inline383 .
Hence tex2html_wrap_inline271 .
(b) tex2html_wrap_inline411 ?
Since tex2html_wrap_inline271 , tex2html_wrap_inline415 since tex2html_wrap_inline81 .
Also tex2html_wrap_inline419 by 10 above.

Proof for 13: Since tex2html_wrap_inline421 , tex2html_wrap_inline423 .
Also since tex2html_wrap_inline425 , tex2html_wrap_inline427 .
Hence A satisfies the conditions for the complement of tex2html_wrap_inline229 .
Hence tex2html_wrap_inline433 .

Next -- Recursive Definition

Back to Schedule
Back to Table of Contents