**24.** (Preliminary for Th, March 29; finalized Sat, April 7) Use induction to prove the fundamental theorem of arithmetic.

**23.** (Preliminary for T, March 27; finalized Sat, March 31) Prove uniqueness of the quotient and remainder in the division algorithm.

(Write clearly and don't make jumps that are too large. If you find yourself struggling to mentally justify a claim you make in the proof, prove a little lemma and then use it.)

**22.** (Preliminary for T, March 20; finalized Sat, March 24) Let $(R,0, 1, +, \cdot,\leq)$ be an ordered ring with identity.

a. Prove that if $x>0$, then $-x<0$.

b. Prove that $1>0$.

**21.** (Preliminary for T, March 13; finalized Sat, March 17) Given a partition $\{X_{\alpha}\}_{\alpha\in I}$ of $X$, show that the relation $R\subseteq X\times X$ defined by $((a,b)\in R \Leftrightarrow \exists \alpha\in I \text{ such that both } a,b\in X_{\alpha})$ is an equivalence relation on $X$ whose equivalence classes are precisely the sets $X_{\alpha}$ of the partition.

**20.** (Preliminary for T, March 20; finalized Sat, March 24) Prove that the polynomial ring $\mathbb{Z}[x]$ over the integers is countably infinite.

**19.** (Preliminary for Th, March 15; finalized Sat, March 24) a. Using our definition of the integers $\mathbb{Z}$ as a quotient of $\mathbb{N}\times\mathbb{N}$, propose an appropriate definition of $<_{\mathbb{Z}}$ (that is, $[(m,n)]<_{\mathbb{Z}}[(p,q)]$ if and only $m,n,p,q$ satisfy ??).

b. Prove that your proposal is well defined and extends the linear order $<_{\mathbb{N}}$ on the natural numbers (i.e., if two integers also happen to be natural numbers, they satisfy $<_{\mathbb{Z}}$ if and only if they satisfy $<_{\mathbb{N}}$).

**18.** (Preliminary for Th, March 1; finalized Sat, March 17) a. Prove by induction that $+:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ is commutative ($\forall m,n, \, \,\, m+n=n+m$) and satisfies *cancellation* ($\forall m,n,p, \,\,\, m+p=n+p$ if and only if $m=n$).

b. Prove by induction that $\cdot :\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ is associative ($\forall m,n,p, \, \,\, m \cdot (n\cdot p) =(m\cdot n)\cdot p$), commutative ($\forall m,n,\,\, \, m \cdot n=n \cdot m$), satisfies cancellation for nonzero values ($\forall m,n,p, \,\,\, m\cdot p=n \cdot p$ implies that $m=n$ if $p\neq 0$), and distributes over addition

($\forall m,n,p,\,\, \, m\cdot (n+p) = m\cdot n + m\cdot p$).

**17.** (Preliminary for Th, Feb 22; finalized Sat, March 3) Prove that for all sets $x,y$, it is impossible for both $x\in y$ and $y\in x$ to hold.

**16.** (Preliminary for Th, Feb 22; finalized Sat, March 3) Using only results proven in class or assigned earlier (i.e., don't use induction), show that for all natural numbers $x,y$, if $y< Succ(x)$, then $y\leq x$.

**15.** (Preliminary for Th, Feb 22; finalized Sat, March 3) a. Prove that for all $x,y\in \mathbb{N}$, if $x<y$, then either $Succ(x)<y$ or $Succ(x)=y$. (We say that $Succ(x)$ is an *immediate successor* of $x$.)) *Hint*: Use induction on $y$.

b. Prove that $(\mathbb{N},<)$ satisfies *trichotomy*: For all $x,y \in \mathbb{N}$, exactly one of the following holds: $x<y, \, x=y,$ or $y<x$. *Hint*: Again use induction on one of the variables. Apply the lemma in part a. at an appropriate point.

**14.** (Preliminary for Th, Feb 8; finalized Sat, Feb 24 (**new date**)) Using induction, prove that if $X$ is a finite set and $f$ is an injective function from $X$ to $X$, then $f$ is bijective.

**13.** (Preliminary for Th, Feb 8; finalized Sat, Feb 17) Using induction, prove that $5^{2n+1} + 2^{2n+1}$ is divisible by 7 for all $n\in \mathbb{N}$.

Proof for 13 (Recitation 2/21)

**12.** (Preliminary for Th, Feb 8; finalized Sat, Feb 17) Give an example of an invalid deduction (i.e., the conclusion is not true even though the hypothesis is) using the $\exists$-introduction rule if we don't require $y$ to be free in $\phi$. (Hint: find a simple formula $\phi$ involving $\forall y$ such that $\phi[y|x]$ is always true but $\exists x \phi$ is not.)

Proof of an invalid deduction (Monday recitation)

Proof of an Invalid Deduction (Tuesday presentation)

Proof of an Invalid Deduction (Wednesday recitation)

**11.** (Preliminary for Th, Feb 8; finalized Sat, Feb 17) Prove that $\mathbb{N}$ is *well-ordered*: every nonempty subset $X$ of $\mathbb{N}$ has a least element.

Proof that N is well-ordered (Thursday presentation)

**10.** (Preliminary for T, Feb 6; finalized T, Feb 13) a. Using our logical axioms and structural rules as discussed in class (but not the axioms of ZFC), give a formal proof of $\vdash \exists x(x=x)$. You could say that our logic assumes that at least one thing exists.

b. Can you prove that there exist at least two things? (If nothing else, give an unofficial wff expressing that there exist at least two things.)

**9.** (Preliminary for T, Feb 6; finalized T, Feb 13) Using our logical axioms and structural rules as discussed in class (but not the axioms of ZFC), give a formal proof that equality is symmetric: i.e., prove $\vdash \forall x \forall y (x=y \rightarrow y=x)$ in our formal system.

Equality is Symmetric Proof (Recitation)

**8.** (preliminary for T, Jan 30; finalized T, Feb 13) a. Let $x$ be a set. Write an "unofficial" wff (i.e., you can omit parentheses if it doesn't create confusion) defining the intersection $y$ consisting of all sets $z$ that belong to all elements $w$ of $x$. (Hereafter we will write $\cap x$ for the intersection of all the sets that are elements of $x$.) Note that $x,y$ should be free variables in your formula (not "bound" by any quantifiers).

b. Does your definition still make sense if $x$ is the empty set? Explain.

c. We defined the natural numbers $\mathbb{N}$ as the set $\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}, \dots\}$. What is $\cap\mathbb{N}$? (Write a brief proof that is clear and precise but not too wordy or formal.)

