Skip to main content
58 votes

Why does induction have to be an axiom?

If you're looking at the Peano axioms for Arithmetic, and by 'the other axioms' you mean: $1. \bf{\forall x \ \neg s(x) = 0}$ $2. \bf{\forall x \forall y (s(x) = s(y) \rightarrow x = y)}$ $3. \bf{\...
Bram28's user avatar
  • 101k
52 votes
Accepted

Difference between provability and truth of Goodstein's theorem

Good question! If you were to consider the system PA + $\neg$G, wouldn't G still hold in the sense that you could never find a counterexample? This gets at an important subtlety here - the issue ...
Noah Schweber's user avatar
44 votes
Accepted

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

Peano arithmetic is a first-order theory, and therefore if it has an infinite model---and it has---then it has models of every cardinality. Not only that, because it has a model which is pointwise ...
Asaf Karagila's user avatar
  • 397k
38 votes
Accepted

How does Peano Postulates construct Natural numbers only?

Yes, you can find other sets on which a successor function is defined that satisfies all the Peano axioms. What makes the natural numbers unique is that you can use the Peano postulates to prove ...
Ethan Bolker's user avatar
  • 97.7k
36 votes
Accepted

Do we have to prove how parentheses work in the Peano axioms?

In formal language theory (most relevantly, context-free languages), there is the notion of an abstract syntax tree. A decent chunk of formal language theory is figuring out how to turns flat, linear ...
Derek Elkins left SE's user avatar
36 votes
Accepted

Can Peano arithmetic prove the consistency of "baby arithmetic"?

$\mathsf{PA}$ has a very interesting property, namely that it proves the consistency of each of its finitely axiomatizable subtheories. This is usually called the reflection principle for $\mathsf{PA}$...
Noah Schweber's user avatar
27 votes
Accepted

Is there a nonstandard model of Peano's arithmetic where any element has only finitely many prime divisors?

There is no such model. The following is a theorem of Peano arithmetic: For every number $n$, there is some number $n'$ that is divisible by all $k < n$. Consider a non-standard model $\langle \...
Z. A. K.'s user avatar
  • 11.7k
23 votes

Statement provable for all parameters, but unprovable when quantified

