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 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.
90
votes
Accepted
What does it mean to suspect that two conjectures are logically equivalent?
First of all, in practice when we say "Conjecture A is equivalent to Conjecture B," what we mean is "We have a proof that Conjecture A is true iff Conjecture B is true." We can have such a proof witho …
- 20.7k
82
votes
What are some important but still unsolved problems in mathematical logic?
Yes, there are several. Here’s a few which I personally care about (described in varying amounts of precision). This is not meant to be an exhaustive list, and reflects my own biases and interests.
I …
49
votes
Why not adopt the constructibility axiom $V=L$?
Let me add to the existing answers a point which may seem "vulgar" at first, but I think is actually important:
V=L is complicated.
And whether or not this ought to be a reason to not raise it to ZF …
42
votes
Zorn's lemma: old friend or historical relic?
I agree with the existing answers, but I personally like Zorn's lemma both pedagogically and mathematically for an additional reason: the "poset of partial solutions" that it introduces is a valuable …
- 20.7k
35
votes
Circular, or missing, definition in set theory?
Caveat: it's become clear from comments and revisions that the original portion of this answer - leading up to the horizontal line below - is not really addressing the heart of the OP. I'm leaving it …
- 20.7k
32
votes
Accepted
Can we take a supremum over all Hilbert spaces?
It is true that we cannot use an arbitrary property$^1$ $P$ to define a set, in the sense that the collection of all things with property $P$ need not be a set. However, the axiom (scheme) of separati …
- 20.7k
25
votes
Accepted
Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?
This is equivalent to the $\Sigma_1$-soundness of $\mathsf{ZFC}$ (and this equivalence is highly robust to replacing $\mathsf{PA}$ with some other theory):
If $\mathsf{ZFC}$ is $\Sigma_1$-sound then t …
- 20.7k
24
votes
Accepted
Do we expect that sufficiently large computable ordinals settle every question of arithmetic?
The question of whether a computable linear order is well-founded is $\Pi^1_1$-complete, so this is true in a sense:
There is a computable function $F$ such that, for every sentence $\varphi$ in the …
- 20.7k
20
votes
For a computable binary tree, is having no computable branches the same as having no probabi...
No, we can construct a computable tree with no computable paths such that there is a probabilistic Turing machine which with nonzero probability constructs a path.
The basic idea is this: kill off a …
- 20.7k
19
votes
Are there 'finitistic' nonrecursive functions (assuming Church's Thesis is false)?
Kalmar's argument is indeed wrong. The problem, of course, lies in his justification of our ability to compute $\psi(x)=0$, where he writes
"We can prove, not in the frame of some fixed postulate …
- 20.7k
19
votes
Situation with Artemov's paper?
I'm primarily giving this answer to prevent a technical misconception from spreading further:
Artemov's notion of entailment, which I'll call "$\vdash_A$" here, is a bit more subtle than it may first …
- 20.7k
19
votes
Accepted
Is every recursively axiomatizable and consistent theory interpretable in the true arithmeti...
The answer is yes. I believe the following is best attributed to Feferman 1960; more generally, look up "arithmetized completeness theorem" (which is annoyingly different from the arithmetic completen …
- 20.7k
18
votes
A Löwenheim–Skolem–Tarski-like property
Here's a counterexample for $\kappa=\aleph_1$: let $B$ be the structure with underlying set $\mathbb{N}\sqcup\mathcal{P}(\mathbb{N})$, equipped with the usual ordering on $\mathbb{N}$ as well as the $ …
- 20.7k
18
votes
Accepted
Cantor-Bernstein with "weakly injective" functions
No, it is not provable in $\mathsf{ZF}$.
It is consistent with $\mathsf{ZF}$ that there is a sequence of disjoint two-element sets whose union is not countable, i.e. $\vert A_i\vert=2$ but there is no …
- 20.7k
18
votes
Similarities between Post's Problem and Cohen's Forcing
The primary difference between forcing arguments in set theory and priority constructions is that the latter care about the complexity of the generic filter in a way the former do not. In particular, …
- 20.7k