Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [peano-axioms]

For questions on Peano axioms, a set of axioms for the natural numbers.

3
votes
5answers
96 views

Why does induction only allow numbers connected to $0$ to be natural?

When learning Peano axioms normally we use induction to suggest that if a property $P(0)$ is true, and if $P(k)$ being true implies $P(k + 1)$ being true (for natural number $k$), then if $P$ is the ...
4
votes
2answers
88 views

Is it true that $0\in 1$?

From Zermelo–Fraenkel set theory and Peano axioms, we have $0=\varnothing$ and $1=\varnothing\cup{\{\varnothing\}}\implies0\in 1$. Many thanks for your help!
0
votes
1answer
39 views

(Peano axioms) Showing why the induction axiom is necessary

On pg no. 3 of this article, the author says let’s consider this version of $\Bbb{N}$ that satisfies all the above axioms, but is not the usual natural numbers we know: $\Bbb{N}=\{0,1,2,3,...,\} ∪\{...
0
votes
1answer
63 views

Proof that Peano Axioms is a theory with equality (according to Mendelson book)

I'm reading Elliott Mendelson's "Introduction to Mathematical Logic". There is a statement with a proof that $S$ (Peano Arithmetic) is a first-order theory with equality. I am not sure whether I ...
5
votes
1answer
55 views

Taking a natural number different from zero as a base case in an inductive proof

Principle of mathematical induction states that if a subset $S$ of a successor set $\omega$ is also a successor set, then $S=\omega$. In primitive terms, it is formulated as: if $S \subset \omega$, ...
2
votes
1answer
157 views

In the extension to integers, how should this restriction on the domain of natural numbers be interpreted?

My interpretation of the sub-paragraph in the book which I am asking about is this: BEGIN SUMMARY Note that in this context 0 is not considered to be a natural number. The pairs of natural numbers $...
3
votes
1answer
208 views

How powerful is PA+Con(PA)+Con(PA+Con(PA))… etc?

From what i remember from Godel encoding there was alot of freedom in how one chooses to expresses the statement Con(PA), my question is if one can classify all statements, or some subclass of all ...
0
votes
1answer
78 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 ...
2
votes
1answer
38 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 ...
0
votes
1answer
46 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^\...
3
votes
3answers
2k views

proof of commutativity of multiplication for natural numbers using Peano's axiom

How do you prove commutativity of multiplication using peano's axioms.I know we have to use induction and I have already proved n*1=1*n.But I cant think of how to prove the inductive step.
5
votes
3answers
195 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
59 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^\...
29
votes
6answers
3k views

A question on Terence Tao's representation of Peano Axioms

While reading Terence Tao's book on Analysis I had some questions regarding the implication of the Peano Axioms. After writing the following four axioms (which I will write without changing their ...
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
33 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
49 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 ...
0
votes
2answers
81 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
28 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 ...
0
votes
1answer
67 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
98 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
37 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 ...
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
98 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
4answers
127 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
49 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
1answer
51 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
4answers
134 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 ...
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
42 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 ...
0
votes
2answers
243 views

Prove cancellation law using peano axioms.

Using Peano axioms, prove $∀x∀y∀z(x+y=x+z→y=z)$. I have been stuck on it for some time, could someone please give a proof? Thanks!
2
votes
1answer
77 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 ...
1
vote
1answer
60 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 ...
0
votes
1answer
55 views

What is Complete Induction without Hypothesis?: Ordering of $\mathbb{N}$ from Peano's Axioms

The following is from Fundamentals of Mathematics, Volume 1 Foundations of Mathematics: The Real Number System and Algebra; Edited by H. Behnke, F. Bachmann, K. Fladt, W. Suess and H. Kunle I've used ...
1
vote
0answers
59 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 ...
3
votes
2answers
106 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
1answer
91 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
55 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 ...
2
votes
3answers
1k views

Why is the Axiom of Infinity necessary?

I am having trouble seeing why the Axiom of Infinity is necessary to construct an infinite set. According to a professor of who's mine teaching a class on "infinity," the Peano axioms are only ...
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
58 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
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 ...
0
votes
1answer
53 views

Peano axioms and Herbrand's theorem

We denote the Peano axioms with $\mathsf {PA}$ and $S=\{0,1,+,\cdot,<\}$ denotes the language of number theory. Let $\varphi$ be the formula $$(1+1)\cdot v_2\equiv(v_0+v_1)\cdot(v_0+v_1+1)+(1+1)\...
4
votes
1answer
84 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
48 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 ...