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 12705
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.
6
votes
Mathematical strength of the statement "Heyting Arithmetic admits Markov's rule"
$\def\ha{\mathsf{HA}}\def\down{{\downarrow}}\def\mr{\mathrel{\mathbf q}}$I believe this can be proved in a fairly weak fragment of arithmetic, such as $\mathsf{I\Delta_0+EXP}$, possibly even in a poly …
- 47.9k
9
votes
Accepted
Can the incompleteness of set theory be isolated to questions about arithmetic?
There does not exist any r.e. theory $T\supseteq\mathsf{ZFC}$ and any set $A$ of arithmetical sentences (true or otherwise) such that $T+A$ is complete and consistent, because ZFC has a truth predicat …
- 47.9k
7
votes
Accepted
Can one define second-order equinumerosity in MSO via first-order cardinality quantifiers?
The answer is negative even for nonmonadic second-order logic by complexity considerations.
Assume for contradiction that such a sentence $\phi$ exists.
First, let us see how difficult it is to check …
- 47.9k
7
votes
Accepted
What's the deal with De Morgan algebras and Kleene algebras?
Per request of the OP, I’m reposting my comments as an answer. This is a series of observations without any references; most of these things are well known/easily shown.
Normal forms.
Using De Morgan …
- 47.9k
9
votes
Accepted
Examples of anti-classical theories in iFOL
One example of an anti-classical theory that’s not artificially constructed for that purpose is $\mathsf{HA+CT_0}$, where the Church–Turing thesis $\mathsf{CT_0}$ is the schema
$$\forall x\:\exists y\ …
- 47.9k
5
votes
Accepted
What oracles make finding isomorphism (of finite structures) easy?
$\def\cX{\mathcal X}\def\cY{\mathcal Y}\def\Th{\mathrm{Th}}$UPDATE: The question was changed so that $\Th_2(\cX)$ no longer refers to the second-order theory of $\cX$, but the second-order diagram. Th …
- 47.9k
4
votes
Is every recursively axiomatizable and consistent theory interpretable in the true arithmeti...
The other answers are enough to answer the question as given. However, let me point out for the record that using the arithmetized completeness theorem over PA is quite an overkill. We can make do wit …
- 47.9k
27
votes
Accepted
Is the theory of ordinals in Cantor normal form with just addition decidable?
The theory of $(\let\ep\varepsilon\ep_0,+,\omega^-)$ is undecidable (I will not mention $0$, $1$, or $<$ in the signature as they are definable). More generally, the same holds for any nonempty class …
- 47.9k
13
votes
Whether an isotone bijection from a power set lattice to another sends singletons to singletons
Yes, such a mapping necessarily sends singletons to singletons.
Let $f\colon\mathcal P(S)\to\mathcal P(T)$ be a monotone bijection (or more generally, a surjective strictly monotone function). By mon …
- 47.9k
16
votes
Accepted
Is it possible to completely embed complete Heyting algebras into upsets of a poset?
No, not in general: for instance, the real interval $([0,1],{\le})$, or any non-atomic complete Boolean algebra, does not have such an embedding. This follows from the following characterization:
Pro …
- 12.9k
27
votes
Does the "three-set-lemma" imply the Axiom of Choice?
To complement godelian’s answer, the three-set lemma is not provable in ZF alone, as it implies the axiom of choice for families of pairs. This holds even if we allow any finite (or even just well ord …
- 47.9k
5
votes
Accepted
What determines non-finite axiomatizability of a class extension of a set theory?
As explained with more details in https://mathoverflow.net/a/87249, every sequential theory that proves the induction schema for all formulas in its languages is reflexive (even uniformly essentially …
- 47.9k
14
votes
Accepted
Quantifier elimination for abelian groups
Abelian groups are the same thing as $\mathbb Z$-modules. In general, for any ring $R$, the theory of left $R$-modules has quantifier elimination down to Boolean combinations of primitive positive for …
- 47.9k
6
votes
Accepted
What is the theory of computably saturated models of ZFC with an *externally well-founded* p...
Observe that if $M\models\def\zfc{\mathrm{ZFC}}\zfc$ has nonstandard $\omega$, then $x\in M$ is externally well founded iff its rank $\rho(x)$ is a standard natural number: this follows easily by iter …
- 47.9k
25
votes
Accepted
Is factorial definable using a $\Delta_0$ formula?
Yes, the graph of factorial is $\Delta_0$.
As mentioned above by Ali Enayat, a direct $\Delta_0$ definition of factorial was constructed by D’Aquino [4]. It is based on collecting contributions of all …
- 4,713