1) **Setup:** - $S = \{\text{Amy}, \text{Bill}, \text{Clara}, \text{Dan}\}$ (students) - $X = \{\text{CS118}, \text{CS130}, \text{CS133}\}$ (exams) - $E(s, t, x)$ = "students $s$ and $t$ are taking exam $x$" **(a)** Every exam that Amy is taking, Bill is also taking >[!hint]- Hint 1 >Leveraging the question's hint, since a student taking an exam is taking it "with themselves," we interpret "$s$ is taking exam $x$" as $E(s, s, x)$. >[!hint]- Hint 2 >To say "Amy is taking it means Bill also takes it", consider that "x occurs means y occurs" can be written as $x \rightarrow y$. > [!check]- Solution > $\forall x \in X \;\bigl(E(\text{Amy}, \text{Amy}, x) \rightarrow E(\text{Bill}, \text{Bill}, x)\bigr)$ > > Leveraging the hint that $s,t$ need not be distinct, we can just set $s$ and $t$ to be the same for saying some student $s$ is taking exam $x$ resulting in $E(s, s, x)$. **(b)** Clara is not taking an exam with anyone else >[!hint]- Hint > Think about how antisymmetry is commonly expressed ($\forall x,y \; (xRy \land yRx) \rightarrow x=y$). > > Can we use this structure of $condition \rightarrow x=y$ to say that any student taking an exam with her must be Clara herself? > [!check]- Solution > $\forall s \in S \;\forall x \in X \;\bigl(E(\text{Clara}, s, x) \rightarrow s = \text{Clara}\bigr)$ > > That is (for all people, for all exams), if Clara shares any exam with some student $s$, then $s$ must be Clara herself. **(c)** Every exam is being taken by at least one student >[!hint]- Hint > How can we use the existential quantifier ($\exists$) here? > [!check]- Solution > $\forall x \in X \;\exists s \in S \; E(s, s, x)$ **(d)** If an exam is being taken by at least 3 students, then it is being taken by everyone >[!hint]- Hint 1 > We can use existential quantifiers (with 3 variables) to state there are 3 students who take an exam. > - How can we make sure these 3 students are distinct (the variables aren't the same)? > - How can we make sure each student takes the exam? >[!hint]- Hint 2 > If-then statements can be expressed by implication. So if $x$ then $y$ can be expressed as $x \rightarrow y$. > [!check]- Solution > $\forall x \in X \;\Bigl(\bigl(\exists s_1, s_2, s_3 \in S \;(s_1 \neq s_2 \wedge s_1 \neq s_3 \wedge s_2 \neq s_3 \wedge E(s_1, s_1, x) \wedge E(s_2, s_2, x) \wedge E(s_3, s_3, x))\bigr) \rightarrow \forall s \in S \; E(s, s, x)\Bigr)$ **(e)** The relation $R$ (where $aRb$ iff $a$ and $b$ take an exam together) is transitive >[!hint]- Hint 1 > You don't have to prove this. You just have to provide the sentence. > Transitivity is defined by: $\forall a,b,c. \; (aRb \land bRc) \rightarrow aRc$ >[!hint]- Hint 2 > You can say $a$ and $b$ are taking an exam together with the expression: > $\exists x \in X. \; E(a, b, x)$. > [!check]- Solution > $\forall a \in S \;\forall b \in S \;\forall c \in S \;\Bigl(\bigl(\exists x \in X \; E(a, b, x)\bigr) \wedge \bigl(\exists y \in X \; E(b, c, y)\bigr) \rightarrow \bigl(\exists z \in X \; E(a, c, z)\bigr)\Bigr)$ --- 2) **(a)** Three distinct formula s.t. any two $a, b$ have $a \lor b$ as a tautology. Recall that a tautology is a formula where the values of each variable does not matter - it is always true, for any assignment of $T/F$ values to the variables. >[!hint]- Hint 1 > Is there a symbol that, when combined with any other formula in an $\lor$, forms a tautology? >[!hint]- Hint 2 > Hint 1 leads to one of the formula. Can you form a tautology using a single variable, to find the other two formula? >[!check]- Solution > $P, \neg P, T$: this works because $P$ and $\neg P$ form a tautology together. And $T$ with literally anything else (so $P, \neg P$) forms a tautology. **(b)** Consider a graph where every integer is a node. The nodes are connected if the absolute difference between the numbers is prime. Is the graph connected? Recall that connected means the graph consists of a single connected component i.e. there is a path from any node to any other node. >[!hint]- Hint 1 > Sometimes in problem solving, you should zoom in on a key detail or key value. > > The absolute difference being prime is interesting, but there are so many primes! > Is there a specific prime number that helps you form large connected components? >[!hint]- Hint 2 > Using Hint 1, there is a way to show the odd numbers form a connected component. > Similarly, the even numbers form a connected component. > > Show this and also consider: > if the odds and evens form a connected component, is there a way to connected these two components? >[!check]- Solution > Each odd number $x$ is connected to the next odd number ($x+2$) and previous odd number ($x-2$), since their difference is $2$ (a prime). So the odd numbers form a big chain and are one connected component. > > Same argument for the even numbers. > > We have two connected components: the odds and the evens. If we show a single connection between any odd number and any even number, then we show that all numbers are connected. We can show $1$ (an odd) and $4$ (an even) are connected since their difference $3$ is a prime. Hence, the entire graph is connected. **(c)** Draw the Hasse diagram for the partial order $(\{2, 3, 4, 5, 8, 12, 24, 25\}, |)$. Also give the minimal and maximal elements. Recall that a Hasse diagram shows the elements as nodes, and has edges between elements $a, b$ if $aRb$ or $bRa$. You should draw $aRb$ with $b$ above $a$. Relations between an element $a$ and itself (so $aRa$) are not drawn. Transitive relations are also not drawn i.e. if $aRb$ and $bRc$ then $aRc$ but don't draw $aRc$ - only draw $aRb$ and $bRc$. >[!hint]- Hint 1 > Start with the smallest numbers - which divide into which? You can notice $2$ divides into $4$ - what smallish numbers does $4$ then divide into? Go from small to big. >[!check]- Solution > ![Hasse Diagram](/Resources/Images/HasseDiagram-2024q.png) > An easy mistake to make here is to confuse *greatest/maximum* with *maximal*. > An element $x$ is maximal if the only thing it relates to is itself. > Similarly, an element $y$ is minimal if the only thing that relates to it is itself. > > As such, the maximal elements: $24, 25$. > The minimal elements: $2, 3, 5$. **(d)** Prove for $n \geq 1$, that $2^{n} + 3^{n} - 5^{n}$ is divisible by $6$. >[!hint]- Hint 1 > For questions like this, there is a very clear structure to follow: > 1) Find the base case > 2) State the inductive hypothesis (IH), which is what you assume to be true i.e. we might assume $2^{k} + 3^{k} - 5^{k}$ is divisible by $6$ > 3) Use IH to prove that it is also true for the next integer i.e. prove that $2^{k+1} + 3^{k+1} - 5^{k+1}$ is also divisible by $6$, given our IH >[!hint]- Hint 2 > Is there a way you can find some multiple of the IH inside your inductive step expression? Make sure the coefficients of your new expression add up to the same values as your original expression! >[!hint]- Hint 3 > Is there a way to prove that $3^k - 3(5^k)$ is divisible by $6$? >[!hint]- Hint 4 > Is there a way to prove that $3(3^{k-1} - 5^k)$ is even i.e. divisible by $2$? >[!check]- Solution >**Claim:** For all natural numbers $n \geq 1$, $6 \mid 2^n + 3^n - 5^n$. > >**Base Cases ($n = 1$):** $2^1 + 3^1 - 5^1 = 2 + 3 - 5 = 0$. > >Since $0 = 6 \times 0$, we have $6 \mid 0$. > >**Inductive Hypothesis (IH):** Assume that for some $k \geq 2$: $6 \mid 2^k + 3^k - 5^k$. > >**Inductive Step:** We must show: $6 \mid 2^{k+1} + 3^{k+1} - 5^{k+1}$. > > Write the $k+1$ expression in terms of the $k$ expression: > >$2^{k+1} + 3^{k+1} - 5^{k+1} = 2 \cdot 2^k + 3 \cdot 3^k - 5 \cdot 5^k$. > > Now, let's take the smallest coefficient ($2$), and factor out that many IHs out. > So let's factor out $2$ IH. > > $2 \cdot 2^k + 3 \cdot 3^k - 5 \cdot 5^k = 2(2^k + 3^k - 5^k) + 1 \cdot 3^k - 3 \cdot 5^k$ > >$= 2 \cdot 2^k + 3 \cdot 3^k - 5 \cdot 5^k$ > >$= 2(2^k + 3^k - 5^k) + 3^k - 3 \cdot 5^k$ > > So we know the IH part is divisible by $6$, what about $3^k - 3 \cdot 5^k$? > > $3^k - 3 \cdot 5^k = 3(3^{k-1} - 5^k)$. > > We know $3^{k-1} - 5^k$ is even (so is divisible by $2$) since for any $n \geq 0$, $3^{n}$ is odd and $5^n$ is odd. And an odd minus an odd will always be even (more formally, we can express odd numbers in the form $2x+1$ and $(2a+1) - (2b+1) = 2a + 1 - 2b - 1 = 2a - 2b = 2(a - b)$ which is even). > > Hence, $3(3^{k-1} - 5^k)$ is divisible by $6$. > > We are allowed to have $3^{k-1}$ since $k \geq 1$, so in our most extreme case $k=1$, we have $3^0=1$ which is odd. > > We have just shown $6 \mid 3(3^{k-1} - 5^k)$ and we know $6 \mid 2(2^k + 3^k - 5^k)$ due to the IH. Hence, $6 \mid 2(2^k + 3^k - 5^k) + 3^k - 3 \cdot 5^k$ and therefore $6 \mid 2^{k+1} + 3^{k+1} - 5^{k+1}$. > > We have proven that it is true for $n=1$ and that if it is true for $n=k$ (with $k \geq 1$), then it is true for $n=k+1$. Hence, by induction, we have $6 \mid 2^n + 3^n - 5^n$ for all natural numbers $n \geq 1$. **(e)** $W$ is all English words. We have a relation $R$ where two words $a,b$ relate only iff $a$ and $b$ have at least one common letter. Is $R$ an equivalence relation? >[!hint]- Hint 1 > An equivalence relation is a relation where it is **reflexive**, **symmetric**, and **transitive**. > > Does $R$ satisfy each of these properties? >[!hint]- Hint 2 > There are counterexamples for $R$ being transitive. Can you think of a case where one word $w_1$ relates to another word $w_2$ which relates to another word $w_3$, but $w_1$ does not relate $w_3$? >[!check]- Solution > Let's go through the properties. > > $R$ is reflexive since every word shares at least one common letter with itself. > $R$ is symmetric since for any two words $w_1, w_2$, we have that if $w_1$ has a letter in common with $w_2$ then of course $w_2$ has a letter in common with $w_1$. > > However, $R$ is not transitive: a word $w_1$ could have some letters in common with $w_2$ and $w_2$ could have *different* letters in common with $w_3$ and so $w_1$ may not have any in common with $w_3$. > > We can see this in the counterexample $w_1=wet$, $w_2=bat$, and $w_3=bar$. We see $w_1$ and $w_2$ have "t" in common, $w_2$ and $w_3$ have "ba" in common, but $w_1$ has nothing in common with $w_3$. **(f)** $A = \{2, 3, 4, 6\}$ and $R$ operates on $A^{2}$. We have for $(a, b), (c, d) \in A^2$ that $(a,b)R(c,d)$ iff $ad = bc$. Give equivalence classes of $(3,3)$ and $(2, 4)$. >[!hint]- Hint 1 > The equivalence class of some element $x$ is everything $x$ relates to (and, because it's an equivalence relation, everything that relates to $x$). > > So for checking what some $x$ could possibly relate to, we are finding $y$ in $xRy$. If our $x$ can be expressed as $(a,b)$, then we are trying to find $y$ (which can be expressed as $(c,d)$) such that $(a,b)Ry = (a,b)R(c,d)$ and $ad = bc$. > > Now substitute $(a,b)$ for the values you're given in the question. >[!check]- Solution > The equivalence class of some element $x$ is everything $x$ relates to (and, because it's an equivalence relation, everything that relates to $x$). > > $(3,3)R(x,y)$ iff $3y = 3x$ so $y=x$. Hence, equivalence class of $(3,3)$ is: $\{(2,2), (3,3), (4,4), (6,6)\}$. > > $(2,4)R(x,y)$ iff $2y = 4x$ so $y = 2x$. Hence, equivalence class of $(2,4)$ is: $\{(2,4), (3,6)\}$. --- 3) Recall that $P(S)$ denotes the power set of a set $S$. **(a)** For all sets $A$ and $B$, compute $|P(A \times B) \cap (P(A) \times P(B))|$. >[!hint]- Hint 1 > What *kind* of object is an element of $P(A \times B)$? What *kind* of object is an element of $P(A) \times P(B)$? Are they the same kind of thing? >[!hint]- Hint 2 > Every element of $P(A \times B)$ is a *set of ordered pairs*. > > Every element of $P(A) \times P(B)$ is a *single ordered pair* $(X, Y)$ where $X \subseteq A$ and $Y \subseteq B$. So every element is a *pair of subsets*. > > So one is "a set of pairs" and the other is "a pair of sets". Can any object be both at once? > [!check]- Solution > $|P(A \times B) \cap (P(A) \times P(B))| = 0$, the intersection is the empty set. > > The two sides contain *different kinds of object*: > - An element of $P(A \times B)$ is a *set of ordered pairs* (a subset of $A \times B$). Even the empty set $\emptyset$ qualifies, it's a (vacuous) set of pairs. > - An element of $P(A) \times P(B)$ is itself a *single ordered pair* $(X, Y)$ with $X \subseteq A$ and $Y \subseteq B$. > > A "set of pairs from $A \times B$" is not the same kind of object as "a single pair of subsets of $A$ and $B$", so no element can lie in both. The intersection is therefore $\emptyset$, and its cardinality is $0$. **(b)** Given a bijection $f: A \to B$, construct a bijection $g: P(A) \to P(B)$. >[!hint]- Hint 1 > You're given a function on elements ($f: A \to B$) and asked for a function on subsets ($g: P(A) \to P(B)$). Is there a way to look into a subset $X$ passed into $g$, and convert each element in $X$ to an element in $B$? >[!hint]- Hint 2 > Try $g(X) = \{f(x) : x \in X\}$, that is, $g$ sends a subset of $A$ to the image of that subset under $f$. > > Then check $g$ is a bijection by proving injectivity and surjectivity (by leaning on the fact that $f$ is a bijection). > [!check]- Solution > Define $g: P(A) \to P(B)$ by > $g(X) = \{f(x) : x \in X\}$. > > **Injective:** suppose $g(X) = g(Y)$. For any $x \in X$, $f(x) \in g(X) = g(Y)$, so $f(x) = f(y)$ for some $y \in Y$. Since $f$ is injective, $x = y \in Y$. Hence $X \subseteq Y$, and by symmetry $Y \subseteq X$, giving $X = Y$. > > **Surjective:** let $T \subseteq B$. Set $X = \{f^{-1}(t) : t \in T\}$, which is well-defined because $f$ is bijective (so $f^{-1}$ exists). Then > $g(X) = \{f(f^{-1}(t)) : t \in T\} = T$. > > So $g$ is both injective and surjective, hence a bijection. **(c)** Let $A$ be a nonempty finite set. Prove that the set of subsets of $A$ with even cardinality and the set of subsets of $A$ with odd cardinality are equinumerous. >[!hint]- Hint 1 > "Equinumerous" means there is a bijection between the two sets. So your job is to construct a bijection between even-cardinality subsets and odd-cardinality subsets. >[!hint]- Hint 2 > $A$ is nonempty, that's the only fact you need. Pick any fixed element $a \in A$. Now think about how toggling whether $a$ is in a subset affects the subset's parity. >[!hint]- Hint 3 > For any subset $X$, "toggle $a$" means: remove $a$ from $X$ if it's there, otherwise add it. Either way, $|X|$ changes by exactly $1$, so the parity flips. > > Why is this map a bijection? > [!check]- Solution > Since $A$ is nonempty, fix any $a \in A$. Let $E = \{X \subseteq A : |X| \text{ is even}\}$ and $O = \{X \subseteq A : |X| \text{ is odd}\}$. > > Define $h: E \to O$ by $h(X) = X \triangle \{a\}$ (symmetric difference with $\{a\}$). Concretely: $h(X) = X \setminus \{a\}$ if $a \in X$, and $h(X) = X \cup \{a\}$ if $a \notin X$. > > In either case $|h(X)| = |X| \pm 1$, so $h$ flips parity. Hence $h$ does map $E$ into $O$. > > The same rule defines a map $O \to E$, and these are inverses of each other: $h(h(X)) = (X \triangle \{a\}) \triangle \{a\} = X$. So $h$ is a bijection between $E$ and $O$. > > Therefore $|E| = |O|$, i.e., the even-cardinality subsets of $A$ and the odd-cardinality subsets of $A$ are equinumerous. --- 4) Call a partial order $(S, \leq)$ **spiky** if it has at least two maximal elements and at least two minimal elements. **(a)** Give a spiky partial order $(S, \leq)$ such that $\leq$ is a function, or prove that none exists. >[!hint]- Hint 1 > Recall the definition of a function: $f : S \to S$ assigns to *every* $s \in S$ exactly one image $f(s) \in S$. Viewing $\leq$ as a relation on $S$ (i.e. a subset of $S \times S$), "$\leq$ is a function" means that for every $s \in S$ there is exactly one pair $(s, t) \in \;\leq$ with first coordinate $s$. >[!hint]- Hint 2 > Be careful with the terminology: an element $x$ is *maximal* iff there is no $y \neq x$ with $x \leq y$, it does *not* have to be a *maximum* (an element above everything else). Similarly, "minimal" is not the same as "minimum". A partial order can have many maximal and many minimal elements at the same time. >[!hint]- Hint 3 > A partial order is reflexive, so $x \leq x$ for every $x$. Nothing forces $x$ to relate to any element other than itself though. What if $x$ relates *only* to itself, for every $x$? > [!check]- Solution > Take any set $S$ with $|S| \geq 2$ together with the *identity function* $f(x) = x$, that is, the equality relation $\leq \;=\; \{(x, x) : x \in S\}$. For example, $S = \{a, b, c, d\}$ with $\leq \;=\; \{(a,a), (b,b), (c,c), (d,d)\}$. > > Equality is reflexive, antisymmetric and transitive (vacuously where needed), so this is a partial order. > > Each element relates only to itself, so every element is *both* maximal and minimal. With $|S| \geq 2$ we get at least two maximal elements and at least two minimal elements, spiky. > > And $\leq$ is indeed a function: each $s \in S$ appears as the first coordinate of exactly one pair $(s, s)$. **(b)** Give a spiky partial order $(S, \leq)$ that is a total order, or prove that none exists. >[!hint]- Hint 1 > A *total* order is a partial order with the extra property that any two elements are comparable: for all $x, y \in S$, either $x \leq y$ or $y \leq x$. >[!hint]- Hint 2 > Suppose $x$ and $y$ are *both* maximal in a total order. Totality gives you a comparison between them; what does maximality then force? > [!check]- Solution > No such spiky total order exists. > > Suppose $(S, \leq)$ is a total order with two maximal elements $x, y$. By totality, $x \leq y$ or $y \leq x$. > - If $x \leq y$ and $x \neq y$, then $y$ sits strictly above $x$, contradicting $x$ being maximal. > - Symmetrically, $y \leq x$ with $x \neq y$ contradicts $y$ being maximal. > > So $x = y$. Hence a total order has *at most one* maximal element, and (by the same argument) at most one minimal element. Spikiness demands at least two of each, so no total order can be spiky. **(c)** For any spiky partial order $(S, \leq)$, what is the minimum cardinality of $S$? And what is the minimum cardinality of $\leq$? >[!hint]- Hint 1 > An element can be both maximal *and* minimal at the same time, it just has to be unrelated (above or below) to anything other than itself. So the same elements can pull double duty as your two maximals *and* your two minimals. >[!hint]- Hint 2 > Reflexivity forces $(s, s)$ to be in $\leq$ for every $s \in S$. So $|\leq| \geq |S|$ automatically. Once you fix the smallest possible $|S|$, ask whether you can avoid adding any *extra* pairs beyond those reflexive ones. > [!check]- Solution > The minimum cardinality of $S$ is $2$, and the minimum cardinality of $\leq$ is also $2$. > > Take $S = \{a, b\}$ with $\leq \;=\; \{(a, a), (b, b)\}$ (the equality relation / identity function). > > - This is a partial order (equality always is). > - Both $a$ and $b$ are maximal (nothing strictly above either) and both are minimal (nothing strictly below either). That's two maximals and two minimals, spiky. > > **Why $|S| = 2$ is minimal:** spiky requires at least two distinct maximal elements, which already forces $|S| \geq 2$. The construction above shows $2$ is achievable. > > **Why $|\leq| = 2$ is minimal:** reflexivity forces $(a, a)$ and $(b, b)$ to be in $\leq$, so $|\leq| \geq 2$ for any partial order with $|S| = 2$. The construction achieves exactly $2$, so $2$ is tight. --- 5) **(a)** Consider a function $f : A \to \mathbb{Z}$ and define the relation $R_f \subseteq A \times A$ by $(x, y) \in R_f$ iff $f(x) = f(y)$. Prove that $R_f$ is an equivalence relation. >[!hint]- Hint > An equivalence relation has three properties: it is **reflexive**, **symmetric**, and **transitive**. Run through each one in turn, for $R_f$, each property reduces to a basic fact about equality. > [!check]- Solution > We check the three properties. > > **Reflexive:** for any $x \in A$, $f(x) = f(x)$, so $(x, x) \in R_f$. > > **Symmetric:** suppose $(x, y) \in R_f$, so $f(x) = f(y)$. Then $f(y) = f(x)$ by symmetry of equality, so $(y, x) \in R_f$. > > **Transitive:** suppose $(x, y) \in R_f$ and $(y, z) \in R_f$, so $f(x) = f(y)$ and $f(y) = f(z)$. By transitivity of equality, $f(x) = f(z)$, so $(x, z) \in R_f$. > > Hence $R_f$ is an equivalence relation. **(b)** Consider the function $f = \{(2, 4), (6, 1), (3, 5), (4, 1), (1, 4)\}$. What are its domain and co-domain? Find all equivalence classes of $R_f$ defined in part (a). >[!hint]- Hint 1 > The **domain** of a function given as a set of pairs is the set of *first* coordinates. The **codomain** is the "target" set $B$ in $f : A \to B$, for a function specified only as pairs, the most natural choice is the set of *second* coordinates that actually appear (i.e. the image). >[!hint]- Hint 2 > Two elements $x, y$ are in the same equivalence class of $R_f$ iff $f(x) = f(y)$. So group elements of the domain by which output they share. > [!check]- Solution > Reading off the pairs: > > | $x$ | $f(x)$ | > | --- | --- | > | 1 | 4 | > | 2 | 4 | > | 3 | 5 | > | 4 | 1 | > | 6 | 1 | > > **Domain:** $\{1, 2, 3, 4, 6\}$. > > **Codomain:** $\{1, 4, 5\}$. (No codomain was declared, so we take the smallest set that makes $f$ a well-defined function, namely the image.) > > **Equivalence classes:** group inputs by their image under $f$. > - $f(1) = f(2) = 4$, so $[1] = [2] = \{1, 2\}$. > - $f(3) = 5$, so $[3] = \{3\}$. > - $f(4) = f(6) = 1$, so $[4] = [6] = \{4, 6\}$. > > The three equivalence classes are $\{1, 2\}, \{3\}, \{4, 6\}$. **(c)** Prove that for every function $f : A \to \mathbb{Z}$, there is a set $M$ and functions $s : A \to M$ and $i : M \to \mathbb{Z}$ such that $s$ is surjective, $i$ is injective, and $f(a) = i(s(a))$ for every $a \in A$. >[!hint]- Hint 1 > Try $M = A$ first. The obvious choice for $s$ is the identity on $A$, which is surjective. What does $i$ have to be? Is $i$ always injective? >[!hint]- Hint 2 > Hint 1 fails when $f$ isn't injective: with $s = \text{id}_A$ we'd be forced to take $i = f$, which only works when $f$ itself is injective. > > So $M = A$ is "too big". Try shrinking $M$ to make $i$ injective by construction. >[!hint]- Hint 3 > Try $M = f(A)$ (the image of $f$). What's the natural choice of $s$ and $i$ in that case? > [!check]- Solution > Take $M = f(A) = \{f(a) : a \in A\}$, the image of $f$ inside $\mathbb{Z}$. Define > - $s : A \to M$ by $s(a) = f(a)$, > - $i : M \to \mathbb{Z}$ by $i(m) = m$ (the inclusion map). > > **$s$ is surjective:** every element of $M$ is of the form $f(a)$ for some $a \in A$ by the definition of $M$, and $s(a) = f(a)$, so $s$ hits every element of $M$. > > **$i$ is injective:** $i$ is just the inclusion of $M \subseteq \mathbb{Z}$ into $\mathbb{Z}$, if $i(m) = i(m')$ then $m = m'$ trivially. > > **The composition reproduces $f$:** for any $a \in A$, $i(s(a)) = i(f(a)) = f(a)$, so $f(a) = i(s(a))$ for every $a \in A$ as required. --- 6) **(a)** Draw three non-isomorphic trees, each with 5 vertices. >[!hint]- Hint 1 > Two trees are *isomorphic* if you can relabel the vertices of one to get the other while preserving the edges. So "non-isomorphic" means the trees have genuinely different shapes, not just different labellings of the same shape. >[!hint]- Hint 2 > A tree on $n$ vertices has $n - 1$ edges, so each of yours has 4 edges. Trying to come up with three different *degree sequences* is a fast way to ensure the trees aren't isomorphic to each other. > [!check]- Solution > ![Three non-isomorphic trees on 5 vertices](/Resources/Images/Trees5-2024q.png) > > The three trees, with their (sorted) degree sequences: > 1) The **path** $P_5$, degree sequence $(1, 2, 2, 2, 1)$. > 2) The **"Y" / broom** (a path of $4$ with an extra leaf attached to the second vertex), degree sequence $(3, 2, 1, 1, 1)$. > 3) The **star** $K_{1,4}$ (one centre joined to four leaves), degree sequence $(4, 1, 1, 1, 1)$. > > The three degree sequences are distinct, so the trees can't be isomorphic to each other. **(b)** Prove that every tree with 5 vertices is isomorphic to one of the three trees that you have given in part (a). >[!hint]- Hint 1 > A tree on $n$ vertices has $n - 1$ edges. So a tree on 5 vertices has exactly 4 edges, and the degree sum is $\sum_v \deg(v) = 2 \cdot 4 = 8$. >[!hint]- Hint 2 > Do a case analysis on the **maximum degree** $\Delta$ of the tree. With only 5 vertices, $\Delta \leq 4$. Argue that $\Delta \geq 2$ (else the degree sum is too small), so $\Delta \in \{2, 3, 4\}$. >[!hint]- Hint 3 > For each case, show the shape is forced: > - $\Delta = 4$: one vertex must be adjacent to all four others. > - $\Delta = 3$: there is a degree-$3$ vertex with $3$ neighbours; the remaining vertex must hang off one of those neighbours (since the tree is connected). > - $\Delta = 2$: every vertex has degree at most $2$, so the tree is a path. > [!check]- Solution > Let $T$ be a tree on 5 vertices. $T$ has $5 - 1 = 4$ edges, so the degree sum is $\sum_v \deg(v) = 2 \cdot 4 = 8$. Every vertex has degree $\geq 1$ ($T$ is connected with $\geq 2$ vertices) and degree $\leq 4$ (only four other vertices to be adjacent to). Let $\Delta$ be the maximum degree. > > If every vertex had degree $1$, the sum would be $5 < 8$, so $\Delta \geq 2$. Hence $\Delta \in \{2, 3, 4\}$. > > **Case $\Delta = 4$.** Some vertex $v$ has degree $4$, so $v$ is adjacent to *all* four other vertices. That accounts for all $4$ edges, so no other edges exist. $T$ is the star $K_{1,4}$. > > **Case $\Delta = 3$.** Let $v$ be a vertex of degree $3$ with neighbours $a, b, c$, and let $w$ be the fifth vertex. The edges $va, vb, vc$ are three of the four edges, leaving exactly one more edge. Since $T$ is connected, $w$ must be reachable from $v$, so the remaining edge involves $w$. It can't be $vw$ (that would push $\deg(v) = 4 > \Delta$), so it must be $aw$, $bw$ or $cw$. By symmetry of the three neighbours of $v$, all three possibilities give isomorphic trees, namely the "Y" / broom. > > **Case $\Delta = 2$.** Every vertex has degree $\leq 2$. A connected graph in which every vertex has degree $\leq 2$ is either a path or a cycle, and trees have no cycles, so $T$ is a path. With 5 vertices, $T \cong P_5$. > > In every case $T$ is isomorphic to one of the three trees from part (a). --- 7) **(a)** For all $a, b \in \mathbb{R}$, define $a \preceq b$ to hold iff $a^2 \leq b^2$. Is $(\mathbb{R}, \preceq)$ a partial order? >[!hint]- Hint 1 > A partial order has three properties: **reflexive**, **antisymmetric**, **transitive**. To prove $\preceq$ is a partial order, all three must hold; to disprove, you only need to find one that fails. >[!hint]- Hint 2 > Antisymmetry says: if $a \preceq b$ and $b \preceq a$ then $a = b$. In our setting, that becomes: if $a^2 \leq b^2$ and $b^2 \leq a^2$ then $a = b$. Does $a^2 = b^2$ force $a = b$ over the reals? > [!check]- Solution > No, $(\mathbb{R}, \preceq)$ is **not** a partial order. Antisymmetry fails. > > **Counterexample.** Take $a = -3$ and $b = 3$. Then $a^2 = 9 = b^2$, so $a^2 \leq b^2$ *and* $b^2 \leq a^2$, i.e. $a \preceq b$ and $b \preceq a$. But $a = -3 \neq 3 = b$, so antisymmetry is violated. > > (Reflexivity and transitivity *do* hold, since they're inherited from $\leq$ on $\mathbb{R}$, but antisymmetry alone is enough to disprove the claim.) **(b)** Prove that every tree is $2$-colourable. *Hint: use mathematical induction. You may assume that every tree has a leaf.* >[!hint]- Hint 1 > Induct on the number of vertices $n$. For the **inductive hypothesis**, assume every tree on $n$ vertices is $2$-colourable. For the **inductive step**, take a tree on $n + 1$ vertices and find a way to reduce it to a tree on $n$ vertices. >[!hint]- Hint 2 > Removing a leaf from a tree gives you a smaller tree. Once the smaller tree is $2$-coloured by the IH, you only need to colour the removed leaf, and a leaf has just one neighbour to clash with. >[!hint]- Hint 3 > *Geometric intuition:* root the tree anywhere and **alternate colours by depth**, even depth gets colour $1$, odd depth gets colour $2$. Adjacent vertices are always at consecutive depths, so they get different colours. The induction is just a clean way to formalise this. > [!check]- Solution > We prove by induction on the number of vertices $n$ that every tree on $n$ vertices is $2$-colourable. > > **Base case ($n = 1$):** a tree with one vertex has no edges; colour the single vertex with colour $1$. There are no edges to violate. > > **Inductive hypothesis:** every tree on $n$ vertices ($n \geq 1$) is $2$-colourable. > > **Inductive step:** let $T$ be a tree on $n + 1$ vertices. By assumption, $T$ has a leaf $v$; let $u$ be its unique neighbour. Let $T' = T - v$ (remove $v$ and the edge $uv$). $T'$ is connected (a leaf lies on no path between other vertices, so removing it preserves connectivity) and acyclic (since $T$ was), hence $T'$ is a tree on $n$ vertices. > > By the IH, $T'$ has a $2$-colouring $c'$. Extend it to a colouring $c$ of $T$ by setting > - $c(x) = c'(x)$ for every vertex $x \neq v$, > - $c(v) = $ the colour *not* used by $c'(u)$. > > Edges entirely within $T'$ are properly coloured by $c'$, hence by $c$. The new edge $uv$ has $c(u) \neq c(v)$ by construction. So $c$ is a proper $2$-colouring of $T$. > > By induction, every tree is $2$-colourable. **(c)** Suppose $f : A \to B$ and $g : B \to C$. Prove that if $f \circ g : A \to C$ is injective and $f$ is surjective, then $g$ is injective. > Note: in this question $f \circ g$ means "apply $f$ first, then $g$", i.e. $(f \circ g)(a) = g(f(a))$ for $a \in A$. >[!hint]- Hint 1 > To show $g$ is injective, take any $b_1, b_2 \in B$ with $g(b_1) = g(b_2)$ and aim to conclude $b_1 = b_2$. >[!hint]- Hint 2 > You don't yet know anything about $b_1, b_2$, but $f$ is **surjective**, so each $b_i$ has a preimage $a_i \in A$ with $f(a_i) = b_i$. >[!hint]- Hint 3 > Feed $a_1, a_2$ into $f \circ g$. The injectivity of $f \circ g$ gives $a_1 = a_2$, and applying $f$ to both sides gives $b_1 = b_2$. > [!check]- Solution > Suppose $b_1, b_2 \in B$ with $g(b_1) = g(b_2)$. We show $b_1 = b_2$. > > Since $f$ is surjective, there exist $a_1, a_2 \in A$ with $f(a_1) = b_1$ and $f(a_2) = b_2$. Then > $(f \circ g)(a_1) = g(f(a_1)) = g(b_1) = g(b_2) = g(f(a_2)) = (f \circ g)(a_2)$. > > Since $f \circ g$ is injective, $a_1 = a_2$. Applying $f$ to both sides, $b_1 = f(a_1) = f(a_2) = b_2$. > > Hence $g$ is injective.