# Tag Info

## Hot answers tagged peano-axioms

• 9,185

### 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.3k
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., ...
• 80.6k

### 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,980

### 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,487
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 ...
• 237k

### 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 ...
• 72.3k
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 ...
• 56k
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

### 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,383

### 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$. ...
• 609k

### 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 ...
• 388k
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 ...
Accepted

• 388k

### 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 ...
• 237k