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.
38
votes
Accepted
Can one show that the real field is not interpretable in the complex field without the axiom...
An interpretation of $(\mathbb R,+,\cdot)$ in $(\mathbb C,+,\cdot)$ in particular provides an interpretation of $\DeclareMathOperator\Th{Th}\Th(\mathbb R,+,\cdot)$ in $\Th(\mathbb C,+,\cdot)$. To see …
- 47.7k
37
votes
Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?
I realized that none of the answers present what I consider to be the most straightforward $\Pi^0_1$ expression for the Riemann hypothesis, namely bounds on the error term in the prime number theorem. …
- 47.7k
35
votes
Accepted
Alternatives to the law of the excluded middle
No, every consistent propositional logic that extends intuitionistic logic is a sublogic of classical logic. (That’s why consistent superintuitionistic logics are also called intermediate logics.)
To …
- 47.7k
30
votes
Accepted
Do you believe P=NP?
Contrary to a popular misunderstanding: if P = NP, then the proof of any statement $A$ can be found by an algorithm in time polynomial in the length of the shortest proof of $A$, not in the length of …
- 47.7k
29
votes
Accepted
Does "every" first-order theory have a finitely axiomatizable conservative extension?
Essentially, yes. An old result of Kleene [1], later strengthened by Craig and Vaught [2], shows that every recursively axiomatizable theory in first-order logic without identity, and every recursivel …
- 47.7k
27
votes
Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?
The standard terminology is that an interpretation $I$ of a theory $U$ in a theory $T$ is faithful if for all sentences $\phi$ in the language of $U$,
$$T\vdash\phi^I\iff U\vdash\phi.$$
(Here and belo …
- 47.7k
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.7k
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.7k
26
votes
Accepted
Countable group with uncountable number of subgroups $< 2^{\aleph_0}$
Subsets $H\subseteq G$ can be identified with their characteristic functions $\chi_H\colon G\to\{0,1\}$, which we can view as elements of the Cantor space $2^G$.
In this perspective, subgroups of $G$ …
- 47.7k
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 …
- 47.7k
25
votes
Accepted
When does $ZFC \vdash\ ' ZFC \vdash \varphi\ '$ imply $ZFC \vdash \varphi$?
$\def\zfc{\mathrm{ZFC}}\def\pr{\operatorname{Prov}\nolimits}$The statement
$\zfc\vdash\pr_\zfc(\ulcorner\varphi\urcorner)$ implies $\zfc\vdash\varphi$ for every sentence $\varphi$ in the language …
- 47.7k
24
votes
Accepted
Are there examples of nonconstructive metaproofs?
In theory, David’s answer is correct. Nevertheless, in practice it is perfectly possible to prove the existence of a proof non-constructively (such as by manipulating models and then appealing to the …
- 47.7k
24
votes
Accepted
Is this conjecture strictly weaker than P=NP?
The conjecture is indeed strictly weaker than $\mathrm{P = NP}$, in the sense that it follows from $\mathrm E=\Sigma^E_2$, which is not known to imply $\mathrm{P = NP}$. Of course, we cannot prove thi …
- 47.7k
24
votes
Accepted
Is there a first-order theory who does not interpret arithmetic yet still does not have a co...
Any theory that can represent all recursive functions has no consistent decidable extension, however there are such theories that do not interpret even as weak an arithmetic as Robinson’s theory $R$, …
- 47.7k
24
votes
Morse-Kelley set theory consistency strength
This is an instance of a much more general result. (See Visser [2] for an overview of various related principles.) A theory is called sequential if it supports encoding of sequences of its objects wit …
- 47.7k