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 not deleted
user 8991
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.
3
votes
Can the omega-rule rescue Hilbert's program?
$PA+\omega$-rule certainly proves $Con(PA)$. If $Con(PA)$ is false, PA proves everything. If $Con(PA)$ is true, this is a $\Pi^0_1$-statement, and $PA+\omega$-rule proves every true $\Pi^0_1$-statem …
- 7,145
6
votes
Accepted
A derivation in Tait calculus
There's no rule that lets you get from a deduction of $\Gamma$ to a deduction of $\Gamma,\Delta$. However it's an easy lemma that, given a deduction of $\Gamma$, there is also a deduction of $\Gamma, …
- 7,145
6
votes
logics restricted in arithmetic hierarchy
There are some theories which, in essence, have only $\Pi^0_2$ formulas, in a way which I think captures what you're trying to capture. These theories are actually entirely quantifier free, but they …
- 7,145
5
votes
Accepted
Compactness theorem with preserved substructure
No. Suppose the signature of T contains a distinguished symbol $\omega$, and $T$ contains the statements $R(\omega)$ and the infinitely many statements $1+\cdots+1<\omega$. Then any finite subset of …
- 7,145
13
votes
Is it possible for P(N) to be larger than Aleph_omega?
Yes. In fact, the only requirement on $2^{\aleph_0}$ is that $cf(2^{\aleph_0})>\aleph_0$. (Cohen's argument can make the power set any regular cardinal, and I think it requires at most small modific …
- 7,145
5
votes
What lets the Square of Opposition fail in Intuitionistic Logic?
I'm not sure if there's a system short of classical logic where (Q) holds for all formulas, however the principle
$$\forall x(\phi\vee\neg\phi)\rightarrow(\neg \forall x\neg\phi\rightarrow\exists x\ph …
- 7,145
8
votes
Accepted
Admissible ordinal beyond $\omega_{1}^{ck} .$
The admissible ordinals are unbounded in $\omega_1$, so there are uncountably many countable admissible ordinals. Barwise's book, "Admissible Sets and Structures" is the standard reference on all thi …
- 7,145
2
votes
Accepted
Elementary functions in a formalized PA
I think your first and last questions more or less answer each other: the elementary functions can be defined using quantifiers, so adding them as symbols makes the quantifier-free formulas more expre …
- 7,145
4
votes
Accepted
Cut elimination algorithms
As Noah pointed out, if it's provable, there must be an algorithm for cut-elimination for STT because the underlying statement is $\Pi_2$ (for any deduction in STT, there is a corresponding deduction …
- 7,145
2
votes
How do quantifiers limit scope?
Bounded quantifiers of various kinds, like $\forall x<t$ or $\exists y\in\mathbb{N}$, are a commonly used notational convention. The convention for such notations is exactly what you expect:
$$\fora …
- 7,145
5
votes
Difference between turnstile and implication
To add to Joel's answer, in the most common theories (for instance, ordinary first-order logic), these are equivalent (by the deduction theorem), but there are plenty of theories where they aren't.
O …
- 7,145
2
votes
Question of combinatorics in the lower part of the Borel hierarchy.
(As Andreas has pointed out, this answer is not correct---it concerns a slightly different class of functions.)
The answer to your first question is yes. For any nice function $f$, consider the tree …
- 7,145
6
votes
Applications of nonconstructive mathematics
The mean and pointwise ergodic theorems are non-constructive, and I understand they were originally developed for applications to thermodynamics.
4
votes
Ultraproduct of Dividing Lines
I'm going to assume we're talking about $\omega$-incomplete ultrafilters.
Others have pointed out that none of the major dividing lines are elementary; that is, these properties are not equivalent to …
- 7,145
7
votes
Accepted
What are key $\Sigma^0_2$ or $\Pi^0_3$ theorems?
I'm not clear whether you're asking if there are any interesting non-$\Pi_2$ theorems in the literature, or any proofs of $\Pi_2$ theorems with interesting non-$\Pi_2$ intermediate steps which cannot …
- 7,145