The provability tag has no wiki summary.
10
votes
2answers
74 views
Growth-rate vs totality
How can one prove the statement, "If a function grows fast enough, it cant be proven total in PA, unless PA is inconsistent"? How fast must it grow to be not provably total?
1
vote
2answers
48 views
formalized provability predicate and implication relation
$\DeclareMathOperator{\pvbl}{pvbl}$ Let $\pvbl$ be the formalized provability predicate.
Sentences $A$, $B$, $C$, $D$ have the following relation.
$\pvbl ( A \rightarrow B)$
$\pvbl ( C \rightarrow ...
2
votes
1answer
56 views
reverse direction of modus ponens
Let $\mathit{pvbl}$ is a formalized provability predicate.
If a sentence $X$ is decidable, then following is correct?
$$ \left(\mathit{pvbl}(X) \to \mathit{pvbl}(Y) \right) \implies \mathit{pvbl}(X ...
4
votes
2answers
101 views
Is it possible that two theories be equiconsistent, with Peano Arithmetic not able to prove this?
Do there exist first-order theories that are are equiconsistent, but which cannot be proven to be equiconsistent using Peano Arithmetic? (I hope not.)
1
vote
3answers
118 views
Proving square root of a square is the same as absolute value
Lets say I have a function defined as $f(x) = \sqrt {x^2}$. Common knowledge of square roots tells you to simplify to $f(x) = x$ (we'll call that $g(x)$) which may be the same problem, but it isn't ...
3
votes
1answer
69 views
properties of the provability predicate applied to open formulas
Good day!
Let $\mathrm{T}$ be a first-order theory which contains the Peano arithmetic and has a recursively enumerable set of axioms. It is well known that one can construct a predicate ...
0
votes
1answer
95 views
Why isn't GL system of provability logic reflexive?
Formula $\square p \rightarrow p$ (axiom T; corresponding to reflexive modal frames) is interpreted as "if p is provable, then p", or more precisely: for all realizations (all substitutions for $p$), ...
3
votes
1answer
194 views
Need help understanding a proof in Boolos's “The Logic of Provability”
I'm currently reading The Logic of Provability by George Boolos and there's a step in a proof that I don't understand.
The author has defined a system of modal logic called GL; its language has a ...
0
votes
0answers
101 views
Uniqueness of super godel numbers of $\varphi$ and $\neg \varphi$
Let $e_{0},e_{1},...,e_{n}$ be a sequence of wffs or other expressions. Code each $e_{i}$ by a regular godel number $g_{i}$, to yield a sequence of numbers $g_{0},g_{1},...,g_{n}$. Then encode this ...
