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 1946
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.
2
votes
Accepted
Is anyone talking about partial interpretations of theories? (Edited)
One common example where this arises is in the consideration of $\omega$-models of set theory. These are precisely the models that interpret their natural numbers as the standard natural numbers $\ome …
- 236k
2
votes
complexity of proof of p(n) grows greater with n if for all x P(x) is unprovable?
Consider the assertion $P(x)$ that asserts "$x$ is not the Gödel code of a proof of a contradiction in PA". If PA is consistent, then we can prove $P(n)$ for any particular natural number $n$, since …
- 236k
7
votes
Accepted
Is $PA+ \neg R_{PA}$ $\Pi_1$- conservative over $PA$?
The Rosser sentence $R$ asserts, "for every proof of $R$ in PA,
there is a smaller proof of $\neg R$." So $\neg R$ asserts, "there
is a proof of $R$ in PA, with no smaller proof of $\neg R$."
In part …
- 236k
3
votes
Accepted
Completeness of a set of propositional formulas
Given a finite propositional theory, one can decide completeness by checking the truth table. As Emil mentions, in general completeness for a finite theory will be NP-complete.
But your examples are …
- 236k
7
votes
Accepted
Can a class of arithmetical statements containing its own soundness condition be closed unde...
The answer to both questions is negative.
Theorem. There is no class $C$ of formulas in the language of
arithmetic, such that
the assertion "$T$ is not $C$-sound" is uniformly expressible in $C$
for …
- 236k
4
votes
Statement of consistency in Godel's second incompleteness theorem
First, notice that one can have a somewhat cheating solution, like this: You didn't say what $A$ was, but let me assume that it is consistent. There are two cases. If $\Sigma$ happens to be consistent …
- 236k
3
votes
Accepted
A question about relativized admissibility theory
Let me assume first that by $\omega_1$ you meant
$\omega_1^L$, that is, the $\omega_1$ of $L$. In this case, no, even the $1$-special reals are not
bounded. To see this, note first that there are unb …
- 236k
1
vote
Existential-universal quadratic arithmetic
I understand your decision problem as follows: we are given finitely many real constants and a formula $F$ that is a disjunction of linear inequalities in the form you mention, having real variables $ …
- 236k
23
votes
Unprovable statements S where the only way to prove S is to assume S
Theorem. There are no minimally unprovable statements, over
any computably axiomatizable theory $T$ interpreting basic arithmetic.
Proof. Suppose that $S$ is not provable in $T$, that $T+S$ is
consis …
- 236k
8
votes
When is $\mathbb{L}$-rank definable in inner models of $\mathbb{V} = \mathbb{L}$?
This is a great question, and very subtle.
Here is a way to see that the relation cannot be uniformly definable. Suppose $L_\alpha$ is a countable model of ZFC, and $\phi$ works as you say in every m …
- 236k
4
votes
Accepted
Is the structure $(\omega,+,2^n)$ undecidable?
As Marty explained in this answer, this question is the central topic of the paper On the expansion $\langle \mathbb{N},+,2^x\rangle$ of Presburger arithmetic, by Françoise Point, based on a joint pro …
- 236k
1
vote
If M is an inner model containing all the reals, might every game in M be determined in V?
Two observations.
First, I note that your hypothesis implies projective determinacy,
since $M$ and $V$ have exactly the same projective sets, and if
they have winning strategies in $V$ then those str …
- 236k
1
vote
Closure of one relation w.r.t other
(This is more of a comment than an answer, but too long for the comment box.)
Your property is saying precisely that $[(R\circ R')\upharpoonright\text{dom}(R)]\subseteq R$.
I'm not sure I like your …
- 236k
10
votes
Provability of termination. Whats wrong with my reasoning?
What you have (re)discovered is a proof of Goedel's first incompleteness theorem via the halting problem. Let us suppose that we have already established that the halting problem is undecidable, which …
- 236k
2
votes
Accepted
Bounded-variable logic: "fewer than $\alpha$ variables" equivalent to "every subformula has ...
If you are speaking of infinitary logic, which your notation (and your other question) suggests, then the statement is not true. Take the case $\alpha=\omega$. Suppose that $\varphi_n$ is a sentence t …
- 236k