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.
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
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
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
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
6
votes
0
answers
241
views
ITTMs with higher types
What is the complexity of Infinite Time Turing Machines (ITTMs) augmented with an initially empty set of real numbers, with the ability to add, remove, and test presence of a real number in the set?
…
- 7,545
2
votes
1
answer
438
views
Cardinal Register Machines
A cardinal register machine is like an ordinal register machine but with branching based on cardinal equality rather than ordinal equality. What is the complexity of the halting problem for cardinal …
- 7,545
2
votes
1
answer
201
views
Determinacy and polynomial time degrees
Is there a function $f:2^{<ℕ}→\{0,1\}$ such that for all $X∈{2^ℕ}$ with $X_{2i+1}=f(X_0,...,X_i)$ all hyperarithmetical properties of the polynomial time degree of $X$ are independent of $X$?
The pol …
- 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
3
votes
1
answer
253
views
Strength of BTEE
What is the consistency strength of Basic Theory of Elementary Embeddings (BTEE) from The spectrum of elementrary embeddings j : V → V by Paul Corazza?
BTEE uses the language of $(V,∈,j)$ and asserts …
- 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
3
votes
0
answers
129
views
Lengths of proofs and quasilinear time
Length of proofs depends not only on the theory but also on its axiomatization. Once an axiomatization is fixed, typical proof systems are equivalent up to a polynomial factor. But what if we care a …
- 7,545
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
7
votes
0
answers
184
views
Infinite cardinals and learnability of probability distributions
Two players play as follows. Player one chooses a secret finitely supported probability distribution $P$ on $ω_k$ (or another known set with $\aleph_k$ elements), and randomly takes $n+1$ samples usi …
- 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
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