Questions tagged [peano-axioms]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
41 views

If I define addition in the following way, how can I prove that it's commutative?

$a+b=a$, if $b=0$ $a+b=S(a)+S^{-1}(b)$, if $b\not=0$ Here a and b are natural numbers defined according to the Peano axioms, while S represents the successor function. Basically, I am trying to prove ...
user avatar
0 votes
0 answers
23 views

Is there a set $A \subset \mathbb{N}$ s.t. $A$ is not the interpretation set of any formula in Peano arithmetic?

More formally, what I want to find is a set $A \subset \mathbb{N}$ s.t. for every formula $\phi$ with only one free variable $x$ in Peano arithmetic, there exists $a \in A$ s.t. $\{ x \mapsto a \} \...
user avatar
2 votes
1 answer
73 views
+50

How do you prove the existence of the addition function without pre-supposing it?

Context: self-study from Smullyan and Fitting's Set Theory and the Continuum Problem (revised ed., 2010). So I have this question, which is exercise 8.4 (a) in Chapter 3 (page 44 of Dover edition). ...
user avatar
  • 4,038
3 votes
2 answers
110 views

Does this proof of the binomial expansion (a+b)^2 work?

I was rereading Terence Tao's Analysis 1 and found this question in the section: Exercise $2.3.4.$ Prove the identity $(a + b)^2 = a^2 + 2ab + b^2$ for all natural numbers a, b. Prior to this we ...
user avatar
  • 33
0 votes
2 answers
47 views

How do I prove formally that for all natural numbers $a\cdot S(c)=b\cdot S(c)\implies a\cdot c=b\cdot c$

Natural numbers, addition, multiplication, and the successor function S, are defined in the wikipedia article regarding Peano axioms. https://en.m.wikipedia.org/wiki/Peano_axioms Originally I was ...
user avatar
-1 votes
0 answers
43 views

How can prove this with Peano Axiom

Me need to prove: They prove about the same, but I don't understand what I should do with S(0)
user avatar
0 votes
1 answer
55 views

Is PA provably definable?

A set of sentences $S$ from the language of arithmetic is called definable if there is a formula $\phi(x)$ such that $\mathbb{N} \models \phi(n)$ iff $n$ is the Gödel number of a formula from $S$. A ...
user avatar
  • 67
4 votes
1 answer
86 views

Prove that for all natural numbers $\neg\big(S(a)+b=a\big)$

The natural numbers are defined as per the Peano axioms. Addition is defined recursively as follows: $$ \begin{cases} a + 0 &= a,\\ a + S(b) &= S(a+b). \end{cases} $$ Prove that $\forall a\...
user avatar
0 votes
1 answer
33 views

Why is a unary numeral system bijective?

In this treatment of unary numeral system, it is called "bijective base-1 numeral system." I understand bijective from functions, but why is it used here? Also, the article says the Peano as ...
user avatar
  • 760
1 vote
0 answers
67 views

Has this logic of relations been done before?

First Order Logic of Relations "FOLR": Language: first order logic with Equality "$=$"(and its axioms), and Membership "$ \in $", nLinks "$\overrightarrow {x_1,..,...
user avatar
  • 3,553
0 votes
0 answers
36 views

Peano's axioms: why is n++ $\neq$ n? [duplicate]

Why is the successor of n, n++, unequal to n? I've been reading about Peano's axioms in Analysis 1 by Terence Tao recently (which I am thoroughly enjoying :)). In one of the exercises I found myself ...
user avatar
0 votes
1 answer
21 views

Gentzen Consistency Proof and Peano's 9th Axiom. Was PA consistent as originally stated or consistent only with a weaker 9th Axiom?

I have done meta-proofs of the consistency of FOL (Studied about 40 years ago), but have not done any for PA and have not looked at (and maybe now could not follow) Gentzen or the other proofs of PA. ...
user avatar
0 votes
1 answer
89 views

How to justify the necessity of the Axioms?

