55
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{\...
- 95.8k
50
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 ...
- 231k
39
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 ...
- 384k
39
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 ...
- 87.1k
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 ...
- 24.4k
35
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}$...
- 231k
25
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 \...
- 7,928
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 ...
- 45.1k
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., ...
- 80k
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 ...
- 6,869
18
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
...
- 3,890
17
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 ...
- 231k
17
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 ...
- 68.9k
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 ...
- 55.4k
15
votes
Accepted
Why is the Axiom of Infinity necessary?
BrianO's answer is spot-on, but it seems to me you may not be too familiar with models and consistency proofs, so I'll try to provide a more complete explanation. If anything it may better steer you ...
- 904
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,+,×\}$ ...
- 6,363
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$. ...
- 604k
14
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 ...
- 384k
13
votes
How to express “b is a power of 10” – Typographical Number Theory in Gödel Escher Bach
how do you express “b is a power of 10”.
Since Rory already covered the problems with your approach, I'll tackle the question of finding a different solution.
In my first attempt to do so, I have ...
- 40.8k
13
votes
Accepted
How can addition be non-recursive?
Tennenbaum's theorem doesn't claim that your TM doesn't work inside the model (if its operation is suitably arithmetized in well-known ways).
It says that there cannot exists a TM that works outside ...
13
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 ...
13
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 ...
- 317k
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 ...
- 231k
12
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 $\...
- 231k
12
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 ...
- 121
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 ...
- 384k
12
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 ...
- 69.5k
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 ...
- 384k
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 ...
- 231k
Only top scored, non community-wiki answers of a minimum length are eligible