suppose there are 2 skew lines in space why there is a unique line passing through origin and intersecting these lines?

@PrateekMourya Where did this question come from? What are your thoughts?

@user21820, I think your excellent teaching is paying off :-) Yesterday, I spend half an hour trying to understand PA3 exercise before even attempting to use an inference rule :-)

@user21820, is the theorem saying: "Every natural number (greater than 1) has (at least) one prime divisor" ?

@F.Zer Indeed it does!

In other words, we are starting to reach some basic facts in number theory, expressed within PA.

I'll give you hints for this exercise, because I will sketch two approaches and I want you to give me one proof for each approach!

First let me introduce you to two things that are equivalent to induction. Your task is to prove that you can derive them from induction.

> Strong induction: For any property P on ℕ, we have ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ) ⇒ ∀k∈ℕ ( P(k) ).

Hints: First derive strong induction. That is, for each property P on ℕ prove "∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ) ⇒ ∀k∈ℕ ( P(k) )" within PA. Next derive well-ordering from strong induction, by proving "¬∃m∈ℕ ( P(m) ∧ ∀k∈ℕ ( P(k) ⇒ k≥m ) ) ⇒ ∀k∈ℕ ( ¬P(k) )".

After you're done with those two, you would have two powerful tools that are often easier to use than induction, even though they are logically equivalent to induction over PA−. Specifically, PA− plus induction can prove any sentence that PA− plus strong induction can prove, and any sentence that PA− plus well-ordering can prove.

The reason they are easier to use is that they enable getting more from less:

Induction requires you to prove P(0) and P(k+1) from P(k). Strong induction only requires you to prove P(k) from ∀i∈ℕ ( i<k ⇒ P(i) ).

Well-ordering allows you to get from "some k∈ℕ satisfies P" to "some minimum m∈ℕ satisfies P". It is as if you get something extra for free.

It is not hard to prove (PA3) using strong induction or well-ordering. I'll let you figure out how to use strong induction yourself. For the proof that uses well-ordering, notice that well-ordering gives you ∀k∈ℕ ( k > 1 ⇒ ∃p∈ℕ ( p > 1 ∧ p | k ∧ ∀q∈ℕ ( 1 < q ∧ q | k ⇒ q ≥ p ) ) ), so you would have to get from "∀q∈ℕ ( 1 < q ∧ q | k ⇒ q ≥ p )" to "¬∃q∈ℕ ( 1 < q < p ∧ q | p )", which is easy using a lemma that | is transitive.

@user21820 Thanks for the explanations ! Could you clarify this phrase: "they are logically equivalent to induction over PA−" ?

I will first derive Strong induction from induction.

If for any property P on ℕ, P(0) ∧ ∀ k ∈ ℕ ( P(k) ⇒ P(k+1) ) ⇒ ∀ k ∈ ℕ ( P(k) ):
	Given P on ℕ:
		If ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ):
			P(0) ∧ ∀ k ∈ ℕ ( P(k) ⇒ P(k+1) ) ⇒ ∀ k ∈ ℕ ( P(k) )
			Given k ∈ ℕ:
				∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k)
				...
	For any property P on ℕ, ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ) ⇒ ∀k∈ℕ ( P(k) )

@user21820, could you tell me if my proof skeleton is correct ?