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

learn more… | top users | synonyms

2
votes
1answer
29 views

Prove that the system $(P, S, 0)$ satisfy Peano Axioms.

Peano Axioms. Let $\mathbb N \neq \emptyset$ be a set and $S:\mathbb N \to \mathbb N$ a function. The elements of $\mathbb N$ are the natural numbers. If $n \in \mathbb N$ then $S(n)$ is the ...
1
vote
1answer
38 views

Connection between number theory and the Von Neumann construction of naturals

There are many unsolved conjectures and hypothesis in number theory. For example, the twin primes conjecture, Goldbach's conjecture, the Riemann hypothesis, infinitude of Mersenne's primes, and many ...
0
votes
2answers
58 views

How to name the natural numbers? [closed]

Suppose we're given the Peano Axioms, particularly $$1. \,0\in \Bbb N\\ 2.\,\forall n (n\in \Bbb N\rightarrow Sn\in \Bbb N)$$ From here, how do we name the numbers? I.e, making the associations ...
1
vote
0answers
24 views

Proof from axioms of $\mathsf{PA}$: every natural number has remainder $0$ or $1$ or $2$ when divided by $3$

Using only the axioms of $\mathsf{PA}$, I want to prove this fact. It came up in a previous year's exam paper, and seems more difficult than I had anticipated... The question was to sketch the idea, ...
0
votes
1answer
32 views

Exercise in Peano Arithmetic

