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 8133
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.
8
votes
Can the incompleteness of set theory be isolated to questions about arithmetic?
Say that a theory $T\supseteq \mathsf{ZFC}$ is CCMA ("complete computable mod arithmetic") iff $T$ is computable but $T^+:=T\cup\mathsf{TA}$ is complete and consistent, where $\mathsf{TA}$ is true ari …
- 20.7k
15
votes
Are integers conservatively embedded in the field of complex numbers?
I don't know a reference, but here's a (slightly overkill) proof:
It's known that $(\mathbb{Z};+,\times)$ interprets an algebraically closed field $K$ of infinite transcendence degree and characterist …
- 20.7k
15
votes
Accepted
Consistency of ZFC with inaccessible cardinals but no measurable cardinals
Suppose $M\models\mathsf{ZFC+GU}$. If $M$ also satisfies $\mathsf{NMC}$, then we're done. Otherwise, let $\kappa$ be (what $M$ thinks is) the smallest measurable cardinal. Then since measurable cardin …
- 20.7k
19
votes
Accepted
Is every recursively axiomatizable and consistent theory interpretable in the true arithmeti...
The answer is yes. I believe the following is best attributed to Feferman 1960; more generally, look up "arithmetized completeness theorem" (which is annoyingly different from the arithmetic completen …
- 20.7k
5
votes
Accepted
Does $\mathrm{L}_{s_{n+1}}$ contain a surjection from $\omega$ to $\mathrm{L}_{s_n}$?
In fact much more is true: if $L_\alpha$ is the first level of the $L$-hierarchy satisfying some first-order theory $T$, then it will be pointwise-definable$^*$ and so $L_{\alpha+2}$ will contain an i …
- 20.7k
9
votes
At what ordinal $\chi$ does $\mathrm{L}_\chi$ contain a surjection from $\omega$ to $\mathrm...
As a precoda to Gabe's answer, it's worth noting that $\beta_0$ is in fact the first ordinal $\alpha$ which "starts a gap," i.e. such that $L_{\alpha+1}\models$ "$\alpha$ is uncountable." (To be preci …
- 20.7k
7
votes
Accepted
Natural functions outside $\sf PA$?
Sure, but this is really a fact about structures rather than theories. For example, $\mathsf{ZFC}$ can define the function sending $n$ to the least natural number not definable in the language of arit …
- 20.7k
9
votes
Accepted
Negating fundamental axioms
In my limited experience (which may soon be changed! :P), merely negating "fundamental" axioms does not yield strong in-system consequences. The word "merely" is doing some work here, though, since of …
- 20.7k
4
votes
Accepted
How can we define non-finitely axiomatizable extensions of set theories?
For any "reasonable" theory $T$, we can find a computable sequence of sentences $(\sigma_i^T)_{i\in\omega}$ such that
$T\cup\{\sigma_i^T: i\not=n\}\not\vdash\sigma_n^T$ for each $n$ (so the extension …
- 20.7k
1
vote
Computability-theoretic results relevant to realizability
This wasn't exactly what I had in mind when I first asked this question, but I don't think it's unrelated either: combining realizability (in a very naive way) with classical computability-theoretic …
- 20.7k
14
votes
Infinitary logics and the axiom of choice
What you're basically describing is the result of replacing, in the usual definition of $\mathsf{ZF}$, schemes ranging over first-order formulas by schemes ranging over formulas in a different logic $ …
- 20.7k
13
votes
Accepted
How are real numbers defined in elementary recursive arithmetic?
They aren't. Analysis requires a richer language. Note the particular restriction in Friedman's conjecture:
...whose statement involves only finitary mathematical objects (i.e., what logicians call a …
- 20.7k
1
vote
What are some proofs of Godel's Theorem which are *essentially different* from the original ...
Yet another one, very belatedly - this time proving the second incompleteness theorem! Below I assume some reasonable bijective (for simplicity) Godel numbering system. This is due to Adamowicz and Bi …
6
votes
Accepted
Constructible cardinality downslides and their consistency strengths?
Since $\omega_1^V\subseteq L$ (simply because $L$'s construction goes through all the ordinals), we obviously can't have $L$ be countable. On the other hand, if $0^\sharp$ exists then every uncountabl …
- 20.7k
7
votes
Accepted
Independence of CH and permutation models?
No, it cannot. This is because CH is fundamentally a statement about pure sets (= sets not containing urelements in their transitive closures). No independence result for statements about "pure sets" …
- 20.7k