Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
967
questions
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 ...
- 171
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 ...
- 589
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 ...
- 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,...
- 1
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 ...
- 1,122
1
vote
1
answer
100
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 ...
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 ...
- 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 ...
- 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 ...
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'...
- 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 ...
- 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 ...
- 1
1
vote
2
answers
70
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,...
- 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 ...
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 ...
- 1,027