# Tag Info

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

### 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 ...

### 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 ...
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 ...

### 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 ...
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 ...
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 ...

### 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,+,×\}$ ...

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

### 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 ...

### 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 ...
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

### 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 ...
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 ...

### 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 ...