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 8133
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.
7
votes
2
answers
625
views
Generalization of the club filter
If $\alpha$ is a (limit) ordinal, then a subset $S\subseteq\alpha$ is club if $\alpha$ is closed as a subset of $\alpha$ under the order topology and unbounded in $\alpha$. The set of all sets contain …
- 20.7k
6
votes
1
answer
318
views
Finding limit-nondecreasing sets for certain functions
This is a question that arose a while ago in work with Damir Dzhafarov on some pieces of reverse mathematics. As far as I know, it has no deep significance; however, it feels like the sort of thing we …
- 20.7k
8
votes
0
answers
220
views
Large "computably un-simplifiable" computable well-orderings
Question
Suppose $A,X$ are computable well-orderings. Say that $A$ is $X$-unsimplifiable if there is no computable well-ordering $B$ whose ordertype is strictly less than that of $A$ but such that Dup …
- 20.7k
3
votes
1
answer
248
views
Is there a maximal fragment of FOL with "no negation at all?"
Say that a logic $\mathcal{L}$ is nowhere-negative iff for every $\mathcal{L}$-theory $T$ there is a structure $\mathfrak{A}$ such that $$\mathit{Th}_\mathcal{L}(\mathfrak{A})=\mathit{Ded}_\mathcal{L} …
- 20.7k
4
votes
0
answers
188
views
Better arguments via worse numberings?
The usual listing $\{\varphi_e: e\in\omega\}$ of partial computable functions has a number of nice properties - the padding lemma, the recursion theorem, etc. Any other numbering which we can "effecti …
- 20.7k
6
votes
0
answers
236
views
A specific model of Z
Short version: there is a natural, very "thin" (but probably not minimal) model of Zeremelo set theory; I'm curious what is known about it.
Zermelo set theory (= ZF without the Replacement scheme) …
- 20.7k
3
votes
1
answer
200
views
Is self-escaping without self-dominating possible?
For a countable structure $\mathcal{S}$, let the cospectrum of $\mathcal{S}$ be the set $CS(\mathcal{S})$ of reals (non-uniformly) computable in every copy of $\mathcal{S}$ (we can also make sense of …
- 20.7k
3
votes
1
answer
236
views
Is there a $\Delta^0_2$ real with "easy total computability problem"?
This was asked at MSE without success. Granted, a bounty is still ongoing there, but it doesn't look like it will be answered.
For (noncomputable) $A\subseteq\omega$ let $\tilde{A}=\{e: \varphi_e^A\m …
- 20.7k
6
votes
0
answers
230
views
Is there a nice(r) counterexample to this strengthening of Tarski's theorem?
Given a regular logic $\mathcal{L}$ and a structure $\mathfrak{A}$ (in a finite relational language $\Sigma$ for simplicity), let $\overline{Th_\mathcal{L}(\mathfrak{A})}$ be the structure defined as …
- 20.7k
2
votes
1
answer
152
views
Hard-to-"realize" instances of downward density
This question is motivated by a vague analogy between true paths in priority arguments and realizers - relative to an oracle - in the sense of intuitionistic logic. Intuitively, I'm looking for a prec …
- 20.7k
10
votes
2
answers
415
views
Climbing up subsets of $\omega_1$ using reals
This is a bit of an odd question, so I've included the motivation below the fold.
Throughout we work in ZFC+"$\omega_1^r$ is countable for all $r\in\mathbb{R}$:"
Say that a set $X\subset\omega_1$ is …
- 20.7k
14
votes
4
answers
2k
views
Fermat's Last Theorem and Computability Theory
This question stems from the paper "Computably categorical fields via Fermat's Last Theorem," by Russell Miller and Hans Schoutens (available online at http://qcpages.qc.cuny.edu/~rmiller/Fermat.pdf). …
- 20.7k
11
votes
0
answers
512
views
Using Lindstrom's theorem to prove Craig interpolation
[EDIT: The theorem I call "Beth definability" below is apparently not generally called that (wikipedia notwithstanding; see https://math.stackexchange.com/questions/288450/two-forms-of-beths-theorem). …
- 20.7k
5
votes
1
answer
338
views
Climbing quickly up $L$
This question is motivated by Joel David Hamkins' answer to Gödel's Constructible Universe in Infinitary Logics (A Possible Approach to HOD Problem), in which he shows that, if we replace first-order …
- 20.7k
10
votes
1
answer
447
views
Sets computable from enough hints
Is there a non-computable set $X\subset\omega$ such that, for some $Y\subset\omega$, any infinite subset or cosubset (=subset of the complement) of $Y$ computes $X$?
More generally, call a set $X$ $n …
- 20.7k