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.

10
votes
0answers
209 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 ...
5
votes
0answers
57 views

Axiomatizing a “bounded” companion to PA

There's nothing special about PA here, I'm just focusing on it since it's strong enough to ignore lots of minor technical issues around foundations. If switching to some other theory would yield a ...
4
votes
0answers
128 views

Algebraically Constructing the Natural Numbers Using a Binary Operation Satisfying Some Properties

Here is the proposed theory: Definition: Let $M$ be a nonempty set with a binary operation $+$ satisfying the following properties: P-0: The operation $+: M \times M \to M$ is both associative and ...
4
votes
0answers
114 views

Is there a weak set theory that can prove that the natural numbers is a model of PA?

$ZFC$ proves that $\mathbb N$ is a model of $PA$. Even $ZF$ does. How weak can go? In particular, is there some weak set theory that proves that $\mathbb N$ is a model of $PA$, but does not proof ...
4
votes
0answers
92 views

Show that there are only $\aleph_0$ many countable models of the following theory.

Consider a language $L$ with $<0,1,S>$, where $S$ is the successor function. Show that there are only $\aleph_0$ many countable models of Th$(\mathbb{N})$, under $L$. This is one of the ...
4
votes
0answers
114 views

Proving there is a unique binary operation we call multiplication

The following is a theorem from the book The Real Numbers and Real Analysis by Bloch which I am currently self-studying. I am pretty sure my proof for uniqueness is correct, but I am wondering is ...
4
votes
0answers
169 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 ...
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
0answers
398 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 > ...
3
votes
0answers
119 views

Let $m,n \in \mathbb{Z}$. Assume $m < n$. Then $m \leq n-1$.

My question is concerning my proof's validity in the theorem written below. If someone could take a moment and see if there is a flaw in it, I'd appreciate it. Lemma. There are no natural numbers ...
3
votes
0answers
210 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 ...
3
votes
0answers
101 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 $\vec{n}...
3
votes
0answers
478 views

True statements about natural numbers that are undecidable in Peano Arithmetic assuming consistency of PA only

I am looking for statements $P$ of Peano Arithmetic ($\textsf{PA}$) that have the following properties: They are as concrete and simple as possible. It is provable by finitistic means that neither $P$...
3
votes
0answers
166 views

Any new axioms for the natural numbers since Peano?

Have any axioms in addition to usual 2nd-order Peano axioms been found to significantly extend the class of derivable propositions about natural numbers?
3
votes
0answers
310 views

