Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [peano-axioms]

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

23
votes
5answers
4k views

Why does induction have to be an axiom?

I noticed that there is an axiom that says that if $S(n)\implies S(n+1)$, and $S(1)$ is true, then $\forall n \in \Bbb N, S(n).$ My question is why is this an axiom? why can't we derive this from the ...
1
vote
1answer
39 views

Proof that an injective system with $i\notin\textrm{ran}{f}$ has a Peano subsystem.

I follow this link, in particular Exercise 2 at the bottom of page 3. Def 1. A System is a tripple $(X,i,f)$, where $X$ is a set, $i$ is called initial element, and $f$ is a function $X\to X$. Def 2....
4
votes
1answer
62 views

Can bounded addition and multiplication be computable in a non-standard model of arithmetic?

Let $M = (N, \oplus, \otimes, <_M, 0_M, 1_M)$ be a nonstandard model of peano arithmetic. $\oplus$ and $\otimes$ are uncomputable due to Tennenbaum's theorem. For $c \in N$, let $\oplus_{<c}, \...
0
votes
1answer
63 views

Can second order peano arithmetic prove that first order peano arithmetic is sound? [closed]

Can second order peano arithmetic prove that first order peano arithmetic is sound? Note that I'm not just talking about its axioms, but also its theorems.
1
vote
1answer
95 views

Is the famous problem number #6 solvable in first order Peano arithmetic?

I just came accross the famous "very difficult" problem 6 of the 1988 International Mathematical Olympiad: Let $a$ and $b$ be positive integers and $k=\frac{a^2+b^2}{1+ab}$. Show that if $k$ is an ...
1
vote
2answers
261 views

Can Peano Arithmetic show that the Continuum Hypothesis is Independent of ZFC?

Can Peano Arithmetic show that the Continuum Hypothesis is Independent of ZFC? In other words, is $PA \vdash Con(ZFC) \implies Con (ZFC + CH) \land Con(ZFC + \lnot CH)$ true? I believe the answer is ...
6
votes
2answers
106 views

Can two different models of arithmetic have non-comparable views of peano arithmetic?

