3
$\begingroup$

I am investigating this claim "The Peano axioms don't imply a countable set of natural numbers". I think the truth of it depends if we you use First order logic or second order logic. In first order logic, the answer is positive and in second order logic the answer is negative due to axiom of induction.

But, now my problem is what does countable here mean?

In my basic mathematics course, we defined it as the set having a bijection of the set with the natural numbers, but I think to use this definition here, we need a concept of natural numbers, which is to me, no longer clear.

Relevant:

  1. What is an example of a non standard model of Peano Arithmetic?

  2. Uncountable models for integers

$\endgroup$
4
  • $\begingroup$ The standard natural numbers (which is the "beginning" of every model) are still well defined in first order Peano. $\endgroup$ Commented Oct 28 at 8:14
  • 2
    $\begingroup$ "The Peano axioms don't imply a countable natural numbers" doesn't make sense, because "countable" by definition means the cardinality of natural numbers. Just there are several models of the Peano axioms, with very different cardinalities. $\endgroup$ Commented Oct 28 at 8:57
  • 1
    $\begingroup$ Clemens, there is a key ambiguity in the formulation of your question. You say you are "investigating this claim 'The Peano axioms don't imply a countable natural numbers'." This is ungrammatical. Did you mean to say "a countable set of natural numbers"? $\endgroup$ Commented Oct 28 at 9:37
  • $\begingroup$ Historically, model theory was developed soon after Cantor's naive set theory became mainstream - so that's the backdrop they were leaning on. $\endgroup$ Commented Oct 28 at 10:37

2 Answers 2

Reset to default
13
$\begingroup$

When X is a concept in widespread mathematical use, the answer to the question "What do model theorists mean when they talk about X?" is always going to be "Exactly what all other mathematicians mean when they talk about X." Model theorists do mathematics in exactly the same way (with the same foundations) that number theorists and topologists do.

So: to a model theorist, "$A$ is countable" means "$A$ can be put in bijection with $\mathbb{N}$".

The root of your question is an unfortunate ambiguity in the quoted claim. (Where did you find it, by the way? You should always cite your sources.)

The correct interpretation of "The Peano axioms don't imply a countable set of natural numbers" is "There exists a model of $\mathsf{PA}$ (the first-order theory Peano Arithmetic) which is not countable". That is, there exists $N\models \mathsf{PA}$ such that there is no bijection between $N$ and $\mathbb{N}$. This is a precise mathmematical statement - there's no circularity here. Maybe it seems circular to you because you think that the point of the theory $\mathsf{PA}$ is to define $\mathbb{N}$? This is a misconception. Theories don't define structures, they only describe their properties. At most, they can characterize them uniquely up to isomorphism, but first-order logic can only do that when the structure is finite. Model theorists have access to $\mathbb{N}$ (e.g. defined in set theory as the least inductive set) just like all other mathematicians.

You are correct, by the way, that there is a second-order theory $\mathsf{PA}_2$ such that (when we use the standard semantics for second-order logic) $\mathbb{N}$ is the unique model of $\mathsf{PA}_2$ up to isomorphism. In this case, instead of "The second-order Peano axioms imply a countable set of natural numbers", it would be more precise to say "Every model of the second-order Peano axioms is countably infinite".

$\endgroup$
-1
$\begingroup$

In set theory, a set $X$ is said to be countable if there exists an injective function $f: X \to N$. By this definition, $N$ is itself trivially countable since we have the injective function $f: N \to N$ such that $f(x)=x$. You don't need induction to prove this.

$\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.