2 Sets and functions 2.2 Set operators 2.4 De Morgan’s laws

2.3 Set algebra

2.3.1 Commutativity and associativity

This section is about the laws that union, intersection, difference, and complement obey.

Theorem 2.3.1.

For all sets $A$ and $B$ ,

•

$A\cap B=B\cap A$ , and
•

$A\cup B=B\cup A$ .

These are called the commutativity properties for intersection and union. These results might seem obvious, but we will write out the proofs carefully because the method of using logical equivalences will be applied to more complex set identities later.

Proof.

By definition,

	$\displaystyle A\cap B$	$\displaystyle=\{x:x\in A\wedge x\in B\}$
	$\displaystyle B\cap A$	$\displaystyle=\{x:x\in B\wedge x\in A\}.$

Theorem 1.5.1 tells us that for any two WFFs $\phi$ and $\psi$ , the formulas $(\phi\wedge\psi)$ and $(\psi\wedge\phi)$ are logically equivalent: one is true if and only if the other is true. So

x\in A\wedge x\in B

is true if and only if

x\in B\wedge x\in A

is true. This shows that for any $x$ we have $x\in A\cap B$ if and only if $x\in B\cap A$ , so by definition of set equality, $A\cap B=B\cap A$ .

The argument for $\cup$ is the same, except that we use the logical equivalence $(\phi\vee\psi)\equiv(\psi\vee\psi)$ . ∎

What this proof shows is that if you have a set $X$ defined in set builder notation using a logical formula

X=\{x:P(x)\}

then it is equal to any other set defined using a logically equivalent formula.

Theorem 2.3.2.

For all sets $A$ , $B$ , $C$ we have

•

$A\cap(B\cap C)=(A\cap B)\cap C$ and
•

$A\cup(B\cup C)=(A\cup B)\cup C$ .

This is the associativity property for $\cap$ and $\cup$ .

Proof.

Like the proof of the last theorem, these equalities follow from the associativity properties for $\wedge$ and $\vee$ we saw in Theorem 1.5.1. ∎

Associativity tells us means there’s no ambiguity in writing

A\cup B\cup C\text{ or }A\cap B\cap C

without any brackets to indicate which union or intersection should be done first. Compare this with

1+2+3.

There’s no need for brackets because it doesn’t matter whether you do 1+2 first then add 3, or whether you add 1 to the result of 2 + 3. On the other hand $1+2\times 3$ or $1-2-3$ require either brackets or a convention on which operation to do first. Similarly $A\cup(B\cap C)$ is different to $(A\cup B)\cap C$ in general, so the brackets here are obligatory, and $A\setminus(B\setminus C)$ is different to $(A\setminus B)\setminus C$ .

2.3.2 The distributive laws

Because we defined unions and intersections using logical conditions on set elements, they should obey laws that come from the results we proved about $\wedge$ and $\vee$ .

Theorem 2.3.3.

For any sets $A$ , $B$ , $C$

1.

$A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$ and
2.

$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ .

Proof.

Consider the first of these identities. The left hand side consists of all things $x$ such that

x\in A\vee(x\in B\wedge x\in C).

(2.2)

The right hand side consists of all things $x$ such that

(x\in A\vee x\in B)\wedge(x\in A\vee x\in C)

(2.3)

By Theorem 1.6.1, for any WFFs $\phi,\psi,\theta$ we have $\phi\vee(\psi\wedge\phi)\equiv(\phi\vee\psi)\wedge(\phi\vee\psi)$ . Thus any $x$ makes (2.2) true if and only if it makes (2.3) true. So $x$ belongs to the first set if and only if it belongs to the second, therefore the two sets are equal.

The second identity can be proved similarly. ∎