For a given model of arithmetic $M$, we say that models view of peano arithmetic, $V(M)$, is $\{\phi : M \models (PA \vdash \phi) \}$. For example the view of the standard model is $\{\phi : PA \...
3
votes
0answers
105 views

Mathematical Induction and Peano Arithmetic

Peano Arithmetic cannot employ Induction for any ε0 ordering. My question is too easy to be interesting and there is a reason obviously for why it has a negative answer. Can you please provide it for ...
3
votes
1answer
372 views

How can we be so sure that we don't live in Pudlak's inconsistent world?

In his Logical Foundation of Mathematics and Computational Complexity (2013), Pavel Pudlak invites the readers to ponder about fictitious people whose natural numbers are nonstandard. His exposition ...
2
votes
1answer
124 views

Can Peano arithmetic prove 0=1 in a standard number of steps (in a non-standard model)?

Let $M$ be a model of $PA + \lnot Con(PA)$. Therefore, there exists an object $p \in \mathbb N_M$ encoding the the $PA \vdash 0=1$. Is there such a model $M$ and $p \in \mathbb N_M$ such that the ...
1
vote
1answer
83 views

Differences between real numbers in $ACA_0 + \lnot Con(PA)$ and standard real numbers?

Let $M = (\mathbb N_M, 0_M, +_M, \times_M, <_M, D_M)$ be a model of $ACA_0 + \lnot Con(PA)$. We define $\mathbb R_M$ as Dedekind cuts on $D_M$. What can we say about the differences between $\...
0
votes
1answer
86 views

ZFC-Infinity+PA: Does it prove Con(PA)?

We define the theory ZFC-Infinity+PA as follows. We start with the axioms of ZFC-Infinity. Next we assert that there is a model of arithmetic $(\mathbb N, 0, S, +, \times)$. Next, for every axiom of (...
4
votes
1answer
83 views

Systems of arithmetic models [closed]

Presburger Arithmetic is decidable theory but weaker than Peano Arithmetic. Are there systems in some sense that are: stronger than Presburger but weaker than Peano and remain decidable? weaker than ...
10
votes
1answer
1k views

Is it a paradox if I prove something as unprovable?

The Goldbach Conjecture asserts: It is possible to write every even number greater that 2 as the sum of two primes. Assume I can prove that the Goldbach Conjecture is unprovable from the Peano ...
1
vote
0answers
35 views

How to prove Peano induction axiom for a candidate model

Suppose you have a candidate structure, and you want to prove it satisfies the Peano axioms. For example, let 1 serve as the first element, and let $s(x)=x/(1+x)$. It's easy to see the non-induction ...
0
votes
2answers
67 views

Looking for examples that illustrate the use of the $\operatorname{seq}$ notation

This question is about the $\operatorname{seq}$ "notation" (for lack of a better word) defined in https://math.stackexchange.com/a/312915/13675 Can someone give some concrete examples illustrating ...
2
votes
2answers
61 views

Prove $\Bbb{N}$ is infinite from Peano axioms

Let there be a set $\Bbb{N}$ defined by these 3 axioms: There exists a set $\Bbb{N}$ such that $1\in \Bbb{N}$ and a function $s:\Bbb{N}\rightarrow\Bbb{N}$ satisfying these properties: $$\not\exists ...
1
vote
0answers
42 views

Strongest decidable system of arithmetics

I have taken no formal mathematics logic course yet, I'm sorry for unclear parts of this question. I've learned about Presburger Arithmetics few days ago, it seemed really interesting. But since then,...
1
vote
1answer
59 views

Is the set of bounded quantified sentences decidable in PA

In the first order theory of $\mathbb N$ with $+$ and $\cdot$ is the set of formulas with bounded quantifiers (universal and existential) decidable, i.e. can we decide for a given such sentence if it ...
2
votes
1answer
51 views

Categoricity of categorical arithmetic

Consider the elementary theory of the category of sets (ETCS). Inside this framework, we have that $(\mathbb N, 0, s)$ is a natural number objet and that : it is a model of the Peano axioms, it is ...
1
vote
1answer
51 views

Limit case of PA theories?

It seems to me that if one is to "believe" in PA, then one must "believe" in Con(PA) (this is, in some sense, what it means to believe in the theory!). Similarly, I think such a wishful thinker might ...
4
votes
1answer
130 views

Are statements of arithmetic without logical negation or existential quantifiers decidable?

Consider the set of statements of arithmetic, such that: the statement contains no existential quantifiers, only universal quantifiers; the statement contains only logical ...
1
vote
1answer
161 views

Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b\text{++} =a$.

In Terence Tao's Analyis Volume One. He presents that following Lemma. I would like to know if the argument presented below is correct? For your ease i have presented the relevant Peano's axiom as ...
3
votes
1answer
82 views

Are there “structure-specific” logical axiomatic systems? Do these have extra power?

I suspect that it will be hard to correctly convey this question, but here goes: How its normally done: The way I've been taught, and what is normally done in mathematical logic, is as follows: We ...
0
votes
1answer
68 views

Does Gödel's theorem rule out derivations from all possible logical systems or just first-order logic?

Gödel's first incompleteness theorem excludes the possibility of formulating a consistent and decidable set of first order sentences which are true in standard arithmetic from which the truth/...
1
vote
1answer
88 views

How much of first order statements can we derive purely from the definitions in arithmetic?

I didn't know how to formulate a more clear title for this question: Take arithmetic to be the structure $\mathcal N= (\mathbb N, \sigma, +,•, 0,1)$ with its standard interpretation. When I use the ...
1
vote
1answer
45 views

Proving that for $x \neq 0$ there exists a $y$ such that $S(y) = x$.

In another proof of mine I had written: Since $d \neq 0$ we can write $S(k) = d$ for some $k$ without violating Peano's 3rd axiom. Apparently this isn't a valid step in a proof so I want to more ...
1
vote
1answer
82 views

Is my proof correct that $a < b \implies S(a) \leq b$?

Proof 1.1: $a < b \iff b = a + d$ for some positive natural number $d$ First we prove that $a < b \implies b = a + d$ for positive $d$. We will prove it by contradiction. Suppose that $d$ is ...
0
votes
4answers
52 views

$a < b$ iff $S(a) \leq b$

I want to prove $a < b$ iff $S(a) \leq b$ but I can't figure it out for the life of me, how to even begin. $S(a)$ is the successor of $a$ and $a < b$ is defined as $a \leq b$ with $a \neq b$. ...
0
votes
0answers
56 views

$(m \not \mid n \wedge m \neq 0) \Leftrightarrow (\exists p, 0<q<m \text{ s.t } n=pm+q)$ [Proof Verification]

Please check if my proof has any error! I'm very happy to receive any suggestion to improve my proof. Many thanks for your help. Definition: $m \text{ divides } n \Leftrightarrow \exists p, n=pm$. ...
1
vote
0answers
58 views

Equivalence of $I\Sigma_n$ and $I\Pi_n$

PA$^{-}\vdash I\Sigma_n \leftrightarrow I\Pi_n$. Here $I\Sigma_n$ refers to the induction principle restricted to $\Sigma_n$ formulas. PA$^{-}$ is just PA without induction. I was reading the paper ...
2
votes
2answers
96 views

$\forall n \in \mathbb{N}, n$ is even $\Leftrightarrow n+1$ is odd

I would like to prove this theorem with only basic properties of Peano's axioms, addition, and multiplication. Please have a check of my below proof. Many thanks for your help! In my definition: $...
0
votes
2answers
93 views

Why isn't $0+a=a$ something we derive?

In the usual natural number definition of addition $0+a=a$ is taken as true by definition. This feels like it should be something we derive from $0+0=0$, instead? As in, let's define addition this way:...
1
vote
0answers
72 views

Having Trouble Seeing Why Friedman's Theorem (1973) is true.

I am reading about non-standard models of peano arithmetic, and came across a theorem by Friedman that states the following. Every non-standard countable model of (peano) arithmetic is isomorphic ...
1
vote
1answer
323 views

Proving distributive law of natural numbers

Is my proof correct? If we define multiplication for natural numbers as $a \times S(b) = (a \times b) + a$ $a \times 0 = 0$ And addition as $a + 0 = a$ $a + S(b) = S(a+b)$ Where $S(n)$ is the ...
3
votes
0answers
396 views

Proving the trichotomy of order for the natural numbers

Is my proof correct? The trichotomy of order for natural numbers states: Let $a,b$ be natural numbers. Then exactly one of the following statements is true: I. $a < b$ II. $a = b$ III. $a > ...
0
votes
1answer
38 views

Trying to prove various things about (in)equalities

After defining things like natural numbers and addition, I'd like to prove some things about the operator $\leq$ and ask if they are correct. Definition 1: Let $a$ and $b$ be natural numbers. We say ...
1
vote
2answers
149 views

“Recursive definitions” in Tao's Analysis Vol I

I am totally confused when Tao gets into recursive definitions (page 26). Paraphrasing, the axioms of natural numbers let us define sequences recursively. Suppose we want to build a sequence $a_0, ...
0
votes
2answers
83 views

What let's us do stuff like $F(a) = F(b)$ for $a=b$? [duplicate]

In Tao's Analysis vol 1 we have various proofs from properties and operations on natural numbers, as well as axioms. For example additive identity $a+0=a$. But then in some proofs we apply these ...
1
vote
1answer
48 views

Are my proofs correct for basic addition properties for natural numbers?

Are my proofs correct? Additive Identity: $a + 0 = a$ Definition of Addition: $a + S(b) = S(a + b)$ where $S(a)$ is the successor of $a$. Claim: $0 + a = a$. Base Case: When $a=0$, we have $0 + ...
0
votes
0answers
59 views

A question about the math definition of predecessor

Every natural number, with the exception of $0$, has a predecessor: $\mathbb{N}^{+} = \mathbb{N} \backslash \{0\}$ I know what predecessor means but can't understand this equation.
1
vote
3answers
50 views

(How) can we derive “primary school rules of arithmetic” from the peano axioms?

The Peano axioms are intended to be able to prove very general statements about arithmetic, such as "all natural numbers can be written as the sum of two primes". However, how can we use the peano ...
1
vote
0answers
285 views

Prove cancellation law on multiplication without using trichotomy of order

In textbook A Course in Mathematical Analysis by prof D. J. H. Garling, the author proves the cancellation law in multiplication before he moves on to prove the trichotomy of order. I have tried to ...
2
votes
1answer
97 views

What does elementary function arithmetic without the induction axiom tell us about the exponential function?

We can extend Robinson arithmetic (Q) to include exponentiation, using the axioms 1) $x^0=1$ and 2) $x^{S(n)} = x^n*x$. Wiki page How much can this extension actually say about exponentiation? ...
1
vote
1answer
25 views