I'm doing some excercises from the book "The Incompleteness Phenomenom" from Goldstern and Judah. I'm doing exercise about Peano Arithmetic and I have to show that: $\vdash(\forall z\leq x(z\geq 1 ...
0
votes
1answer
24 views

Prove that it is a theorem

I'm doing some excercises from the book "The Incompleteness Phenomenom" from Goldstern and Judah. I'm doing exercise about Peano Arithmetic and I have to show that: $\vdash p|x \wedge r·s=p \to ...
0
votes
1answer
25 views

Give a derivation in Peano Arithmetic

I'm doing some excercises from the book "The Incompleteness Phenomenom" from Goldstern and Judah. Show that: $\vdash \exists y[y>1 \wedge \forall z(z\leq 0\wedge z>1\to z|y)]$ Hint: Show that ...
3
votes
1answer
70 views

Does no non-standard model of Peano Arithmetic make the integers a principal ideal domain?

Though I do not find a reference now, I have heard no non-standard model of Peano Arithmetic has a principal ideal domain as its ring of integers. Is that right? Is it trivial? Or is there a good ...
6
votes
2answers
90 views

Is the axiom of induction constructively verifiable for a non-standard model of Peano arithmetic?

There exist models of the natural numbers which include infinite numbers. Such models are called non-standard models of arithmetic. (Proof: by the compactness theorem, there exist models of Peano ...
0
votes
1answer
58 views

Peano and induction according to Schaum's Outline

As some of you may have noticed, I've been coming at Peano from a few different angles. This time I'm stuck on what the Schaum's Outline Abstract Algebra version might mean. Here's Schaum's Peano: ...
0
votes
2answers
63 views

Peano axioms with only sets and mapping

I've got Serge Lang's Undergraduate Algebra (2nd edition). In the Appendix is a treatment of the Peano Axioms, but, as he says: " The rules of the game from now on allow us to use only sets and ...
2
votes
1answer
34 views

Could relational operators be used to construct formal theory of natural numbers which is “stronger” than Peano Axioms?

This is a beginner's question about foundational construction of (alternative?) number theory. The notion of mathematical equality is closely related to logico-philosophical notion of 'Law of ...
0
votes
0answers
11 views

Metamathematic: Cover the case if X=Y

I want to formalize: "If X is less than Y, Then U is equal to Y ", and have been told that $$ \bf [\forall V \sim X=(Y+V)]U=Y $$ does not cover the case X=Y. Therefore I have rewritten it as $$ \bf ...
0
votes
3answers
81 views

Peano Induction Axiom

This is a typical rendition the Peano Axiom of Induction: If subset $S \subseteq \mathbb{N}$ contains $1$ and is closed under the successor function (i.e., $n \in S$ implies $\sigma\text{n} \in S$ ...
2
votes
2answers
63 views

About ZFC, peano's axioms, first oder logic and completeness?

I read somewhere that the peano's axioms can be derived out of ZFC. But if that is the case ZFC would be incomplete right( by Godel's incompleteness theorem)? But since ZFC is in first order logic , ...
0
votes
1answer
88 views

Does Tennenbaum's theorem apply to Modular Arithmetic?

I recently asked on math.stackexchange Are the algebraic numbers recursive? I had assumed the field of algebraic numbers is a model of a theory I call Modular Arithmetic. I also assumed Tennenbaum's ...
0
votes
1answer
106 views

Are the algebraic numbers recursive?

I am interested in a theory I call Modular Arithmetic (MA). MA has the same axioms as first order Peano arithmetic (PA) except $\forall x Sx \neq 0$ is replaced with $\exists x Sx=0$. MA has finite ...
3
votes
2answers
275 views

How can addition be non-recursive?

Tennenbaum's theorem says neither addition nor multiplication can be recursive in a non-standard model of arithmetic. I assume recursive means computable and computable means computable by a Turing ...
3
votes
0answers
81 views

Independence of First-Order Peano Axioms

In class was given these 7 (first-order) axioms of Peano arithmetic (the + denotes successor): enter image description here The task task is to prove that these axioms are independent. I have figured ...
5
votes
0answers
88 views

Is it possible to formalize all mathematics in terms of ordinals only?

Our experience shows that all finitary mathematical objects could be encoded using the natural numbers, and all operations on those objects could be expressed in terms of a few basic operations on ...
0
votes
2answers
47 views

What is the method to solve these kind of questions?

Here is the exercise : We define in $\textbf{PA}$ : "$x \mid y \equiv \exists z \ y=xz"$ "$\text{irr}(x) \equiv \forall z(z\mid x \rightarrow z=1 \vee z=x)$" "$\text{prime}(x)\equiv x>1 \wedge ...
7
votes
3answers
162 views

Why might Dieudonne have been “begging the question” by appealing to second-order Peano Axioms?

Following a comment by Peter Smith, I've been reading A. R. D. Mathias's paper The Ignorance of Bourbaki. Parts of the paper are above my head, but I understand it well enough for my own amateurish ...
3
votes
2answers
87 views

How to prove that doesnt exist a natural number such that is equal to it successor from Peano axioms?

Im getting a hard time trying to prove the general for any natural number $n$ such that $$\nexists n\in\Bbb N: S(n)= n$$ From the second Peano axiom we know that $$\nexists n\in\Bbb N: S(1)= n$$ ...
1
vote
3answers
591 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 ...
0
votes
0answers
21 views

Understanding Demonstration There's no Bijection between a set and a proper set of it.

I'm in need of help to understand the demonstratrion of the theorem: Given $I_n=\{ p \in N / p\le n \}$ there's no bijection $f: A \to I_n$ between the set $I_n$ and the proper subset of it $A$. The ...
1
vote
1answer
42 views

Defining Primes in Non-standard Models of Peano Arithmetic

I was recently reading a post basically discussing an "intuition" that Goldbach's Conjecture may be a statement which is undecidable (the post does not specify which axiomatic system the statement is ...
1
vote
3answers
96 views

How to prove $\mathbb{N}\subseteq\mathbb{R}$ given basic field axiomatisation.

I understand that $\mathbb{R}$ can be defined axiomatically in a number of different ways, including as an extension from more basic number systems (e.g., $\mathbb{N}$, $\mathbb{Z}$, or $\mathbb{Q}$) ...
1
vote
2answers
63 views

Can the Recursion Theorem be proved in Peano Arithmetic?

A recursive function on $\mathbb{N}$ can be defined as follows: Given an element $a \in \mathbb{N}$ and a function $f:\mathbb{N}\rightarrow\mathbb{N}$, we can define a function ...
0
votes
1answer
76 views

Is there an non provable sentence from Peano Arithmetic?

I'm trying to deduce the following sentence using only Peano Axioms: "There exist infinite prime numbers" Since PA is known to be incomplete, its possible there is no such proof supporting the ...
2
votes
2answers
135 views

On what sets other than $\mathbb{N}$ might we use proof by induction?

Suppose we have a set $S$ with $s_1\in S$ and $f: S\to S$ and $n\subset S$ such that $n=\{s_1, f(s_1), f(f(s_1)), \cdots \}$ ($n$ not necessarily infinite). To establish properties of $n$, can we ...
4
votes
2answers
131 views

Peano Arithmetic before Gödel

If I understand correctly, Gödel was the one to discover how to encode finite sequences of integers in Peano Arithmetic, with his Chinese Remainder Theorem trick (his "beta function"). As a ...
-2
votes
1answer
57 views

Arithmetic theory

Assuming that Peano’s first-order arithmetic (PA) is indeed a consistent, effective, and arithmetic theory. Is there a way to extend PA to a theory $T$, such that $T$ is consistent, effective but ...
0
votes
1answer
37 views

Proving the artihmetic property of a theory

When can we say a threorom is arithmetic? Is it by following the first 9 axioms of Peano arithmetics? Or should it only allow us to express idioms of natural numbers? For example, can we add a claim ...
2
votes
1answer
113 views

Tao's definition of addition [closed]

In Tao's Real Analysis he defines addition: Let $m$ be a natural number. To add zero to $m$, we define $0+m \equiv m$. Now suppose inductively that we have define how to add $n$ to $m$. Then we ...
1
vote
2answers
39 views

Peano Arithmetic: How would this formalized statement be correct?

Using Peano Axioms I have formalized the following: x is the square of an odd prime number For some odd prime number x' , x is its square IF x is some odd prime number, THEN x is the square of x' IF ...
1
vote
1answer
82 views

How do we know $\mathbb{N}$ is a model of Peano Arithmetic?

The induction axiom in the theory of Peano Arithmetic (PA) is actually an axiom scheme such that for every formula $\phi(x,\bar{y})$ with free variables $x,\bar{y}$ ($\bar{y}$ being a string of ...
3
votes
1answer
141 views

Stuck on GEB chapter 9 - is b a MU number? is b a TNT number?

I'm reading through Gödel, Escher, Bach, and I found myself stuck at chapter 9. I've been rereading through several times already, but I must be missing something. To clarify my background, I'm a ...
1
vote
2answers
50 views

A subtle point regarding the axiom of induction

The fifth of Peano's axioms states the following: If $S\subset \mathbb{N}$ such that $1 \in S$ and $n \in S \Rightarrow \sigma(n) \in S$, then $S = \mathbb{N}$ (where $\sigma(n)$ is the successor ...
-1
votes
1answer
71 views

Why is there a need for ordinal analysis?

Consider the Peano axioms. There exists a model for them (namely, the natural numbers with a ordering relation $<$, binary function $+$, and constant term $0$). Therefore, by the model existence ...
3
votes
1answer
25 views

End Extension models of $I\Delta_0$

Recently I'm thinking about below question, but I can not prove or disprove it. Is it true that for every model $M\models I\Delta_0$ there exists a model $M'\models PA$ such that $M'$ is end ...
1
vote
1answer
40 views

Is $ConPA \rightarrow \neg \Box \neg ConPA$ true in the standard model of arithmetic?

It can be shown (using Löb's theorem) that $$PA \nvdash ConPA \rightarrow \neg \Box \neg ConPA.$$ But what can be said about this sentence in the standard model of arithmetic $\mathcal{N} = ...
0
votes
1answer
34 views

PA2 (Peano Arithmetic in 2º order logic and categoricty)

Second order logic implies categoricity in peano arithmetic. But why are the models isomorphic to the standard model of aritmhetic and not to another non standard model, for example?
0
votes
2answers
37 views

For each $x,y∈\mathbb N$, if $x≤y$ and $y≤x$, then $x=y$ [duplicate]

Proof: For each $x,y∈\mathbb{N}$, if $x≤y$ and $y≤x$, then $x=y$ By definition of order, $x≤y$ if and only if $x<y$ or $x=y$ By definition of order, $x<y$ if there exist a $K∈\mathbb{N}$ such ...
1
vote
2answers
43 views

For each $x,y,z∈\mathbb N$, if $x<y$ then $x+z<y+z$

For each $x,y,z∈\mathbb{N}$, if $x<y$ then $x+z<y+z$ I know how to solve this if it was $x=y$ then $x+z=y+z$ (which my professor said I need to do) Is there a definition that says I can change ...
2
votes
0answers
76 views

Prove if $x<y$ then $x+z<y+z$ [duplicate]

Note I am looking a proof using Peano's axiom as I am working on the Natural Numbers, not the Real Numbers. I need help proving "For each x,y,z in N, if $x<y$ then $x+z<y+z$ This must be done ...
1
vote
1answer
60 views

Proof of “if $x<y$, then $xz<yz$”

I need help proving "For each $x,y,z$ in $\mathbb{N}$, if $x<y$, then $xz<yz$." This must be done using Peano's axioms and the definitions of addition, multiplication, and ordering. I have ...
0
votes
1answer
36 views

PA subsets consistency

IF i have T in piano arithmetic and suppose I add a new symbol c suppose it is T1 T1=T U {c>1,c>1+1,c>1+1+1.......} Is it true that every finite subset of T1 is consistent and can we show that a ...
0
votes
1answer
135 views

Really confused about non-standard arithmethics

A computer science major here (not really that much into math) have to solve this problem but cannot find any solutions. Really appreciate it if someone can clear things out for me (sorry but the ...
4
votes
1answer
62 views

Where is the (original) proof of Klaus Potthoff's Theorem about the order type of arithmetic models?

I am looking for a complete proof, respectively for the complete original proof of the following theorem, which is attributed to Klaus Potthoff: If $\mathfrak{M}$ is a nonstandard model of PA, ...
3
votes
1answer
44 views

Is there an overview of possible order types of fragments of first-order arithmetic?

I know, that there aren't many results on order types of arithmetic fragments. E.g. there are some basic results which one can find in texts of Kaye and Bovykin. But does anyone know, if there is ...