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

learn more… | top users | synonyms

0
votes
0answers
18 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 ...
0
votes
1answer
53 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
208 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
92 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
95 views

Is 1 + 1 + 1 … a finite number? [closed]

Just a simple question whether the "number" $x = 1 + 1 + 1 ...$ is a finite number. On one hand, you can think of x as the result of a never-ending process; $0$ is finite and $n + 1$ is finite when ...
3
votes
1answer
31 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
39 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
42 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
60 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
20 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 ...
3
votes
1answer
62 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
66 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
46 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
134 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
89 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
52 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
82 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
56 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
63 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
77 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
73 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
65 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
47 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
47 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 ...
1
vote
1answer
37 views

Modifying the Peano Axioms to allow multiple successors

If you took the familiar Peano Axioms and replaced the axiom $x \in \mathbb{N} \implies \exists y\in \mathbb{N}(y =S(x))$ with $x \in \mathbb{M} \implies (\exists y_1\in \mathbb{M})(\exists ...
2
votes
2answers
114 views

embdedding standard models of PA into nonstandard models

Maybe it's well known to experts, but is there always an embedding $f$ of the standard model of Peano arithmetic into a nonstandard model? By Peano arithmetic I mean its first-order version, with the ...
1
vote
1answer
65 views

Failures of categoricity not related to size?

The paradigmatic cases I know of theories failing to be categorical are cases that seem tied to the language's inability to distinguish between different infinite cardinalities of the theories domain. ...
2
votes
4answers
166 views

Peano's Axioms: Mathematical Philosophy

In Peano Axioms, why is it necessary to define number and successor. Does not using them imply that we know what they mean? Or could they have just as easily been any two arbitrary terms which are not ...
1
vote
2answers
92 views

Prove that the set of all integers $>0$ is the smallest inductive set

An inductive set is a set $I$ such that $1 \in I$ and if $x \in I$ then $x+1 \in I.$ Some authors define the set of all integers $>0$ as the smallest inductive set, say Apostol's Analysis. But I ...
1
vote
2answers
144 views

How is first-order logic derived from the natural numbers?

I've heard that first-order logic comes from Peano Arithmetic, yet I can't see how. We don't need numbers to formulate quantifiers, variables, functions, constants, relations or even sets. Insted, it ...
1
vote
1answer
162 views

Construction of a model of Peano Arithmetic

I'm studying the axioms of Zermelo-Frankel Set Theory at the moment. I already know the following six axioms: The axiom of empty set The axiom of extensionality The axiom of pairing The axiom of ...
0
votes
0answers
48 views

Strong logical system without principle of explosion

Are there some logical systems strong enough to contain theorems of first/second order Peano Arithmetic but constructed in such way that principle of explosion does not hold for them?
1
vote
0answers
51 views

Is there a difference between induction in Peano Arithmetic and Presburger Arithmetic

Following this question I still do not get clearly the difference between defining exponentiation in PA but impossiblity of recursively define multiplication in Presburger Arithmetics I was thinking ...
2
votes
1answer
59 views

Peano's Axioms and Induction

I was reading Landau's Foundations of Analysis. He starts his construction of number systems by stating five axioms. My question is related to the fifth, the axiom of induction: Let there be given a ...
2
votes
4answers
148 views

Counting numbers vs Natural numbers; Peano Axioms

I can feel that my question is going to be a somewhat lengthy one, but I will try my best to deliver it in as short a form as I can manage. So to begin, I've always thought that the numbers such as ...
2
votes
2answers
88 views

Check my proof of “overspill” in non-standard models of Peano arithmetic.

Proposition Let $\mathcal{M}$ be a nonstandard model of Peano arithmetic, $\phi(v,\bar{w})$ a formula in the language of arithmetic, and $\bar{a} \in \mathbb{M}$. Show that if $\mathcal{M} \models ...
1
vote
1answer
40 views

Proving the order relation in $\mathrm{PA}$ is total.

Let $\mathrm{PA}$ be the first order logic axioms of Peano Arithmetic. Define an order relation by: $$ x\leq y\; \text{ if }\; (\exists z)(x+z=y). $$ Can it be proved that this relation is total?
8
votes
1answer
252 views

Gödel's Second Incompleteness Theorem and Arithmetically Non-Definable Theories

My recursion theory knowledge has become a bit rusty, so I will appreciate any corrections for misstatements. Gödel's incompleteness theorem is often exploited by philosophical discussions which ...
4
votes
0answers
109 views

Incompleteness theorem

Correct me if I am wrong at any point! Godel's incompleteness theorem allows us to express "PA is consistent" in the language of Peano arithmetic, and shows that this is not provable in PA. Let's ...
1
vote
1answer
94 views

Prove true in natural numbers (Peano Arithmetic)

While reviewing old exercise sheets, I have found this question and am having difficulties understanding some of the logic: Let $\mathbb{N}$(natural numbers) be a model for Peano Arithmetic, that ...
1
vote
2answers
117 views

Prove $x' \neq x$ using Peano axioms

I am looking at Edmund Landau, Foundation of analysis and do not agree with is proof of Theorem 2 part 2. I put the pages here for easy reference (http://pbrd.co/1y89p7b and http://pbrd.co/1y89A2s). ...
1
vote
1answer
150 views

Definition of the sum of natural numbers

After define the natural numbers using the Peano axioms, I'm trying to understand the definition of sum between natural numbers, let $s$ be the successor function used in the Peano axioms. The most ...
2
votes
1answer
61 views

Why is it impossible to define multiplication in Presburger arithmetic yet possible to define exponentiation in Peano Arithmethic?

Hello my question is related to Why is it impossible to define multiplication in Presburger arithmetic? and to How is exponentiation defined in Peano arithmetic?. I would have preferred to add it as a ...
2
votes
3answers
95 views

Possible not countable extension of the natural numbers?

This question comes from:Is $1234567891011121314151617181920212223......$ an integer? We define $\mathcal{A}$ as the set of infinite strings of digits $$ \bar a_i=a_0 a_1a_2a_3\cdots a_i \cdots ...
3
votes
2answers
258 views

Why don't we use Presburger's arithmetic instead of Peano's arithmetic?

I was reading about quantifier elimination and discovered the Presburger Arithmetic, the article mentions two points about it: It is decidable, complete and consistent. It omits multiplication ...
2
votes
4answers
160 views

Another problem on Peano Axioms (indirectly) from Tao's Analysis book

In Terence Tao's book Analysis I, the definition of $1$ is given right after stating the first two axioms, namely the following axioms, Axiom 1. $0$ is a natural number. Then Tao elaborates the ...
1
vote
1answer
73 views

Why are all computable functions representable in PA?

I'm trying to understand the proof of the first incompleteness theorem, and more specifically, the diagonal lemma. Suppose $GN(x)$ is the Gödel Number of a formula $x$. The first step of the diagonal ...
1
vote
1answer
115 views

Reference request - Outline of Edward Nelson's Inconsistency Proof

Edward Nelson retracted his inconsistency proof before it was published. Unfortunately, the outline given by Nelson has been removed. Is there a copy of it on the web? I am interested in how the ...
6
votes
2answers
124 views

Why isn't it necessary to postulate the existence of $1$?

These are the Peano axioms, I'll focus on the second one now: If $a$ is a number, the successor of $a$ is a number. Basically, here is defined the successor function $S(n)=n+1$. My question is, ...
1
vote
2answers
71 views

For which subsystems T of 2nd order arithmetic is there a model of T + $\neg$Con(T)?

A theory T might have the following property: there is a model of T + $\neg$Con(T) 1st order PA has this property, but full 2nd order PA doesn't. Among subsystems of 2nd order arithmetic, which ones ...