**7.** (preliminary for T, Jan 30; finalized T, Feb 13) Write an "official" (include all parentheses, etc.) wff expressing the Empty Set Axiom ("there exists a set with no elements").

**6**. (preliminary for T, Jan 23; finalized Th, Jan 25) We saw from exercise 2 (infinitude of primes and finding large primes) that sometimes an indirect proof (e.g., by contradiction) is just masking a similar "constructive" proof. Using the numbers $\sqrt{2}$ and $\sqrt{2}^{\sqrt{2}}$, prove that there exist irrational numbers $a,b$ such that $a^b$ is rational. Can you use the proof to find specific values of $a,b$? Why or why not?

Proof of existence of a rational equal to an irrational raised to an irrational power

**5**. (preliminary for T, Jan 23; finalized Th, Jan 25) a. Explain the ambiguity of "formulas" like the following if we don't require parentheses: $\phi \wedge \psi\vee \theta$ (assume we can assign truth values to $\phi, \psi,$ and $\theta$).

b. Carefully define an appropriate notion of "unique readability"; i.e., a precise statement of what it means for formulas to be unambiguous.

c. Recall from class the result that no wff has a proper initial segment that is also a wff. Use this lemma to prove that wffs satisfy your definition of unique readability from part b.

Proof of unique readability of wffs

**4**. There is something odd about our use of sets, intersections, and other mathematical entities in the previous problem. Discuss the issue and propose a resolution.

Circularity in using set theory to prove results about set theory?

**3**. We defined the set WFF of well-formed $\mathcal{L}_{ST}$-formulas inductively, in “bottom-up” fashion. Call a set $S$ of $\mathcal{L}$-strings “good” if $S$ contains all atomic formulas and is closed under application of the connectives and quantifiers: if $\phi$ and $\psi$ belong to $S$, then $\neg\phi$, $(\phi \wedge \psi)$, $(\phi \vee \psi)$, $(\phi\rightarrow \psi)$, $\forall x \phi$ and $\exists x \phi$ also belong to $S$. (“Good” isn't a standard term here; we're just using it as a placeholder word to make the statement of the proposition less unwieldy.) Prove that the intersection of all good sets of $\mathcal{L}$-strings is exactly equal to WFF. (“Top-down” characterization)

Proof that WFF equals the intersection of all "good sets"

**2**. a. Prove that there are infinitely many prime numbers. (Hint: Here is a sketch of the classic proof dating back to Euclid. Suppose toward contradiction that there are only finitely many prime numbers. Consider the number $N$ defined to be the product of all (finitely many) prime numbers, plus 1. Find something wrong with $N$. We will prove it later, but for now you may assume the *Fundamental Theorem of Arithmetic*, namely that every positive integer can be written as a product of prime numbers; moreover that product is “unique up to reordering”, i.e., no matter how you write a given number as a product of primes, all the representations involve the same primes and the same number of each prime.)

Proof of the Infinitude of Primes

b. (i) Describe an algorithm that takes as input a positive integer $n$ and outputs a prime number greater than $n$. Prove that your algorithm satisfies the required property. (You may assume that testing a number for primality is a primitive operation; that is, you don't need to explain how to check if a given number is prime.) (ii) (Challenge question; optional): Give an upper bound (in terms of $n$) on the size of the prime your algorithm (or another algorithm you think of if your original isn't suitable to analyze) finds with input $n$. Prove that your bound really works. (Hint: Think about Euclid's proof.)

**1**. State and prove the Pythagorean Theorem for right triangles in the plane. (Study your insights from our prior class discussion but write it up without copying.)

**Definition:** A positive integer $p$ is *prime* if $p$ is greater than 1 and is not divisible by any positive integers other than 1 and itself.