# Solutions Theorems with Proofs
# Solutions — Theorems with Proofs (Part 2)

*Full statements and proofs for every item in the theorem list. Where the exam lets you choose ("any two", "any one"), proofs for all the reasonable options are given so you can pick whichever you're asked for or were taught to prefer. Recall the scoring: theorem/statement = 1 mark, proof = 3 marks (split as 0.5/0.5 and 1.5/1.5 when two statements are asked).*

> **⚠️ Sourcing note:** Sections 6–9 (composition of relations and functions) are **not covered by any file in your project** — only "Examples" decks for relations exist there, not the main lecture deck with the actual theorem statements/proofs (the list cites "slide 13" and "slide 29" of a deck that isn't among your uploads). The proofs below for those four items use standard definitions consistent with your confirmed course conventions (the $S$-then-$R$ composition order, $R\subseteq X\times Y$ notation), but **please check them against your actual lecture slides** if you get the chance, in case your course phrases the definition of "function" or uses different variable names.

---

## 1. Properties of logical operators (slide 8)

**Proposition.** For every proposition $p,q,r$, the following are tautologies (always true).

All ten properties are proved below by truth table — for any two propositions/connectives, two sides of a biconditional are logically equivalent exactly when they have the same truth value in every row.

### Idempotence
$$p\lor p \Leftrightarrow p \qquad p\land p \Leftrightarrow p$$

| $p$ | $p\lor p$ | $p\land p$ |
|---|---|---|
| T | T | T |
| F | F | F |

Both columns equal $p$ in every row, so both equivalences are tautologies. $\blacksquare$

### Commutativity
$$p\lor q \Leftrightarrow q\lor p \qquad p\land q \Leftrightarrow q\land p$$

| $p$ | $q$ | $p\lor q$ | $q\lor p$ | $p\land q$ | $q\land p$ |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | T | T | F | F |
| F | T | T | T | F | F |
| F | F | F | F | F | F |

The $p\lor q$ and $q\lor p$ columns agree row-by-row, and likewise for $p\land q$ and $q\land p$. $\blacksquare$

### Absorption laws
$$(p\lor q)\land p \Leftrightarrow p \qquad (p\land q)\lor p \Leftrightarrow p$$

| $p$ | $q$ | $p\lor q$ | $(p\lor q)\land p$ | $p\land q$ | $(p\land q)\lor p$ |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | T | T | F | T |
| F | T | T | F | F | F |
| F | F | F | F | F | F |

Both derived columns match the $p$-column in every row. $\blacksquare$

### Associativity
$$p\lor(q\lor r) \Leftrightarrow (p\lor q)\lor r \qquad p\land(q\land r) \Leftrightarrow (p\land q)\land r$$

| $p$ | $q$ | $r$ | $q\lor r$ | $p\lor(q\lor r)$ | $p\lor q$ | $(p\lor q)\lor r$ | $q\land r$ | $p\land(q\land r)$ | $p\land q$ | $(p\land q)\land r$ |
|---|---|---|---|---|---|---|---|---|---|---|
| T|T|T| T | T | T | T | T | T | T | T |
| T|T|F| T | T | T | T | F | F | T | F |
| T|F|T| T | T | T | T | F | F | F | F |
| T|F|F| F | T | T | T | F | F | F | F |
| F|T|T| T | T | T | T | T | F | F | F |
| F|T|F| T | T | T | T | F | F | F | F |
| F|F|T| T | T | F | T | F | F | F | F |
| F|F|F| F | F | F | F | F | F | F | F |

In every row, $p\lor(q\lor r)$ matches $(p\lor q)\lor r$, and $p\land(q\land r)$ matches $(p\land q)\land r$. $\blacksquare$

### De Morgan's laws
$$\neg(p\lor q) \Leftrightarrow \neg p\land\neg q \qquad \neg(p\land q) \Leftrightarrow \neg p\lor\neg q$$

| $p$ | $q$ | $p\lor q$ | $\neg(p\lor q)$ | $\neg p\land\neg q$ | $p\land q$ | $\neg(p\land q)$ | $\neg p\lor\neg q$ |
|---|---|---|---|---|---|---|---|
| T | T | T | F | F | T | F | F |
| T | F | T | F | F | F | T | T |
| F | T | T | F | F | F | T | T |
| F | F | F | T | T | F | T | T |

$\neg(p\lor q)$ matches $\neg p\land\neg q$, and $\neg(p\land q)$ matches $\neg p\lor\neg q$, in every row. $\blacksquare$

### Distributivity
$$p\land(q\lor r) \Leftrightarrow (p\land q)\lor(p\land r)$$

| $p$ | $q$ | $r$ | $q\lor r$ | $p\land(q\lor r)$ | $p\land q$ | $p\land r$ | $(p\land q)\lor(p\land r)$ |
|---|---|---|---|---|---|---|---|
| T|T|T| T | T | T | T | T |
| T|T|F| T | T | T | F | T |
| T|F|T| T | T | F | T | T |
| T|F|F| F | F | F | F | F |
| F|T|T| T | F | F | F | F |
| F|T|F| T | F | F | F | F |
| F|F|T| T | F | F | F | F |
| F|F|F| F | F | F | F | F |

$$p\lor(q\land r) \Leftrightarrow (p\lor q)\land(p\lor r)$$

| $p$ | $q$ | $r$ | $q\land r$ | $p\lor(q\land r)$ | $p\lor q$ | $p\lor r$ | $(p\lor q)\land(p\lor r)$ |
|---|---|---|---|---|---|---|---|
| T|T|T| T | T | T | T | T |
| T|T|F| F | T | T | T | T |
| T|F|T| F | T | T | T | T |
| T|F|F| F | T | T | T | T |
| F|T|T| T | T | T | T | T |
| F|T|F| F | F | T | F | F |
| F|F|T| F | F | F | T | F |
| F|F|F| F | F | F | F | F |

Both columns match in every row, in each table. $\blacksquare$

### Inference rules

**Law of contrapositive:** $(p\Rightarrow q) \Leftrightarrow (\neg q\Rightarrow\neg p)$

| $p$ | $q$ | $p\Rightarrow q$ | $\neg q$ | $\neg p$ | $\neg q\Rightarrow\neg p$ |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |

The two implication columns agree in every row. $\blacksquare$

**Modus ponens:** $((p\Rightarrow q)\land p)\Rightarrow q$

| $p$ | $q$ | $p\Rightarrow q$ | $(p\Rightarrow q)\land p$ | $((p\Rightarrow q)\land p)\Rightarrow q$ |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | T |

The final column is T in every row, so the formula is a tautology. $\blacksquare$

**Syllogism:** $((p\Rightarrow q)\land(q\Rightarrow r))\Rightarrow(p\Rightarrow r)$

| $p$ | $q$ | $r$ | $p\Rightarrow q$ | $q\Rightarrow r$ | $(p\Rightarrow q)\land(q\Rightarrow r)$ | $p\Rightarrow r$ | full formula |
|---|---|---|---|---|---|---|---|
| T|T|T| T | T | T | T | T |
| T|T|F| T | F | F | F | T |
| T|F|T| F | T | F | T | T |
| T|F|F| F | T | F | F | T |
| F|T|T| T | T | T | T | T |
| F|T|F| T | F | F | T | T |
| F|F|T| T | T | T | T | T |
| F|F|F| T | T | T | T | T |

The final column is T throughout. $\blacksquare$

**Property 10:** $((p\Rightarrow q)\land(q\Rightarrow p)) \Leftrightarrow (p\Leftrightarrow q)$

| $p$ | $q$ | $p\Rightarrow q$ | $q\Rightarrow p$ | $(p\Rightarrow q)\land(q\Rightarrow p)$ | $p\Leftrightarrow q$ |
| --- | --- | ---------------- | ---------------- | --------------------------------------- | -------------------- |
| T   | T   | T                | T                | T                                       | T                    |
| T   | F   | F                | T                | F                                       | F                    |
| F   | T   | T                | F                | F                                       | F                    |
| F   | F   | T                | T                | T                                       | T                    |

The two right columns agree in every row. $\blacksquare$

---

## 2. Properties of the subset relation (slide 6)

**Proposition.** For every set $A,B,C$:

**Transitivity:** $(A\subseteq B \land B\subseteq C) \Rightarrow A\subseteq C$.

*Proof.* Assume $A\subseteq B$ and $B\subseteq C$. By definition of $\subseteq$, $\forall x(x\in A\Rightarrow x\in B)$ and $\forall x(x\in B\Rightarrow x\in C)$. Fix any $x$ with $x\in A$. Then $x\in B$ (first assumption), and so $x\in C$ (second assumption). Hence $\forall x(x\in A\Rightarrow x\in C)$, i.e. $A\subseteq C$. $\blacksquare$

**Antisymmetry:** $(A\subseteq B \land B\subseteq A) \Rightarrow A=B$.

*Proof.* Assume $A\subseteq B$ and $B\subseteq A$. By definition of $\subseteq$: $\forall x(x\in A\Rightarrow x\in B)$ and $\forall x(x\in B\Rightarrow x\in A)$. Combining these, $\forall x(x\in A\Leftrightarrow x\in B)$. By the definition of set equality (two sets are equal iff they have exactly the same elements), this means $A=B$. $\blacksquare$

*(The remaining two properties on this slide — $\varnothing\subseteq A$ and $A\subseteq A$ — are not listed as askable proof questions, but are quick to note: $\varnothing\subseteq A$ holds vacuously since there is no $x\in\varnothing$, so the implication $x\in\varnothing\Rightarrow x\in A$ is true for every $x$; $A\subseteq A$ holds since $x\in A\Rightarrow x\in A$ is trivially true.)*

---

## 3. Properties of set union and set intersection (slide 12)

**Proposition.** For every set $A,B,C$:

### Properties of union

**1. Idempotence:** $A\cup A = A$.
*Proof.* $x\in A\cup A \overset{(1)}{\Leftrightarrow} x\in A\lor x\in A \overset{(2)}{\Leftrightarrow} x\in A$. (1) definition of $\cup$; (2) idempotence of $\lor$. $\blacksquare$

**2. Associativity:** $A\cup(B\cup C) = (A\cup B)\cup C$.
*Proof.* $x\in A\cup(B\cup C) \overset{(1)}{\Leftrightarrow} x\in A \lor x\in B\cup C \overset{(1)}{\Leftrightarrow} x\in A\lor(x\in B\lor x\in C) \overset{(2)}{\Leftrightarrow} (x\in A\lor x\in B)\lor x\in C \overset{(1)}{\Leftrightarrow} x\in A\cup B \lor x\in C \overset{(1)}{\Leftrightarrow} x\in(A\cup B)\cup C$. (1) definition of $\cup$; (2) associativity of $\lor$. $\blacksquare$

**3. Commutativity:** $A\cup B = B\cup A$.
*Proof.* $x\in A\cup B \overset{(1)}{\Leftrightarrow} x\in A\lor x\in B \overset{(2)}{\Leftrightarrow} x\in B\lor x\in A \overset{(1)}{\Leftrightarrow} x\in B\cup A$. (1) definition of $\cup$; (2) commutativity of $\lor$. $\blacksquare$

**4. Property of $\varnothing$:** $A\cup\varnothing = A$.
*Proof.* $x\in A\cup\varnothing \overset{(1)}{\Leftrightarrow} x\in A\lor x\in\varnothing \overset{(2)}{\Leftrightarrow} x\in A \lor \text{F} \overset{(3)}{\Leftrightarrow} x\in A$. (1) definition of $\cup$; (2) definition of $\varnothing$ (no element belongs to it); (3) $p\lor\text{F}\Leftrightarrow p$. $\blacksquare$

**5.** $A\subseteq B \Leftrightarrow A\cup B = B$.
*Proof.*
($\Rightarrow$) Suppose $A\subseteq B$. We always have $B\subseteq A\cup B$ (every element of $B$ is in $A\cup B$, by definition of $\cup$). Conversely, if $x\in A\cup B$ then $x\in A$ or $x\in B$; in the first case $x\in B$ too, since $A\subseteq B$; in the second case $x\in B$ trivially. So $A\cup B\subseteq B$. By antisymmetry of $\subseteq$ (Section 2), $A\cup B=B$.
($\Leftarrow$) Suppose $A\cup B=B$. For any $x\in A$, we have $x\in A\cup B$ (by definition of $\cup$), hence $x\in B$ (since $A\cup B=B$). So $A\subseteq B$. $\blacksquare$

### Properties of intersection

**1. Idempotence:** $A\cap A = A$.
*Proof.* $x\in A\cap A \overset{(1)}{\Leftrightarrow} x\in A\land x\in A \overset{(2)}{\Leftrightarrow} x\in A$. (1) definition of $\cap$; (2) idempotence of $\land$. $\blacksquare$

**2. Associativity:** $A\cap(B\cap C) = (A\cap B)\cap C$.
*Proof.* Analogous to union, using associativity of $\land$ in place of $\lor$:
$x\in A\cap(B\cap C) \overset{(1)}{\Leftrightarrow} x\in A\land(x\in B\land x\in C) \overset{(2)}{\Leftrightarrow} (x\in A\land x\in B)\land x\in C \overset{(1)}{\Leftrightarrow} x\in(A\cap B)\cap C$. $\blacksquare$

**3. Commutativity:** $A\cap B = B\cap A$.
*Proof.* $x\in A\cap B \overset{(1)}{\Leftrightarrow} x\in A\land x\in B \overset{(2)}{\Leftrightarrow} x\in B\land x\in A \overset{(1)}{\Leftrightarrow} x\in B\cap A$. (1) definition of $\cap$; (2) commutativity of $\land$. $\blacksquare$

**4. Property of $\varnothing$:** $A\cap\varnothing = \varnothing$.
*Proof.* $x\in A\cap\varnothing \overset{(1)}{\Leftrightarrow} x\in A\land x\in\varnothing \overset{(2)}{\Leftrightarrow} x\in A\land\text{F} \overset{(3)}{\Leftrightarrow}\text{F} \overset{(2)}{\Leftrightarrow} x\in\varnothing$. (1) definition of $\cap$; (2) definition of $\varnothing$; (3) $p\land\text{F}\Leftrightarrow\text{F}$. $\blacksquare$

**5.** $A\subseteq B \Leftrightarrow A\cap B = A$.
*Proof.*
($\Rightarrow$) Suppose $A\subseteq B$. We always have $A\cap B\subseteq A$. Conversely, if $x\in A$ then, since $A\subseteq B$, also $x\in B$; hence $x\in A\cap B$. So $A\subseteq A\cap B$. By antisymmetry of $\subseteq$, $A\cap B = A$.
($\Leftarrow$) Suppose $A\cap B=A$. For any $x\in A$, since $A=A\cap B$ we get $x\in A\cap B$, hence $x\in B$. So $A\subseteq B$. $\blacksquare$

---

## 4. Distributivity of set union and set intersection (slide 14)

**Proposition.** For every set $A,B,C$:
$$A\cap(B\cup C) = (A\cap B)\cup(A\cap C) \qquad A\cup(B\cap C) = (A\cup B)\cap(A\cup C)$$

**Proof of $A\cap(B\cup C) = (A\cap B)\cup(A\cap C)$.**
$$x\in A\cap(B\cup C) \overset{(1)}{\Leftrightarrow} x\in A\land x\in B\cup C \overset{(2)}{\Leftrightarrow} x\in A\land(x\in B\lor x\in C) \overset{(3)}{\Leftrightarrow} (x\in A\land x\in B)\lor(x\in A\land x\in C) \overset{(1)}{\Leftrightarrow} x\in A\cap B \lor x\in A\cap C \overset{(2)}{\Leftrightarrow} x\in(A\cap B)\cup(A\cap C)$$
(1) definition of $\cap$; (2) definition of $\cup$; (3) distributivity of $\land$ over $\lor$. $\blacksquare$

**Proof of $A\cup(B\cap C) = (A\cup B)\cap(A\cup C)$.**
$$x\in A\cup(B\cap C) \overset{(1)}{\Leftrightarrow} x\in A\lor x\in B\cap C \overset{(2)}{\Leftrightarrow} x\in A\lor(x\in B\land x\in C) \overset{(3)}{\Leftrightarrow} (x\in A\lor x\in B)\land(x\in A\lor x\in C) \overset{(1)}{\Leftrightarrow} x\in A\cup B \land x\in A\cup C \overset{(2)}{\Leftrightarrow} x\in(A\cup B)\cap(A\cup C)$$
(1) definition of $\cup$; (2) definition of $\cap$; (3) distributivity of $\lor$ over $\land$. $\blacksquare$

---

## 5. Properties of set complement (slide 17)

**Proposition.** Let $U$ be the universal set. For every $A,B\subseteq U$:

**1. $\overline{\overline{A}} = A$.**
*Proof.* $x\in\overline{\overline{A}} \overset{(1)}{\Leftrightarrow} \neg(x\in\overline{A}) \overset{(1)}{\Leftrightarrow} \neg\neg(x\in A) \Leftrightarrow x\in A$. (1) definition of complement; the last step is double-negation elimination. $\blacksquare$

**2. $\overline{\varnothing} = U$.**
*Proof.* $x\in\overline{\varnothing} \overset{(1)}{\Leftrightarrow} \neg(x\in\varnothing) \overset{(2)}{\Leftrightarrow} x\in U$. (1) definition of complement; (2) by definition of $\varnothing$ and $U$ (nothing is in $\varnothing$, everything relevant is in $U$). $\blacksquare$

**3. $\overline{U} = \varnothing$.**
*Proof.* $x\in\overline{U} \overset{(1)}{\Leftrightarrow} \neg(x\in U) \overset{(2)}{\Leftrightarrow} x\in\varnothing$. (1) definition of complement; (2) by definition of $\varnothing$ and $U$. $\blacksquare$

**4. $A\cap\overline{A} = \varnothing$.**
*Proof.* $x\in A\cap\overline{A} \overset{(1)}{\Leftrightarrow} x\in A\land x\in\overline{A} \overset{(2)}{\Leftrightarrow} x\in A\land\neg(x\in A) \overset{(3)}{\Leftrightarrow} x\in\varnothing$. (1) definition of $\cap$; (2) definition of complement; (3) by definition of $\land$ and $\varnothing$ (a statement and its negation are never both true). $\blacksquare$

**5. $A\cup\overline{A} = U$.**
*Proof.* $x\in A\cup\overline{A} \overset{(1)}{\Leftrightarrow} x\in A\lor x\in\overline{A} \overset{(2)}{\Leftrightarrow} x\in A\lor\neg(x\in A) \overset{(3)}{\Leftrightarrow} x\in U$. (1) definition of $\cup$; (2) definition of complement; (3) by definition of $\lor$ and $U$ (a statement or its negation is always true). $\blacksquare$

**6. $A\subseteq B \Leftrightarrow \overline{B}\subseteq\overline{A}$.**
*Proof.*
$$A\subseteq B \overset{(1)}{\Leftrightarrow} \forall x(x\in A\Rightarrow x\in B) \overset{(2)}{\Leftrightarrow} \forall x(\neg(x\in B)\Rightarrow\neg(x\in A)) \overset{(3)}{\Leftrightarrow} \forall x(x\in\overline{B}\Rightarrow x\in\overline{A}) \overset{(1)}{\Leftrightarrow} \overline{B}\subseteq\overline{A}$$
(1) definition of $\subseteq$; (2) law of contrapositive; (3) definition of complement. $\blacksquare$

**7. $\overline{A\cap B} = \overline{A}\cup\overline{B}$ (De Morgan's law for $\cap$).**
*Proof.* $x\in\overline{A\cap B} \overset{(1)}{\Leftrightarrow} \neg(x\in A\cap B) \overset{(2)}{\Leftrightarrow} \neg(x\in A \land x\in B) \overset{(3)}{\Leftrightarrow} \neg(x\in A)\lor\neg(x\in B) \overset{(1)}{\Leftrightarrow} x\in\overline{A}\lor x\in\overline{B} \overset{(4)}{\Leftrightarrow} x\in\overline{A}\cup\overline{B}$. (1) definition of complement; (2) definition of $\cap$; (3) De Morgan's law for the logical operators $\land,\lor$; (4) definition of $\cup$. $\blacksquare$

**8. $\overline{A\cup B} = \overline{A}\cap\overline{B}$ (De Morgan's law for $\cup$).**
*Proof.* $x\in\overline{A\cup B} \overset{(1)}{\Leftrightarrow} \neg(x\in A\cup B) \overset{(2)}{\Leftrightarrow} \neg(x\in A \lor x\in B) \overset{(3)}{\Leftrightarrow} \neg(x\in A)\land\neg(x\in B) \overset{(1)}{\Leftrightarrow} x\in\overline{A}\land x\in\overline{B} \overset{(4)}{\Leftrightarrow} x\in\overline{A}\cap\overline{B}$. (1) definition of complement; (2) definition of $\cup$; (3) De Morgan's law for the logical operators $\lor,\land$; (4) definition of $\cap$. $\blacksquare$

*(Properties 7 and 8 are the De Morgan's laws for sets.)*

---

## 6. Associativity of composition of binary relations (slide 13) ⚠️ *not in project files — see note above*

**Proposition.** For all relations $R\subseteq X\times Y$, $S\subseteq Y\times Z$, $T\subseteq Z\times W$, the composition of binary relations is associative:
$$T\circ(S\circ R) = (T\circ S)\circ R.$$
Here, recall composition is defined so that $(x,z)\in S\circ R \iff \exists y: (x,y)\in R \land (y,z)\in S$ — i.e. $R$ is applied first, then $S$ (your course's confirmed convention).

*Proof.* For any $x\in X$ and $w\in W$:
$$
\begin{aligned}
(x,w)\in T\circ(S\circ R)
&\overset{(1)}{\Leftrightarrow} \exists z: (x,z)\in S\circ R \ \land\ (z,w)\in T \\
&\overset{(1)}{\Leftrightarrow} \exists z: \big(\exists y: (x,y)\in R \land (y,z)\in S\big) \land (z,w)\in T \\
&\overset{(2)}{\Leftrightarrow} \exists y\,\exists z: (x,y)\in R \land (y,z)\in S \land (z,w)\in T \\
&\overset{(2)}{\Leftrightarrow} \exists y: (x,y)\in R \land \big(\exists z: (y,z)\in S \land (z,w)\in T\big) \\
&\overset{(1)}{\Leftrightarrow} \exists y: (x,y)\in R \land (y,w)\in T\circ S \\
&\overset{(1)}{\Leftrightarrow} (x,w)\in (T\circ S)\circ R
\end{aligned}
$$
(1) definition of composition (applied to the inner and outer compositions); (2) reordering and regrouping of the existential quantifiers and conjunctions, which is always logically valid. Since $(x,w)$ was arbitrary, $T\circ(S\circ R) = (T\circ S)\circ R$. $\blacksquare$

---

## 7. Inverse of the composition of binary relations (slide 13) ⚠️ *not in project files — see note above*

**Proposition.** For all relations $R\subseteq X\times Y$ and $S\subseteq Y\times Z$:
$$(S\circ R)^{-1} = R^{-1}\circ S^{-1}.$$

*Proof.* For any $z\in Z$ and $x\in X$:
$$
\begin{aligned}
(z,x)\in R^{-1}\circ S^{-1}
&\overset{(1)}{\Leftrightarrow} \exists y: (z,y)\in S^{-1} \land (y,x)\in R^{-1} \\
&\overset{(2)}{\Leftrightarrow} \exists y: (y,z)\in S \land (x,y)\in R \\
&\Leftrightarrow \exists y: (x,y)\in R \land (y,z)\in S \\
&\overset{(1)}{\Leftrightarrow} (x,z)\in S\circ R \\
&\overset{(2)}{\Leftrightarrow} (z,x)\in (S\circ R)^{-1}
\end{aligned}
$$
(1) definition of composition; (2) definition of inverse relation (swap coordinates). Since $(z,x)$ was arbitrary, $(S\circ R)^{-1} = R^{-1}\circ S^{-1}$. $\blacksquare$

---

## 8. Composition of functions is a function (slide 29) ⚠️ *not in project files — see note above*

**Definition (function).** A relation $f\subseteq X\times Y$ is a function from $X$ to $Y$ if $\forall x\in X\,\exists!\, y\in Y: (x,y)\in f$ (every $x\in X$ has exactly one image under $f$).

**Theorem.** Let $f:X\to Y$ and $g:Y\to Z$ be functions. Then the composition $g\circ f$ (apply $f$ first, then $g$) is a function from $X$ to $Z$.

*Proof.* Let $x\in X$ be arbitrary; we must show there is exactly one $z\in Z$ with $(x,z)\in g\circ f$.

*Existence.* Since $f$ is a function and $x\in X$, there exists a (unique) $y\in Y$ with $(x,y)\in f$. Since $g$ is a function and $y\in Y$, there exists a (unique) $z\in Z$ with $(y,z)\in g$. By definition of composition, $(x,z)\in g\circ f$.

*Uniqueness.* Suppose $(x,z_1)\in g\circ f$ and $(x,z_2)\in g\circ f$. By definition of composition, there exist $y_1,y_2\in Y$ with $(x,y_1)\in f, (y_1,z_1)\in g$ and $(x,y_2)\in f, (y_2,z_2)\in g$. Since $f$ is a function, $(x,y_1)\in f$ and $(x,y_2)\in f$ force $y_1=y_2$ (call this common value $y$). Then $(y,z_1)\in g$ and $(y,z_2)\in g$; since $g$ is a function, $z_1=z_2$.

So every $x\in X$ has exactly one image under $g\circ f$, i.e. $g\circ f$ is a function from $X$ to $Z$. $\blacksquare$

---

## 9. Composition of injective functions is injective (slide 29) ⚠️ *not in project files — see note above*

**Definition (injective).** A function $f:X\to Y$ is injective if $\forall x_1,x_2\in X: f(x_1)=f(x_2) \Rightarrow x_1=x_2$.

**Theorem.** Let $f:X\to Y$ and $g:Y\to Z$ be injective functions. Then $g\circ f: X\to Z$ is injective.

*Proof.* Let $x_1,x_2\in X$ with $(g\circ f)(x_1) = (g\circ f)(x_2)$, i.e. $g(f(x_1)) = g(f(x_2))$. Since $g$ is injective, this forces $f(x_1) = f(x_2)$. Since $f$ is injective, this in turn forces $x_1 = x_2$. Hence $g\circ f$ is injective. $\blacksquare$

---

## 10. Properties of conjugation and absolute value (slide 14)

Let $z=a+bi$, $w=c+di$ with $a,b,c,d\in\mathbb{R}$ be complex numbers. All ten properties below (excluding the triangle inequality, which is not required) can be proved directly from the algebraic form; any two of the conjugation properties or any two of the absolute-value properties may be asked.

### Conjugation properties

**1. $\overline{\overline{z}} = z$.**
*Proof.* $\overline{z} = a-bi$, so $\overline{\overline{z}} = \overline{a-bi} = a+bi = z$. $\blacksquare$

**2. $\overline{z+w} = \overline{z}+\overline{w}$.**
*Proof.* $z+w = (a+c)+(b+d)i$, so $\overline{z+w} = (a+c)-(b+d)i = (a-bi)+(c-di) = \overline{z}+\overline{w}$. $\blacksquare$

**3. $\overline{zw} = \overline{z}\cdot\overline{w}$.**
*Proof.* $zw = (ac-bd)+(ad+bc)i$, so $\overline{zw} = (ac-bd)-(ad+bc)i$. On the other hand, $\overline{z}\cdot\overline{w} = (a-bi)(c-di) = ac - adi - bci + bdi^2 = (ac-bd) - (ad+bc)i$. The two sides agree. $\blacksquare$

**4. $z+\overline{z} = 2\operatorname{Re}(z)$.**
*Proof.* $z+\overline{z} = (a+bi)+(a-bi) = 2a = 2\operatorname{Re}(z)$. $\blacksquare$

**5. $z-\overline{z} = 2\operatorname{Im}(z)\cdot i$.**
*Proof.* $z-\overline{z} = (a+bi)-(a-bi) = 2bi = 2\operatorname{Im}(z)\cdot i$. $\blacksquare$

### Absolute value properties (and the link between them)

**6. $z\cdot\overline{z} = |z|^2$.**
*Proof.* $z\cdot\overline{z} = (a+bi)(a-bi) = a^2+b^2 = |z|^2$. $\blacksquare$

**7. If $z\neq 0$ then $z^{-1} = \dfrac{\overline{z}}{|z|^2}$.**
*Proof.* By property 6, $z\cdot\overline{z}=|z|^2$. Since $z\neq 0$, also $|z|^2\neq 0$, so we may divide both sides by $|z|^2$: $z\cdot\dfrac{\overline{z}}{|z|^2}=1$. This shows $\dfrac{\overline{z}}{|z|^2}$ is the multiplicative inverse of $z$. $\blacksquare$

**8. $|0|=0$, and if $z\neq 0$ then $|z|>0$.**
*Proof.* $|0|=\sqrt{0^2+0^2}=0$. If $z\neq0$ then $a\neq0$ or $b\neq0$, so $a^2+b^2>0$, hence $|z|=\sqrt{a^2+b^2}>0$. $\blacksquare$

**9. $|\overline{z}| = |z|$.**
*Proof.* $|\overline{z}| = |a-bi| = \sqrt{a^2+(-b)^2} = \sqrt{a^2+b^2} = |z|$. $\blacksquare$

**10. $|zw| = |z|\cdot|w|$.**
*Proof.* Using property 6 repeatedly: $|zw|^2 = (zw)\overline{(zw)} \overset{\text{prop. 3}}{=} zw\,\overline{z}\,\overline{w} = (z\overline{z})(w\overline{w}) \overset{\text{prop. 6}}{=} |z|^2|w|^2 = (|z||w|)^2$. Since absolute values are non-negative, taking square roots gives $|zw|=|z||w|$. $\blacksquare$

---

## 11. Multiplication in polar form (slide 19)

**Theorem.** Let $z,w\in\mathbb{C}$ be nonzero complex numbers given in polar form, $z=|z|(\cos\varphi+i\sin\varphi)$ and $w=|w|(\cos\psi+i\sin\psi)$, where $|z|,|w|$ are their absolute values and $\varphi,\psi$ are arguments. Then the product $zw$ in polar form is
$$zw = |z||w|\big(\cos(\varphi+\psi) + i\sin(\varphi+\psi)\big),$$
i.e. multiplying two complex numbers multiplies their absolute values and adds their arguments.

*Proof.*
$$
\begin{aligned}
zw &= |z|(\cos\varphi+i\sin\varphi)\cdot|w|(\cos\psi+i\sin\psi)\\
&\overset{(1)}{=} |z||w|\,(\cos\varphi+i\sin\varphi)(\cos\psi+i\sin\psi)\\
&\overset{(2)}{=} |z||w|\,\big(\cos\varphi\cos\psi - \sin\varphi\sin\psi + i(\cos\varphi\sin\psi+\sin\varphi\cos\psi)\big)\\
&\overset{(3)}{=} |z||w|\big(\cos(\varphi+\psi) + i\sin(\varphi+\psi)\big)
\end{aligned}
$$
(1) commutativity of multiplication; (2) expanding the product using $i^2=-1$; (3) the trigonometric addition formulas $\cos(\varphi+\psi)=\cos\varphi\cos\psi-\sin\varphi\sin\psi$ and $\sin(\varphi+\psi)=\cos\varphi\sin\psi+\sin\varphi\cos\psi$. $\blacksquare$

---

## 12. $n^{\text{th}}$ roots of a complex number (slide 21)

**Theorem.** Let $z=|z|(\cos\varphi+i\sin\varphi)$ be a nonzero complex number and $n\in\mathbb{N}^+$. The $n^{\text{th}}$ roots of $z$ — i.e. the complex numbers $w$ with $w^n=z$ — are
$$w_k = \sqrt[n]{|z|}\left(\cos\!\left(\frac{\varphi}{n}+\frac{2k\pi}{n}\right) + i\sin\!\left(\frac{\varphi}{n}+\frac{2k\pi}{n}\right)\right), \qquad k=0,1,\ldots,n-1.$$

*Proof.* We use the fact (from De Moivre's formula) that for any $w=|w|(\cos\psi+i\sin\psi)$, $w^n = |w|^n(\cos n\psi+i\sin n\psi)$. We also use the fact that two complex numbers in polar form are equal exactly when their absolute values agree and their arguments differ by an integer multiple of $2\pi$:
$$|z|(\cos\varphi+i\sin\varphi) = |w|(\cos\psi+i\sin\psi) \iff |z|=|w| \ \text{and}\ \varphi=\psi+2k\pi \text{ for some } k\in\mathbb{Z}.$$

Now, $w^n=z$ is equivalent to $|w|^n(\cos n\psi+i\sin n\psi) = |z|(\cos\varphi+i\sin\varphi)$, which by the fact above holds if and only if:
$$|w|^n = |z| \iff |w| = \sqrt[n]{|z|}, \qquad\text{and}\qquad n\psi = \varphi+2k\pi \text{ for some } k\in\mathbb{Z} \iff \psi = \frac{\varphi}{n}+\frac{2k\pi}{n} \text{ for some } k\in\mathbb{Z}.$$

As $k$ ranges over all integers, $\psi=\frac{\varphi}{n}+\frac{2k\pi}{n}$ takes exactly $n$ distinct values modulo $2\pi$, obtained by letting $k=0,1,\ldots,n-1$ (further integer values of $k$ just repeat these arguments, shifted by a multiple of $2\pi$). Hence $z$ has exactly $n$ distinct $n^{\text{th}}$ roots, given by $w_k$ for $k=0,1,\ldots,n-1$ as stated. $\blacksquare$

---

## 13. Permutations without repetition (slide 7)

**Theorem.** Let $n\in\mathbb{N}$. The number of permutations of an $n$-element set (the number of ways to order all $n$ of its elements in a sequence) is $P_n = n!$.

*Proof (combinatorial argument).* The first element of the sequence can be chosen in $n$ different ways. After this, the second element can be chosen in $n-1$ different ways (one element has already been used), the third in $n-2$ ways, and so on, until the last element, which can be chosen in exactly $1$ way. By the multiplication principle, the total number of orderings is $n\cdot(n-1)\cdot\ldots\cdot 2\cdot 1 = n!$. $\blacksquare$

*Proof (by induction on $n$, more formal).* Let $|A|=n$.
*Base step:* $n=0$. There is exactly $1$ way to order $0$ elements (the empty sequence), so $P_0=1=0!$.
*Inductive step:* Suppose $n>0$ and $P_{n-1}=(n-1)!$ (inductive hypothesis). The first element of the sequence can be chosen in $n$ ways; by the inductive hypothesis, the remaining $n-1$ elements can then be ordered in $(n-1)!$ ways. By the multiplication principle, the $n$ elements can be ordered in $n\cdot(n-1)! = n!$ ways, so $P_n=n!$. $\blacksquare$

---

## 14. Permutations with repetition (slide 11)

**Definition.** Let $a_1,a_2,\ldots,a_m$ be $m$ distinct objects and $k_1,k_2,\ldots,k_m\in\mathbb{N}$. A sequence of length $n=k_1+k_2+\ldots+k_m$ containing each $a_i$ exactly $k_i$ times is a permutation with repetition of $a_1,\ldots,a_m$ with repetition numbers $k_1,\ldots,k_m$.

**Theorem.** The number of permutations with repetition of $m$ distinct objects with repetition numbers $k_1,k_2,\ldots,k_m$ is
$$\frac{n!}{k_1!\cdot k_2!\cdot\ldots\cdot k_m!}, \qquad \text{where } n=k_1+k_2+\ldots+k_m.$$

*Proof.* If all $n=k_1+\ldots+k_m$ elements were treated as distinguishable (e.g. by labelling repeated copies), there would be $n!$ possible orderings. However, we do not wish to distinguish between identical copies of the same object: for each kind $i$, only the *set of positions* occupied by copies of $a_i$ matters, not which particular copy sits where. Fixing the $k_i$ positions assigned to kind $i$, the copies of $a_i$ occupying these positions can be permuted among themselves in $k_i!$ ways without producing a different sequence. Hence in the count of $n!$, every genuinely distinct sequence (with repetition) was counted $k_1!\cdot k_2!\cdot\ldots\cdot k_m!$ times. Dividing out this overcounting, the number of permutations with repetition is $\dfrac{n!}{k_1!\cdot k_2!\cdot\ldots\cdot k_m!}$. $\blacksquare$

---

## 15. Variations without repetition (slide 13)

**Definition.** Let $A$ be a set and $k\in\mathbb{N}$. A sequence of length $k$ formed from elements of $A$, containing each element of $A$ at most once, is a $k$-variation (without repetition) of $A$.

**Theorem.** Let $k\in\mathbb{N}^+$. The number of $k$-variations without repetition of an $n$-element set is
$$V_n^k = n\cdot(n-1)\cdot\ldots\cdot(n-k+1) = \frac{n!}{(n-k)!} \quad\text{if } k\leq n, \qquad \text{and } 0 \text{ otherwise.}$$

*Proof.* Let $k\leq n$. The first element of the sequence can be chosen in $n$ different ways from the set $A$. After this, the second element can be chosen in $n-1$ different ways (the element already used cannot be chosen again). Continuing this way, the third element can be chosen in $n-2$ ways, and so on, until the $k^{\text{th}}$ element, which can be chosen in $n-k+1$ ways. By the multiplication principle, the total number of $k$-variations is $n\cdot(n-1)\cdot\ldots\cdot(n-k+1) = \dfrac{n!}{(n-k)!}$. If $k>n$, there are not enough distinct elements in $A$ to fill $k$ positions without repetition, so $A$ has no $k$-variation without repetition. $\blacksquare$

---

## 16. Variations with repetition (slide 15)

**Definition.** Let $A$ be a set and $k\in\mathbb{N}$. A sequence of length $k$ formed from elements of $A$, where any element of $A$ may occur more than once, is a $k$-variation with repetition of $A$.

**Theorem.** Let $n,k\in\mathbb{N}$. The number of $k$-variations with repetition of an $n$-element set is $n^k$.

*Proof.* The first element of the sequence can be chosen in $n$ different ways. Since repetition is allowed, the second element can again be chosen in $n$ different ways, independently of the first; likewise for every subsequent position. By the multiplication principle, the total number of sequences of length $k$ is $\underbrace{n\cdot n\cdot\ldots\cdot n}_{k \text{ times}} = n^k$. $\blacksquare$

---

## 17. Combinations without repetition (slide 18)

**Definition.** Let $k\in\mathbb{N}$. A $k$-element subset of a set $A$ is a $k$-combination (without repetition) of $A$. For $n,k\in\mathbb{N}$ with $k\le n$, the binomial coefficient is defined as $\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$.

**Theorem.** Let $n,k\in\mathbb{N}$. The number of $k$-combinations of an $n$-element set is
$$C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!} \quad\text{if } k\leq n, \qquad \text{and } 0 \text{ otherwise.}$$

*Proof.* Let $A$ be an $n$-element set and suppose $k\le n$. First, count the $k$-variations without repetition of $A$ — i.e. sequences of $k$ distinct elements where order matters — there are $\frac{n!}{(n-k)!}$ of these (Section 15). Now, if we stop distinguishing the order of the $k$ chosen elements, each $k$-element subset of $A$ corresponds to exactly $k!$ of these ordered sequences (the number of ways to arrange $k$ elements into order). So the count $\frac{n!}{(n-k)!}$ over-counts each subset by a factor of $k!$. Dividing out gives the number of $k$-element subsets: $\dfrac{n!}{k!(n-k)!}$. If $k>n$, an $n$-element set clearly has no $k$-element subsets. $\blacksquare$

---

## 18. Combinations with repetition (slide 21)

**Definition.** Let $k\in\mathbb{N}$. A $k$-combination with repetition (or $k$-multiset) from a set $A$ is a selection of $k$ elements from $A$, where repetition is allowed and order does not matter (only how many times each element of $A$ is chosen).

**Theorem.** Let $n\in\mathbb{N}^+$, $k\in\mathbb{N}$. The number of $k$-combinations with repetition of an $n$-element set is
$$\binom{n+k-1}{k}.$$

*Proof.* Let $A=\{a_1,a_2,\ldots,a_n\}$. Every $k$-combination with repetition of $A$ can be encoded as a $0$–$1$ sequence: write the number of times $a_1$ was chosen as that many $1$'s, then a $0$ as a separator, then the number of times $a_2$ was chosen as that many $1$'s, then a separator, and so on up to $a_n$. Such a sequence contains exactly $k$ ones (the total number of elements chosen) and $n-1$ zeros (the separators between the $n$ kinds of element), so it has length $n-1+k$. Conversely, every such $0$–$1$ sequence of length $n+k-1$ with exactly $k$ ones corresponds to exactly one $k$-combination with repetition. The number of such sequences equals the number of ways to choose which $k$ of the $n+k-1$ positions hold the $1$'s, which is $\binom{n+k-1}{k}$. Hence the number of $k$-combinations with repetition of $A$ is $\binom{n+k-1}{k}$. $\blacksquare$

---

## 19. Binomial theorem (slide 24)

**Theorem.** For any $x,y\in\mathbb{R}$ and $n\in\mathbb{N}$,
$$(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^k y^{n-k}.$$

*Proof.* Write $(x+y)^n$ as a product of $n$ factors: $(x+y)^n = (x+y)\cdot(x+y)\cdot\ldots\cdot(x+y)$. By the distributive law, expanding this product gives a sum of terms, each obtained by choosing either $x$ or $y$ from each of the $n$ brackets and multiplying the choices together. Every such term has the form $x^k y^{n-k}$ for some $0\le k\le n$ (where $k$ is the number of brackets from which $x$ was chosen). For a fixed $k$, the term $x^k y^{n-k}$ appears once for every way of choosing which $k$ of the $n$ brackets contribute an $x$ (the rest then contribute $y$); this can be done in $\binom{n}{k}$ different ways. Hence the coefficient of $x^k y^{n-k}$ in the expansion is $\binom{n}{k}$, giving $(x+y)^n=\sum_{k=0}^n\binom{n}{k}x^k y^{n-k}$. $\blacksquare$

---

## 20. Properties of binomial coefficients (slide 25)

**Proposition.** For every $n,k\in\mathbb{N}$ with $k\leq n$:

**1. Symmetry rule:** $\dbinom{n}{k} = \dbinom{n}{n-k}$.

*Proof.* By the theorem on combinations without repetition, $\binom{n}{k}$ equals the number of $k$-element subsets of an $n$-element set $A$. We count these subsets a second way: for each $k$-element subset $S\subseteq A$, the complementary set $A\setminus S$ is an $(n-k)$-element subset of $A$, and this correspondence $S \mapsto A\setminus S$ is a bijection between $k$-element subsets and $(n-k)$-element subsets of $A$. So the number of $k$-element subsets equals the number of $(n-k)$-element subsets, i.e. $\binom{n}{k}=\binom{n}{n-k}$. $\blacksquare$

**2. Pascal's identity:** $\dbinom{n+1}{k+1} = \dbinom{n}{k}+\dbinom{n}{k+1}$ if $n>k$.

*Proof.* Let $A$ be an $(n+1)$-element set; by definition $A$ has $\binom{n+1}{k+1}$ subsets of size $k+1$. We count these subsets a second way. Fix one element $x_0\in A$. The $(k+1)$-element subsets of $A$ split into two disjoint groups:
- those *containing* $x_0$: choosing such a subset amounts to choosing the remaining $k$ elements from $A\setminus\{x_0\}$ (which has $n$ elements), giving $\binom{n}{k}$ subsets;
- those *not containing* $x_0$: such a subset must have all $k+1$ of its elements chosen from $A\setminus\{x_0\}$, giving $\binom{n}{k+1}$ subsets.

Adding these two disjoint counts gives the total: $\binom{n+1}{k+1} = \binom{n}{k}+\binom{n}{k+1}$. $\blacksquare$

For every $n\in\mathbb{N}$:

**3.** $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$.

*Proof.* By the theorem on combinations without repetition, for each $0\le k\le n$, $\binom{n}{k}$ is the number of $k$-element subsets of an $n$-element set $A$. Summing over all $k$ from $0$ to $n$ counts every subset of $A$ exactly once (each subset has some definite size between $0$ and $n$), so the sum equals the total number of subsets of $A$, which is $|\mathcal{P}(A)| = 2^n$ (Section "Sets"). $\blacksquare$

**4.** $\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0$.

*Proof.* Apply the Binomial theorem with $x=-1, y=1$: $(-1+1)^n = \sum_{k=0}^n \binom{n}{k}(-1)^k 1^{n-k} = \sum_{k=0}^n (-1)^k\binom{n}{k}$. Since $(-1+1)^n = 0^n = 0$ (for $n\ge 1$; for $n=0$ both sides equal $1$ trivially, consistent with the convention $0^0=1$), we get $\sum_{k=0}^n(-1)^k\binom{n}{k}=0$. $\blacksquare$

---

## 21. Handshaking theorem (slide 6)

**Theorem (Handshaking theorem).** Let $G=(\varphi,E,V)$ be a graph (where $\varphi$ assigns to each edge its endpoint(s), $E$ is the edge set and $V$ the vertex set), and for $v\in V$ let $d(v)$ denote the degree of $v$ (the number of edges incident to $v$, counting each loop twice). Then the sum of the degrees of all vertices of $G$ equals twice the number of edges:
$$\sum_{v\in V} d(v) = 2|E|.$$

*Proof (by induction on the number of edges).*
*Base step:* If $|E|=0$, there are no edges, so every vertex has degree $0$; both sides of the equality are $0$.
*Inductive step:* Suppose the statement holds whenever a graph has $n$ edges, for some $n\in\mathbb{N}$ (inductive hypothesis). Let $G$ be a graph with $n+1$ edges. Remove one edge $e$ from $G$ to obtain a graph $G'$ with $n$ edges; by the inductive hypothesis, $\sum_{v\in V} d_{G'}(v) = 2n$. Now add the edge $e$ back to $G'$ to recover $G$. Adding $e$ increases the degree-sum by exactly $2$: if $e$ joins two distinct vertices, each of their degrees increases by $1$ (total $+2$); if $e$ is a loop at a single vertex, that vertex's degree increases by $2$ (since a loop is counted twice in the degree). Either way, $\sum_{v\in V} d_G(v) = \sum_{v\in V} d_{G'}(v) + 2 = 2n+2 = 2(n+1) = 2|E|$. So the statement holds for $G$, completing the induction. $\blacksquare$

---

*End of answer key. Sections 6–9 should be double-checked against your actual relations/functions lecture slides if you can get hold of them, since that deck wasn't part of your uploaded project files.*