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 39521
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.
42
votes
1
answer
4k
views
Mathematicians wearing hats on arbitrary total orders
I've been pondering the following generalisation of a famous problem (the special case where $T = \mathbb{N})$:
Question: We have some totally-ordered set $T$ of mathematicians, each wearing a hat wh …
- 12.4k
40
votes
2
answers
3k
views
Ultrafilters as a double dual
Given a set $X$, let $\beta X$ denote the set of ultrafilters. The following theorems are known:
$X$ canonically embeds into $\beta X$ (by taking principal ultrafilters);
If $X$ is finite, then ther …
- 12.4k
16
votes
1
answer
591
views
Is this theory decidable?
It is well-known that both Presburger arithmetic (by contrast with Peano arithmetic) and Tarski geometry are decidable. I was in the shower this morning and wondered whether there exists an elegant mu …
- 12.4k
15
votes
2
answers
2k
views
Why is weak Kőnig's lemma weaker than Kőnig's lemma?
Kőnig's lemma states that any finitely-branching tree with infinitely many nodes contains an infinite path. Weak Kőnig's lemma states the same thing about binary trees.
It's known that these are not …
- 12.4k
15
votes
What is an explicit bijection in combinatorics?
Here's an example (credit: Paul Russell) of the sort of bijection you want to rule out.
Question: Find an explicit bijection $f$ between the size-$k$ and size-$(k + 1)$ subsets of $\{1, 2, \dots, 2k+ …
- 12.4k
7
votes
3
answers
229
views
Ordinal-indexed transitive antichain of sets with urelements
Operate in ZFC. Can we find a function-class $\phi$ whose domain is the class of ordinals such that the following properties hold?
If $x \in \phi(\alpha)$, then either $x \in \mathbb{N}$ or there ex …
- 12.4k
6
votes
Set theories without "junk" theorems?
The problems you mention occur as a result of two related reasons:
Objects such as the set of real numbers, which do not intrinsically belong to set theory, are 'encoded' as a set, so we can ask mea …
- 12.4k
5
votes
Ordinal-indexed transitive antichain of sets with urelements
Assuming Vopenka's principle (a large cardinal axiom), we can show there is no such $\phi$. In particular, a corollary of Vopenka's principle is that every proper class of directed graphs contains som …
- 12.4k
5
votes
Automorphism of the transfinite rooted binary tree
Although this question already has an accepted answer, which is correct for the question as stated, I posit that the surreal number tree is best viewed as a tree in the order-theoretic rather than the …
- 12.4k
3
votes
Accepted
Can all lengths of shortest non-halting inputs of all Turing machines be limited by the Busy...
There exists a family of Turing machines $\{ \mathcal{T}_n : n \in \mathbb{N} \}$ such that:
$\mathcal{T}_n$ has $k n$ states where $k$ is some fixed universal constant;
$F(\mathcal{T}_n) \geq BB(BB …
- 12.4k
2
votes
Are there non-commutative models of arithmetic which have a prime number structure?
Commutativity is not necessary for the notion of primes. For instance, consider the Hurwitz integers, namely quaternions whose components are either all integers or all half-integers:
$$ H = \{ a + b …
- 12.4k
1
vote
Can we add set complements on top of ZF?
If you take your description and rename $\textrm{set} \mapsto \textrm{class}$ and $\textrm{small set} \mapsto \textrm{set}$, and add some further axioms beyond the ones you mention (such as global cho …
- 12.4k