# Solutions Examples and Applications
# Solutions — Examples and Applications (Part 1)

*Worked answers to every example in the list. Specific sets/numbers can vary in the real exam, but the method stays the same. Where a question says "give an example", any correct example works — one valid choice is shown.*

---

## Logic

**Predicates** $\mathrm{M}(x)$: "$x$ is a mouse", $\mathrm{C}(x)$: "$x$ likes cheese".

- **"Every mouse likes cheese."**
$$\forall x\,\big(\mathrm{M}(x) \Rightarrow \mathrm{C}(x)\big)$$

- **"Some mice like cheese."**
$$\exists x\,\big(\mathrm{M}(x) \wedge \mathrm{C}(x)\big)$$

> Watch the connective: "every … " uses $\Rightarrow$, "some …" uses $\wedge$. Writing $\exists x(\mathrm{M}(x)\Rightarrow\mathrm{C}(x))$ would be wrong (it's true even if no mice exist).

---

## Sets

**Subset of $A=\{1,2,3,4,5\}$.** Any of these works, e.g.
$$\{1,3,5\} \subseteq A. \qquad (\text{also valid: } \varnothing,\ \{2\},\ A \text{ itself, …})$$

**Operations on $A=\{1,2,a\}$ and $B=\{a,b\}$.**

| Operation | Result |
|---|---|
| Union $A\cup B$ | $\{1,2,a,b\}$ |
| Intersection $A\cap B$ | $\{a\}$ |
| Difference $A\setminus B$ | $\{1,2\}$ |
| Difference $B\setminus A$ | $\{b\}$ |
| Symmetric difference $A\,\triangle\,B$ | $\{1,2,b\}$ |
| Cartesian product $A\times B$ | $\{(1,a),(1,b),(2,a),(2,b),(a,a),(a,b)\}$ |

**Complement.** $U=\{a,b,c,d,e,f,g,h\}$, $A=\{a,c,e\}$:
$$\overline{A} = U\setminus A = \{b,d,f,g,h\}.$$

**Power set of $A=\{0,2,4\}$** (all $2^3=8$ subsets):
$$\mathcal{P}(A)=\big\{\,\varnothing,\ \{0\},\ \{2\},\ \{4\},\ \{0,2\},\ \{0,4\},\ \{2,4\},\ \{0,2,4\}\,\big\}.$$

**Number of subsets of $A=\{a,b,c,d,e,f\}$.** A set with $n$ elements has $2^n$ subsets:
$$2^{6}=64.$$

---

## Relations

**Partition of $A=\{1,2,a,b,c,d,e,f,g,h\}$.** A partition splits $A$ into non‑empty, pairwise disjoint blocks whose union is $A$. One example:
$$\big\{\ \{1,2\},\ \{a,b,c\},\ \{d,e,f,g,h\}\ \big\}.$$

**Binary relation from $A=\{1,2,3,4,5\}$ to $B=\{a,c,d,e,f,g\}$.** Any subset of $A\times B$, e.g.
$$R=\{(1,a),(2,c),(3,e),(5,g)\}.$$

**Domain, range, inverse of** $R=\{(0,4),(1,3),(1,4),(3,1),(3,4),(5,2)\}$.

- **Domain** (first coordinates): $\operatorname{dom}R=\{0,1,3,5\}$
- **Range** (second coordinates): $\operatorname{rng}R=\{1,2,3,4\}$
- **Inverse** (reverse every pair): 
$$R^{-1}=\{(4,0),(3,1),(4,1),(1,3),(4,3),(2,5)\}.$$

**Restriction / image / inverse image.**
$R=\{(1,2),(1,4),(2,2),(2,4),(3,1),(5,2),(5,5)\}$, $A=\{1,4,5\}$.

- **Restriction $R|_A$** = pairs of $R$ whose **first** coordinate is in $A$:
$$R|_A=\{(1,2),(1,4),(5,2),(5,5)\}.$$
- **Image $R(A)$** = **second** coordinates of pairs whose first coordinate is in $A$:
$$R(A)=\{2,4,5\}.$$
- **Inverse image $R^{-1}(A)$** = **first** coordinates of pairs whose **second** coordinate is in $A$:
  pairs with second coord in $\{1,4,5\}$ are $(1,4),(3,1),(5,5)$, so
$$R^{-1}(A)=\{1,3,5\}.$$

**Extension / restriction of** $R=\{(1,3),(2,1),(3,1),(5,3)\}$.

- An **extension** $S\supseteq R$ (add at least one pair), e.g.
$$S=\{(1,3),(2,1),(3,1),(5,3),(4,4)\}.$$
- A **restriction** $S\subseteq R$ (drop at least one pair), e.g.
$$S=\{(1,3),(2,1)\}.$$

**Relations on $A=\{1,2,3,4,5\}$ with a given property.** (One example each.)

- **Reflexive** (contains every $(x,x)$):
$$R=\{(1,1),(2,2),(3,3),(4,4),(5,5)\}.$$
- **Irreflexive** (contains no $(x,x)$):
$$R=\{(1,2),(2,3)\}.$$
- **Symmetric** (if $(x,y)$ then $(y,x)$):
$$R=\{(1,2),(2,1),(3,3)\}.$$
- **Antisymmetric** (if $(x,y)$ and $(y,x)$ then $x=y$):
$$R=\{(1,2),(2,3),(1,1)\}.$$
- **Strictly antisymmetric** (if $(x,y)$ then never $(y,x)$ — so it must be irreflexive too):
$$R=\{(1,2),(1,3),(2,3)\}.$$
- **Transitive** (if $(x,y)$ and $(y,z)$ then $(x,z)$):
$$R=\{(1,2),(2,3),(1,3)\}.$$

> The empty relation $\varnothing$ satisfies irreflexive, symmetric, antisymmetric, strictly antisymmetric and transitive simultaneously — handy if you ever get stuck, though it's good to show a non‑trivial example.

**Equivalence relation** $\sim$ on a set $X$ (reflexive, symmetric, transitive). Example:
$$X=\mathbb{Z}, \qquad x\sim y \iff x-y \text{ is even (i.e. } x\equiv y \bmod 2).$$
*(Finite alternative: $X=\{1,2,3\}$, $\sim\,=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$.)*

**Partial order** $\preceq$ on a set $X$ (reflexive, antisymmetric, transitive). Example:
$$X=\mathbb{R}, \qquad x\preceq y \iff x\le y.$$
*(Or: $X=\mathcal{P}(S)$ for any set $S$, with $\preceq\,=\,\subseteq$.)*

**Function from $A=\{1,2,3,4\}$ to $B=\{a,b,c,d,e,f\}$** (each element of $A$ assigned exactly one value). Example:
$$f=\{(1,a),(2,b),(3,c),(4,d)\}.$$

**Injective / surjective / bijective**, $A=\{1,2,3,4\}$, $B=\{a,b,c,d\}$.

- **Injective** (distinct inputs → distinct outputs):
$$f=\{(1,a),(2,b),(3,c),(4,d)\}.$$
- **Surjective** (every element of $B$ is hit). Since $|A|=|B|=4$, the same map works:
$$f=\{(1,a),(2,b),(3,c),(4,d)\}.$$
- **Bijective** (both injective and surjective):
$$f=\{(1,a),(2,b),(3,c),(4,d)\}.$$

> Because $|A|=|B|$, the simplest injection is already a bijection. If $|B|>|A|$ no surjection exists; if $|B|<|A|$ no injection exists.

**Composition** $R\circ S$, where $R=\{(1,2),(1,4),(2,3),(2,4)\}$, $S=\{(1,2),(1,3),(4,1)\}$.

Convention: $(x,z)\in R\circ S \iff \exists y:\ (x,y)\in S \ \wedge\ (y,z)\in R$ — **apply $S$ first, then $R$.**

- $(1,2)\in S$ and $(2,3),(2,4)\in R \Rightarrow (1,3),(1,4)$
- $(1,3)\in S$, but no pair $(3,\cdot)\in R \Rightarrow$ nothing
- $(4,1)\in S$ and $(1,2),(1,4)\in R \Rightarrow (4,2),(4,4)$

$$\boxed{R\circ S=\{(1,3),(1,4),(4,2),(4,4)\}}$$

---

## Complex numbers

**$z=-3-5i$, $w=-1+4i$.**

- $z+w=(-3-1)+(-5+4)i = -4 - i$
- $zw=(-3-5i)(-1+4i)= 3 -12i +5i -20i^2 = 3 -7i +20 = 23 - 7i$

**$z=2-5i$.**

- $|z|=\sqrt{2^2+(-5)^2}=\sqrt{4+25}=\sqrt{29}$
- $\overline{z}=2+5i$

**$z=3(\cos 30^\circ+i\sin 30^\circ)$, $w=5(\cos 12^\circ+i\sin 12^\circ)$.**

Multiply moduli, add arguments; divide moduli, subtract arguments:

- $zw = 3\cdot 5\,\big(\cos(30^\circ+12^\circ)+i\sin(30^\circ+12^\circ)\big)= 15(\cos 42^\circ+i\sin 42^\circ)$
- $\dfrac{z}{w} = \dfrac{3}{5}\,\big(\cos(30^\circ-12^\circ)+i\sin(30^\circ-12^\circ)\big)= \tfrac{3}{5}(\cos 18^\circ+i\sin 18^\circ)$

**$z=2(\cos 15^\circ+i\sin 15^\circ)$.**

- **Power (De Moivre):** $z^4 = 2^4\big(\cos(4\cdot 15^\circ)+i\sin(4\cdot 15^\circ)\big)= 16(\cos 60^\circ+i\sin 60^\circ)$

- **Cube roots:** $\sqrt[3]{z}=\sqrt[3]{2}\left(\cos\dfrac{15^\circ+360^\circ k}{3}+i\sin\dfrac{15^\circ+360^\circ k}{3}\right)$, $k=0,1,2$:

| $k$ | argument | root |
|---|---|---|
| $0$ | $5^\circ$ | $\sqrt[3]{2}(\cos 5^\circ+i\sin 5^\circ)$ |
| $1$ | $125^\circ$ | $\sqrt[3]{2}(\cos 125^\circ+i\sin 125^\circ)$ |
| $2$ | $245^\circ$ | $\sqrt[3]{2}(\cos 245^\circ+i\sin 245^\circ)$ |

---

## Combinatorics

**First four rows of Pascal's triangle** (rows $0$–$3$):

```
        1
      1   1
    1   2   1
  1   3   3   1
```

**Counts for $A=\{1,2,\ldots,10\}$, $n=10$** (factorials may be left un‑evaluated):

| Type | Formula | Value |
|---|---|---|
| Permutations without repetition | $n!$ | $10!$ |
| $4$‑variations without repetition | $\dfrac{n!}{(n-4)!}=\dfrac{10!}{6!}$ | $10\cdot 9\cdot 8\cdot 7$ |
| $4$‑variations with repetition | $n^4$ | $10^4$ |
| $4$‑combinations without repetition | $\dbinom{n}{4}=\dfrac{10!}{4!\,6!}$ | $210$ |
| $4$‑combinations with repetition | $\dbinom{n+4-1}{4}=\dbinom{13}{4}$ | $715$ |

**Permutations with repetition**, repetition numbers $k_1=2,\ k_2=1,\ k_3=4,\ k_4=4$ (total $n=2+1+4+4=11$):
$$\frac{11!}{2!\,\cdot 1!\,\cdot 4!\,\cdot 4!}.$$

**Binomial expansion of $(x+y)^5$** (coefficients are row 5: $1,5,10,10,5,1$):
$$(x+y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5.$$

**Inclusion–exclusion principle for four sets:**
$$
\begin{aligned}
|A\cup B\cup C\cup D| =\ & |A|+|B|+|C|+|D| \\
 &-\big(|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|\big)\\
 &+\big(|A\cap B\cap C|+|A\cap B\cap D|+|A\cap C\cap D|+|B\cap C\cap D|\big)\\
 &-|A\cap B\cap C\cap D|.
\end{aligned}
$$

---

## Graphs

**Edge count from degrees.** A $5$‑vertex graph $G$ with degrees $7,7,6,3,3$.

By the **handshake lemma**, the sum of all vertex degrees equals twice the number of edges:
$$\sum_{v}\deg(v) = 2|E|.$$
$$7+7+6+3+3 = 26 \quad\Rightarrow\quad |E| = \frac{26}{2} = 13.$$

> Note: a *simple* graph on $5$ vertices can have max degree $4$, so degree $7$ means $G$ has multiple edges and/or loops (a multigraph). The handshake lemma still applies regardless.

---

*End of answer key.*