2

An inductive set is a set $I$ such that $1 \in I$ and if $x \in I$ then $x+1 \in I.$

Some authors define the set of all integers $>0$ as the smallest inductive set, say Apostol's Analysis. But I am wondering, how to prove that the set of all integers $>0$ is indeed the smallest inductive set under, say the Peano axioms?

Yes
  • 20,719
  • The problem is that you haven't defined integers, and PA alone only 'knows' about natural numbers. – user21820 Mar 21 '15 at 11:59
  • @user21820: Would you mind thus help me edit the question to make it more clear? Or are you suggesting that in such a case it is impossible to give a proof? – Yes Mar 21 '15 at 12:00
  • 1
    Well you can look at Lord_Farin's answer. Basically you have to decide what you mean by integers (smallest ring with characteristic zero? equivalence classes of pairs of naturals? something else?) and how your PA is represented (quantified over everything? only over naturals?) and what are naturals (everything in the domain of discourse? or just one class of objects?). In some cases the answer would be trivial and in others not so. – user21820 Mar 21 '15 at 12:20

2 Answers2

3

Perhaps the most useful way out of this problem is to say it cannot be done.

For, on the one hand, we have a construction of $\Bbb N_{>0}$ given some ambient structure (usually $\Bbb R$ as a complete ordered field) where we have defined $1$ and $+$.

On the other, we have a completely axiomatic description of what $\Bbb N$ is (the distinction between $\Bbb N$ and $\Bbb N_{>0}$ is not really material).

Because the definition of "inductive set" is particular to the former situation, we cannot expect it to carry over to the second because it refers to some ambient properties that we cannot describe using Peano's Axioms.

We can, of course, verify that the construction satisfies the axioms (this is actually an important step in establishing the usefulness of this construction of $\Bbb N$ in $\Bbb R$).

We could also go from $\Bbb N$ and build up $\Bbb Z, \Bbb Q, \Bbb R$, define $1$ and $+$ on this $\Bbb R$ (after having proved it is a complete ordered field), and then reconsider the problem, but this seems to me like a pointless circular exercise.

Lord_Farin
  • 17,743
0

Let $X$ be a Dedekind-infinite set. Then, by definition, there exists $f:X\to X$ such that $f$ is injective but not surjective.

Since $f$ is not surjective, there exists $x_0 \in X$ such that $\forall y\in X:f(y)\ne x_0$. It is then possible to extract a subset $I\subset X$ such that $(I,f,x_0)$ satisfies the Peano Axioms where $f$ is used as the successor function, and $x_0$ as the zero (first element). $I$ will be the smallest subset of $X$ such that $x_0\in I$, and if $x\in I$ then $f(x)\in I$.

Note, too, that all ordered triples $(N,S,0)$ that satisfy the Peano Axioms are order-isomorphic, i.e. they are essentially identical in structure and size. In some sense then (you will have to tweak your definition a bit), the set of natural numbers is the smallest inductive set.

Dan Christensen
  • 14,529
  • Why did you use a Dedekind-infinite set in your argument. I am confused about the motivation here. Is a Dedekind-infinite set's existence guaranteed by the Zermelo axioms? I am familiar the definition of Dedekind infinite, e.g. a set is Dedekind-infinite iff it is equipollent to a proper subset of itself. – john Feb 07 '23 at 14:01
  • @john These are equivalent definitions. I have found my version to be much easier to use in formal proofs. – Dan Christensen Feb 08 '23 at 01:07