Interpretations and Peano arithmetic

In a step of a proof about Peano arithmetic the following calculation is made: $N(ss^k0)=N(s)N(s^k0)$ where $N$ is the interpretation which identifies $sx$ with $S(x)$ where $S$ is the successor ...
1
vote
4answers
92 views

Why isn't the additive identity also an axiom?

In the Peano axioms, the concept of addition is described: $$a+0=a$$ $$a+S(b)=S(a+b)$$ where $S(n)$ is the successor function. As far as I can tell $a+0=a$ is (even in books such as Tao's Analysis ...
1
vote
0answers
69 views

Mathematical induction - the set version v.s. predicate version

There are two versions I know for mathematical induction, as well as structural induction. One says for all subset $S$ of $\Bbb N$, $1\in S\wedge (\forall n,~n\in S\rightarrow s(n)\in S)\rightarrow S=\...
0
votes
1answer
39 views

Is it to say that whenever we use mathematical induction, we're inevitably admitting Peano axioms for $\Bbb N$ indeed?

From Enderton's mathematical logic book sec 1.1, there is a thing called construction sequence for wffs. For example, $P\wedge Q\to R$ can be thought as $\langle P,~Q,~P\wedge Q,~R,~P\wedge Q\to R\...
2
votes
1answer
91 views

Variations in the Statement of Strong Induction: Equivalent or Different?

I often see two variations in how the principle of strong induction is stated: First Variation: $\Big(B\!\subseteq\!\mathbb{N}\wedge1\!\in\!B\wedge\big(\forall x[x\!\leq\!k\rightarrow x\!\in\!B]\...
0
votes
1answer
44 views

Is $K_{n-1}$ a $\Sigma_{n-1}$-elementary substruture of $K_n$ [closed]

Is $K_{n-1}$ a $\Sigma_{n-1}$ elementary substruture of $K_n$? Let $M$ be any non-standard model of PA. $K_n$ is define to be the set of $\Sigma_n$-definable elements of $M$. I have a feeling the ...