All Questions
Tagged with peano-axioms first-order-logic
156
questions
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 ...
- 301
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 ...
- 446
-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 ...
1
vote
1
answer
161
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, ...
- 4,432
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)$
...
- 103
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
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 ...
- 792
0
votes
0
answers
59
views
Non recursive provably total functions
It is provable that every primitive recursive function is total in 1st order PA. Some non primitive recursive functions are also provably total in PA.
Can we show that a function is totally provable ...
user1203803
0
votes
1
answer
47
views
Meaning of Provable recursiveness
Is there any difference between provably total function and provable recursiveness of a function in first order PA ?
From provably total I mean that the totality of the function itself is provable in ...
user1203803
0
votes
0
answers
40
views
Proving the set of true expressions in a theory cannot be expressed in this theory
Suppose we have a first-order theory $T_C$ that includes a binary function $C$.
$C$ is a bijection $\Sigma \to \mathbb{N}$ where $\Sigma$ is the alphabet of $T_C$.
The function $C$ is defined as ...
- 521
3
votes
1
answer
108
views
On the consistency of satisfiable first order theories
Considering this question, we know that a first order theory that admits a model has to be consistent.
A model for a theory $T$ in a language $\mathcal L$ is an interpretation of $\mathcal L$ in which ...
- 987
1
vote
1
answer
83
views
Does the property $T\vdash Pvbl_T(\ulcorner \sigma \urcorner) \implies T\vdash \sigma$ apply to set theories?
I know from other posts that $PA\vdash Pvbl_{PA}(\ulcorner \sigma \urcorner ) \implies PA\vdash \sigma$ and this applies to other extensions/restrictions of PA as well. Does it also apply to set ...
- 855
3
votes
3
answers
195
views
If Goldbach's conjecture G is undecidable in PA, then can we prove $\mathbb N\models G$?
Suppose Goldbach's conjecture $G$ is undecidable in first-order Peano arithmetic, $\sf{PA}$. That would mean there are models in which $G$ is true and other in which it is false. But intuitively, this ...
- 6,672