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.
3
votes
Infinite descending consistency chains
Informed by Fedor Pakhomov's excellent answer, and using "slow" iterated $Σ_1$-soundness, here is an infinite sequence of sound theories $T$ such that $T_i$ = PA + 1-Con($T_{i+1}$).
Set $T_i$ = PA + …
- 7,545
6
votes
Infinitary generalizations of HOD
If the number of parameters is unlimited (i.e. ordinals can be used as literals) (but see the addendum if that is not the case), then $\mathrm{HOD}_{κ,λ} = \mathrm{HOD}_{κ,ω} = \mathrm{HOD}(\mathrm{Or …
- 7,545
12
votes
Accepted
Is Collection really stronger than Replacement?
The theories are equiconsistent and have the same strength as second order arithmetic $\text{Z}_2$. Since we have an $L$-definable well-ordering of the constructible universe $L$, replacement implies …
- 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
1
vote
Accepted
Cardinal Register Machines
Unbounded Computations
Independent of the restrictions, the halting problem is $Σ_1(\mathrm{Card})$-complete, where $\mathrm{Card}$ is the cardinality function (and $Σ_1$ is $Σ^V_1$). Also, there ar …
- 7,545
0
votes
Accepted
Determinacy and polynomial time degrees
Yes, and with a proper indexing, this also holds for a very restricted type of reduction called the prefix reduction: $X≤Y ⇔ ∃a ∀s (X_s ⇔ Y_{a⌢s})$ ('$⌢$' is string concatenation), with the equivalen …
- 7,545
3
votes
Accepted
Strength of BTEE
BTEE is conservative over the stationary reflection principle (SRP), i.e. ZFC + (schema) {there is $n$-subtle cardinal}$_{n∈\mathbb{N}}$. Using $n$-ineffable in the schema is equivalent.
Note that we …
- 7,545
6
votes
Accepted
Consistency of "the sharp of every set exists"
In one sense, closure under sharps is itself a standard point in the hierarchy of consistency strengths. Just like the exact consistency strength of "ZFC + measurable" is "ZFC + measurable", so is the …
- 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
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
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
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
6
votes
Accepted
Large cardinals without replacement
Overall, the large cardinal axiom hierarchy is very similar between ZC (ZFC minus replacement; we are including regularity) and ZFC. A large cardinal axiom (unprovable in ZFC) satisfied by $κ$ typica …
- 7,545
3
votes
Accepted
Complexity of induction formulas in proof theoretic ordinals
By a padding argument, for reasonable notation systems, an elementary time computable predicate $P$ in $\mathrm{TI}(β,ECP)$ can be chosen to be polynomial time computable.
For example, for limit $α<β …
- 7,545
0
votes
Accepted
Decidability of S2S with real numbers
Yes, it is decidable, with the following general result for an arbitrary (not necessarily decidable) $M$. Let us interpret an $n$-tuple of $M$-formulas $φ$ with $m$ free variables as a function $φ:M^ …
- 7,545