Set

Properties of Set Operation



Subjects to be Learned

Contents

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.

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
    tex2html_wrap_inline235
            -------     Commutative Laws

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

6. tex2html_wrap_inline241
    tex2html_wrap_inline243
            -------     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.

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 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
tex2html_wrap_inline337
tex2html_wrap_inline339
tex2html_wrap_inline341
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.
tex2html_wrap_inline351
tex2html_wrap_inline353
tex2html_wrap_inline355
tex2html_wrap_inline357
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
tex2html_wrap_inline369
tex2html_wrap_inline371
tex2html_wrap_inline373
tex2html_wrap_inline375
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