Set
Basic properties of set operations are discussed here. 1 - 6 directly correspond
to
1.
------- Identity Laws
2.
------- Domination Laws
3.
------- Idempotent Laws
4.
------- Commutative Laws
5.
------- Associative Laws
6.
------- Distributive Laws
7. If and , then ,
and .
8. If , then and .
9.
10.
11.
( cf. )
( cf. )
------- De Morgan's Laws
12. if and only if and
13. .
Additional properties:
14. A
A
B
15. A
B
A
The properties 1 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:
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
if and only if
For that we need to show that for an arbitrary element in the universe x,
if and only if
Here the only if part is going to be proven. The if part can be proven similarly.
by the definition
of .
by the definition of .
by the distribution
from the equivalences of propositional logic.
by the definition of .
by the definition of .
Proof for 8: (a) If then .
Let x be an arbitrary element in the universe.
Then .
Since , .
Also .
Hence .
Hence .
Since (use "addition" rule),
follows.
(b) Similarly for .
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
Hence .
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 .
Then there is an element x that is in , i.e.
Hence does not hold.
Hence .
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
Hence
Proof for 12: (a) ?
Try to prove and .
Let x be an arbitrary element in the universe.
Then if , then since . Hence .
Hence .
If , then . Since (from ),
must hold. Hence .
Hence .
(b) ?
Since , since .
Also by 10 above.
Proof for 13: Since , .
Also since , .
Hence A satisfies the conditions for the complement of .
Hence .