Clearly and unambiguously communicate computational ideas using appropriate formalism. Translate across levels of abstraction.
Translating between symbolic and English versions of statements using precise mathematical language
Using appropriate signpost words to improve readability of proofs, including ‘arbitrary’ and ‘assume’
Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.
Judging logical equivalence of compound propositions using symbolic manipulation with known equivalences, including DeMorgan’s Law
Writing the converse, contrapositive, and inverse of a given conditional statement
Determining what evidence is required to establish that a quantified statement is true or false
Evaluating quantified statements about finite and infinite domains
Apply proof strategies, including direct proofs and proofs by contradiction, and determine whether a proposed argument is valid or not.
Identifying the proof strategies used in a given proof
Identifying which proof strategies are applicable to prove a given compound proposition based on its logical structure
Carrying out a given proof strategy to prove a given statement
Carrying out a universal generalization argument to prove that a universal statement is true
Using proofs as knowledge discovery tools to decide whether a statement is true or false
No class Monday of Week 7 (02/16/2026) in observance of UCSD holiday.
Review quiz based on Week 6 class material (due Monday 02/16/2026)
Midquarter feedback: please let us know what’s working well for you and what isn’t. https://canvas.ucsd.edu/courses/71479/quizzes
Review quiz based on Week 7 class material (due Monday 02/23/2026)
Consider the following game: two players start with two (equal) piles of jellybeans in front of them. They take turns removing any positive integer number of jellybeans at a time from one of two piles in front of them in turns.
The player who removes the last jellybean wins the game.
Which player (if any) has a strategy to guarantee to win the game?
Try out some games, starting with \(1\) jellybean in each pile, then \(2\) jellybeans in each pile, then \(3\) jellybeans in each pile. Who wins in each game?
Notice that reasoning about the strategy for the \(1\) jellybean game is easier than about the strategy for the \(2\) jellybean game.
Formulate a winning strategy by working to transform the game to a simpler one we know we can win.
Player 2’s Strategy: Take the same number of jellybeans that Player 1 did, but from the opposite pile.
Why is this a good idea: If Player 2 plays this strategy, at the next turn Player 1 faces a game with the same setup as the original, just with fewer jellybeans in the two piles. Then Player 2 can keep playing this strategy to win.
Claim: Player 2’s strategy guarantees they will win the game.
Proof: By strong induction, we will prove that for all positive integers \(n\), Player 2’s strategy guarantees a win in the game that starts with \(n\) jellybeans in each pile.
Basis step: WTS Player 2’s strategy guarantees a win when each pile starts with \(1\) jellybean.
In this case, Player 1 has to take the jellybean from one of the piles (because they can’t take from both piles at once). Following the strategy, Player 2 takes the jellybean from the other pile, and wins because this is the last jellybean.
Recursive step: Let \(n\) be a positive integer. As the strong induction hypothesis, assume that Player 2’s strategy guarantees a win in the games where there are \(1, 2, \ldots, n\) many jellybeans in each pile at the start of the game.
WTS that Player 2’s strategy guarantees a win in the game where there are \(n+1\) in the jellybeans in each pile at the start of the game.
In this game, the first move has Player 1 take some number, call it \(c\) (where \(1 \leq c \leq n+1\)), of jellybeans from one of the piles. Playing according to their strategy, Player 2 then takes the same number of jellybeans from the other pile.
Notice that \((c = n+1) \lor (c \leq n)\).
Case 1: Assume \(c = n+1\), then in their first move, Player 2 wins because they take all of the second pile, which includes the last jellybean.
Case 2: Assume \(c \leq n\). Then after Player 2’s first move, the two piles have an equal number of jellybeans. The number of jellybeans in each pile is \[(n+1) - c\] and, since \(1 \leq c \leq n\), this number is between \(1\) and \(n\). Thus, at this stage of the game, the game appears identical to a new game where the two piles have an equal number of jellybeans between \(1\) and \(n\). Thus, the strong induction hypothesis applies, and Player 2’s strategy guarantees they win.
Definition The set of linked lists of natural numbers \(L\) is defined recursively by \[\begin{array}{ll} \textrm{Basis Step: } & [] \in L \\ \textrm{Recursive Step: } & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N} \textrm{, then } (n, l) \in L \end{array}\]
Visually:
Example: the list with two nodes whose first node has \(20\) and whose second node has \(42\)
Definition: The length of a linked list of natural numbers \(L\), \(length: L \to \mathbb{N}\) is defined by \[\begin{array}{llll} \textrm{Basis Step:} & & length(~[]~) &= 0 \\ \textrm{Recursive Step:} & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N}\textrm{, then } & length(~(n, l)~) &= 1+ length(l) \end{array}\]
Definition: The function \(prepend : L \times \mathbb{N} \to L\) that adds an element at the front of a linked list is defined by \[\phantom{prepend(~(l, n)~) = (n, l)}\]
Definition The function \(append : L \times \mathbb{N} \to L\) that adds an element at the end of a linked list is defined by \[\begin{array}{llll} \textrm{Basis Step:} & \textrm{If } m \in \mathbb{N}\textrm{ then } & \phantom{append(~([], m)~)} & \phantom{= (m, []) }\\ \textrm{Recursive Step:} & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N}\textrm{ and }m \in \mathbb{N}\textrm{, then } & \phantom{append(~(~(n, l), m~)~) } &\phantom{= (n, append(~(l, m)~)~)} \end{array}\]
Claim: \(\forall l \in L ~ (~length(~append(~(l, 100)~)~) > length(l)~)\)
Proof: By structural induction on \(L\), we have two cases:
Basis Step
| 1. To Show \(length(~append(~([], 100)~)~) > length(~[]~)\) | Because \([]\) is the only element defined in the basis step of \(L\), we only need to prove that the property holds for \([]\). |
| 2. To Show \(length(~(100,[])~) > length(~[]~)\) | By basis step in definition of \(append\). |
| 3. To Show \((1 +length(~[]~)) > length(~[]~)\) | By recursive step in definition of \(length\). |
| 4. To Show \(1+0 > 0\) | By basis step in definition of \(length\). |
| 5. \(T\) | By properties of integers |
| QED | Because we got to \(T\) only by rewriting To Show to equivalent statements, using well-defined proof techniques, and applying definitions. |
Recursive Step
Consider an arbitrary: \(l' \in L\), \(n \in \mathbb{N}\), and we assume as the induction hypothesis that: \[length(~append(~(l', 100~)~)~) > length(l')\] Our goal is to show that \(length(~append( ~(~(n,l'), 100~)~)~) > length(~(n,l')~)\) is also true. We start by working with one side of the candidate inequality: \[\begin{align*} LHS &= length(~append( ~(~ (n,l'), 100~)~)~) \\ &= length(~(n, append(~(l', 100)~)~ )~) \qquad \text{by the recursive definition of $append$}\\ &= 1 + length(~ append(~(l', 100)~) ~) \qquad \text{by the recursive definition of $length$}\\ &> 1+ length(l') \qquad \text{by the induction hypothesis}\\ &= length( (n,l') ) \qquad \text{by the recursive definition of $length$}\\ &= RHS \end{align*}\]
Prove or disprove: \(\forall n \in \mathbb{N} ~\exists l \in L ~(~length(l) = n~)\)
For a set of numbers \(X\), how do you formalize “there is a greatest \(X\)” or “there is a least \(X\)”?
Prove or disprove: There is a least prime number.
Prove or disprove: There is a greatest integer.
Approach 1, De Morgan’s and universal generalization:
Approach 2, proof by contradiction:
Extra examples: Prove or disprove that \(\mathbb{N}\), \(\mathbb{Q}\) each have a least and a greatest element.
Definition: Greatest common divisor Let \(a\) and \(b\) be integers, not both zero. The largest integer \(d\) such that \(d\) is a factor of \(a\) and \(d\) is a factor of \(b\) is called the greatest common divisor of \(a\) and \(b\) and is denoted by \(gcd(~(a, b)~)\).
Why do we restrict to the situation where \(a\) and \(b\) are not both zero?
Calculate \(gcd(~(10,15)~)\)
Calculate \(gcd(~(10,20)~)\)
Claim: For any integers \(a,b\) (not both zero), \(gcd(~(a,b)~) \geq 1\).
Proof: Show that \(1\) is a common factor of any two integers, so since the gcd is the greatest common factor it is greater than or equal to any common factor.
Claim: For any positive integers \(a,b\), \(gcd(~(a,b)~) \leq a\) and \(gcd( ~(a,b)~) \leq b\).
Proof Using the definition of gcd and the fact that factors of a positive integer are less than or equal to that integer.
Claim: For any positive integers \(a,b\), if \(a\) divides \(b\) then \(gcd(~(a,b)~) = a\).
Proof Using previous claim and definition of gcd.
Claim: For any positive integers \(a,b,c\), if there is some integer \(q\) such that \(a = bq + c\), \[gcd(~(a,b)~) = gcd (~(b,c)~)\] Proof Prove that any common divisor of \(a,b\) divides \(c\) and that any common divisor of \(b,c\) divides \(a\).
Lemma: For any integers \(p, q\) (not both zero), \(gcd \left(~ \left(~\frac{p}{gcd(~(p,q)~)}, \frac{q}{gcd(~(p,q)~)} ~\right) ~\right) = 1\) . In other words, can reduce to relatively prime integers by dividing by gcd.
Proof:
Let \(x\) be arbitrary positive integer and assume that \(x\) is a factor of each of \(\frac{p}{gcd(~(p,q)~)}\) and \(\frac{q}{gcd(~(p,q)~)}\). This gives integers \(\alpha\), \(\beta\) such that \[\alpha x = \frac{p}{gcd(~(p,q)~)} \qquad \qquad \beta x = \frac{q}{gcd(~(p,q)~)}\] Multiplying both sides by the denominator in the RHS: \[\alpha x \cdot gcd(~(p,q)~)= p \qquad \qquad \beta x \cdot gcd(~(p,q)~)= q\] In other words, \(x \cdot gcd(~(p,q)~)\) is a common divisor of \(p, q\). By definition of \(gcd\), this means \[x \cdot gcd (~(p,q)~) \leq gcd (~(p,q)~)\] and since \(gcd(~(p,q)~)\) is positive, this means, \(x \leq 1\).
We’ve seen multiple representations of the set of positive integers (using base expansions and using prime factorization). Now we’re going to expand our attention to other sets of numbers as well.
The set of rational numbers, \(\mathbb{Q}\) is defined as \[\left\{ \frac{p}{q} \mid p \in \mathbb{Z} \text{ and } q \in \mathbb{Z} \text{ and } q \neq 0 \right\} \text{~~~~or, equivalently,~~~~} \{ x \in \mathbb{R} \mid \exists p \in \mathbb{Z} \exists q \in \mathbb{Z}^+ ( p = x \cdot q) \}\]
Extra practice: Use the definition of set equality to prove that the definitions above give the same set.
We have the following subset relationships between sets of numbers:
\[\mathbb{Z}^{+} \subsetneq \mathbb{N} \subsetneq \mathbb{Z} \subsetneq \mathbb{Q} \subsetneq \mathbb{R}\]
Which of the proper subset inclusions above can you prove?
Goal: The square root of \(2\) is not a rational number. In other words: \(\neg \exists x \in \mathbb{Q} ( x^2 - 2 = 0)\)
Attempted proof: The definition of the set of rational numbers is the collection of fractions \(p/q\) where \(p\) is an integer and \(q\) is a nonzero integer. Looking for a witness \(p\) and \(q\), we can write the square root of \(2\) as the fraction \(\sqrt{2 }/1\), where \(1\) is a nonzero integer. Since the numerator is not in the domain, this witness is not allowed, and we have shown that the square root of \(2\) is not a fraction of integers (with nonzero denominator). Thus, the square root of \(2\) is not rational.
The problem in the above attempted proof is that
Lemma 1: For every two integers \(a\) and \(b\), not both zero, with \(gcd(~(a,b)~) = 1\), it is not the case that both \(a\) is even and \(b\) is even.
Lemma 2: For every integer \(x\), \(x\) is even if and only if \(x^2\) is even.
Proof: Towards a proof by contradiction, we will define a statement \(r\) such that \(\sqrt{2} \in \mathbb{Q} \to (r \land \lnot r)\).
Assume that \(\sqrt{2} \in \mathbb{Q}\). Namely, there are positive integers \(p, q\) such that \[\sqrt{2} = \frac{p}{q}\] Let \(a= \frac{p}{gcd( ~(p,q)~)}\), \(b = \frac{q}{gcd(~(p,q)~)}\), then \[\sqrt{2} = \frac{a}{b} \qquad \text{and} \qquad gcd(~(a,b)~) = 1\]
By Lemma 1, \(a\) and \(b\) are not both even. We define \(r\) to be the statement “\(a\) is even and \(b\) is even”, and we have proved \(\lnot r\).
Squaring both sides and clearing denominator: \(2b^2 = a^2\).
By definition of even, since \(b^2\) is an integer\(, a^2\) is even.
By Lemma 2, this guarantees that \(a\) is even too. So, by definition of even, there is some integer (call it \(c\)), such that \(a = 2c\).
Plugging into the equation: \[2b^2 = a^2 = (2c)^2 = 4c^2\] and dividing both sides by \(2\) \[b^2 = 2c^2\] and since \(c^2\) is an integer, \(b^2\) is even. By Lemma 2, \(b\) is even too. Thus, \(a\) is even and \(b\) is even and we have proved \(r\).
In other words, assuming that \(\sqrt{2} \in \mathbb{Q}\) guarantees \(r \land \lnot r\), which is impossible, so \(\sqrt{2} \notin \mathbb{Q}\). QED