Pairwise operations

Definition 16   Let $A$ and $B$ be sets. Then the intersection

$$A\cap B=\{x\vert x\in A \mbox{ and } x\in B\}$$

Definition 17   Let $A$ and $B$ be sets. Then the union

$$A\cup B=\{x\vert x\in A \mbox{ or } x\in B\}$$

Definition 18   Let $A$ and $B$ be sets. Then $A\subseteq B$ iff

$$x\in A \rightarrow x \in B$$

.

Notice that $A=B$ if and only if both $A\subseteq B$ and $B\subseteq A$. The definitions of $A\cup B$ and $A\cap B$ also make it immediate that $A\cap B \subseteq A$, $A\cap B \subseteq B$, $A\subseteq A\cup B$, and $B\subseteq A\cup B$. Other close ties are given by

Proposition 19   The following are equivalent:

1. $A\subseteq B$
2. $A\cap B = A$
3. $A\cup B= B$

(6 Points )

Definition 19   Let $A$ and $B$ be sets. Then

$$A\setminus B=\{x\vert x\in A \mbox{ and } x\not\in B\}$$

Definition 20   Let $A$ and $B$ be sets. Then

$$A\times B=\{(a,b)\vert a\in A \mbox{ and } b\in B\}$$

The projections $\pi_A:A\times B\to A$ and $\pi_B:A\times B\to B$ take the pair $(a,b)$ to $a$ and $b$ respectively.

Proposition 20   Let $A$ and $B$ be sets and let $f:C\to A$ and $g:C\to B$ be functions. Then there is a unique function $(f,g):C\to A\times B$ such that $\pi_A\circ (f,g)=f$ and $\pi_B\circ (f,g)=g$.

(3 Points )

Definition 21   Let $A$ and $B$ be sets. Then the disjoint union

$$A + B=\{(a,1)\vert a\in A\}\cup \{(b,2)\vert b\in B\}$$

The injection maps are $\iota_A:A\to A+B$ with $\iota_A(a)=(a,1)$ and $\iota_B:B\to A+B$ with $\iota_B(b)=(b,2)$.

Proposition 21   Let $A$ and $B$ be sets and let $f:A\to C$ and $g:B\to C$ be functions. Then there is a unique function $(f+g):A+B\to C$ such that $(f+g)\circ \iota_A=f$ and $(f+g)\circ \iota_B=g$.

(3 Points )

Definition 22   The symmetric difference of sets $A$ and $B$ is

$$A\bigtriangleup B= (A\setminus B)\cup (B\setminus A)$$

Proposition 22   The set operations $A\setminus B$ and $A\cup B$ can be expressed using $\bigtriangleup$ and $\cap$.

(2 Points )

Proposition 23   Show that $\times$ and $+$ as defined above are neither associative nor commutative and have no identity elements.

(3 Points )

There is a sense in which the preceding proposition misrepresents the situation. We can weaken associativity, commutativity and identity so that they will (sort of) hold for $\times$ and $+$:

Proposition 24   We can salvage associativity, commutativity and identity for $\times$ and $+$ by asking for isomorphism rather than equality.

(3 Points )

Some further propositions relate union, intersection, Cartesian product and disjoint sum. For these either find a proof or a counterexample and salvage by indicating an appropriate direction for a subset relationship:

Proposition 25   $A\times (B\cup C) =( A\times B)\cup (A\times C)$

(2 Points )

Proposition 26   $A + (B\cap C) =( A+ B)\cap (A+ C)$

(2 Points )

Proposition 27   $(A\times B)\cup (C\times D) = (A\cup C) \times (B \cup D)$

(3 Points )

Proposition 28   $(A\times B)\cap (C\times D) = (A\cap C) \times (B \cap D)$

(3 Points )

Proposition 29   $(A+ B)\cup (C+ D) = (A\cup C) + (B \cup D)$

(3 Points )

Proposition 30   $(A+ B)\cap (C+ D) = (A\cap C) + (B \cap D)$

(3 Points )