I am studying the logical fundaments of mathematics, but very often I have trouble to understand Peano's and ZFC/ZFC axioms. In Tao's book Analysis I, I found very helpful when he points out what ...
user avatar
0 votes
0 answers
31 views

Can this system interpret PA?

Can PA be interpreted in the following system? Language: bi-sorted first order logic with equality "$=$", successor "$S$", membership "$\in$", and pairing "$P$"....
user avatar
  • 3,553
2 votes
0 answers
73 views

What are the inference rules of Peano Arithmetic? [duplicate]

There are many examples in the literature (for example, in this question) where the author says that something "is provable in Peano arithmetic" or "is not provable in Peano arithmetic&...
user avatar
29 votes
1 answer
2k views

Can Peano arithmetic prove the consistency of "baby arithmetic"?

I am reading Peter Smith's An Introduction to Gödel's Theorems. In chapter 10, he defines "baby arithmetic" $\mathsf{BA}$ to be the zeroth-order version of Peano arithmetic ($\mathsf{PA}$) ...
user avatar
  • 4,879
4 votes
1 answer
92 views

Why does this nonstandard model of Robinson Arithmetic fail to be a model of PA?

As talked about in this question, there is a nonstandard model of Robinson arithmetic of the form: $z_0 + z_1\omega + z_2\omega^2 + z_3\omega^3 + ... + z_n\omega^n$ in which $\omega$ is a formal ...
user avatar
0 votes
1 answer
90 views

Why was it important for Peano arithmetic to prove ITS OWN consistency?

A paraphrase of Gödel's Second Incompleteness Theorem into non-technical language states that, if a formal system is powerful enough to express Peano arithmetic, that system is unable to prove its own ...
user avatar
0 votes
1 answer
32 views

Are positive integer structures axiomatizable?

