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 questions 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.
35
votes
8
answers
2k
views
Examples of statements with a high quantifier complexity
What are some natural properties, definitions, and statements that require many alternating quantifiers?
The complexity could be $\Pi^0_k$, $\Pi^1_k$, $\Pi^V_k$, or something else entirely, as long $k …
- 7,545
18
votes
1
answer
532
views
When can we add choice to a model of ZF
For countable transitive models of ZF, is existence of a ZFC extension with the same height a first order property?
In other words, is there a statement $τ$ (in the language of set theory) such that f …
- 7,545
17
votes
3
answers
1k
views
Minimum transitive models and V=L
Is there a c.e. theory $T⊢\text{ZFC}$ in the language of set theory such that the minimum transitive model of $T$ exists but does not satisfy $V=L$?
You may assume that ZFC has transitive models. Not …
- 7,545
16
votes
0
answers
638
views
Consistency strength of $j:L_δ→L_δ$ for some δ
What is the consistency strength of existence of a nontrivial elementary embedding $j:L_δ→L_δ$ for some ordinal $δ$?
The consistency strength is strictly between totally ineffable and $ω$-Erdős cardi …
- 7,545
12
votes
3
answers
775
views
Infinite descending consistency chains
What are some examples of consistent theories $T_i$ (extending elementary arithmetic EA) such that for $∀i∈ℕ \,\, T_i ⊢ \mathrm{Con}(T_{i+1})$?
Such theories exist; see for example An infinitely desc …
- 7,545
12
votes
1
answer
457
views
Does $Π^1_{2n+1} = (Σ^1_{2n+1})^{M_{2n-1}}$?
Every $Π^1_1$ formula $φ$ without free second order variables can be converted into a $Σ^1_1$ $ψ$ such that $φ ⇔ ψ^\mathrm{HYP}$, and vice versa. ($\mathrm{HYP}$ is the hyperarithmetical universe, wh …
- 7,545
11
votes
1
answer
618
views
Cut-free proofs in ZFC
If a statement $P$ has a ZFC proof of length $n$, must it also have a cut-free ZFC proof of length polynomial in $n$?
By a cut-free ZFC proof, I mean a proof in sequent calculus without cut rule of s …
- 7,545
10
votes
0
answers
322
views
Definability up to isomorphism versus definability of an isomorphic copy
Question: Is it provable in ZFC that every structure that is ordinal definable up to isomorphism has an ordinal definable isomorphic copy? If not, what are some counterexamples? All structures are s …
- 7,545
10
votes
2
answers
829
views
Adding nonconstructive disjunction to intuitionistic logic
In constructive mathematics, under realizability interpretations, we can define nonconstructive disjunction $A⅋B$ as follows:
A witness for $A⅋B$ gives a candidate witness for $A$ and a candidate witn …
- 7,545
10
votes
1
answer
347
views
$Π^0_1$ Proof Ordinals
Natural theories extending EFA (exponential/elementary function arithmetic) are well-ordered by $Π^0_1$ provability, and we would like a formal definition of the well-ordering that is robust yet as fi …
- 7,545
9
votes
1
answer
963
views
Complexity of $L[\mathrm{cf}]$
Assuming large cardinal axioms, which real numbers are in $L[\mathrm{cf}]$, where $\mathrm{cf}$ is the cofinality function on ordinals?
$L[\mathrm{cf}]$ is the minimal inner model that 'knows' the co …
- 7,545
9
votes
1
answer
368
views
Decidable theories with arbitrary complexity
Are there complete finitely axiomatizable first order theories (with equality) with arbitrarily high computational complexity?
Here, arbitrarily high (computational) complexity means that for every co …
- 7,545
8
votes
0
answers
280
views
Natural examples of recursive pseudowellorderings
Question: What are some natural examples of recursive pseudowellorderings?
By natural, I mean in the style of reasonable ordinal notation systems as opposed to dependent on a Gödel numbering or an en …
- 7,545
8
votes
1
answer
1k
views
α-Mahlo vs weakly compact cardinals
Question: What is the consistency strength of existence of a $(κ^{++})^L$-Mahlo cardinal $κ$?
I am particularly interested in how the strength compares to weakly compact cardinals (and other levels …
- 7,545
8
votes
0
answers
181
views
Intuition for branch uniqueness in inner model theory
In inner model theory, what is the intuition behind the expectation that under appropriate conditions, we should have a single preferred branch to continue an iteration at a limit stage?
At the level …
- 7,545