Print this problem set out (there are X problems!) and answer the problems on the given sheet.
  1. Consider the following theorem and proof:
    (no zero divisors) Over the integers, if $x*y = 0$ then $x = 0$ or $y = 0$.
    Assume by way of contradiction that x*y = 0 and both x and y are nonzero.
    • case $0 \lt x$: if $0 \lt y$ then by point v of the axioms for "a total order for rings" $x*0 \lt x*y$ so $0 \lt x*y$, which by the trichotemy law means $x*y \neq 0$. if $y \lt 0$ then by point v of the axioms for "a total order for rings" $x*y \lt x*0$ so $x*y \lt 0$, which by the trichotemy law means $x*y \neq 0$.
    • case $x \lt 0$: then $0 \lt -1*x$, so by the previous case, $(-1*x)*y \neq 0$. Therefore $-1*(-1*x)*y \neq 0$, so $x*y \neq 0$
    In both cases $x*y \neq 0$, which contradicts our assumption. Thereore the theorem holds.

    a. write the theorem statement in first order logic (you may treat $x$ and $y$ as constants, i.e. you do not need "$\forall x,y$")

    b. prove in step-by-step first-order logic style that the assumption "that x*y = 0 and both x and y are nonzero" really is the logical negation of the theorem statement.

  2. Consider the following theorem and proof:
    (Removing common factors) Over the integers, if $a*b = a*c$ then $a = 0$ or $b = c$.
    Assume $a*b = a*c$. If $a = 0$ then the theorem holds regardless of $b$ and $c$. So assume $a \neq 0$. We will first show that if $b$ is non-negative then $b = c$. We will prove this by induction on $b$. If $b = 0$, then $a*b=0$ so $a*c=0$. By the no zero divisors theorem from problem 1, $a = 0$ or $c=0$. But by assumption $a\neq 0$, so we must have $c = 0$, and so $b = c$. Consider the case $b > 0$. If we subtract $a$ from both sides of $a*b=a*c$ we get $a*(b-1)=a*(c-1)$, which by the inductive hypothesis gives us $a=0$ or $b-1=c-1$. But we are in the case where $a \neq 0$, so $b-1=c-1$. Adding 1 to both sides, we get $b=c$. Therefore, we deduce that for all non-negative $b$ the theorem holds. Finally, if $b$ is negative, then since $a*b=a*c$ we have $a*(-1*b)=a*(-1*c)$, and because $0 \lt -1*b$, the induction shows us that $-1*b=-1*c$, and multiplying both sides by -1 gives us $b=c$.

    Your job For the inductive part of the proof: Circle and label the base case. Circle and label the inductive case. Clearly identify where the inductive hypothesis is applied.


  3. Prove the following theorem: in any ring $--x = x$. Note: You have the ring axioms at your disposal, as well the theorems from Class 19. Also, remember that we use $-x$ to denote the additive inverse of $x$. Just to clarify, this is really a function $\text{ai}(x)$, so $-x = \text{ai}(x)$ and $--x = \text{ai}(\text{ai}(x))$.
  4. Consider the following theorem and proof:
    In a ring that is non-trivial and has a total order, $0 \lt 1$.
    1. By the Trichotemy Law (), exactly one of 1<0, 1=0, 0<1 is true.
    2. By the Problem 3 theorem from the last homework, $0 \neq 1$, so either 1<0 or 0<1.
      1. Assume $1 \lt 0$.
      2. Then $0 \lt -1$ by the "Negation & Order" .
      3. By point v. from the definition of order for rings, $-1*0 \lt -1*-1$.
      4. By , $-1*0 = 0$, and by , $-1*-1 = --1$.
      5. Finally, by the Problem 3 theorem from this homework, $--1 = 1$.
      6. So we get $0 \lt 1$, which contradicts what we assumed, so we deduce $\neg(1 \lt 0)$.
    4. Since $0 \neq 1$ and $\neg(1 \lt 0)$, the only option left from the Trichotemy Law is $0 \lt 1$.

    Hopefully you can follow along with that theorem and make sense of it, even some lines of the proof actually stand for many lines if we were to write it out "step-by-step". Your job is to write out the "step-by-step" version of line c.3. I've done c.1 and c.2 for you to demonstrate what I mean.

    c.1 
    0: 1 < 0                       [Assumption A]
    c.2
    1: ∀x[x < 0 => 0 < -x] 	       [Negation and Order Theorem]	 
2: 1 < 0 => 0 < -1             [Specialize x to 1 in line 1]
3: 0 < -1                      [Modus ponens on 2 and 1]
    c.3 
    














	    
____________________________________________________________________________________________________
    Fill in with your point-by-point proof of step c.3.

  5. Given that $n$ is even, prove that $n-1$ is odd. Give a "prose proof", i.e. not full first-order logic!
  6. Prove that there is no largest even number.
    Note 1: This a great place to use proof by contradiction!
    Note 2: Don't spend a lot of time on this if you don't see the trick.