All Questions
Tagged with theories-of-arithmetic induction
7 questions
2
votes
1
answer
154
views
The Dirichlet principle and arithmetical induction
Let us consider the Dirichlet principle as follows: for all natural numbers $n > k > 0$, there is no injection from $\{0, \dots, n-1\}$ into $\{0, \dots, k-1\}$.
Is it true that in some non-...
3
votes
1
answer
171
views
Models of arithmetical theory R + induction in which successor is not injective
Consider the arithmetical theory sometimes denoted by $\mathsf{R}$. The non-logical vocabulary of $\mathsf{R}$ consists of '$0$', '$S$', '$+$' and '$\times$'. The axioms of this theory are all true ...
7
votes
1
answer
246
views
Independent/Easy fraction of sentences over PA
Let $S(n)$ be the set of all sentences over PA of length at most $n$ (counting the quantifier symbols, boolean connectives, arithmetic operations and constants, and counting each variable as length $1$...
- 2,912
3
votes
2
answers
993
views
Neither Even Nor Odd Natural 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)$. In Even XOR Odd Infinities? I asked if this statement ...
- 687
9
votes
1
answer
1k
views
ERA, PRA, PA, transfinite induction and equivalences
I'm quite sure I don't understand very well the links between proof theoretical ordinals of theories, the axioms of transfinite induction and the objects a theory can prove to exist.
For instance I'm ...
1
vote
3
answers
3k
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((Sx=...
- 687
32
votes
11
answers
11k
views
Is PA consistent? do we know it?
1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please).
2) There are proofs (...