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.
15
votes
Accepted
Are there "non-constructive" sets in second-order arithmetic?
This may or may not be true depending on the background set theory.
On the one hand, it is consistent with ZFC that there exists a $\Delta^1_2$-definable well-ordering $\prec$ of the reals. Then one …
- 47.6k
9
votes
complexity of proof of p(n) grows greater with n if for all x P(x) is unprovable?
You didn’t specify what you mean by “complexity”. If one interprets it as the number of lines in the proof, this is a famous conjecture of Kreisel (usually stated contrapositively: if there is a const …
- 47.6k
11
votes
Accepted
Are all the theorems true?
$\def\zfc{\mathrm{ZFC}}\def\pa{\mathrm{PA}}$First, there is no consistent recursively axiomatizable theory extending Robinson’s arithmetic which has the property of having existential witnesses as des …
- 47.6k
7
votes
Accepted
Is the first order theory of ordered rings without infinitesimals effectively enumerable?
The answer to the first question is no. First, let $\chi=\forall x>0\\,\exists y\\,(xy=1)$ and $T'=T+\chi$, so that $T'$ is the first-order theory of archimedean ordered fields. Let $\phi(x)$ be a for …
- 47.6k
3
votes
Existential-universal quadratic arithmetic
The problem is undecidable even if all the real constants $c_i$ are integers $0,\pm1$ (so that there is no issue of their representation) and all $b=0$.
By the MRDP theorem, the following problem is …
- 47.6k
4
votes
Accepted
Normal form in second-order logic
First, if you don’t place any restrictions on the transformation, you can actually make $S'$ as simple as you want in any logic: if $S$ is valid, let $S'$ be any fixed tautology, otherwise let $S'$ be …
- 47.6k
4
votes
Accepted
About some functions in the set of the natural numbers
$\let\fii\varphi\let\ol\overline$Andreas has already answered the original question, however it was raised in the comments whether $f$ coincides with the sequence in http://oeis.org/A022342:
$$\tag{$* …
- 47.6k
12
votes
Is metatheory, providing proof of the incompleteness theorem, consistent?
As already pointed out by Steven Landsburg, there are plenty of such theories if you stick to conventional mathematics. If you are some sort of an ultrafinitist,
the incompleteness theorem is provable …
- 47.6k
2
votes
Accepted
Zeros of polynomials in discretely ordered rings
The answer is no. The argument below is essentially due to Kaye [1] (Lemmas 2.1 and 5.8). Put $$p(a,x,y)=x^2-2axy+y^2-1.$$
Lemma 1: In any discretely ordered ring (DOR), if $p(a,x,y)=0$, $0< x\le y$, …
- 47.6k
7
votes
Accepted
Are undecidable consequences of Con recursively enumerable?
The answer is no, and in particular, $X$ is $\Pi^0_1$-hard. Let $\sigma(x)=\exists v\,\theta(x,v)$ be a complete $\Sigma^0_1$-formula, where $\theta\in\Delta^0_0$, and find a formula $\pi(x)$ such tha …
- 47.6k
13
votes
What are the models of Peano Arithmetic plus the negation of the corresponding Gödel sentenc...
While there is only one standard model, there are indeed many distinct (and elementarily nonequivalent) nonstandard models. As for distinguishing those that satisfy G and those that do not, I’m afraid …
- 47.6k
3
votes
Complete proof system
It’s impossible to give anything but vague answer to such a vague question, but on a hand-waving high level, there are basically two common approaches to completeness proofs:
Show that any set of fo …
- 47.6k
10
votes
"Almost all" quantifier
No. For example, Robinson’s Q + $\forall x\,G_y\,x<y$ is a categorical theory (its only model up to isomorphism is the standard model of arithmetic), hence it is not equivalent to any first-order sent …
- 47.6k
7
votes
Accepted
decidable fragments of first-order logic without the finite countermodel property
If you restrict attention to the traditional prefix–vocabulary classes, validity in the following fragments is decidable without having the finite model property (note that it is customary in the lite …
- 47.6k
2
votes
Accepted
Difference about defined symbols in metatheory or in object language
To begin with the second question, everyday reasoning in mathematics is in the object language. (Though if you happen to be a logician, this object language may well get used as a meta-language for an …
- 47.6k