Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with lo.logic
Search options answers only
not deleted
user 113213
first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, theories of truth, truth revision, consistency.
14
votes
Accepted
Is there a $\Pi_2$ sentence $A$ such that $\text{ZFC}^- + A$ proves powerset?
No, using downward Löwenheim-Skolem theorem (and transitive collapses), every true $Π_2$ statement holds in $H(λ)$ for every cardinal $λ>ω$. ($H(λ)$ consists of all sets whose transitive closure has …
- 7,545
4
votes
Accepted
Descriptive complexity of analytic continuation
For an analytic function given by its power series, existence of an analytic continuation to some open set intersecting the unit circle is $Σ^0_2$.
To see this, for an analytic function, its power ser …
- 7,545
4
votes
Accepted
Numerical choice and reverse mathematics
Both your choice principle, and its weakening to only give upper bounds, are equivalent to $\text{ATR}_0$ over $\text{RCA}_0$. I think your question provides a good illustration of hyperarithmetic th …
- 7,545
5
votes
Are Berkeley cardinals easier to refute in ZFC than Reinhardt cardinals?
Here is another even simpler refutation. Recall that $δ$ is Berkeley iff for every predicate $A$ and $α≥δ$, there is a nontrivial elementary self-embeding of $(V_α,∈,A)$ with critical point $<δ$. (T …
- 7,545
9
votes
Accepted
Which are the hereditarily computably enumerable sets?
The complexity of h.c.e. sets is quite subtle as the structure of the target set affects our ability to offload complexity to the limiting process. The property of being an h.c.e. code is $Π^1_1$ com …
- 7,545
4
votes
Accepted
1970 question of Reinhardt - how large is this ordinal?
The consistency strength is above that of $n$-iterable cardinals for finite $n$. Thus, despite the seeming weakness of the statement, the $ω$-Erdős upper bound given by Reinhardt is fairly close to t …
- 7,545
6
votes
Accepted
How much of second-order arithmetic do you need for $\mathbf{\Sigma}^1_1$-determinacy to giv...
$\mathsf{RCA}_0 + \mathbf{\Sigma}^1_1\text{-Det}$ suffices to get sharps for all reals (and thus ctm of ZFC and more).
With boldface determinacy principles, we can bootstrap the background theory. $\ …
- 7,545
12
votes
Accepted
How much determinacy do you need for second order arithmetic to be as strong as ZFC?
Because ZFC proves soundness of $\text{Z}_2$, no consistent finite extension of $\text{Z}_2$ proves all second order arithmetic statements that are provable in ZFC (for example, the statement "the con …
- 7,545
3
votes
Accepted
Axiomatization of S2S
S2S can be axiomatized by:
$∃!s ∀t \, (t0≠s ∧ t1≠s)$ (empty string, denoted by $ε$)
$∀s,t \, ∀i∈\{0,1\} \, ∀j∈\{0,1\} \, (si=tj ⇒ s=t ∧ i=j)$ (tree successors; the use of $i$ and $j$ is an abbrevi …
- 7,545
21
votes
Do we expect that sufficiently large computable ordinals settle every question of arithmetic?
The claim of well-foundedness depends not only on the ordinal $α$, but also on how $α$ is represented by a recursive well-ordering.
Pathological representations
Strong statements from small ordinals: …
- 7,545
3
votes
Accepted
On the strength of higher-logic analogues of $\mathsf{ZFC}$ + Montague's Reflection Principle
The first chromatic cardinal is the first Mahlo cardinal. (Per the connection with the reflection in the question, I assume that in the definition, $α$ and the first argument of $c_i$ need not be ina …
- 7,545
2
votes
What sort of cardinal number is the Löwenheim–Skolem number for second-order logic?
The Löwenheim number (compared to LS, this uses sentences rather than theories) for the second order logic $L^2$ is the least $κ$ such that $V_κ$ satisfies all true $Σ_2$ sentences. This $κ$ has cofi …
- 7,545
3
votes
Accepted
How large are the stabilization times of Ordinal Turing Machines with an oracle for the tran...
For ordinal Turing machines with an oracle $S⊂Ord$,
- the set/class of output locations that are written at some point is $Σ^{L[S]}_{1,S}$ (i.e. $Σ_1$ in $L[S]$ with a predicate for $S$) and can be ar …
- 7,545
2
votes
How large is the supremum of halting times of Infinite Time Turing Machines, assuming that h...
The ordinal is the supremum of the ordinals in the $Σ_2$ hull of $L_{ω_1}$. It is robust to the choice of the computational model as long as (uniformly in $x$) the halting problem is $Π^1_1(x)$-hard …
- 7,545
7
votes
Accepted
What is the Turing degree of the monadic theory of the real line?
Gurevich and Shelah showed in The monadic theory and the “next world” that the monadic theory of the real line (or even just the Cantor Discontinuum) can compute
- the $V^B$ theory of second order ari …
- 7,545