Proving the induction principle?

Question

Suppose we have a language that just consists of a term "a" and a successor function s(x). We know that p(a) is true and we know that $\forall x: p(x) \to p(s(x))$ is true. Suppose we don't have the induction rule: p(a), $\forall x: p(x) \to p(s(x)) \vdash \forall x: p(x)$. Then we couldn't prove the conclusion $\forall x: p(x)$, could we?

I ask because in some course the prof says: For the language introduced above, our rule of inference [induction rule] is sound. Suppose we know that a schema is true of a and suppose that we know that, whenever the schema is true of an arbitrary ground term τ, it is also true of the term s(τ). Then, the schema must be true of everything, since there are no other terms in the language.

IMO he can't write that because he basically claims he can prove the soundness of the induction rule beyond. But as far as I understand you cannot prove the soundness of this rule beyond, i.e. you have to assume (per axiom) it and then you can prove it trivially from the assumption (and of course the assumption could be always wrong so you could never be sure the "schema must be true of everything". Am I right?

Answer 1

You are right. Counterexample to the argument that $\forall x \ p(x)$ logically follows from $p(a)$ and $\forall x (p(x) \to p(s(x)))$:

Take as the domain all non-negative integers, interpret $a$ as $1$, $s$ as the successor function, and $p(x)$ as $x$ is a positive integer. Then the premises hold, but since $0$ is not a positive integer, the conclusion does not.

Answer 2

We know that $p(a)$ is true and we know that $\forall x: p(x) \to p(s(x))$ is true.

If there also exists $b$ in the domain of discussion that is distinct from $a$, then, without the induction schema, you could not rule out $s(a)=a$, $s(b)=b$ and $\neg p(b)$. It would be vacuously true that $p(b) \to p(s(b))$.

EDIT: In answer to your follow-up question: What if $a$ is the only object in the domain of discussion? Then $P(x)$ will be true for all $x$ in the domain of discussion. Here, $U(x)$ means that $x$ is an object in the domain of discussion.

Proof: (Induction not required)

Answer 3

It depends on what else the professor said, since there is a specific sense in which he is correct.

It is true that we cannot possibly justify induction in a non-circular way. See this post for more details, but I wish to quote a single key part of that post:

The second [circularity] is the understanding of the arithmetic on the natural numbers including induction. This boils down to the understanding of "repeat". If you do not know the meaning of "repeat" or "again" or other forms, no explanation can pin it down.

Think about it; there is no way to explaining how to repeat something an arbitrary finite number of times without relying on prior understanding of natural numbers including induction.

However, we can justify adding the induction axiom schema to PA$^-$, though this justification will rely on meta-induction on the length of finite strings. Specifically, if you can define the natural numbers to be exactly those that can be written in the form "$0+1+\cdots+1$" for some number of "$+1$"s, then the natural numbers also obey the induction axiom schema. See this post for details. Note that such a definition requires assumptions that are at least as strong as induction.

For example, in ZFC we can construct the intersection of all inductive sets, using the one given by the axiom of infinity. But such a construction is in fact impredicative, which is even less philosophically justifiable than induction; if you doubt induction holds for natural numbers, you will certainly not believe that the axiom of infinity plus such impredicative constructions are valid.

On the other hand, we can assume that we can construct the set of strings that can be generated starting from "$0$" by appending "$+1$". This is equivalent to having induction, but some logicians prefer this generative form (also known as inductive constructions) to the axiomatic form (i.e. the induction schema).

To summarize the intuitive reasoning in the linked post:

If every natural number is of the form "$0+1+\cdots+1$" for some number of "$+1$"s, then the induction rule is sound because the conclusion it gives us is true for every natural number $k$, since we can construct a proof that uses the induction step $k$ times to deduce the desired statement about $k$.

Constructing such a proof of course requires induction, but hopefully you can see why it is possible if you believe in the existence of the set of all strings of the form "$0+1+\cdots+1$" for some number of "$+1$"s. So I think that the professor is referring to the term model. Indeed, if there is only one constant-symbol $0$ and one function-symbol $s$ in the language (and no others) and there is a term model, then for any first-order property $Q$ over the language, if that term model satisfies ( $Q(0) ∧ ∀k ( Q(k) ⇒ Q(s(k)) )$ ) then it also satisfies $∀k ( Q(k) )$, precisely for the reason that every element in the term model is generated by $s$ from $0$.

Also note that the meta-reasoning only tells us that there exists a proof for each natural $k$, and not that there is a proof for the universal statement, and furthermore the existence of a proof does not imply truth unless you also assume the soundness of the system without induction.