I am reading "Set theory, logic and their limitations" by Moshe Machover (page 264).

If $\mathfrak {^*N}$ is an $\mathcal L$-structure and $X$ is any subset of $^*N$, we say that $X$ is inductive in $\mathfrak {^*N}$ if it satisfies the condition:

If $^*0 \in X$, and for every $x \in X$ also $^*s(x) \in X$, then $X =$ $^*N$

It goes on to say that the Principle of induction states that every subset of $N$ is inductive (in the standard interpretation).

However, this definition seems a bit different from some other definitions I've seen that seem to remove the "if" qualifier?


1 Answer 1


I do not "see the problem".

See Derek Goldrei, Classic set theory (1996), page 39 :

Definition. The set $y$ is inductive if $\emptyset \in y$ and $x^+ \in y$ whenever $x \in y$.

Machover's definition amout to saying that a subset $X$ of $^*N$ is inductive in $\mathfrak {^*N}$ iff $X =$ $^*N$.

In other words, every subset $X$ of $^*N$ which contains $0$ and is closed under the "operation" of successor is equal to $^*N$ itself.

And this "fit with" Remark (ii) : The Principle of Induction says that every subset of $N$ is inductive in $\mathfrak {N}$.

From Remark (i) we have that : all instances of the induction postulates 13.1 hold in $\mathfrak {N}$ iff all sets that are parametrically definable in $\mathfrak {N}$ are inductive in $\mathfrak {N}$.

But we must consider the "limitation" in Remark (iii) : first-order induction postulates only manage to state (under the standard interpretation) the inductiveness of subsets of $N$ that are parametrically definable in $\mathfrak {N}$. However, there are only denumerably many such subsets of N [while, by Cantor's Thm, there are uncountably many subsets of $N$].


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .