2
$\begingroup$

In Terence Tao's Analysis I, he admits to leaving out some details when writing about induction in his presentation of Peano Arithmetic (note that he uses $n++$ to denote the successor of $n$):

Axiom 2.5 (Principle of mathematical induction). Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n++)$ is also true. Then $P(n)$ is true for every natural number $n$.

Remark 2.1.10. We are a little vague on what “property” means at this point, but some possible examples of $P(n)$ might be “$n$ is even”; “$n$ is equal to $3$”; “$n$ solves the equation $(n + 1)^2 = n^2 + 2n + 1$”; and so forth. Of course we haven’t defined many of these concepts yet, but when we do, Axiom 2.5 will apply to these properties. (A logical remark: Because this axiom refers not just to variables, but also properties, it is of a different nature than the other four axioms; indeed, Axiom 2.5 should technically be called an axiom schema rather than an axiom - it is a template for producing an (infinite) number of axioms, rather than being a single axiom in its own right. To discuss this distinction further is far beyond the scope of this text, though, and falls in the realm of logic.)

Trying to better understand this axiom (schema) and what is meant by "property", I navigated to the Wikipedia page for the Peano axioms, where it is written,

The axiom of induction is in second-order, since it quantifies over predicates (equivalently, sets of natural numbers rather than natural numbers), but it can be transformed into a first-order axiom schema of induction. Such a schema includes one axiom per predicate definable in the first-order language of Peano arithmetic, making it weaker than the second-order axiom.

My understanding is that in an interpretation of Peano Arithmetic, each "property", i.e., (single-place) predicate is interpreted by a Boolean-valued function on the domain of discourse.

But then how can one go about discussing all possible predicates without referencing a specific domain of discourse? In order to know the possible predicates, don't we need to first fix a domain of discourse? But this is getting into interpretations, whereas I was trying to state axioms without reference to an interpretation. Or should we just restrict the predicate symbols in our language to some fixed set of symbols, e.g., $P_0, P_1, P_2, \dotsc$, and then apply the axiom schema of mathematical induction to only those symbols, thereby avoiding reference to specific interpretations?

$\endgroup$
2
  • $\begingroup$ Correct: the "properties" are all and only those expressible in the language. Thus (as per previous discussions) you have to take into account that Tao's treatment (presumably for need of exposition) is not "fully formal". Thus, to specify what properties are expressible we have to write the "syntactical specifications" of the language. $\endgroup$ Commented Apr 4, 2017 at 6:00
  • $\begingroup$ If the language is the standard FO language for arithmetic, the set of symbols is made of : $0, +, \times, S$. So, no predicate symbols at all. But we have many properties indeed: $\text {Even}(x)$, for ex, is expressible as : $\exists y \ (x=y \times S(S(0)))$. $\endgroup$ Commented Apr 4, 2017 at 6:02

3 Answers 3

Reset to default
2
$\begingroup$

The $P(n)$ is really just any first-order logic formula with one free variable that you can define using your language. $P$ does not need to be a predicate symbol, and there is no need to specify any domain of discourse.

Thus, for example, if we want to prove that $\forall x.\,0 + x = x$, we have as $P(x):=0 + x = x$. The corresponding instance of the induction schema would thus be:

$(0 + 0 = 0 \land \forall x (0 + x = x \rightarrow 0 + S(x) = S(x))) \rightarrow \forall x.\,0 + x = x$

$\endgroup$
2
$\begingroup$

Suppose $\mathcal{M}$ is a model of the second-order theory of arithmetic. Then all subsets of the domain of $\mathcal{M}$ satisfy the axiom of induction.

In the first-order theory, however, we have a first order axiom for every definable subset of the domain of $\mathcal{M}$. We are given a signature, which is often chosen to include the successor function $S$, addition, multiplication, the constant $0$, the order relation, and equality. With this fixed vocabulary and the logical symbols we can build formulae (in one free variable and zero or more parameters).

Then for each of these formulae we have an induction axiom from our axiom schema:

$$ \forall p_1 \cdots \forall p_k \,.\, (F(0,p_1,\ldots,p_k) \wedge \forall x \,.\, F(x,p_1,\ldots,p_k) \rightarrow F(Sx,p_1,\ldots,p_k)) \rightarrow \\ \forall x \,.\, F(x,p_1,\ldots,p_k) \enspace, $$

where $p_1, \ldots, p_k$ are the parameters. For each valuation of the parameters, each formula defines a subset of the domain of a model. The same subset may have multiple definitions. The subset described by a formula for a given valuation of the parameters obviously depends on the structure, and in particular on the interpretation of the elements of the signature, but the set of axioms generated by the axiom schema does not.

The weakness of the first-order formulation comes from there being countably many formulae. Hence the axiom schema cannot cover all the uncountably many subsets of the domain.

$\endgroup$
2
  • $\begingroup$ Why are there only countably many formulae? $\endgroup$ Commented Apr 4, 2017 at 3:06
  • 3
    $\begingroup$ @justin - Because all the formulas are finite strings from a finite "alphabet"; you can actually code each formula as a unique natural number, giving you an injection from formulae to natural numbers. $\endgroup$ Commented Apr 4, 2017 at 3:19
1
$\begingroup$

From Wolfram MathWorld, the principle of induction is stated as follows (with minor edit):

If a set P of numbers contains zero and also the successor of every number in P, then every number is in P.

More formally:

$$\forall P\subset N:[0\in P \land \forall x\in P: S(x)\in P \implies P=N]$$

where $S$ is the usual successor function given by Peano's Axioms.

This version implicitly quantifies over subsets of $N$. It is not an axiom schema. The property in question is handled by an axiom of set theory -- the axiom schema of separation -- that allows for arbitrary subsets of any given set, the set $N$ in this case.

Example: Suppose you want to prove the no number is its own successor. Applying the axiom schema of separation, we can then construct the subset $P=\{x\in N: S(x)\ne x\}$ and apply the induction principle to prove that $P=N.$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.