Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
167
questions with no upvoted or accepted answers
7
votes
0
answers
3k
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 > ...
- 5,651
6
votes
0
answers
175
views
To what degree are arbitrary true statements about the natural numbers provable?
Gödel's First Incompleteness Theorem states that if we have a recursive and consistent set of axioms $A$ in $\mathcal{L}_{\text{NT}}$, then there is a true first order statement about natural numbers $...
- 961
6
votes
0
answers
103
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 ...
- 249k
5
votes
0
answers
154
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 ...
- 21.4k
5
votes
0
answers
434
views
Independence of First-Order Peano Axioms
In class was given these 7 (first-order) axioms of Peano arithmetic (the + denotes successor):
NT1 $\quad(\forall x) \neg\left(x^{+}=\overline{0}\right)$
NT2 $\quad(\forall x)(\forall y)\left(x^{+}=y^...
- 887
4
votes
0
answers
69
views
There are no loops in a Peano system. I've attempted a proof. Is my proof correct?
Definition (Peano systems). Suppose $P$ is a set, $1 \in P$, and $S: P \to P$ is a function. The triple $(P, S, 1)$ is a Peano system if the following conditions hold.
(P1) $\forall x (1 \neq S(x))$, ...
4
votes
0
answers
121
views
Is there a least standard model of Peano Arithmetics?
Here's the informal part: I'm trying to get a better intuition about the differences between the standard model and the non-standard ones. Some people seem to be really good at imagining what non-...
- 41
4
votes
0
answers
87
views
Peter Smith's Hilbertian argument
Peter Smith in "An Introduction to Gödel's Theorems" presents a broadly Hilbertian argument (in the sense of Hilbert's program) on page 276 (2nd edition):
Theorem 37.2 If $I$ is consistent ...
- 1,718
4
votes
0
answers
102
views
Every provably recursive function in PA is bounded by a Hardy function
The following lemma and proof are from Takeuti's Proof Theory (2nd edition, pp. 126-127), I've highlighted the problematic part in blue:
How does Takeuti get this inequality? If the proof $x$ is not ...
- 1,718
4
votes
0
answers
102
views
Characterization of provably recursive functions in PA
This concerns Takeuti's Proof Theory: the book contains a lot of wonderful material, but the presentation is sometimes lacking (and so many typos!). At least that has been my experience so far, ...
- 1,718
4
votes
0
answers
301
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 ...
- 11.5k
4
votes
1
answer
100
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}, \...
- 10.5k
4
votes
0
answers
131
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 ...
- 10.5k
4
votes
0
answers
118
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,157
4
votes
0
answers
353
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