# Induction versus Natural Numbers

$0$ is finite. If $n$ is finite, then $n+1$ is finite. Hence, by induction, all numbers are finite. What is the catch?

-
Huh? There's no catch. All natural numbers are finite. The set of all natural numbers is not finite, which is what the axiom of infinity is concerned with. – George Lowther Aug 21 '10 at 22:01
I edited to remove reference to axiom of infinity. I guess I thought there was such a thing as an infinite number; perhaps that's not the case; if so, my mistake... – Grigori Strassmann Aug 21 '10 at 22:35
Sure there are infinite numbers, but there are different types: cardinals, ordinals, surreals, hyperreals, and probably more. I interpreted your question more easily with the original title because it seemed clear that you were talking about cardinals. – Dan Brumleve Aug 21 '10 at 23:50
@GrigoriStrassmann You should try and think over these type of questions by yourself. It'll prove much more useful. – Pedro Tamaroff May 8 '12 at 1:18
@Stahl: Is there an actual point to bumping all those two and a half years old threads? It's taking up precious space from the front page. Please limit yourself to one or two edits at most per several hours. – Asaf Karagila Mar 23 '13 at 20:20

You have to be careful with your wording in this type of question. There is more than one type of number. Usually, what is being referred to is clear from the context, but here it is not. Natural numbers (0,1,2,3,...,etc) are all finite, and standard induction only applies to these.

There are other types of numbers, such as cardinal numbers and ordinal numbers which can be infinite. The principle of induction does not apply to these. There is an extension of induction, called transfinite induction. On top of showing that the desired property holds for n+1 whenever it holds for n, transfinite induction also involves proving that the property holds in a limiting sense. The property of being finite does not survive this limit, so there is no problem with having infinite ordinal numbers.

Usually when someone says number without being clear about what they are referring to, they mean natural numbers, integers, real numbers or, possibly, complex numbers. In that case, there are no infinite numbers.

This is not the kind of thing which should cause problems in a serious mathematical discussion, but I've seen this ambiguity create confusion many times before on internet forums.

-

You might call each natural number finite (that's what induction applies to). Wait until you hear about these, though.

EDIT: As the comment to the question points out, the natural numbers are collectively infinite in number, if that's what you're referring to.

-
Well, so there is no issue with infinite sets of natural numbers. How about one singe infinite natural number? What's the problem with the inductive reasoning that all individual numbers are finite? Those inaccessible cardinals are interesting. How can I construct one of those? – Grigori Strassmann Aug 21 '10 at 22:17
There are no infinite natural numbers. – Qiaochu Yuan Aug 21 '10 at 22:34

The Axiom of Infinity may be relevant to your understanding, because it concerns the existence of an infinite set, which is also an infinite cardinal number. Without it all sets are finite and equivalent to natural numbers, for the reason that you state (induction is not powerful enough). Starting with Cantor's Theorem you can build even larger cardinals by taking the power set of the infinite set asserted to exist by the Axiom of Infinity. There is also a technique called transfinite induction which is used to prove propositions about ordinals and cardinals.

http://en.wikipedia.org/wiki/Transfinite_induction

-

I'll approach this from a naive set theory standpoint, since it can easily be translated to other contexts. If we define zero as the empty set, and n+1 as (n)\union{n}, then we let the natural numbers be the set of all of these (yes, we need an axiom to guarantee its existence). In this case we define a set as finite iff it can be put in bijection with an element of the natural numbers. The key here is that 'finite' is just so defined that the statement that natural numbers (meaning the elements of the natural numbers) are finite is wholly trivial. This of course is only talking of finitude from the perspective of cardinallity.

Since finitude is often used to refer to other properties, being 'finite' means something distinct and often not logically related (e.g. as in points in an affine subspace of a projective space, as something being bounded, or as select elements of an algebraic structure), this question could be improved by specifying what you mean by 'finite'.

-
I think that it follows from the first order induction schema that all elements of your set of natural numbers will satisfy the same formulas as elements of the "official" natural numbers defined by the PA axioms. And of course you are right, since we use first-order logic nearly exclusively, we define "finite" by reference to an element of the "natural numbers". However, even your construction of the natural numbers can't prevent that your set will contain infinite numbers for certain nonstandard models of PA. – Thomas Klimpel May 8 '12 at 1:27
@ThomasKlimpel What do you mean by infinite numbers? I believe that there is no way of restricting the above described set so that it only contains elements which can be arrived at by "adding ones finitely many times" in an intuitive sense. Hence, non-standard models of PA. But my point above is merely that the statement that 'positive whole numbers are finite' is an entirely trivial consequence of definitions. – J. David Taylor Dec 16 '12 at 23:08
An infinite number is one which is not finite in the intuitive sense. As you describe, a number is finite in the intuitive sense, if it can be arrived at by "adding ones finitely many times". Anyway, I slightly changed my mind about these issues, because I learned that first-order logic can define the set of non-standard natural numbers. It's only unable to define the negation of this property. – Thomas Klimpel Dec 17 '12 at 10:48

An interesting catch here is that the proposition "n is finite" cannot be expressed by a unary predicate "p(n)" in first-order logic. The first order induction schema (from the Peano axioms) only applies to unary predicates in first-order logic, hence you cannot prove that every natural number is finite, at least not with the first-order Peano axioms.

-
Which is why there are nonstandard models of PA. – Quinn Culver May 8 '12 at 0:41
@QuinnCulver I just couldn't help to point out that there really is an interesting catch in the proof of the OP. – Thomas Klimpel May 8 '12 at 1:45
"n is finite" is a unary predicate on natural numbers in the first-order Peano arithmetic: the always true one. What you're observing is that a non-standard model does not map this internal notion of finiteness to an external notion of finiteness that references the standard natural numbers. – Hurkyl May 8 '12 at 2:12
@Hurkyl If "n" is finite, then "n satisfies a first order formula of the type n=S(S(...(S(0))...))". So if "n" is finite and given explicitly, it can be proved that it is indeed finite. If "n" doesn't satisfy any first order formula of the type "n=S(S(...(S(0))...))", then it isn't finite, but you can't necessarily prove (within the given axiom schema) that this is indeed the case. You can prove that all finite numbers are natural numbers. You may use the predicate "n is a natural number" as a convenient substitute for the non-existent predicate "n is finite". – Thomas Klimpel May 8 '12 at 6:15
"n is a natural number" is not just a convenient substitute for "n is finite"; it's more or less the usual definition of what "___ is finite" means when applied to natural numbers. It's just as misleading to say that first-order Peano arithmetic doesn't have a unary "n is finite" predicate as it would be to say that first-order ZFC has neither a "P is the power set of S" binary predicate nor a "S is uncountable" unary predicate. – Hurkyl May 8 '12 at 6:52