Set Operations

Union

Definition: Union

The union of two sets $A$ and $B$ is the set which contains exactly the elements which are in $A$, in $B$ or in both $A$ and $B$.

$$\{x\mid x\in A\vee x\in B\}$$

NOTATION

$$A\cup B$$

Properties

Theorem: Cardinality of the Set Union

The union of two sets $A$ and $B$ has cardinality

$$|A\cup B|=|A|+|B|-|A\cap B|$$

PROOF

TODO

Theorem: Commutativity of the Set Union

The union of two sets $A$ and $B$ is commutative.

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

PROOF

TODO

Intersection

Definition: Intersection

The intersection of two sets $A$ and $B$ is the set of all elements shared by $A$ and $B$.

$$\{x\mid x\in A\wedge x\in B\}$$

NOTATION

$$A\cap B$$

Properties

Theorem: Commutativity of Set Intersection

The intersection of two sets $A$ and $B$ is commutative.

$$A\cap B=B\cap A$$

PROOF

TODO

Theorem: Associativity of Set Intersection

The intersection operation is associative for all sets $A,B,C$:

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

PROOF

TODO

Set Difference

Definition: Set Difference

The set difference $A\setminus B$ of two sets $A$ and $B$ is the set which contains exactly the elements in $A$ which are not elements of $B$.

$$\{x\mid x\in A\wedge x\notin B\}$$

NOTATION

$$A\setminus BA-B$$

Cartesian Product

Definition: Cartesian Product

The Cartesian product $A\times B$ of two sets $A$ and $B$ is the set of all ordered pairs $(a;b)$ where $a\in A$ and $b\in B$.

$$A\times B\stackrel{\text{def}}{=}\{(a;b)\mid a\in A\wedge b\in B\}$$

Properties

Theorem: Cardinality of the Cartesian Product

The Cartesian product of two sets $A$ and $B$ has cardinality

$$|A\times B|=|B\times A|=|A|\cdot |B|$$

PROOF

TODO

Distributive Laws

Theorem: Distributive Laws for Set Operations

The intersection, union and difference of all sets $A,B,C$ obey the following distributive laws:

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

PROOF

TODO