What is the method to solve these kind of questions?

Question

Here is the exercise :

We define in $\textbf{PA}$ :

"$x \mid y \equiv \exists z \ y=xz"$

"$\text{irr}(x) \equiv \forall z(z\mid x \rightarrow z=1 \vee z=x)$"

"$\text{prime}(x)\equiv x>1 \wedge \forall y, z(x\mid yz \rightarrow x \mid y \vee x \mid z)$"

I have to show that in $\textbf{PA}$ : $\forall x, y(y\ne 0\rightarrow \exists a,b(x=ay+b \wedge 0\le b <y)$ and prove the uniqueness of $a,b$.

Then I have to prove that : $\textbf{PA} \vdash \forall x (x>1\rightarrow(\text{irr}(x) \leftrightarrow \text{prime}(x)))$

I tried induction without success. I don't know what is the method to solve this kind of question...

Thanks in advance !

Answer 1

The Division Theorem states: Let $x$ be a nonnegative integer and $y$ be a positive integer. Then there exist unique integers $a,b$ such that $x=ay+b$, and $0 \le b \le y-1$.

Informal proof: First, existence is proven, by fixing $y$ and doing induction on $x$. Clearly, we can take $(a,b)=(0,0)$ when $x=0$.

Now suppose that the theorem is true when $x=n$; that is, $n=a'y+b'$, and $0\le b' \le y-1$. Now consider $x=n+1$.

If $b' < y-1$, then we can take $(a,b)=(a',b'+1)$. Clearly, $$ay+b = a'y + b'+1 = (a'y+b')+1 = n+1,$$ and $b'+1 \le y-1$ since $b' < y-1$.

Now, if $b'=y-1$, we take $(a,b)=(a'+1,0)$. Then $$ay+b = (a'+1)y+0=a'y + y = a'y + b' + 1 = (a'y+b')+1 = n+1,$$ and clearly $0 \le b \le y-1$.

By induction, the theorem is true for all nonnegative $x$.

Uniqueness is a bit messier; the easiest proof is probably: Suppose $x=ay+b=a'y+b'$, where $0 \le b \le y-1$ and $0 \le b' \le y-1$. Note that $$ 0-(y-1) \le b-b' \le (y-1)-0,$$ by subtracting the second equation from the first. Also, $$b-b' = (x-ay) - (x-a'y) = a'y - ay = y (a'-a),$$ so $b-b'$ is a multiple of $y$ which is between $-(y-1)$ and $y-1$. The only such number that qualifies is $0$; hence, $b=b'$. Consequently, $a=a'$, which proves uniqueness.

However, it's difficult to write this in PA unless you've constructed the negative numbers and proven all the properties of subtraction already.

Answer 2

DanielV's comment is totally correct; proving a statement in Peano's arithmetic is similar to coding it in a programming language, or to use a looser analogy proving in a different language (Chinese?). First, you should be able to carry the proof in your own language (maybe somewhat informally), and then you translate it formally.

Let's start with the second implication, for which you don't need induction.

First, you split an equivalence into two statements, so you are left to prove that $\forall x >1$, you have to prove $\mathrm{prime}(x) \to \mathrm{irr}(x)$ and $\mathrm{irr}(x) \to \mathrm{prime}(x)$. Those are universal statements, but it's often easier to work with existential statements, since they give you some 'witness', i.e. a mathematical objects satisfying a property that will help you carry the proof. So it would be easier to switch to an existential statement, you can switch to the equivalent contrapositive formulation, i.e. instead of $p \to q$ you show $\neg q \to \neg p$.

So applied to your problem, let's try to show $\neg \mathrm{irr}(x) \to \neg \mathrm{prime}(x)$. Since $\neg \mathrm{irr}(x)$, there is a $z$ such that $z \neq 1$ and $z \neq x$ and $\exists y (x = yz)$. You can then use this witness to show that $x$ is not prime, and you're done. The other implication will follow similarly.

To prove the other statement, just go through the proof (see https://en.wikipedia.org/wiki/Euclidean_division#Proof for example) and translate it to PA axioms bit by bit, there's no specific technique. Since it doesn't use any complicated theorem, the matter is just in justifying each step through the invocation of the correct axiom.