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

learn more… | top users | synonyms

0
votes
4answers
345 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
17 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
26 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
82 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
41 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
60 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
133 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 ...
3
votes
2answers
100 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
53 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
108 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
37 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
68 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
110 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
48 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
68 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
24 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
39 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
30 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
36 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
41 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
71 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
48 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
35 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
126 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
51 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
39 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 ...
0
votes
0answers
22 views

Quantitative results on PA completeness?

Are there any results estimating the number of sentences in PA that are not provable together with their negations, as a function of the sentence length or the depth of the sentence parse tree or ...
-1
votes
2answers
69 views

Can Incompleteness be Computable?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
6
votes
2answers
231 views

Is it possible to develop Analysis solely from Peano's axioms

...and a few definitions on the way? When I studied Calculus using Spivak's book It was clearly shown that, in order to prove some fundamental theorems (intermediate value theorem being one of them), ...
0
votes
3answers
114 views

Godel's Second Incompleteness and the Assumption of Consistency

As I understand it, Godel's Second Incompleteness Theorem states that given a theory $T$ that is any extension of Robinson Arithmetic, that if that theory is consistent then it cannot prove a given ...
3
votes
1answer
33 views

The set $T=\{l\in\mathbb{N}: ml=nl \ \text{implies} \ m=n \}$ is inductive.

I'm trying to prove the following statement: $ml=nl$ implies $m=n$ for every $m,n,l\in \mathbb{N}$. So I defined the set $T=\{l\in\mathbb{N}: ml=nl \ \text{implies} \ m=n \}$ and if I prove that ...
0
votes
1answer
42 views

Injective function, $f:X\to X$ with $f(X)\subset X$, but $T\subseteq X$ is not inductive set.

I'm looking for an example of the following manner: Suppose that $f:X\to X$ is a injective function(where $X$ some set), such that the following property not holds: If $T$ is subset of $X$, with ...
3
votes
0answers
50 views

Induction Can't Prove Complexity?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
1
vote
1answer
85 views

A proof that every set of natural numbers contains a minimal element

I'm currently trying to extend my basic knowledge and in order to do so, I started with the Peano-axioms. I think, I understand the underlying thoughts and I want to prove the following theorem using ...
1
vote
0answers
23 views

Expressing $y=\lfloor rx\rfloor$ in PA

The formula: $$y=\lfloor x\sqrt2\rfloor$$ is expressible in first-order PA, as: $$y^2<2x^2<(y+1)^2$$ So, even though $\sqrt2$ isn't a natural number, we can still represent a formula with ...
4
votes
1answer
89 views

Are all models of Peano arithmetic elementary equivalent?

By Löwenheim-Skolem we know there are models of (first order) PA that are not isomorphic to the standard model, but are elementary equivalent to it, i.e. they satisfy the same set of first-order ...
4
votes
1answer
75 views

How is a formal system including only a first-order axiomatization of induction stronger than a system without?

Stumbled upon another aspect of Peano arithmetic that I find confusing... I understand that what I write in the title is in fact the case, e.g. certain statements provable in PA not being provable in ...
2
votes
1answer
63 views

Peano and consistency, how to understand it rightly.

I'm struggling with the notion of consistency, and a few cases : I'm writing in the following $Con(T)$ to denote the arithmetic formula which expresses the consistency of $T$, for $T$ a consistent ...
4
votes
1answer
147 views

Why a system becomes incomplete once it's capable of doing arithmetic?

For a Formal axiomatic system to obey Godel's incompleteness theorems, It has to be powerful enough to incorporate Peano Axioms. Why It does not apply to say, Presburger arithmetic or the axioms of ...
3
votes
0answers
94 views

Expressing quantifier free $\mathcal{L}_{PA}$-formulae $\varphi(y,\vec{x})$ with polynomials

I'm stuck at the following exercise: I want to show that for every quantifier-free formula in the language of $\mathsf{PA}$ there are polynomials $P(y,\vec{x}),Q(y,\vec{x})$ such that for all ...
1
vote
1answer
60 views

How does PA prove all $\Delta_0$-formulas which are true in the standard model?

Let $\varphi(x_1,\dots,x_n)$ be a $\Delta_0$-formula, i.e. a formula in which every quantifier is bounded. I want to prove that $$ \text{PA}\vdash\varphi(\overline{n_1},\dots,\overline{n_k}) \iff ...
0
votes
3answers
123 views

The necessity of the axiom of induction

$\underline{First\ question}$ Let $P(n)$ be a proposition about $n$. In standard mathematical induction, we require: (1)$P(0)$ holds. (2)If $P(n)$ holds, $P(n+1)$holds. Here we use "the axiom of ...
1
vote
3answers
61 views

Regarding Peano's Axioms

According to the Wikipedia entry on the Peano axioms: "the number 1 can be defined as $S(0)$, 2 as $S(S(0))$ (which is also $S(1)$), and, in general, any natural number n as the result of n-fold ...
2
votes
2answers
72 views

Variations in the successor fuction from Peano's axioms

Concerning the successor function in Peano's axioms, what prevents me from defining it in the following way: 0 to 2, 2 to 1, 1 to 4, 4 to 3, 3 to 6, 6 to 5, 5 to 8, 8 to 7 ... and so on. It seems ...
0
votes
1answer
80 views

Which one of the following logical propositions is to be preferred?

I'm trying to update the symbolism of Giuseppe Peano's "Arithmetices Principia", to make the translation freely available. Might I ask you, which of the following might be a correct mathematical ...
4
votes
1answer
86 views

Transfinite Induction in Peano Arithmetic

I have heard that Peano Arithmetic (PA) cannot perform transfinite induction up to $\varepsilon_0$. This seems to imply that it can induct up to smaller ordinals, like $\omega$ or $\omega^\omega$ or ...
1
vote
2answers
66 views

Set of axioms for finite subset of Natural Numbers

I would like to get a set of Peano like first-order axioms for a finite subset of natural numbers $N'$ such that $0 \leq N' \leq Max$, with $Max$ denoting the upper-bound. (So my signature might be ...
2
votes
3answers
62 views

Prove that the greatest common factor of $m+n$ and $m^2+n^2$ is 1 or 2 if $m$ and $n$ are relatively prime.

Prove that the greatest common factor of $m+n$ and $m^2+n^2$ is $1$ or $2$ if $m$ and $n$ are relatively prime natural numbers. Can anyone give a step-by-step answer for this?
0
votes
3answers
51 views

Why doesn't inequality hold as a property in natural number induction?

It is said that all natural numbers follow the rule of induction: if a said property holds for one number and for its successor, it holds for all natural numbers. But, let us define the following ...