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 1946
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.
26
votes
1
answer
1k
views
Can we find strong fixed-points in the fixed-point lemma of Gödel's incompleteness theorem, ...
At Graham Priest's talk for the CUNY set theory seminar yesterday, an issue arose concerning the possibility (or impossibility) of a stronger-than usual form of the arithmetic fixed-point lemma often …
- 237k
16
votes
2
answers
1k
views
Are the vertical sections of the Ackermann function primitive recursive?
The Ackermann function $A(m,n)$ is a binary function on the natural numbers defined by a certain double recursion, famous for exhibiting extremely fast-growing behavior.
One finds various slightly dif …
- 237k
21
votes
2
answers
1k
views
Is the union of a chain of elementary embeddings elementary?
I am a little confused about what I think must be either a standard theorem or a standard counterexample in model theory, and I am hoping that the MathOverflow model theorists can help sort me out abo …
- 237k
36
votes
8
answers
2k
views
Does the truth of any statement of real matrix algebra stabilize in sufficiently high dimens...
This question is related to this recent but currently
unanswered MO
question
of Ricky Demer, where it arose as a comment.
Consider the structure $R^n$ consisting of $n\times n$
matrices over the real …
- 237k
20
votes
7
answers
2k
views
Does every set admit a rigid binary relation? (and how is this related to the Axiom of Choice?)
Let us say that a set B admits a rigid binary relation, if there is a binary relation R such that the structure (B,R) has no nontrivial automorphisms.
Under the Axiom of Choice, every set is well-or …
- 237k
76
votes
9
answers
6k
views
Can we unify addition and multiplication into one binary operation? To what extent can we fi...
The question is the extent to which we can unify addition
and multiplication, realizing them as terms in a single
underlying binary operation. I have a number of questions.
Is there a binary operati …
- 237k
7
votes
2
answers
730
views
For a partition of $\mathbb{R}$ into countably infinite sets, must there be an almost-disjoi...
My question arises from a construction I gave in my recent
answer to a question of Alexander Pruss concerning large families of independent non-measurable sets of reals. In that argument, using
the co …
- 237k
22
votes
4
answers
1k
views
Is there a Leibnizian model with no definable elements, in a finite language?
A first-order structure $M$ is Leibnizian, if any two distinct
elements $a,b\in M$ satisfy different $1$-types; that is, if there
is some formula $\varphi$ such that $M\models\varphi(a)$ and
$M\models …
- 237k
6
votes
1
answer
366
views
Is $n$ uniformly computable from an oracle for the $n^{\rm th}$ jump $0^{(n)}$?
This is a little curiosity that came up in a project I am working on, and I thought someone might have a nice way to see the answer.
Question. Can we uniformly compute $n$ from an oracle for the $n^{ …
- 237k
20
votes
2
answers
1k
views
For a computable binary tree, is having no computable branches the same as having no probabi...
It is a classical result of computability theory that there is a
computable infinite binary tree $T\subset 2^{<\omega}$ with no
computable infinite branch.
One way to construct such a tree is to fix …
- 237k
12
votes
3
answers
881
views
Is there a simple instance of intransitivity for implicit definability?
This question continues the theme of some recent questions on implicit definability.
A relation $R$ is implicitly definable in a first-order structure $M$ if there is a property $\varphi(\dot R)$, exp …
- 237k
19
votes
4
answers
1k
views
Does every decidable question about finitely presented groups amount to a question about ab...
This question is about an issue left unresolved by Chad
Groft's excellent
question and
John Stillwell's excellent
answer of
it. Since I find the possibility of an affirmative answer
so tantalizing, I …
- 237k
17
votes
1
answer
865
views
Which finitely presented groups can be distinguished by decidable properties?
This question continues the line of inquiry
of these
three
questions.
Question. Which finitely presented groups can be
distinguished by decidable properties?
To be precise, let us say that φ is a de …
- 237k
11
votes
2
answers
663
views
What is the computational-complexity-theoretic analogue of computable inseparability? For ex...
Disjoint sets $A$ and $B$ are computably inseparable, if there
is no computable separating set, a computable set $C$ containing $A$ and disjoint from $B$. The
existence of c.e. computably inseparable …
- 237k
10
votes
1
answer
462
views
If $\kappa$ is weakly inaccessible and $A\subset\kappa$, can $L[A]$ violate $\kappa^{\lt\kap...
In some current work, my co-authors and I had wanted in a certain
argument to appeal to $\kappa^{\lt\kappa}=\kappa$ in $L[A]$, in a
situation where $A\subset\kappa$ and $\kappa$ was weakly
inaccessibl …
- 237k