Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
875
questions
0
votes
1
answer
245
views
Unconventional models and Peano Arithmetic
I'm trying to show that $\mathbb{Z}[x]^+ \models \mathsf{PA}^-$. What are the initial segments of this model?
- 1,139
3
votes
1
answer
187
views
Can An Axiom Schema be Independent?
Consider the following theory: Ring Theory (RT) + $\forall x(Sx=x+1)$ + first order induction (Ind). The finite rings $Z/nZ$ are models of this theory. Now consider RT + $\forall x(Sx=x+1)$ + Not(Ind)....
- 1,245
16
votes
2
answers
3k
views
How does (ZFC-Infinity+"There is no infinite set") compare with PA?
How does (ZFC-Infinity+"There is no infinite set") compare with (first order) PA? Intuitively, neither theory should be more powerful than the other.
- 66.1k
1
vote
1
answer
925
views
Gödel, Escher, Bach: $ b $ is a power of $ 10 $.
I’d like to verify if my formula correctly expresses that a number is a power of $ 10 $, using the $ \sf{TNT} $ language provided by Hofstadter in his famous book Gödel, Escher, Bach: An Eternal ...
- 51
38
votes
2
answers
8k
views
How is exponentiation defined in Peano arithmetic?
How would exponentiation be defined in Peano arithmetic? Unless $n$ is fixed natural number, $x^n$ seems to be hard to define.
Edit 2: So, what would be the way to define $x^n+y^n = z^n$ using $\...
- 799
7
votes
3
answers
859
views
Nonstandard models of Presburger Arithmetic
I have a question about nonstandard models of Presburger Arithmetic. I read that an example of a nonstandard model is the set of polynomials with rational coefficients with positive leading ...
- 71
1
vote
1
answer
90
views
Does adjoining an induction schema to a theory of arithmetic interact nicely with adjoining its consistency statement?
I'm struggling to articulate this question, but here it goes.
For any first order theory $T$ involving a unary function symbol $S$ (intuitively, the successor function), let $I(T)$ denote the theory ...
- 66.1k
2
votes
2
answers
699
views
How to prove that $+$ is commutative on the natural numbers?
Let $N$ be a non empty set. Let $s:N\to N$ a function satisfying:
there is only one element in $N-s(N)$ (denoted by $1$);
$s$ is injective;
for any subset $X\subset N$, if $1\in X$ and $(n\in N \...
- 6,218
3
votes
0
answers
375
views
Why Does Induction Prove Multiplication is Commutative?
Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2).
GA has second order induction and a single successor axiom:
$$\forall x \forall y \forall z\bigr((...
- 1,245
5
votes
1
answer
266
views
Complete induction in the Peano system
Is complete induction valid in the Peano model of the naturals and why. In more detail if $L$ is the first order language $\{ +, \cdot, 0, <,S\}$ and $T$ is the theory with non-logical axioms
$$...
- 4,213
2
votes
1
answer
310
views
Can we apply a successor operation in Peano's arithmetic infinitely many times, is the successor well defined?
If we look at the axioms of Peano arithmetic, e.g. http://mathworld.wolfram.com/PeanosAxioms.html, they contain an axiom:
If $a$ is a number, the successor of $a$ is a number.
However, the axioms do ...
- 2,747
5
votes
2
answers
505
views
Sequent calculus and first incompletness theorem
Wikipedia says that sequent calculus is sound and complete (http://en.wikipedia.org/wiki/Sequent_calculus#Properties_of_the_system_LK). Godel first incompleteness theorem says that system capable of ...
- 2,352
2
votes
2
answers
400
views
Are all models of peano arithmetics descibed using first order logic non standard?
It is known that there are non-standard models of Peano Arithmetics when it is described using first order logic. My question is if there is standard model (one which does not contains non-standard ...
- 2,352
2
votes
1
answer
112
views
Find the representation in Peano system
It's known that all recursive functions are representable in Peano arithmetic. I am trying to find representation of subtraction function
$f(x,y)= \left\{\begin{matrix}
x-y &if& x>y\\
0 &...
- 4,653
1
vote
0
answers
194
views
Ring Theory and Induction
Andrew Boucher has developed a theory called General Arithmetic (GA): http://www.andrewboucher.com/papers/ga.pdf
GA is a sub-theory of Peano Arithmetic (PA). If we add an induction schema (IND) to ...
- 1,245
1
vote
2
answers
529
views
Closed under equality
In the Wikipedia article on "Peano axioms" I read this (source):
For all $a$ and $b$, if $a$ is a natural number and $a = b$, then $b$ is also a natural number. That is, the natural numbers are ...
- 111
0
votes
1
answer
265
views
How is The strengthened finite Ramsey theorem known to be true for natural numbers?
http://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem states that independence of "The strengthened finite Ramsey theorem" from PA is proved by implying consistency of PA.
But how do we know ...
- 101
2
votes
3
answers
107
views
showing $\nexists\;\beta\in\mathbb N:\alpha<\beta<\alpha+1$
I want to prove that $\nexists\; \beta\in\mathbb N$ such that $\alpha<\beta<\alpha+1$ for all $\alpha\in\mathbb N$. I just want to use the Peano axioms and $+$ and $\cdot$
If $\alpha<\beta$ ...
user45389
5
votes
2
answers
3k
views
Is there a formal definition of "Greater Than"
Intuitively, one can say that $S(n) > n$. But how do we prove it using the Peano Axioms. It seems like I need a formal statement as to what $>$ means.
- 3,808
17
votes
1
answer
784
views
Is every model of modular arithmetic either even or odd?
Modular Arithmetic (MA) has the same axioms as first order Peano Axioms (PA) except $\forall x (Sx \ne 0)$ is replaced with $\exists x(Sx = 0)$.
(http://en.wikipedia.org/wiki/Peano_axioms#First-...
- 179
0
votes
1
answer
782
views
Peano's Postulates Proofs
How can I prove the following two questions:
Prove using Peano's Postulates for the Natural Numbers that if a and b are two natural numbers such that a + b = a, then b must be 0?
Prove using Peano's ...
- 139
4
votes
5
answers
730
views
Peano postulates
I'm looking for a set containing an element 0 and a successor function s that satisfies the first two Peano postulates (s is injective and 0 is not in its image), but not the third (the one about ...
- 63
4
votes
2
answers
1k
views
Induction as Peano Axiom
Let P be some proposition. If we have that $P(0)$ is true and that if $P(n)$ is true, then $P(S(n))$ is true, where $S(n)$ is the successor of natural number $n$. Then we have that $P(n)$ is true for ...
- 75
22
votes
4
answers
9k
views
Why is Peano arithmetic undecidable?
I read that Presburger arithmetic is decidable while Peano arithmetic is undecidable. Peano arithmetic extends Presburger arithmetic just with the addition of the multiplication operator. Can someone ...
- 645
27
votes
1
answer
1k
views
Is there a natural model of Peano Arithmetic where Goodstein's theorem fails?
Goodstein's Theorem is the statement that every Goodstein sequence eventually hits 0. It is known to be independent of Peano Arithemtic (PA), and in fact, was the first such purely number theoretic ...
- 48.8k