Skip to main content

Questions tagged [peano-axioms]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
78 views

Godel's incompleteness theorem: Question about effective axiomatization

I am studying Godel incompleteness theorems and I am struggling with the definition of effective axiomatization. From Wikipedia: A formal system is said to be effectively axiomatized (also called ...
Tereza Tizkova's user avatar
0 votes
0 answers
41 views

Understanding Peano Arithmatic and Axioms

I am new to analysis and started reading a PDF I found on Reddit, the link is here. I stumbled on a few question about basic Peano axioms and the definitions that the PDF derived from it. In case ...
Redwanul Sourav's user avatar
0 votes
0 answers
27 views

Proving the existence of hyperoperations in a Peano system

In Mendelson's "Number Systems" he defines and subsequently proves the existence and uniqueness of binary operators $+$ and $\times$, as well as exponentiation, in $P$ using the so-called ...
marsus16112's user avatar
1 vote
0 answers
35 views

Why is the material conditional treated like logical entailment in second order quantification? [closed]

According to this Wikipedia article the second order axiom of induction is: $$\forall P(P(0)\land \forall k(P(k) \to P(k+1)) \to \forall x(N(x) \to P(x))$$ Where N(x) means x is a natural number. That ...
Electro-blob's user avatar
0 votes
0 answers
31 views

Finite axiomatization of EFA

According to the paper Fragments of Peano's Arithmetic and the MRDP theorem (Section 6), elementary function arithmetic (EFA) is finitely axiomatizable. Is there a known explicite finite ...
user avatar
-3 votes
1 answer
63 views

Naive Set Theory - proof of commutativity of products

I am working through Halmos's Naive Set Theory on my own and trying to do all the exercises, including what are merely suggestions in the text. I am right now in section 13, which shows a derivation ...
Manuel Del Río Rodríguez's user avatar
0 votes
1 answer
37 views

Ability of Peano axiom with integer set?

Axioms: Peano Axioms (defines natural number, introducing 0 and ') For each predicate φ, there exist exactly one set X, s.t. forall x, φ(x) <=> x∈X. So, it's possible to define less-than in ...
l4m2's user avatar
  • 229
0 votes
2 answers
77 views

Axiomatic reason why $a=4 \implies a>1$ for $a \in \mathbb{N}$

This is a trivial task: Given $a \in \mathbb{N}$ and $$a=4$$ Show $$a > 1$$ Part of the challenge for newcomers like me is that "easy" tasks actually make it harder to think about the ...
Penelope's user avatar
  • 3,325
0 votes
1 answer
47 views

not precisely understanding what is asked by ex 3.5.13 Tao Analysis I (only one natural number system)

I am failing to understand the intent of the question posed by exercise 3.5.13 of Tao's Analysis I 4th ed. The purpose of this exercise is to show that there is essentially only one version of the ...
Penelope's user avatar
  • 3,325
2 votes
2 answers
75 views

Proof that each natural number has a unique successor

I've proven that every positive natural number has a unique predecessor using Peano's axioms. But now, I was wondering how I could prove that every natural number has a unique successor using the same ...
Aryaan's user avatar
  • 283
-1 votes
2 answers
159 views

How to justify why succession and addition cannot be circularly defined like this?

I am reading Tao's Analysis I, in which he states: One may be tempted to [define the successor of $n$ as] $n + 1$. . . but this would introduce a circularity in our foundations, since the notion of ...
Princess Mia's user avatar
  • 3,009
-2 votes
2 answers
152 views

Why is addition not completely defined here?

Say for the natural numbers, we define addition this way: $0 + 0 = 0$, and if $n+m = x$, then $S(n) + m = n+S(m) = S(x) $ Say we have the regular Peano axioms, except we delete the axiom of ...
Princess Mia's user avatar
  • 3,009
0 votes
0 answers
30 views

Question about the Peano axioms + linear order axioms

The signature consists of $S$, $0$ & $<$ and the axioms are: I - $\forall x (S(x) \not= 0)$ II - $\forall x \forall y (S(x) = S(y) \to x = y)$ III - First-order Induction schema IV - $<$ is ...
Hussein Aiman's user avatar
2 votes
2 answers
134 views

Is it circular to include reachability from $0$ like this as a Peano axiom?

I am wondering whether it makes logical and semantic sense to include, as an axiom to define the natural numbers, that "every natural number is either $0$ or the result of potentially repeated ...
Princess Mia's user avatar
  • 3,009
3 votes
1 answer
60 views

Specific example of a property $P$ that Peano arithmetic proves holds true for every specific number, but not for all numbers.

Can someone give a specific example, if there is any, of a predicate $P(x)$ expressible in the language of Peano arithmetic, such that the first-order theory of Peano Arithmetic proves $P(0)$, $P(1)$, ...
user107952's user avatar
  • 21.4k
-2 votes
2 answers
277 views

Can we modify the Peano axioms like this? [closed]

I am wondering if the following modifications of the Peano axioms result in a set of axioms equivalent to the Peano axioms, in the sense that any set of numbers satisfies these modified axioms if and ...
Princess Mia's user avatar
  • 3,009
1 vote
0 answers
25 views

Order type of cuts satisfying $\mathsf I\Sigma_n$

When $M$ is a model of Peano arithmetic, a cut of $M$ is an initial segment $I$ of $M$ such that $I$ is closed under successor. There is some work on cuts that satisfy $\mathsf I\Sigma_n$, Peano ...
C7X's user avatar
  • 1,311
2 votes
0 answers
76 views

Are the models of PA recursively enumerable?

Is there a Turing machine (TM from now on) which lists every model of PA (without the induction axiom schema, so just addition and multiplication)? More specifically, can such a TM list all infinite ...
nicholasbelotserkovskiy's user avatar
0 votes
1 answer
71 views

Proving that the set of non-negative half-integers satisfies Peano's axioms

I postulate that the following set $\{0,0.5,1,1.5,...\}$ represents the natural numbers. Of course, intuitively, this isn't true. But let me try to show this using Peano's axioms. I'll first define ...
Aryaan's user avatar
  • 283
1 vote
1 answer
53 views

Using Peano's axioms to disprove the existence of self-looping tendencies in natural numbers

Let me clarify by what I mean by "self-looping". So, we know that Peano's axioms use primitive terms like zero, natural number and the successor operation. Now, I want to prove that the ...
Aryaan's user avatar
  • 283
2 votes
1 answer
53 views

Peano Arithmetic can prove any finite subset of its axioms is consistent

Timothy Chow writes in a MathOverflow answer [...] here is a classical fact: for any finite subset of the axioms of PA (remember that PA contains an axiom schema and hence has infinitely many axioms),...
Christian Chapman's user avatar
0 votes
2 answers
36 views

Confusion about the validity of the proof of Trichotomy of order for natural numbers in Tao's Analysis

It's well-known that in Tao's Analysis I P28, he provides a provement of Trichotomy of order for natural numbers as follows. Denote the number of correct propositions among the three (i.e. $a<b,\ ...
Richard Mahler's user avatar
-2 votes
1 answer
53 views

Contradiction and Godel's incompleteness theorems

If T is a recursively axiomatizable formal system containing peano arithmetic and is able to carry out the proof for the Godel's incompleteness theorems (so according to Wikipedia includes primitive ...
Nikolai riber skånstrøm's user avatar
3 votes
1 answer
140 views

Is Gödels second incompleteness theorem provable within peano arithmetic?

All following notation and assumptions follow Gödel's Theorems and Zermelo's Axioms by Halbeisen and Krapf. Exercise 11.4 c) states "Conclude that the Second Incompleteness Theorem is provable ...
Lassadar's user avatar
  • 171
1 vote
1 answer
159 views

Understanding the Arithmetical Hierarchy

I am trying to get acquainted with the arithmetical hierarchy, and as I wrote down some examples, I got a bit confused. Consider the language $L=\{+\cdot,<,=,0,1\}$ of $\mathsf{PA}$. For example, ...
John's user avatar
  • 4,432
1 vote
1 answer
74 views

Why doesn't $RCA_0$ prove $\Sigma^0_1$-comprehension?

Answer: because that's $ACA_0$, alright, but: Friedman et al.'s 1983 "Countable algebra and set existence axioms" has [verbatim, including old terminology and dubious notation]: Lemma 1.6 ($...
ac15's user avatar
  • 1,084
0 votes
1 answer
77 views

Is it possible to construct a real number theory on Peano arithmetic?

I know how to construct $\mathbb{Z}, \mathbb{Q}, \mathbb{R}$ from $\mathbb{N}$ in set theory. For example, the construction of $\mathbb{Z}$ is, $$\mathbb{Z}=\mathbb{N}^2/\sim$$ $$(a, b)\sim(c, d)\...
MathMan's user avatar
  • 103
2 votes
1 answer
72 views

Is there a problem if I don't use $0$ in Peano arithmetic?

Peano arithmetic is the following list of axioms (along with the usual axioms of equality) plus induction schema. $\forall x \ (0 \neq S ( x ))$ $\forall x, y \ (S( x ) = S( y ) \Rightarrow x = y)$ ...
MathMan's user avatar
  • 103
0 votes
3 answers
241 views

Allegedly: the existence of a natural number and successors does not imply, without the Axiom of Infinity, the existence of an infinite set.

The Claim: From a conversation on Twitter, from someone whom I shall keep anonymous (pronouns he/him though), it was claimed: [T]he existence of natural numbers and the fact that given a natural ...
Shaun's user avatar
  • 45.7k
3 votes
1 answer
423 views

PA + "(PA + this axiom) is consistent"

By Gödel's second incompleteness theorem, no sufficiently powerful formal system can prove its own consistency. I was wondering what happens if one tries to manually append an axiom stating a formal ...
volcanrb's user avatar
  • 3,054
0 votes
2 answers
143 views

Help me check my proof of the cancellation law for natural numbers (without trichotomy)

can you guys help me check the fleshed out logic of 'my' proof of the cancellation law for the natural numbers? It's in Peano's system of the natural numbers with the recursive definitions of addition ...
mouldyfart's user avatar
0 votes
1 answer
80 views

Can we conclude that Peano's axioms consistent from soundness?

One of the corollaries of soundness says that if $\Gamma$ is satisfiable, then $\Gamma$ is consistent. I am wondering whether we can conclude that Peano's axioms $\mathsf{PA}$ is consistent from the ...
John Davies's user avatar
0 votes
1 answer
117 views

Proving the Weak Goodstein Theorem within $\mathsf{PA}$

In Cichon, E. A., A short proof of two recently discovered independence results using recursion theoretic methods, Proc. Am. Math. Soc. 87, 704-706 (1983). ZBL0512.03028. the following process is ...
John's user avatar
  • 4,432
0 votes
0 answers
94 views

Rigorous proof that cardinality of a disjoint union is the sum of cardinalities for finite sets

In a lot of books there are intuitive(but sort of hand wavy) proofs for finite, disjoint sets $A$ and $B$ that $$ |A \cup B| = |A| + |B| $$ since $A = \{a_1,a_2,a_3,\cdots,a_{|A|}\}$ and $B = \{b_1,...
MathCat's user avatar
1 vote
1 answer
171 views

Precise statement of Gödel's Incompleteness Theorems [duplicate]

I have seen the following statements of Gödel's Incompleteness Theorems: Gödel's First Incompleteness Theorem (v1) If $T$ is a recursively axiomatized consistent theory extending PA, then $T$ is ...
Gavin Dooley's user avatar
  • 1,122
1 vote
1 answer
99 views

In the axiomatic treatment of natural numbers, can we define what a natural number is?

In his book Number Systems and the Foundations of Analysis, Elliot Mendelson first defines a Peano system (p. 53). He then goes on to prove that two arbitrary Peano systems are isomorphic — they are ...
Mostafizur Rahman's user avatar
3 votes
2 answers
190 views

Do $P(0)$ and $P(n)\implies P(n+1)$ yield $P(5)$ without an axiom of induction?

As I understand it, Peano arithmetic needs the axiom of induction to prevent non-standard models of the natural numbers. Given $P(0)$ and $P(n)\implies P(n+1) \forall n\in \mathbb{N}$ I can apply ...
Numeral's user avatar
  • 1,860
1 vote
2 answers
104 views

Model Theory in the Language of Peano Arithmetic

Most introductory textbooks on model theory establish the theory based on the ZF set theory (e.g. [1]). In particular, a structure is defined to be a 4-tuple of sets, and so on. In [2], I came to ...
Student's user avatar
  • 1,822
-3 votes
1 answer
243 views

Why Löwenheim–Skolem theorem asserts the non-existence of such predicates in 1st order logic

Suppose there was a predicate, in the language of 1st order $ \mathsf {PA} $, such that it is only true for standard natural numbers i.e. it accepts ALL and ONLY standard natural number, and it ...
Alex Matyasaur's user avatar
0 votes
1 answer
109 views

Confusion about $\mathsf{PA}$'s self-provable consistency sentences

Edit: This long question was basically answered by a quick comment! I'll accept an answer if someone posts one, but it's basically answered already. Background: In Peter Smith's Introduction to Gödel'...
WillG's user avatar
  • 6,672
1 vote
1 answer
144 views

Infinite statements from finite axioms

I want to know if a given finite subset of axioms of PA1 ( 1st order peano arithmetic ) can prove infinite sentences in PA1 such that those proofs need no other axioms except those in the given finite ...
jason's user avatar
  • 1
0 votes
1 answer
113 views

is arithmetic finitely consistent? [duplicate]

Let's take PA1( First order axioms of peano arithmetic ) for example. From godel's 2nd incompleteness theorem, PA1 can't prove its own consistency, more specifically it can't prove that the largest ...
jason's user avatar
  • 1
1 vote
2 answers
69 views

Modern reference on PA degrees?

I'm currently trying to work my way around some papers from Jockush et al, and PA degrees come up frequently. I'd be interested in a modern reference/survey summarizing the main results on the subject,...
Robly18's user avatar
  • 461
0 votes
1 answer
61 views

The Peano Axioms in Polish Notation

I am new to Polish Notation, and would like someone to translate the Peano axioms into PN for me. Either the first order or second order axioms would do, but if you can do both that would be much ...
Anthony Khodanian's user avatar
3 votes
1 answer
97 views

Are there examples of statements not provable in PA that do not require fast growing (not prf) functions?

Goodstein's theorem is an example of a statement that is not provable in PA. The Goodstein function, $\mathcal {G}:\mathbb {N} \to \mathbb {N}$, defined such that $\mathcal {G}(n)$ is the length of ...
Burnsba's user avatar
  • 1,027
0 votes
2 answers
65 views

Peano axioms - do we need a specific property to show that the principle of mathematical induction implies the "correct" set of natural numbers?

From Terence Tao's Analysis I, Axiom 2.5 for the natural numbers reads My intuition behind this axiom is that every natural number is an element of a "chain" of natural numbers that goes ...
jvf's user avatar
  • 585
6 votes
2 answers
886 views

Formally how do we view finite sets

This might be silly, but I have been thinking about how we would work with finite sets very formally. So, $\{1,2,3,\cdots,n\} = \{k \in \mathbb{Z}^+ \mid k \leq n\}$ gives a representee for which any ...
MathNerd23571113's user avatar
6 votes
5 answers
2k views

Confusion about Löb's theorem [duplicate]

To quote wikipedia: Löb's theorem states that in any formal system that includes PA, for any formula P, if it is provable in PA that "if P is provable in PA then P is true", then P is ...
G. Bellaard's user avatar
0 votes
0 answers
32 views

Is pointwise definability of a model of PA equivalent to it being the standard model? [duplicate]

The standard model of Peano Arithmetic is pointwise definable, because every finite natural number is parameter-free definable. What about the converse? That is, if a model $M$ of PA is pointwise ...
user107952's user avatar
  • 21.4k
3 votes
1 answer
196 views

What are the parameter-free definable elements of a model of Peano Arithemetic?

Let $M$ be a model of Peano Arithmetic. What are the parameter-free definable elements of $M$? I conjecture that they are precisely the standard natural numbers, meaning, no nonstandard infinite ...
user107952's user avatar
  • 21.4k

1
2 3 4 5
20