Articles of peano axioms

Peano arithmetic with the second-order induction axiom

I am in the middle of my PhD and I am trying to reinforce my knowledge of mathematics by studying the foundations of Analysis. The first task is to get the bases of the natural numbers. So for this I chose the ZFC axioms which gives the consistence of the PA axioms. My first question […]

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 mappings.” Good. Here they are: There is an element $0 \in \mathbb{N}$ We have $\sigma(0) \ne 0$ […]

Prove $\langle \mathbb{N}, x \mapsto x +1, 1 \rangle$ is a Peano system without circular reasoning

How can we show that the structure $\langle \mathbb{N}, x \mapsto x +1, 1 \rangle$ is a model of a Peano system? How can we show that it satisfies the axiom of induction? Don’t we have to implicitly rely on this axiom, and thereby make our reasoning circular? And if we do, then what has […]

clarify the term “arithmetics” when talking about Gödel's incompleteness theorems

I am not quite sure what really is meant when talking about “arithmetics” in context of Gödel’s incompleteness theorems. How I so far understand it: Gödel proved that every sufficiently powerful first-order theory is not both consistent and complete at the same time. This is, you pick a first-order language (so the logical symbols are […]

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 axiom schema of induction for each formula. I’m stuck at the step how to show $f$ is well defined. We can […]

Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific number $y$ such that Peano arithmetic proves $y = f(x)$. (This follows from the fact that $f$ is […]

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 \qquad a_i \in \{0,1,2,3,4,5,6,7,8,9\} $$ We can easily show, with Cantor’s diagonal proof, that $\mathcal{A}$ is a not countable set. We define : $$ \bar a_i =\bar b_i \iff a_i =b_i […]

Initial Segments of Modular Arithmetic

Modular arithmetic (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 is $\omega$-inconsistent and all infinite models of MA have non-standard elements. I have been been trying to figure out if every infinite model of MA is an initial segment of some […]

How do we know that certain concrete nonstandard models of the natural numbers satisfy the Peano axioms?

It is easy to come up with objects that do not satisfy the Peano axioms. For example, let $\Bbb{S} = \Bbb N \cup \{Z\}$, and $SZ = S0$. Then this clearly violates the axiom that says that $Sa=Sb\to a = b$, unless we agree that $Z=0$, in which case what we have is exactly the […]

Why is bounded induction stronger than open induction?

It seems to me that any formula in the language of first-order arithmetic which has only bounded quantifiers can be written as a formula without any quantifiers. For instance, “There exists an n < 1000 such that P(n)” can be written as “P(1) or P(2) or … or P(999)”, and “for all n < 100, […]