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.8k
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.8k
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.8k
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.8k
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.8k
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.8k
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.8k
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.8k
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.8k
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.8k
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.8k
10
votes
Accepted
Does PA prove (Artemov-style) the consistency of a stronger system?
This property holds more-or-less for every consistent recursively axiomatized theory $T$, even with Q in place of PA.
More precisely, there is a hidden parameter in the question, namely what formula $ …
- 47.8k
9
votes
Accepted
Are there atoms in the lattice of intermediate logics?
There are no atoms.
Assume for contradiction that $L$ is an atom. Since $L$ strictly contains IPC, there is a finite rooted Kripke frame $F$ that does not validate $L$, thus $L$ proves the Jankov–De J …
- 47.8k
6
votes
Whether the pure implicational fragment of intuitionistic propositional logic is a finitely-...
A related property in which the implicational fragment differs from full intuitionistic logic is that the former is locally finite: for every finite $n$, there are only finitely many inequivalent form …
- 47.8k
7
votes
Accepted
Does this hierarchy of fragments of $I \Sigma_1$ collapse?
That the hierarchy collapses follows immediately from the fact that $I\Sigma_1$ (or equivalently, $I\Pi_1$) is finitely axiomatizable.
As a matter of fact, the hierachy collapses already to its $0$th …
- 47.8k