Skip to main content

# Tag Info

## Hot answers tagged peano-axioms

58 votes

• 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 ...
• 46.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., ...
• 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 ...
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 ...
• 249k
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 ...
• 4,068
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 ...
• 8,963
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 ...
• 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 ...
• 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 ...
• 60.2k
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,473
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$. ...
• 619k
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 ...
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 ...
• 334k
13 votes
Accepted

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 $\... • 249k 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 ... 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 ... • 249k 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 ... 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 ... • 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 ... • 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 ... • 60.2k 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 ... • 249k 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 ...
• 249k

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