# Questions tagged [peano-axioms]

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

160 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2k views

• 1,047
80 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 ...
• 229k
114 views

### Can ZFC decide more values of the Busy Beaver function than PA?

This is related to a previous question. In that question, I asked whether ZFC can define the Busy Beaver function. I was told even Peano Arithmetic(PA) can define it, and also that PA can't decide ...
• 16.8k
393 views

• 9,837
130 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 ...
• 9,837
116 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 ...
• 2,097
305 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 ...
• 201
736 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$...
• 18.4k
298 views

### What is one set of axioms which are sufficient for Calculus?

I am curious to find out what are the "minimum axioms" needed in order to be able to have highschool level math. Another way to explain it: if we were visited by a super intelligent race of aliens (...
• 22.7k
31 views

### In RCA0, Prove that for all n, fⁿ(i) exists

I wanted to prove in RCA0 that: If f:A→A be a function and i∈A, then for all n, fⁿ(i) exists. To reach that, I proved another theorem. I wrote my proof but I'm not sure it's rigorous. If you read it, ...
67 views

• 31
106 views

• 133
44 views

### Is Peano arithmetic considered to be an algebraic structure?

(Sorry if I'm a imprecise in my formulations, I am new to math.) I recently discovered algebraic structures and they seem quite fundamental, I'm wondering whether Peano arithmetic could be expressed ...
104 views

### Did all axiomatic systems face a crisis with the discovery of Russell's paradox?

When Bertrand Russell outlined his paradox to Gottlob Frege just as his Grundgesetze was going to print, it effectively destroyed the consistency of Frege's theory of arithmetic. But was this the ...
• 757
28 views

I'm trying to solve the following question set by my professor: Show that if $S$ is a definable set of sentences, and $Pr_S$ is an associated proof predicate, and $X$ and $Y$ are any formulae, then $... • 21 2 votes 0 answers 301 views ### Proof of commutativity of addition using Peano axioms I'm studying the proof of commutativity of addition using only Peano axioms (with the distinguished element being 0 rather than 1), the definition of addition, and x+0=0+x=x. The main idea is ... 2 votes 0 answers 263 views ### Exercise 2.2.1 in Analysis by Terence Tao Induction Proof of Addition Associative Law Natural Numbers The proposition 2.2.5 and also exercise 2.2.1 of Analysis by Terence Tao is as below: Show for any natural numbers$a, b, c$, we have$(a+b)+c = a+(b+c)$the associative rule The proof should use ... • 499 2 votes 0 answers 50 views ### What examples of known theorems of PA that were first provable in stronger set theories like Z or ZFC? Are there known examples of theorems of$\sf PA$that were first proved in systems vastly more powerful than$\sf PA$, like$\sf ZFC$for example, and then afterwards the proof of them in$\sf PA$was ... • 4,137 2 votes 0 answers 101 views ### What is the omega-completion of$ACA_0$The omega rule is an infinitary rule of logic which says that from$\phi(0),\phi(1),\phi(2),...$you can infer$\forall n\phi(n)$. My question is, what is the theory$T$obtained by adding the omega ... • 9,852 2 votes 0 answers 93 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}...
• 3,287
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 ...