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.
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
18
votes
Is the analysis as taught in universities in fact the analysis of definable numbers?
While you cannot define undefinable numbers, you can quantify over all real numbers, whether or not they are definable. "Let $a$ be a number" does not assume that $a$ is definable, but is merely a sh …
- 7,545
17
votes
Accepted
Is this theory the complete theory of the real ordered field?
It is not. Using set forcing, we can add 'undefinable' reals in a controlled manner, while keeping complexity of parameter-free definable sets low.
Specifically, let $M$ be a countable $ω$-model of Z …
- 7,545
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
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
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
11
votes
Arguments against large cardinals
Large cardinals offer a detailed coherent picture — with a single principle, that of symmetry, reaching even (essentially) the strongest large cardinals. They continually offer new results — without …
- 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
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
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
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
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
6
votes
Is there a computable ordinal encoding the proof strength of ZF? Is it knowable?
For every c.e. theory T (extending a weak base theory), we already know a polynomial time computable linear ordering $≺$ that captures the $Π^1_1$ strength of T:
Provably in a weak base theory, a $Π^1 …
- 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
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