Set

- equalities involving set operations
- intersection of sets
- subset relations
- proofs of equalities
- proofs of subset relations

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.

------- 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

Consider an arbitrary element

Hence by Universal Generalization, every element is in

Hence .

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, considering the Univesal Generalization rule, 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

Since

**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 )

**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 .