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 9269
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.
5
votes
Statement of consistency in Godel's second incompleteness theorem
I think there is a typo in Problem 18.6 of Belaniuk's text, because the
$\mathcal{A}$ in the problem refers to a (rather weak) fragment of $PA$
(but strong enough to numeralwise represent all recursiv …
- 17.7k
14
votes
What are the models of Peano Arithmetic plus the negation of the corresponding Gödel sentenc...
Here is the most "tangible" distinctive feature of models of $PA$ that satisfy the negation of Gödel's true but unprovable sentence.
Let $\phi$ be a true $\Pi^0_1$ arithmetical sentence that is not p …
- 17.7k
8
votes
Is there a theory in a finite language that is computably axiomatizable but not by a finite ...
This answers complements Fedor Pakhamov's, who provided an example of a computable theory that is not axiomatizable by finitely many schemas.
Following up on the comment by Andreas Blass to the questi …
- 17.7k
13
votes
Are there any natural recursively but not primitive-recursively axiomatized theories?
Here is another proposal. In this edition, the PS has been completely changed
Let $T_{ZFC}$ = arithmetical truths that $ZFC$ "knows about", i.e., the set of arithmetic sentences $\phi$ such that $ZFC …
- 17.7k
22
votes
Can we find strong fixed-points in the fixed-point lemma of Gödel's incompleteness theorem, ...
The existence of a Gödel-numbering that supports a strong fixed point was claimed by Kripke in his famous essay Outline of a Theory of Truth, Journal of Philosophy vol. 72 pp.690–716 (the only online …
- 17.7k
7
votes
Accepted
How do you prove that Q+Con(PA) can't be interpreted in ACA_0?
Firstly, your proposed reasoning does not work since $Con(PA)$ is a $\Pi^0_1$ statement.
Secondly, your parenthetical assumption is not in accordance with the general meaning of interpretations, and …
- 17.7k
11
votes
Accepted
Uncountable models of Kelley-Morse set theory with only a countable number of sets
The first relevant theorem is the following classical result:
Theorem A. (Mostowski, Keisler) If $M$ is a countable model of Kelley-Morse + Choice Scheme, then there is an elementary extension $M^{*} …
- 17.7k
4
votes
Accepted
Finite T-uples and the axiom of Regularity
Question 3 also has a negative answer (Joel Hamkins has already answered the first two questions).
The model $V(a,b,c)$ described in detail in my answer to an analogous question works here as well si …
- 17.7k
7
votes
Accepted
ordered fields with the bounded value property
EDIT NOTE: A postscript has been added to indicate why the answer does not change if one is forced to work in $ZF+AC_\omega$ (prompted by a query of James Propp). Thanks to James Propp, Ricky Demmer, …
- 17.7k
6
votes
Accepted
ordered fields with the bounded value property, without choice
In my answer to the related question, $AC_{\omega}$ was only used to ensure that one can get hold of a regular uncountable cardinal (i.e., $\omega_1$). And of course Gitik's remarkable theorem assures …
- 17.7k
6
votes
Incompleteness theorems for theories with omega-rule
Footnote to Emil Jeřábek's answer:
(1) Rosser (Journal of Symbolic Logic, 1937) was the first to show that there is a true $\Sigma^1_1$-statement that is unprovable in (second order arithmetic + the $ …
- 17.7k
5
votes
Accepted
Skolem's method for checking truth-value assignments - a "cut-free proof procedure" for firs...
The answer to the question can be found in Section I (especially p.11) of this source (it is a newly typeset version of Joseph E. Quinsey's 1980 Oxford doctoral thesis Some Problems in Logic: APPLICAT …
- 17.7k
18
votes
Accepted
Does ZF(C) prove countable reflection?
As Monroe Eskew points out in his comment to the question, the positive answer is well-known for ZFC, thanks to the ZF reflection theorem and the Löwenheim-Skolem Theorem (in the form: every model in …
- 17.7k
10
votes
Is every order type of a PA model the \omega of some ZFC model?
Joel Hamkins has already answered the question in the positive for countable models of PA; indeed PA can be relaxed to IOpen in his argument.
In the uncountable case, as far as I know, the problem is …
- 17.7k
9
votes
Set theory determined by $V_\alpha$ for limit ordinals $\alpha>\omega$
This answer concerns the second question (which asks whether there is a characterization of the theory of models of the form $V_{\alpha}$, where $\alpha$ ranges over limit ordinals), and its elaborati …
- 17.7k