The answer to your question is a resounding: IT DEPENDS! This takes us into some set theory, which - while interesting - is a bit off the beaten track perhaps for CS; to address this, I've made the first part of my answer strictly about the computability theory, and then added a separate section ...
This was previously asked at MSE without success. Suppose $T$ is a complete first-order theory with continuum-many countable models up to isomorphism. We define two sets of Turing degrees associated to $T$ via second-order logic: $SecTh(T)$ is the set of Turing degrees of second-order theories ...
There can indeed be ways of doing this, although I don't know of a natural one which works assuming only ZFC. I would say that they fall into two categories (and I suggest Kanamori's book as a great source on this sort of thing if you're interested): Fine structural (ZFC + "restricted universe"...
Your question as it stands is quite unclear, but let me take a stab at it; based on your previous questions, if nothing else I think you'll find this interesting. The simplest interpretation of your question is to look for an analogue of the Busy Beaver function for iterates of the Turing jump t...
Below, $T$ is a complete first-order theory in a finite language with no finite models. Also asked at MO. Question Suppose $T$ has continuum-many countable models. We define two sets of Turing degrees associated to $T$ via second-order logic: $SecTh(T)$ is the set of Turing degrees of second-or...
The Turing jump $0^{(\alpha)}$ is defined for ordinals $\alpha<\omega_1^{\mathit{CK}}$ with $0^{(0)} = \varnothing$, $0^{(\alpha+1)}$ is the diagonal halting problem using $0^{(\alpha)}$ as an oracle, $0^{(\lambda)}$ for a limit $\lambda$ is the effective join of the $0^{(\lambda_n)}$ for a comp...
Below I've addressed your specific questions. However, based on your multiple questions about this I think it might be more useful to give a list of good sources, so I'll do that first. On "gaps" in the constructible universe: Marek/Srebrny, Gaps in the constructible universe. The introduction ...
I'll focus only on the second-order situation here, since my answer applies a fortiori to the higher orders. It essentially$^1$ requires us to introduce a new notation, to the point that - in my opinion - true second-order arithmetic (which I'll call "$TA_2$") is fundamentally impossible to desc...
There's an interesting situation here: while the question itself isn't a duplicate, a previous answer of mine I think resolves it. I don't quite know what to do in this case, so I've written a same-spirit, different-phrasing below, and not marked this question as a duplicate; to avoid "double-dip...
You are getting at infinitary (first-order) logic. While a well-defined (and natural, and extensively studied) concept, it is quite different from ordinary first-order logic. Before diving into more detail, let me point out the main issue with your suggestion: There are "infinitely long" expr...
Let me begin by linking to the current standard textbook on infinitary logic: Lectures on infinitary logic by Dave Marker. You may also be interested in his primer on the topic. It's also worth pointing out the huge collection Model-theoretic logics - one of the seminal texts in abstract model t...
« first day (8 days earlier) ← previous day next day → last day (744 days later) »