Great question! Yes, there are specific examples. One of the most famous is Goodstein's theorem. If $A(n)$ is the statement that Goodstein's sequence starting at $n$ terminates, then it is known (via ...
Caleb Stanford's user avatar
20 votes
Accepted

Statement provable for all parameters, but unprovable when quantified

Possibly the easiest example is to let $A(x)$ say that $x$ is not the Gödel number of a proof of $0=1$ from the axioms of PA. Because there is no such proof, $A(0)$ is true, $A(1)$ is true, etc., ...
Carl Mummert's user avatar
  • 82.1k
20 votes

Difference between first and second order induction?

The informal statement of induction is: For any property $P$ of natural numbers, if $P(0)$ holds, and $P(n)$ implies $P(n+1)$ for all $n$, then $P(n)$ holds for all $n$. Of course, this raises ...
Alex Kruckman's user avatar
19 votes
Accepted

Presburger arithmetic

Presburger arithmetic is clearly consistent - it has a model (namely, $\mathbb{N}$, or more precisely $(\mathbb{N}; +)$). So there's not much to say there. Meanwhile, it is a recursively axiomatizable ...
Noah Schweber's user avatar
19 votes

Why does induction have to be an axiom?

The Peano Postulates describe what we want the natural numbers to look like. One thing we want is for the natural numbers to be one continuous stream ...
I. J. Kennedy's user avatar
19 votes

Peano axiom of induction with "no junk"

The set of all the dominoes in the picture satisfies axioms 1-8. (The caption says this, if properly interpreted. The dark dominoes by themselves do not satisfy axiom 8. They satisfy axiom 1 only if ...
Michael Weiss's user avatar
16 votes
Accepted

Is it a paradox if I prove something as unprovable?

Unprovable ≠ Undecidable. If PA can prove neither the conjecture nor its negation, it is undecidable in PA. If you ever prove such a result, you certainly cannot be working within PA, because PA ...
user21820's user avatar
  • 59.2k
16 votes

What's the relationship between ZFC and Peano axioms? Are they overlapping, complementary or separate?

The two system are not related in a direct way. Peano axioms come to axiomatize arithmetic, whereas Zermelo–Fraenkel (with or without choice) come to axiomatize the properties of the set theoretic ...
Asaf Karagila's user avatar
  • 397k
16 votes
Accepted

Confusion about Löb's theorem

Say that the formal system is $\sf PA + \lnot Con(PA).$ Then the system proves every statement is provable in $\sf PA$, but surely it doesn't prove every statement (unless it is inconsistent, which by ...
spaceisdarkgreen's user avatar
15 votes

Difference between provability and truth of Goodstein's theorem

It's important not to conflate the system PA with the natural numbers themselves. There are other "nonstandard" models of PA: sets other than the natural numbers that admit definitions of $\{S,+,×\}$ ...
Gregory J. Puleo's user avatar
14 votes

Are there natural numbers that are not the descendant of 0?

The induction axiom ensures that $\Bbb N$ cannot contain a cycle like your $a,b,c$ cycle. It says that if $0\in A$, and for each $n\in\Bbb N$, $n\in A$ implies that $n+1\in A$, then $A=\Bbb N$. ...
Brian M. Scott's user avatar
14 votes
Accepted

Why are we using first-order logic and how to fix PA?

The boundaries of our ability to "fix" things are set by Gödel's incompleteness theorem. Contrary to what you seem to be assuming, this theorem is not really specific to first-order logic -- it tells ...
hmakholm left over Monica's user avatar
14 votes
Accepted

How Can the Peano Postulates Be Categorical If They Have NonStandard Models?

There are two different versions of "Peano arithmetic": a first-order version and a second-order version. The second-order version has as its induction axiom the statement that for any subset $S$ of ...
Eric Wofsey's user avatar
13 votes
Accepted

Is there a 'nice' axiomatization in the language of arithmetic of the statements ZF proves about the natural numbers?

While not part of the question itself, I think it's worth noting that there is a huge gap between "model satisfying the arithmetic consequences of $\mathsf{ZFC}$" and "some model of $\...
Noah Schweber's user avatar
13 votes

Who first proved Peano Arithmetic is not finitely axiomatizable?

In 1952 Czesław Ryll-Nardzewski proved that first order PA is not finitely axiomatizable. The proof uses nonstandard models. Andrzej Mostowski proved the same result (also in 1952) but without using ...
Thorsten Elof's user avatar
13 votes

Do we have to prove how parentheses work in the Peano axioms?

Short version: you're right, there is a serious issue here, and it comes down to the exact rules we use to form terms. You've phrased it in terms of trivialization ("doesn't this reduce the proof of ...
Noah Schweber's user avatar
13 votes

Can Peano Arithmetic show that the Continuum Hypothesis is Independent of ZFC?

Yes, the independence result is provable in PA (and even weaker theories). The usual proofs are phrased in terms of models, for better human comprehension, but they can also be phrased as purely ...
Andreas Blass's user avatar
12 votes

Is every true statement about the natural numbers provable in ZFC?

Not really. The statement "$\sf ZFC$ is consistent" can be translated into a statement about the natural numbers in the standard coding way, it's even a $\Pi_1$ statement as far as $\sf PA$ is ...
Asaf Karagila's user avatar
  • 397k
12 votes

George Boolos and Gödel's Second Incompleteness Theorem

While $2+2=4$ seems like an easy target for a way to prove $2+2\neq 5$, you're implicitly assuming that $4\neq 5$ and that $4=5$ cannot be proved. But if arithmetic is inconsistent, you can prove that ...
Asaf Karagila's user avatar
  • 397k
12 votes
Accepted

Formally how do we view finite sets

This is actually very subtle, in fact IMO one of the most underrated subtleties to come out of mathematical logic. To get the unsurprising part out of the way first, the way we do it is, as you ...
spaceisdarkgreen's user avatar
11 votes

Can Peano Arithmetic show that the Continuum Hypothesis is Independent of ZFC?

As Andreas says, it is in fact provable in PA and even much weaker theories - the difficulty of course being how to remove the "semantic" content. However, it's worth noting that we can show ...
Noah Schweber's user avatar
11 votes

Why does induction have to be an axiom?

Ultimately the way we prove (usually) that a given axiom $\alpha$ isn't already a consequence of a set of axioms $T$ is by constructing a model (I've linked to a formal definition, but you should skip ...
Noah Schweber's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible