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 4600
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.
32
votes
Accepted
On sentences true in all finite groups
The answer is Yes for the second question, about $(\exists x)(\forall y)w=1$. Following Christian Remling's idea:
If a sentence like
$$\exists x(\forall y)(yxy^{-1}x^2y^{-9}\dots=1)$$
holds in all fin …
- 24.8k
25
votes
Accepted
What is the reverse mathematical strength of the fundamental theorem of algebra?
Tanaka and Yamazaki (in the volume Reverse Mathematics 2001, see review) show that a substantial portion of field theory can be done in the weak base theory RCA$_0$, by proving in RCA$_0$ the fundamen …
- 24.8k
25
votes
Accepted
Languages beyond enumerable
Yes, for starters there is the arithmetical hierarchy, where enumerable = $\Sigma^0_1$ and it continues $\Pi^0_1$, $\Delta^0_2$, $\Sigma^0_2$ etc.
See also the Computability Menagerie.
- 24.8k
21
votes
Accepted
Question arising from Voevodsky's talk on inconsistency
Let $S$ be a first order definable Martin-Löf random set such as Chaitin's $\Omega$. If Peano Arithmetic, or ZFC, or any other theory with a computable set of axioms, proves infinitely many facts of t …
- 24.8k
21
votes
For which Millennium Problems does undecidable -> true?
$P\ne NP$ is a $\Pi^0_2$ statement:
for each polynomial $p$ and Turing machine $M$ implementing an algorithm attempting to decide SAT, there is a formula $\phi_M$ such that if we look at the comp …
20
votes
Accepted
Why is weak Kőnig's lemma weaker than Kőnig's lemma?
The issue is that for a finitely branching subtree $T$ of $\omega^{<\omega}$, the function $f$ mapping $\sigma$ to the greatest $n$ such that the concatenation $\sigma ^\frown n$ is in $T$ may not be …
- 24.8k
19
votes
Accepted
Is Turing degree actually useful in real life?
Application to everyday life
Any time you watch the "spinning beach ball" or "hour glass" on your computer, trying to decide whether it's time to reboot or just wait a little longer, you are doing som …
18
votes
In what sense is GCD an extension of boolean OR?
In the ordering $\preceq$ of nonnegative integers by divisibility, 1 is the least element and 0 is the greatest, and we have for instance
$$
1\preceq 2\preceq 6\preceq 12\preceq\dots\preceq 0.$$
In th …
- 24.8k
18
votes
Why is this new result such a big deal?
They show that $\DeclareMathOperator{\WKL}{WKL}\DeclareMathOperator{\RT}{RT}\DeclareMathOperator{\RCA}{RCA} \RT^2_2$ is $\Pi^0_3$-conservative over $\RCA_0$. Thus, there is no way that $\RT^2_2$ can b …
- 24.8k
17
votes
Probably true, but provably unprovable
Let $c$ be a constant such that
$$\mathrm{PA}\not\vdash K(x)\ge c$$
for all binary strings $x$, where $K$ is Kolmogorov complexity. Such a $c$ exists by Chaitin's Incompleteness Theorem and the linked …
- 24.8k
13
votes
Examples of $\aleph_0$-categorical nonhomogeneous structures
How about: dense linear order with endpoints.
It's $\aleph_0$-categorical by the same proof as for the case without endpoints.
It's not homogeneous because of the endpoints.
- 24.8k
13
votes
Interesting meta-meta-mathematical theorems?
You could let $\alpha_0$ be the statement Con(ZFC), and $\alpha_{n+1}$ be ZFC $\not\vdash\alpha_n$, and at limit ordinals $\alpha_\lambda$ is $(\forall \beta<\lambda)($ZFC $\not\vdash \alpha_\beta)$. …
- 24.8k
13
votes
How did the Baker-Gill-Solovay paper come to be?
Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊
The Annals of t …
- 24.8k
11
votes
Can We Decide Whether Small Computer Programs Halt?
You're right that such a project is possible. Calude et al. (http://www.emis.de/journals/EM/expmath/volumes/11/11.3/Calude361_370.pdf) have some results in this direction.
- 24.8k
10
votes
Proof complexity of two directions of equivalency?
This fits in the program of reverse mathematics. For instance: a subtree of the set of all finite binary strings has an infinite path iff it is infinite. One direction is provable in RCA $_0$ and the …
- 24.8k