Why Does Induction Prove Multiplication is Commutative?

Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom: $$\forall x \forall y \forall z\bigr((...
2
votes
0answers
66 views

A property of representable functions?

Recall that a function $f:\mathbb{N}^k\rightarrow\mathbb{N}$ is representable in Peano arithmetic if there exists a formula $\varphi(x_1,\dots ,x_k,y)$ such that for every $n_1,\dots,n_k,m\in\mathbb{N}...
2
votes
0answers
155 views

Are 'numerals' closed under exponentiation?

I have read Edward Nelson's Warning signs of a possible collapse of contemporary mathematics a couple of times, it is a very interesting read, but I do not understand the conclusory paragraph. In ...
2
votes
0answers
74 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 ...
2
votes
0answers
49 views

Prove $[(n, k)] = 7^{*} \iff n - k = 7$

Prove $[(n, k)] = 7^{*} \iff n - k = 7$ given $7^{*} = [(8,1)] \in \mathbb{Z}$ and $k < n \in \mathbb{N}$ using any facts about addition in the Peano System. $k < n \in \mathbb{N}$ is defined ...
2
votes
0answers
135 views

Prove that the product of 2 positive natural numbers is also positive.

First time doing real analysis, using Tao's Analysis I, and I'm stuck in the second problem (2.3.2) If n and m are both positive, then nm is also positive. How do I prove such an obvious statement? I ...
2
votes
0answers
317 views

Recursive non-standard models?

Any algebraically closed field (ACF) is a model of Modular Arithmetic (MA). MA has the same axioms as first order Peano arithmetic except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. MA ...
2
votes
0answers
121 views

How strong is ramified predicative second-order arithmetic?

A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...
2
votes
0answers
106 views

Can we define root extraction using Peano Arithmetic?

I've been playing with Peano Arithmetic and I've got multiplication, division, exponentiation, and logarithms. I can't figure out root extraction but I have a stab at it. Exponentiation: $a^0 = 1, a^{...
1
vote
0answers
37 views

How is it shown using the additive cancellation law that $x\mapsto x+h$ has an inverse?

See Fundamentals of Mathematics, Volume 1 page 101, for context. This is one of those facts that is so obvious that I find it difficult to prove. My question regards part of the proof of the ...
1
vote
0answers
59 views

Nonstandard proof codes for Con(PA)

Note: This question is inspired by a paper being discussed in the FoM mailing list. The formal statement Con(PA) is a statement about the existence of a proof code for the derivation of a ...
1
vote
0answers
57 views

Why we care only about $\Pi_1$ parameters in axiom schemes?

There is exist tradition to formulate axiom schemes such as induction, comprehension or replacment in a way like "for each formula $\phi(y,\overline{x})$ with free variables $y$ and $\overline{x}=x_1,....
1
vote
0answers
120 views

How should this proof of the associativity of natural number addition be understood?

The context of this question is the proofs of the basic laws of arithmetic beginning with Peano's axioms which are stated starting with the number 1, rather than 0. The modified principle of induction ...
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 ...
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
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 ...
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
0answers
286 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 ...
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=\...
1
vote
0answers
73 views

First Incompleteness Theorem made exact…

First Incompleteness Theorem, according to WIKIpedia: "Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are ...
1
vote
0answers
90 views

What's a good source on how to construct all sets of numbers?

Lately I've been interested in building, formally, all sets of numbers, starting from ℕ, then ℤ, then ℚ, then ℙ, then ℝ, then iℝ, then ℂ. The only book I have come up, so far, is "Foundations of ...
1
vote
0answers
114 views

Why do we need second-order logic?

I often read that without second-order logic we can't have a theory of natural numbers because we wouldn't be able to express the well-ordering principle. OK, then there must be a flaw in the ...
1
vote
0answers
64 views

What are the practical (if any) problems with PA and the existence of non-standard models

Forgive me if this question sounds naive or somewhat poorly constructed due to my nebulous understanding of the concepts involved... I have recently been reading about the nature of PA, and how, ...
1
vote
0answers
40 views

Decidability of equations in True Arithmetic

Is the validity of equations (with variables) in True Arithmetic decidable? In 1, Andreas Blass argues that validity of negated equations is undecidable by sketching a reduction of Hilbert's 10th ...
1
vote
0answers
37 views

Is the tree of the complete extensions of a theory T a recursive tree?

I am trying to prove another statement, which is the following: There is a complete extension of PA whose degree is below 0'. Moreover, one can show that there is a complete extension T of PA in each ...
1
vote
0answers
42 views

Peano Equivalent for Rationals

First let us establish that There exists a bijection between rationals, $\mathbb{Q}$ and natural numbers $\mathbb{N}$. Using the Peano Axiom's (and considering Gödel's incompleteness theorem), we can ...
1
vote
0answers
213 views

if arithmetic is not axiomatizable, why are the Peano Axioms called so?

In mathematical logic it is proven that the theory of natural numbers is not axiomatizable nor enumerable, both in first order and second order logic. Where axiomatizable means: A theory (e.g. the ...
1
vote
0answers
28 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 $\...
1
vote
0answers
137 views

What is “Euclidean geometry, under Peano's axiom system”?

I read the following in the article on "Primitive Notion" on Wikipedia: Euclidean geometry, under Peano's axiom system the primitive notions are point, segment and motion. I could not find any ...
1
vote
0answers
541 views

Binary Representation of Complex Numbers

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 has finite models based on modular arithmetic. MA ...
1
vote
0answers
191 views

First Order Definitions of Finite

I would like some predicates in the language of first order Peano arithemetic (PA) that are true for the standard natural numbers and false for other types of numbers like negative numbers, fractions, ...
1
vote
0answers
361 views

Peano system vs natural numbers

What exactly is the difference between natural numbers and an arbitrary peano system? In particular there is a proof in my book for recursion on natural numbers, as well as an erroneous proof of ...
1
vote
0answers
140 views

Ring Theory and Induction

Andrew Boucher has developed a theory called General Arithmetic (GA): http://www.andrewboucher.com/papers/ga.pdf GA is a sub-theory of Peano Arithmetic (PA). If we add an induction schema (IND) to ...
0
votes
0answers
32 views

Basis of Mathematics

I was reading up on Goedel's Theorems and was wondering what exactly is the basis of Mathematics today and is the discussion around an axiomatic system settled? I know that there are several attempts ...
0
votes
0answers
147 views

How did mathematicans prove things before ZFC or Peano

I do not get it. How was a+b=b+a or a (b +c) = ab + ac proved by ancient mathematicians before set theory or Peano axioms? If you cannot logically prove the laws of arithmetic without Peano or set ...
0
votes
0answers
39 views

Why natural numbers are generalized in $\mathbb{Z}$ to ensure the group structure respect to the sum?

The natural numbers $\mathbb{N}$ are defined through the Peano axioms and then generalized in $\mathbb{Z}$ to ensure the group structure with respect to the sum. Why do we need to ensure such group ...