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 5017
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.
1
vote
0
answers
96
views
What computable pseudo-ordinals are there with initial segment $\omega_1^{CK}(1+\eta+1)$?
The notion of a “computable pseudo-ordinal”, i.e. a computable linear order with no hyperarithmetical descending chains, is an old one going back to Stephen Kleene. Joe Harrison wrote the definitive …
- 4,597
3
votes
0
answers
69
views
What are all the order types of maximal chains of $\Delta^0_2$ sets?
A set of natural numbers is $\Delta^0_2$ if it’s computable from the halting set. Consider the quasi-order/pre-order of all $\Delta_0^2$ sets ordered by $m$-reduction, or equivalently consider the pa …
- 4,597
3
votes
0
answers
279
views
What is the meaning and proof of Harvey Friedman’s ultrafinite incompleteness sentence?
On page 7 of his paper “Adventures in Incompleteness”, Harvey Friedman states the following:
IN ANY LONG ENOUGH SEQUENCE $x_1,...,x_n$ FROM $\{1,2,3\}$, SOME $(x_i,...,x_{2i})$ IS A SUBSEQUENCE OF SO …
- 4,597
6
votes
1
answer
271
views
Does $\text{ACA}_0$ + True Arithmetic prove the well-foundedness of every recursive ordinal?
As discussed in Noah Schweber's answer to What is the proof-theoretic ordinal of true arithmetic?, it is somewhat ambiguous what “the proof-theoretic ordinal of True Arithmetic” might mean. In one se …
- 4,597
4
votes
1
answer
139
views
Does the set of infinite random strings satisfy an analogue of immune sets?
Let $K(x)$ denote the Kolmogorov complexity of a finite binary string $x$. A finite binary string $x$ is called Kolmogorov random if $K(x) \geq |x|$. And an infinite binary sequence is called Martin …
- 4,597
5
votes
1
answer
270
views
Does there always exist a categorical extension of $ZFC_2$ with no set models?
$ZFC_2$, i.e. second-order Zermelo-Fraenkel set theory with Choice, has only one proper class model upto isomorphism, namely $V$. But it may or may not also have set models. If $V$ has no inaccessib …
- 4,597
10
votes
1
answer
868
views
What is the theory of the random poset?
$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random po …
- 4,597
4
votes
0
answers
197
views
Are there any 1-decidable algebraic extensions of $\mathbb{Q}$ which are not decidable?
A model $M$ is decidable if the set of all first-order formulas which are true in $M$ is a recursive set. And a model is $1$-decidable if the set of all existential formulas which are true in $M$ is …
- 4,597
11
votes
1
answer
395
views
What is the Turing degree of the monadic theory of the real line?
The monadic theory of the real line is the set of all sentences in the monadic second-order language of order which are true in $\mathbb{R}$. In this 1982 paper, Gurevich and Shelah show that true fi …
- 4,597
4
votes
1
answer
286
views
What is the lowest complexity definition of $\mathbb{Z}$ in an infinite algebraic extension ...
In 2009, Jochen Koenigsmann showed that $\mathbb{Z}$ is universally definable in the field $\mathbb{Q}$. And in 2012, Jennifer Park proved a result which implies that $\mathbb{Z}$ is $\exists\forall$ …
- 4,597
8
votes
1
answer
248
views
What is the lowest complexity definition of $\mathbb{Z}$ in an infinite extension of $\mathb...
In 2009, Jochen Koenigsmann showed that $\mathbb{Z}$ is universally definable in the field $\mathbb{Q}$. And in 2012, Jennifer Park proved a result which implies that $\mathbb{Z}$ is $\exists\forall$ …
- 4,597
6
votes
1
answer
516
views
What is the Galois group of one ultrapower over another ultrapower?
Let $F$ be a field, let $E$ be a field extension of $F$, and let $U$ be an ultrafilter. Then my question is, what is the relationship between the Galois groups $Gal(\Pi_U E/\Pi_U F)$ and $Gal(E/F)$?
…
- 4,597
10
votes
1
answer
405
views
Is $\mathbb{Z}$ universally definable in any number fields other than $\mathbb{Q}$?
In 2009, Jochen Koenigsmann showed that $\mathbb{Z}$ is universally definable in the field $\mathbb{Q}$. My question is, are there any other number fields in which $\mathbb{Z}$ is universally definab …
- 4,597
5
votes
1
answer
422
views
Is there a complete characterization of ordered fields without definable proper subfields?
$\mathbb{Q}$ has no proper subfields. As a result, all ordered fields elementarily equivalent to $\mathbb{Q}$ have no proper subfields which are first-order definable without parameters. And by the …
- 4,597
8
votes
1
answer
463
views
What subsystem of third order arithmetic proves the real numbers are Dedekind complete?
Reverse mathematics is mainly about subsystems of second-order arithmetic, but in recent years it’s expanded to cover subsystems of third-order arithmetic as well. Now the fact that the real numbers …
- 4,597