Recall the first-order Peano axioms for structures of the form $(N;0,S,+,*)$: $\neg \exists x Sx = 0$ $\forall x \forall y (Sx = Sy \rightarrow x=y)$ The axiom schema of induction (which are really ...
user avatar
  • 13.3k
4 votes
1 answer
124 views

Can the fact that NBG without choice is a conservative extension of ZF be proved in Peano Arithmetic?

Consider NBG without choice. Denote this theory NBG'. It is fairly easy once one knows a bit of model theory to demonstrate that this theory is a conservative extension of ZF. An outline of the ...
user avatar
  • 19.3k
1 vote
2 answers
169 views

Successor arithmetic is not finitely axiomatizable

Consider the theory $\text{Th}(\mathbb{N}, 0, S)$, with $S$ being the successor function. In his book A Course in Model Theory, Poizat claims (p. 109) that this theory is not finitely axiomatizable. ...
user avatar
  • 4,877
3 votes
1 answer
112 views

Models of successor arithmetic

Consider the theory $\text{Th}(\mathbb{N}, S, 0)$, which we know to be axiomatized by the following axioms: $\forall x (S(x) \neq 0)$ $\forall x \forall y (S(x) = S(y) \rightarrow x=y)$ $\forall x (x ...
user avatar
  • 4,877
2 votes
2 answers
40 views

Does the side of the successor function in the second postulate of the definition of addition matter?

In Peano arithmetic addition is usually defined with the following two postulates: $(1a):p + 0 = p$ $(2a):p + S(q) = S(p+q)$ Lets say I put the successor term of the second postulate on the left? ...
user avatar
7 votes
1 answer
134 views

How much arithmetic can we find definably in the surreals?

Playing fast and loose with size issues for simplicity, let $\mathfrak{S}$ be the structure of the surreal numbers equipped with addition, multiplication, and the simplicity order. I'm curious how ...
user avatar
1 vote
0 answers
48 views

Question regarding natural numbers in Tao’s Analysis 1.

This doubt might be a mistake on my part, but its confused me for a while now so I decided to ask here. In Terrence Tao’s “Analysis 1”, at the beginning of the chapter about Natural Numbers (where he ...
user avatar
  • 79
3 votes
0 answers
194 views

Which sentences are irreducibly self-referential?

Below, all sentences/formulas are in the language of arithmetic, and for simplicity we conflate numbers with numerals and sentences with Godel numbers. Now asked at MO. Say that a sentence $\varphi$ ...
user avatar
12 votes
2 answers
1k views

Is there a nonstandard model of Peano's arithmetic where any element has only finitely many prime divisors?

By the compactness theorem, there are nonstandard models where don't have finite prime decomposition, and some elements are divisible by infinitely many distinct primes. But what if we want a nice ...
user avatar
1 vote
0 answers
56 views

Are there any arithmetic statements where there does not exist a proof proving the statement?

Because of Godel's Incompleteness Theorems, there must exist certain statements about the numbers which have no proof via the Peano axioms. This includes The Strengthened Ramsey Theorem. However, this ...
user avatar
  • 2,615
0 votes
0 answers
17 views

Proving $H_a: a≠0 $ and $a, b, c$ are natural numbers such that $ab = ac \rightarrow b=c$, proper use of induction

Learning on my own from the ground up, I'm developing a series of basic proofs using Peano's axioms and I suspect I'm misusing the proposition $ka=kb \rightarrow b=c$ in my inductive hypothesis $h_k$ ...
user avatar
  • 101
1 vote
0 answers
42 views

How can I proove only one of these three holds? $m>n, m=n, m<n$.

I'm going to finish constructing real numbers from the Peano axiom. I've just finished constructing natural numbers and integers and now I'm going to construct an inequality within the integer range, ...
user avatar
  • 5,106
0 votes
0 answers
50 views

Prove that intersection of a non-empty set of natural numbers is itself a natural number using ZF set theory and Peano axioms

Update I was going to use this question to solve another question using intersection approach. I could find an answer for that question using another approach and posted an answer there but I still ...
user avatar
2 votes
2 answers
96 views

Halmos's set theory If $E$ is a non-empty set of natural numbers, exists some $k$ in $E$ such that $k \leqq m$ for all $m\in E$. Prove by intersection

Update I saw a similar question which provided a proof by using axiom of induction and I wrote an answer by adapting to one of the answers of that question. But I hope someone can give another proof ...
user avatar
2 votes
2 answers
126 views

Formal induction over two variables

Induction. According to the Peano Axioms in this article https://en.wikipedia.org/wiki/Peano_axioms, one axioms states that if $\varphi$ is a unary predicate such that $\varphi(0)$ is true and $$\...
user avatar
2 votes
1 answer
84 views

How exactly are you allowed to use free set/predicate variables in first-order arithmetic?

In first-order arithmetic, you can't quantify over sets of numbers. However, you can include sets as free variables. I don't think this is just a meta-linguistic thing, as I've read papers about Peano ...
user avatar
  • 21
3 votes
2 answers
134 views

(Request for) simple constructive proof of existence of nonstandard model of PA

I know of two straightforward nonconstructive proofs of the existence of nonstandard models of arithmetic. By the existence of the standard model of PA, PA is satisfiable and has an infinite model. ...
user avatar
  • 6,426
0 votes
0 answers
40 views

Gentzen's consistency proof of PA

What would be some good introcutory references to start reading about Gentzen's consistency proof of Peano arithmetic?
user avatar
  • 1
1 vote
1 answer
51 views

Peano axioms without identity and function symbols

Can the first-order Peano axioms be reformulated without identity and without function symbols? I tried doing this by characterizing one of the following relations axiomatically, but end up with ...
user avatar
  • 5,060
0 votes
0 answers
20 views

Equivalence of two characterizations of initial segments of $\mathbb N$

In proving the recursion theorem, Tao in his Analysis, asks to show the existence of the sets $\{0, \ldots, n\}$ directly from the Peano axioms so that $+$, $\ge$, etc. are not yet defined (which he ...
user avatar
  • 1,967
3 votes
1 answer
77 views

Interesting examples of first-order, one-sorted proper extensions of PA

Are there any interesting nontrivial examples of first-order, one-sorted theories of natural numbers (i.e. theories whose quantifiers range over natural numbers only and not, say, sets of natural ...
user avatar
  • 5,060
3 votes
0 answers
48 views

Soundness for first order

While reading the book by Peter Smith I came across two different definitions of soundness, the general definition A theory $T$ is sound iff its axioms are true (on the interpretation built into T’s ...
user avatar
2 votes
1 answer
62 views

How to prove non-equality using Peano axioms?

Using the five Peano axioms of first-order theory arithmetic, one can prove '1+1=2', '2+3=5' or '342+637=979' (don't try the last one!). However, my question is how to prove a non-equality such as &...
user avatar
  • 79
0 votes
0 answers
40 views

How can I encode a proof in PA as a godel number?

It seems straightforward to encode a wff in PA as a number. I can't see how to encode a proof. Could someone please tell me how this is usally done? Thanks.
user avatar
5 votes
1 answer
109 views

Satisfaction of Peano postulates in topos with natural numbers object

Let $\mathcal{T}$ a topos with a natural numbers object, noted $N$. Also assume that $\mathcal{T}$ is not degenerate, meaning that its initial and terminal objects $\emptyset$ and $*$ are not ...
user avatar
0 votes
1 answer
42 views

Peano axioms and Induction to prove $s(x) \cdot y = x \cdot y + y$

Using the following axioms $A1: \forall x \in \mathbb{N}: x + 0 = x$ $A2: \forall x,y \in \mathbb{N}: x + s(y) = s(x+y)$ $M1: \forall x \in \mathbb{N}: x \cdot0 = 0$ $M2: \forall x,y \in \mathbb{N}: x ...
user avatar
4 votes
1 answer
154 views

What is the difference between "Peano arithmetic," "second-order arithmetic," and "second-order Peano arithmetic?"

I think this needs to be clarified, so it would be helpful to see an answer to this somewhere. I've seen the following terms: Peano arithmetic. Second-order arithmetic. Second-order Peano arithmetic. ...
user avatar
1 vote
0 answers
66 views

Are the naturals really a subset of the real numbers? [duplicate]

Ok, so this question seems obvious, right? But what I mean is the numbers in the way they are logically / axiomaticaly defined in the foundations of Mathematics. As far as I know, the naturals are in ...
user avatar
0 votes
3 answers
56 views

Landau Foundations of Analysis Axiom 4: Is it necessary?

Landau gives 5 axioms as the foundations for deriving the theorems in the first chapter: Axiom 1: 1 is a natural number. Axiom 2: If $x = y$ then $x' = y'$. Axiom 3: 1 is not a successor to any ...
user avatar
0 votes
2 answers
59 views

How to prove that there are $n$ natural numbers that are less or equal than $n$ and what properties are allowed to use in induction.

Let $n \in \mathbf{N}$. I wondered how to prove that there are exactly $n$ natural numbers that are smaller or equal than $n$. This seems somewhat circular which confuses me. I guess the way to do ...
user avatar
  • 241
5 votes
1 answer
67 views

a stronger fixed point theorem

Given a unary predicate $\phi$, the Fixed Point Lemma of PA tells us that there is a sentence $S$ such that: $$\mbox{PA} \vdash S \leftrightarrow \phi (\ulcorner S \urcorner)$$ (Note that $\phi$ doesn'...
user avatar
1 vote
1 answer
43 views

Finiteness, finite sets and representing its elements.

A set $S$ is called finite if there exists a bijection from $S$ to $\{1,...,n\}$ for one $n \in \mathbf{N}$. It is then common to write its elements as $s_1,...,s_n$. I now wonder, why this is ...
user avatar
  • 241

1
2 3 4 5
17