Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
0
votes
1answer
77 views
Is there an error in this proof the the “strong induction” theorem? Is this Escherian logic?
By set predicates, I mean the "tests for inclusion" used in defining sets. That may be more of a computer scientific than mathematical use of the the term predicate. I included predicate logic in ...
0
votes
1answer
42 views
Does $n^\prime\ne n^{\prime\prime}$ require proof by contradiction? $n^\prime$ is the successor of $n$.
This is the statement of Peano's axioms I will assume for this discussion:
$1$ is a number.
To every number $n$ there corresponds exactly one number $n^\prime.$
$n^\prime=m^\prime\implies n=m.$
$n^\...
0
votes
1answer
57 views
Is Peano's axiom of induction needed to show $n^\prime\ne n^{\prime\prime}$?
This is the statement of Peano's axioms I will assume for this discussion:
$1$ is a number.
To every number $n$ there corresponds exactly one number $n^\prime.$
$n^\prime=m^\prime\implies n=m.$
$n^\...
1
vote
1answer
36 views
Peano axioms: S(1)=1?
I was reading through the Peano axioms here, and a question came up:
Can we define $S(0)=1$, and $S(1)=1$?
It seems to me (at least as it is stated) that it would satisfy all of the axioms listed.
...
0
votes
1answer
32 views
Terminology: arithmetic vs. expressible vs. represented
A function $f:\mathbb{N}^k\rightarrow\mathbb{N}$ is arithmetic iff its graph is arithmetic, i.e., there is a formula $\psi(\vec{x},y)$ in the language of Peano arithmetic such that for all $\vec{a}$ ...
1
vote
2answers
47 views
Proof of cancellation law for multiplication of natural numbers.
The cancellation law for the multiplication of natural numbers is:
$$\forall m, n\in\mathbb N, \forall p\in\mathbb N-\{0\}, m\cdot p=n\cdot p\Rightarrow m=n.$$
Is it possible to show this using ...
5
votes
3answers
194 views
Are there “interesting” theorems in Peano arithmetic, that only use the addition operation?
More precisely, are there "interesting" theorems of Presburger arithmetic, other than the following four well-known "interesting" ones?
The commutativity of addition.
The theorem stating there are ...
0
votes
1answer
65 views
Do Gödel's incompleteness theorems apply to finitist axiomatic systems that reject the axiom of infinity?
I'm curious which axiomatic frameworks Gödel's incompleteness theorems apply. Do the theorems apply to any axiomatic system that adopts potential infinity? Or just to those that adopt completed ...
0
votes
2answers
89 views
Is it consistent for $P(\mathbb{N})$ to be present in a low layer of the Constructible Universe?
$ZF+V=L$ implies that $P(\mathbb{N})$, the power set of the set of natural numbers, is a subset of $L_{\omega_1}$. But my question is, is it consistent with $ZF$ if $P(\mathbb{N})$ is a subset of $L_{...
1
vote
0answers
49 views
In the extension to integers, how should this restriction on the domain of natural numbers be interpreted?
The book is now available on archive.org so if you are interested in looking at the original discussion, here it is:
Behnke, Bachmann, Fladt & Suss [Eds.] - Fundamentals of Mathematics Vol.1, The ...
1
vote
0answers
30 views
How is it shown using the additive cancellation law that $x\mapsto x+h$ has an inverse?
See Fundamentals of Mathematics, Volume 1 page 101, for context.
This is one of those facts that is so obvious that I find it difficult to prove. My question regards part of the proof of the ...
0
votes
1answer
24 views
How would I show that PA proves the godel sentence for PA implies Con(PA)
Started off with definitions:
godel sentence for PA is the sentence in PA that cannot be proved nor disproved
Con(PA) formalizes PA is consistent
We know godels first incompleteness theorem is ...
2
votes
1answer
35 views
Is this a valid proof that $\forall_{x,y}\left[x\ne y\implies x<y\lor x>y\right]$ in $\mathbb{N}_1$?
I do not consider the following to prove all of the so-called trichotomy of order, since I take that to be a statement that exactly one of $<.=,>$ holds for any given pair of numbers.
The ...
1
vote
1answer
36 views
First-order Peano arithmetic and (the lack of) implicit definition of addition
I'm trying to show, through the existence of non-standard models of arithmetic, that the first-order Peano axioms (without those of multiplication) don't implicitly define addition in the sense of ...
3
votes
1answer
96 views
Can we prove the Peano axioms from a type theoretic construction of the natural numbers?
Here are two quotes that, while not literally contradictory, reach conclusions that are opposite in spirit.
The first one states that the Peano axioms can be proven to hold for an explicit ...
2
votes
0answers
42 views
Is there a formal term for the algebraic structure equivalent to Thurston's hemigroup without identity? [duplicate]
This question is not a duplicated of https://math.stackexchange.com/a/3183330/342834 . It is a follow-on, asking about the distinction between the subject of that post, and the subject of this post.
...
2
votes
1answer
48 views
Decidability of Gödel sentences.
Letting $\text{Pr}(x)$ be a formula that weakly represents the set $\{x:x\text{ is a Gödel code of a provable sentence in PA}\}$, where PA means Peano Arithmetic.
Gödel's first incompleteness theorem ...
2
votes
4answers
126 views
In Peano's Axioms are the uniqueness of the successor and $x^{\prime}=y^{\prime}\implies{x=y}$ redundant?
In Peano's Axioms are the uniqueness of the successor and the property $x^{\prime}=y^{\prime}\implies{x=y}$ redundant?
This seems obvious to me, but I may be missing something. In the various forms ...
2
votes
1answer
47 views
Consistent theories that proves their own consistence
Restrict the whole question to first order logic only. Gödel second incompleteness theorem tell us that, if, for example, we are working with Peano language, every T (recursively axiomatized, ...
0
votes
3answers
86 views
What is the pitfall in the inductive “proof” of P(x):= x does not succeed 1?
The following statement of Peano's axioms appears in Fundamentals of Mathematics, Volume 1 Foundations of Mathematics: The Real Number System and Algebra; Edited by H. Behnke, F. Bachmann, K. Fladt, W....
0
votes
1answer
41 views
First Order Logic Peano arithmetic Proof
I'm trying to prove:
$\forall x\forall y((x=y)\longrightarrow(x\not<y)$
I tried starting off with
$u=v, u+s(z) = v\vdash u = v$
$u=v, u+s(z) = v\vdash u+s(z) = v$
.
.
.
$u=v, u+s(z) = v\vdash ...
2
votes
1answer
66 views
Peano axioms and commutativity of addition
I'm trying to prove the commutativity of addition in Peano arithmetic in something like a natural deduction system, but am stuck halfway (I say "something like a natural deduction system" because I ...
0
votes
4answers
132 views
Proving $a\ne{b}\implies{a<b}\lor{b<a}$ for natural numbers beginning with 1 using Peano's Axioms without induction hypothesis
Here, I am asking specifically about a proof which does not use an induction hypothesis, and which relies exclusively on Peano's axioms as stated herein. My interest is not in simply producing the ...
1
vote
1answer
59 views
Peano axioms: prove that there is no natural number between n and sucessor of n
Let $m \in \mathbb{N}$. Show that $\nexists n \in \mathbb{N}$ such that $m < n < s(m)$, where $s$ is the successor function.
Here's my proof using only the Peano Axioms I was introduced. I'd ...
3
votes
2answers
95 views
How to prove that first-order PA proves the consistency of each of its finite sub-theories?
The locus classicus of this theorem (the ''reflexivity'' of PA) is Mostowski's 1952 On models of axiomatic systems. I freely admit that I can't read the rather archaic formalism of this paper. Is ...
1
vote
0answers
55 views
Nonstandard proof codes for Con(PA)
Note: This question is inspired by a paper being discussed in the FoM mailing list.
The formal statement Con(PA) is a statement about the existence of a proof code for the derivation of a ...
1
vote
1answer
88 views
Is the 'copy' of the naturals in ZF a unique way to represent the second-order arithmetic in first-order logic?
The following line of thought came into me while studying introductory logic and set theory. I feel like there is an error in it somewhere, but I can't point it. It might even be correct.
We have the ...
2
votes
1answer
23 views
Are “lower bound” and “upper bound” unambigous? What if one's in the negative axis?
Are "lower bound" and "upper bound" unambigous? What if one's in the negative axis?
Consider e.g.
$$\{-n: n \in \mathbb{N} \}$$
This has no lower bound, if one consider lower to mean towards $- \...
1
vote
0answers
58 views
Prove that 1+1=2. [duplicate]
Ok... I know that $1+1=2$, but how does that work? What mathematical forces drive this simple, yet profound equation, and how do you prove it?
Here is what I did:
Let $a=1$. This means that we are ...
1
vote
1answer
54 views
Peano axioms and first-order logic with $\exists^{\infty}$
All Peano axioms except the induction axiom are statements in first-order logic.
The induction axiom is written as $\forall X(0 \in X \land \forall n(n \in \mathbb{N} \rightarrow (n \in X \land n' \in ...
1
vote
1answer
28 views
Peano axiom of induction- why cannot it be replaced by something simpler?
The Peano axiom of induction for natural numbers says that
For any property $P(n)$ , if $P(0)$ holds, and that whenever $P(n)$ holds, $P(n++)$ holds, then
$P(n)$ holds for all natural numbers.
Can ...
1
vote
0answers
57 views
Why we care only about $\Pi_1$ parameters in axiom schemes?
There is exist tradition to formulate axiom schemes such as induction, comprehension or replacment in a way like "for each formula $\phi(y,\overline{x})$ with free variables $y$ and $\overline{x}=x_1,....
0
votes
2answers
79 views
Must heredity be explicilty stated in addtion to Peano's axioms when defining natural numbers?
My question is stated in bold text.
This question pertains to the following formulation of Peano's axioms
used to formalize an introduction of the natural numbers (beginning
with 1) consisting of ...
0
votes
1answer
50 views
How can I prove transitivity of < in Peano Arithmetic
I wish to prove
$$(\forall x)(\forall y)(\forall z)((x < y \land y < z) \rightarrow x < z)$$
only using the rules of Peano Arithmetic (PA) including the induction rule. I have seen other ...
0
votes
0answers
32 views
Basis of Mathematics
I was reading up on Goedel's Theorems and was wondering what exactly is the basis of Mathematics today and is the discussion around an axiomatic system settled? I know that there are several attempts ...
4
votes
1answer
82 views
How do we know PA is incomparable with PRA + $\epsilon_0$?
Gödel 2 says that no subtheory of PA can prove Con$_{PA}$, and even though most natural theories $T$ extending PA can prove Con$_{PA}$, this is relatively uninteresting since anyone doubting the ...
3
votes
1answer
78 views
Is there a computable and complete “probabilistic” theory of arithmetic?
Let $\mathbb T$ be a probability distribution over complete and consistent theories of first order arithmetic that contain $PA$. Additionally, we will require that for any sentence $\phi$ in the ...
1
vote
2answers
47 views
How do Peano's arithmetical axioms guarantee that we can construct the natural number set?
I'm probably not understanding but I don’t see how the axioms can guarantee total construction of the natural number set.
The successor function as well as the axiom of induction guarantee that the ...
1
vote
1answer
52 views
Unprovable sentence, but provably it is provable.
Work in Peano Arithmetic, PA. Let Prov(n) be a standard proof predicate, so that $PA \vdash Prov(\ulcorner \phi \urcorner) \text{ iff } PA \vdash \phi$ .
By Löb's theorem, we know that if $PA \vdash ...
0
votes
0answers
145 views
How did mathematicans prove things before ZFC or Peano
I do not get it. How was a+b=b+a or a (b +c) = ab + ac proved by ancient mathematicians before set theory or Peano axioms? If you cannot logically prove the laws of arithmetic without Peano or set ...
5
votes
0answers
55 views
Axiomatizing a “bounded” companion to PA
There's nothing special about PA here, I'm just focusing on it since it's strong enough to ignore lots of minor technical issues around foundations. If switching to some other theory would yield a ...
0
votes
2answers
53 views
A (quantifier-free) is true in standard model of PA ==> PA |- A ??
Is the following statement correct ?
A is a formula in PA without a quantifier and
A is true for the standard model of arithmetic, i.e. the model
|N = (N,+,×,0,1,<)
This means: |N |= A
==>
A is ...
1
vote
1answer
39 views
Is it necessary to prove uniqueness of Peano addition?
If we define addition as follows:
Define $a+0=a$.
For all $a,b\in\mathbb N$ such that $a+b$ is defined, define $a+S(b)=S(a+b)$.
It's easy to show through induction that this defines addition for all ...
3
votes
1answer
112 views
Consistency of PA from a Formalist Perspective
In this lengthy thread there's people bickering back and forth about the consistency of PA (Peano Arithmetic) and misunderstandings abound. In reading it I came to an understanding I found useful, ...
1
vote
4answers
114 views
How do Peano Axioms imply “nextness” with the successor?
Going with this explanation of Peano's Axioms, I cannot understand how/where the successor function is definitively stated to be the very next number in the case of natural numbers. In this treatment, ...
0
votes
0answers
39 views
Why natural numbers are generalized in $\mathbb{Z}$ to ensure the group structure respect to the sum?
The natural numbers $\mathbb{N}$ are defined through the Peano axioms and then generalized in $\mathbb{Z}$ to ensure the group structure with respect to the sum.
Why do we need to ensure such group ...
0
votes
1answer
43 views
Is this sufficient to prove the associativity of natural number addition?
This question is regarding the same proposition as is discussed in How should this proof of the associativity of natural number addition be understood?
Here I wish to ask if a much simpler proof than ...
1
vote
0answers
119 views
How should this proof of the associativity of natural number addition be understood?
The context of this question is the proofs of the basic laws of arithmetic
beginning with Peano's axioms which are stated starting with the number 1, rather than 0. The modified principle of induction ...
2
votes
0answers
65 views
A property of representable functions?
Recall that a function $f:\mathbb{N}^k\rightarrow\mathbb{N}$ is representable in Peano arithmetic if there exists a formula $\varphi(x_1,\dots ,x_k,y)$ such that for every $n_1,\dots,n_k,m\in\mathbb{N}...
2
votes
3answers
159 views
Peano Axiom Proofs: Proving $a < b$, if and only if $a + + \leq b$
As for where I am getting my Peano Axioms, its from Terrance Tao's Analysis I text (math.unm.edu/~crisp/courses/math401/tao.pdf).
I am unsure whether my proof is correct for proving the forward ...
