Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
814
questions
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 ...
- 139
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 \} \...
- 433
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).
...
- 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 ...
- 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 ...
- 139
-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)
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 ...
- 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\...
- 139
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 ...
- 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,..,...
- 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 ...
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. ...
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 ...
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$"....
- 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&...
- 21
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}$) ...
- 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 ...
- 6,096
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 ...
- 145
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 ...
- 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 ...
- 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. ...
- 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 ...
- 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? ...
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 ...
- 218k
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 ...
- 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$ ...
- 218k
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 ...
- 1,921
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 ...
- 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$ ...
- 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, ...
- 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 ...
- 254
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 ...
- 254
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 $$\...
- 195
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 ...
- 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. ...
- 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?
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 1,971
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 &...
- 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.
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 ...
- 909
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 ...
user973482
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.
...
- 1,924
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 ...
- 21
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 ...
- 3
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 ...
- 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'...
- 473
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 ...
- 241