Skip to main content
Benedict Eastaugh's user avatar
Benedict Eastaugh's user avatar
Benedict Eastaugh's user avatar
Benedict Eastaugh
  • Member for 14 years, 1 month
  • Last seen this week
awarded
comment
Does the consistency of a large cardinal axiom imply the $\omega$-consistency of that axiom?
Note that Emil Jeřábek's answer also provides a negative answer to the second question of whether the consistency of some large cardinal axiom implies the existence of an $\omega$-model of that axiom, since consistency in $\omega$-logic (equivalent to the existence of an $\omega$-model via the Henkin–Orey completeness theorem) strictly implies $\omega$-consistency.
revised
How much choice is needed to show that formally real fields can be ordered?
Added note on provability in RCA0 of existence of real closure for countable ordered fields
Loading…
Loading…
comment
Turing degrees of sets separating two computably inseparable sets (theorems and antitheorems)
You could also look at §3.7 of Soare's 2016 book Turing Computability; the low basis theorem is theorem 3.7.2. A nice survey is also given by Diamondstone, Dzhafarov and Soare, '$\Pi^0_1$ classes, Peano arithmetic, randomness, and computable domination' (NDJFL 51(1):127–159, 2010).
comment
Can a halting oracle determine if a Turing machine is an ordinal?
The set of (indexes of) recursive ordinals, aka Kleene's $\mathcal{O}$, is $\Pi^1_1$-complete, so you would need an oracle for a $\Pi^1_1$-complete set.
awarded
Loading…
comment
How can Kőnig's Lemma be expressed in Monadic Second-Order Logic of 2 Successors?
@NoahSchweber I don't think $\mathsf{WKL}_0$ is conservative over $\mathsf{RCA}_0$ for $\Sigma^1_1$ sentences. $\Pi^1_1$ sentences yes, but for $\Sigma^1_1$ sentences an instance of WKL for a recursive counterexample like the Kleene tree will be a $\Sigma^1_1$ sentence that $\mathsf{RCA}_0$ cannot prove.
awarded
answered
Loading…
comment
Self-referential Quinean proof of Löb's Theorem
It seems like a proof of this sort would just be pushing the fixed-point lemma into the Gödel numbering. See for example Appendix A of Halbach and Visser (2014).
Loading…
comment
Simple constructive proof for the hyperplane separating theorem (HST)?
I would imagine that one could prove this result from an appropriate constructive version of the Hahn–Banach theorem, e.g. the one in §9.3 of Bishop's 1967 book Foundations of Constructive Analysis.
awarded
awarded
awarded
revised
Loading…
comment
Does the fixed point lemma / diagonalization require capturing or not?
$\psi$, although on re-reading I see that the sentence was less clearly phrased than it could have been.