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 not deleted
user 23648
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.
2
votes
Construction of models for true but unprovable formulas
Yes, check out the Paris-Harrington theorem's use of indicators as one way to do this for a specific kind of Ramsey theorish combinatorial claim. It's kinda a tough slog but it's a really explicit co …
- 3,029
5
votes
What do we gain with higher order logics?
Some of these answers want to convince you HOL is more expressive. That's true in a certain sense but it's easily misleading.
Specifically, let's be careful to distinguish two different notions that …
- 3,029
1
vote
1
answer
90
views
Downward density of w-REA sets under arithmetic reducibility?
Is the question of the downward density of the w-REA sets under $\leq_a$ still open? If not can anyone point me to a proof? That is do we know if for every $\omega$-REA set $X >_a 0_a$ there exists …
- 3,029
1
vote
0
answers
52
views
Term for degrees realizing least possible first n jumps
Is there a term for (Turing) degrees which realize the least possible jump (in the following sense) for the first n jumps.
That is degrees which satisfy for all $0 < m \leq n$:
$$X^m \equiv_T X \oplus …
- 3,029
2
votes
0
answers
231
views
Is computability theory less cumulative than other areas in mathematics?
I love compatibility theory, degree theory etc and I'm astonished by the advances that have been made in the field but it often seems like computability is less cumulative than other areas of mathemat …
- 3,029
2
votes
Proof of the existence of hyperimmune-free degrees
You have to be careful here and realize that $Q(\sigma)$ is a function from $2^{<\omega}$ to $2^{<\omega}$ and thus $Q(\sigma)$ can be arbitrarily long even if $|\sigma|=n$.
When the construction mak …
- 3,029
4
votes
2
answers
464
views
Infinite descending chain of Turing jumps with equality
How can one demonstrate there is no sequence $X_i$ of sets such that $X_{i+1}' = X_i$ (this is really equality as sets though Turing equivalence would be interesting too).
I know it fails if I relax e …
- 3,029
4
votes
Meta-incomputability
It's worth noting that the answer above is answering the following question: is there a formula $\phi(x)$ in the language of ZFC such that ZFC can't prove either $\lbrace x \in \omega \mid \phi(x) \rb …
- 3,029
0
votes
Do "seemingly impossible functional programs" work with arrow types interpreted as Turing ma...
Yes you can.
EDIT: That means find a computable program $H(e)$ taking an index $e$ for a predicate $P_e$ that returns $1$ (assuming $P_e$ satisfies above conditions) iff there is some code for an elem …
- 3,029
7
votes
1
answer
155
views
Join Density in R.E. Degrees: Are there r.e. B, C with all r.e. X below B computable or C jo...
Are there r.e. sets $B >_T 0$ and $C >_T 0$, $C \not\geq_T B$ such that for all r.e. $W \leq_T B$ either $W \leq_T 0$ or $C \oplus W \geq_T B$. The explanation for the title is because one can think …
- 3,029
1
vote
1
answer
92
views
If $X \leq_T Y + 0'$ does there exist $Z \leq_T Y$, $Z \leq_T X$ with $X \leq_T Z'$?
If $X \leq_T Y + 0'$ does there always exist $Z \leq_T Y$, $Z \leq_T X$ with $X \leq_T Z'$?
Obviously, we can find $Z \leq Y$ where the $y$-th column of $Z$ has a limit equal to $X(y)$. Just let $\la …
- 3,029
2
votes
Accepted
If $X \leq_T Y + 0'$ does there exist $Z \leq_T Y$, $Z \leq_T X$ with $X \leq_T Z'$?
Ohh, I think I'm being dumb. The answer is no.
Given $X \not\leq_T 0'$ we build $Y$ using the finite extension method and modify the usual minimal pair construction by coding in the bits of $X$ into …
- 3,029
2
votes
Accepted
Proving things about a formal logical system
So in a usual mathematical proof you choose some system if axioms from which you prove it. For instance, there are claims about the natural numbers you can prove in ZFC but not from the axioms of Pea …
- 3,029
3
votes
1
answer
224
views
Adding sort of sets over theory with multiple sorts?
It's relatively standard to add a sort of sets over some base theory and supplement the axioms with comprehension principles as in second order arithmetic.
Is there a nice way to do this if your initi …
- 3,029
8
votes
1
answer
395
views
Good source for admissible set theory?
So I need to writeup some old results of Harrington's which imply various results about admissible ordinals. I've never really learned admissible recursion theory so what's a good reference?
- 3,029