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,487
9
votes
How do Peano's axioms make it clear what the successor is equal to?
The general concept of an axiom system does not tell you what the objects are that it refers to, it tells you only properties of those objects and of the interactions between them. The axioms do not ...
- 115k
7
votes
In the Peano Axioms, how do we know that the successor of a natural number $n$ is $n + 1$? (It's never explicitly stated that it should be "$+1$")
1 is defined as $S(0)$, where $S$ denotes the successor function. The relevant convention does not concern what is known about numbers, but only what we call them. Of course, our preconceptions about ...
- 237
7
votes
Peano axiom of induction with "no junk"
The idea is that the first $8$ axioms describe natural numbers together with some possible "junk". Those junk may have various forms.
Axioms 1–8 are also satisfied by the set of all light ...
- 13.2k
6
votes
Accepted
Can Goodstein's theorem be false in some model of Peano arithmetic? How?
I think it's helpful to consider $(i)$ a simpler statement than Goodstein's theorem and $(ii)$ a weaker theory than $\mathsf{PA}$. The reason for the former is that Goodstein's theorem has lots of ...
- 237k
6
votes
Accepted
How do Peano's axioms make it clear what the successor is equal to?
`how do we know that the successor of $1$ is $2$ based on Peano's axioms'
$2$ is defined to be the successor of $1$, so $2=1'$. Define addition by the following two rules:
$x+1=x'$
$x+y'=(x+y)'$
So, ...
- 4,714
5
votes
Accepted
Gödel's second incompleteness theorem and Consistency.
You're right that a $T$-proof of the consistency of $T$ itself isn't very compelling (although if $T$ purports to be able to resolve all arithmetical questions then via Godel coding this is something $...
- 237k
5
votes
Accepted
What ZF can do and Peano's axiom cannot.
[I'm a little surprised this isn't a duplicate. But I looked through "[peano-axioms] ZF" on MSE and "[theories-of-arithmetic] ZF" on MO, and couldn't find anything. I also couldn't ...
- 8,487
5
votes
Accepted
Representability of Goodstein function in PA
Strong representability (in a given theory) does not imply provable totality (in that theory). Specifically, a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is strongly representable in an appropriate ...
- 237k
5
votes
Does the property $T\vdash Pvbl_T(\ulcorner \sigma \urcorner) \implies T\vdash \sigma$ apply to set theories?
This is ultimately an arithmetic soundness assumption on the theory. For instance, it fails for $\sf PA+\lnot Con(PA),$ or any other theory that is consistent but proves its own inconsistency.
There’s ...
- 55.5k
4
votes
Proof by induction without using inductive hypothesis / Peano Axioms
The implicit assumption here is that if
$P(0)$ is true, and
$P(a)$ is true implies that $P(a + 1)$ is true for any natural $a$,
then $P$ is true over all naturals (including $0$). Notice that ...
4
votes
Proof in Peano Arithmetic
Maybe some intuition for how the addition and multiplication axioms work will help.
Axioms 3 and 4 are a recursive definition of addition: for evaluating $x+y$, they either tell you the answer (if $y=...
- 134k
4
votes
What is the mathematical definition of "standard arithmetic/standard natural numbers"?
Your use of the word "intuitive" means that we're entering philosophical waters.
In ZFC, as you know, one can prove the formal version of the assertion "there is, up to isomorphism, ...
- 8,487
4
votes
First order theories stronger than PA
We have to distinguish between superficially different theories, and theories that are "essentially different".
For example, you ask about adding exponentiation to PA. As noted in the ...
- 8,487
4
votes
Accepted
How do Robinson arithmetics axioms prevent this model of N?
This image is really only about how the successor function behaves, so is more suitable to a discussion of the Peano axioms than to a discussion of Peano Arithmetic. But more to the point: in order to ...
- 55.5k
4
votes
If Goldbach's conjecture G is undecidable in PA, then can we prove $\mathbb N\models G$?
If we could prove (in any given system) that $G$ is undecidable in PA, then we could prove there that it is true. But it is quite possible that $G$ happens to be undecidable (and true) but there is ...
- 437k
4
votes
Accepted
Are the natural numbers definable in ZFC-Inf
Yes. If $\mathfrak{M}\models\mathsf{ZF}$-$\mathsf{Inf}$, the "natural numbers of $\mathfrak{M}$" are the things which $\mathfrak{M}$ thinks satisfy the following formula:
$\nu(x):\quad$ $x$ ...
- 237k
4
votes
Is there a concept of finiteness independent of the successor function?
We can use the definition of Dedekind infinite to avoid appealing to "foreverness" or the successor function. To do this we say a set $S$ is infinite if there exists some $S' \subsetneq S $ ...
- 10.3k
3
votes
Accepted
Extending a Model of $ T + \operatorname {Con} ( T ) $ to a model of $ T + \neg \operatorname {Con} ( T ) $
The answer is yes.
Suppose $T$ is as above, $\mathfrak{M}\models T$, and $\mathfrak{M}$ has no extension to a model of $T+\neg Con(T)$. Then by compactness, we can extract an existential sentence $\...
- 237k
3
votes
Accepted
Proof in Peano Arithmetic
You are going in the right direction. For your next step, note that $S0 \times S0$ is equal to $S0 \times 0 + S0$ by axiom 6, which in turn is equal to $0 + S0$ by axiom 5. Now you've gotten rid of ...
- 26.7k
3
votes
Accepted
Proof by induction without using inductive hypothesis / Peano Axioms
Writing the principle of induction in symbolic form helped me understand what's going on here.
$$
\left(P(0)\wedge\forall a\,(P(a)\Rightarrow P(a^{++})\right)\Rightarrow\forall a\,(P(a))
$$
In the ...
- 26.6k
3
votes
Accepted
Fifth Peano axiom — Properties of the natural numbers
We have an official way of writing PA that only uses a little more than a dozen different characters. They include the successor function, plus, and times. The induction axiom then accounts for all ...
- 372k
3
votes
Accepted
Presburger arithmetic is consistent, but relative to what?
You are right that there is no completely philosophically satisfying way to prove a foundational theory's consistency--however you prove it, that will just raise the question of the soundness of the ...
- 323k
3
votes
Accepted
Can exponentiation be defined in Robison's Q by use of the exponential Diophantine equation?
It's not really proper to speak of "definability in a theory." Definability really is a notion appropriate to structures: it does make sense to ask whether (for example) multiplication is ...
- 237k
3
votes
Accepted
Peano axioms and meaning of successor map in Jacobson's Basic Algebra I
The Peano axioms are a way to define the natural numbers; to introduce the concepts of addition when trying to define the natural numbers would be circular.
So: "for any $a$" means "for ...
- 177k
3
votes
If Goldbach's conjecture G is undecidable in PA, then can we prove $\mathbb N\models G$?
It is a theorem of $\sf PA$ that
$\lnot\mathsf{provable}_{\sf PA}(\mathsf{negation}(\ulcorner G\urcorner))\to G.$
When we work in set theory, "$G$" means (internally) the exact same thing ...
- 55.5k
2
votes
What is adding Con(PA) to PA good for?
This is not quite an answer but it is related. Gentzen showed that you can prove the consistency of PA using primitive recursive arithmetic together with transfinite induction up to a countable ...
- 409k
2
votes
Does Peano Arithmetic prove all identities involving addition, multiplication, and exponentiation?
There is strong evidence that the answer is yes.
What is known is that the set of identities in addition, multiplication, and exponentiation is computable. This is due to Macintyre, The laws of ...
- 237k
2
votes
In the Peano Axioms, how do we know that the successor of a natural number $n$ is $n + 1$? (It's never explicitly stated that it should be "$+1$")
The Peano Axioms are just that: a bunch of statements expressed in the language of first-order logic. And notice that they don't use the $1$ symbol, so you're right: how can we tell that $s(0)$ is ...
- 97.4k
2
votes
Proof of the Principle of Backwards Induction
To justify step 5, you would have to prove $\forall x \forall y (y \leq x ++ \to y \leq x \lor y = x++)$. This would need to follow from a definition of $\leq$, which you did not provide in your ...
- 30.8k
Only top scored, non community-wiki answers of a minimum length are eligible