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(\mathrm{M}(x)\Rightarrow \mathrm{C}(x))$

• “Some mice like cheese.” $\exists x(\mathrm{M}(x)\wedge \mathrm{C}(x))$

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.(\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△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)=\{\varnothing ,\{0\},\{2\},\{4\},\{0,2\},\{0,4\},\{2,4\},\{0,2,4\}\}.$

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: $\{\{1,2\},\{a,b,c\},\{d,e,f,g,h\}\}.$

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): $\mathrm{dom}R=\{0,1,3,5\}$
• Range (second coordinates): $\mathrm{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},x\sim y⟺x-y\text{ is even (i.e. }x\equiv y\mathrm{mod}2).$ (Finite alternative: $X=\{1,2,3\}$, $\sim =\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$.)

Partial order $⪯$ on a set $X$ (reflexive, antisymmetric, transitive). Example: $X=\mathbb{R},x⪯y⟺x\le y.$ (Or: $X=\mathcal{P}(S)$ for any set $S$, with $⪯=\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⟺\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(\cos (30^{\circ }+12^{\circ })+i\sin (30^{\circ }+12^{\circ }))=15(\cos 42^{\circ }+i\sin 42^{\circ })$
• $\frac{z}{w}=\frac{3}{5}(\cos (30^{\circ }-12^{\circ })+i\sin (30^{\circ }-12^{\circ }))=\frac{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(\cos (4\cdot 15^{\circ })+i\sin (4\cdot 15^{\circ }))=16(\cos 60^{\circ }+i\sin 60^{\circ })$

• Cube roots: $\sqrt[3]{z}=\sqrt[3]{2}\left(\cos \frac{15^{\circ }+360^{\circ }k}{3}+i\sin \frac{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,\dots ,10\}$, $n=10$ (factorials may be left un‑evaluated):

Type	Formula	Value
Permutations without repetition	$n!$	$10!$
$4$‑variations without repetition	$\frac{n!}{(n-4)!}=\frac{10!}{6!}$	$10\cdot 9\cdot 8\cdot 7$
$4$‑variations with repetition	$n^4$	$10^4$
$4$‑combinations without repetition	$\left(\genfrac{}{}{0ex}{}{n}{4}\right)=\frac{10!}{4!6!}$	$210$
$4$‑combinations with repetition	$\left(\genfrac{}{}{0ex}{}{n+4-1}{4}\right)=\left(\genfrac{}{}{0ex}{}{13}{4}\right)$	$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^{4}y+10x^3{y}^2+10x^2{y}^3+5x{y}^4+y^5.$

Inclusion–exclusion principle for four sets:

$$\begin{array}{rl}|A\cup B\cup C\cup D|=& |A|+|B|+|C|+|D|\\ & -(|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|)\\ & +(|A\cap B\cap C|+|A\cap B\cap D|+|A\cap C\cap D|+|B\cap C\cap D|)\\ & -|A\cap B\cap C\cap D|.\end{array}$$

---

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\mathrm{deg}(v)=2|E|.$ $7+7+6+3+3=26\Rightarrow |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.