15
votes
Accepted
Second-order logic as the basis for set theory
The thing about the second-order of $\sf ZFC$ is that $M$ is a model of second-order $\sf ZFC$ if and only if $M$ is isomorphic to $V_\kappa$ for an inaccessible $\kappa$. So right off the bat you ...
- 388k
11
votes
Categoricity of second order theories - precisely what does it mean?
To supplement Asaf's answer, let me observe that there are natural second-order theories whose categoricity is undecidable in ZFC. Specifically, let's take second-order ZFC ("ZFC$_2$") itself!
It's ...
- 237k
11
votes
Accepted
Categoricity of second order theories - precisely what does it mean?
The point is that you already assume there is some set theory in play when you talk about second-order logic.
In other words, you use first-order set theory to talk about second-order "everyday ...
- 388k
10
votes
Accepted
How are sets defined in reverse mathematics?
The answer is in the name of the book.
The system described is equivalent to a particular (monadic) second-order theory using Henkin semantics.
Instead of talking about "sets", Simpson could have ...
- 24.6k
9
votes
Does intuitionist second-order logic prove the negations of some classical theorems?
This would surprise me too. Suppose we call $\phi$ a classical theorem iff there is a deduction $\vdash_c \phi$ in classical logic. If there now were an intuitionistic deduction $\vdash_i \neg \phi$, ...
- 2,976
8
votes
Accepted
Which second-order theories have a model?
Such a property cannot exist, at least if
a "purely syntactic" property means something that can be expressed as a first order arithmetical property of the Gödel numbers of the theory's axioms (which ...
7
votes
Is it possible to derive the axiom of induction from a construction of the natural numbers?
Yes, it is possible to prove that a "natural numbers type structure" satisfies the induction axiom. The proof will be carried out in the same set theory that is used to form the natural number type ...
- 80.6k
7
votes
Second order ZFC, intuition required
EDIT: in light of Carl Mummert's comments below, I've decided to add a clarification re: semantics of second-order logic to this answer. It's a bit long, so it's at the end.
The language of second-...
- 237k
7
votes
Accepted
Terms in second-order logic
One issue is that, although a first-order language has only one type of basic variables, for individuals, a general language for second order logic has an infinite collection of types of basic ...
- 80.6k
6
votes
Which second-order theories have a model?
For simplicity, it is common to work just with the language of equality. Let $V^2$ be the set of second-order validities in this language. It is also somewhat common to look at the set $V^2$ instead ...
- 80.6k
6
votes
Accepted
Relation between consistency of ZF, MK and NBG
ZF is consistent iff NBG is consistent. If MK is consistent, then ZF and NBG are consistent, but this cannot be reversed (working in MK, say). So the relative consistency strengths are $MK>NBG=ZF$...
- 323k
6
votes
Which logic is stronger? SOL or $\frak{L}_{\infty,\infty}$?
While Model-theoretic logics is indeed a wonderful source, for this particular question it's overkill. The logics $\mathfrak{L}_{\infty,\infty}$ and $SOL$ are incomparable in a precise sense.
One ...
- 237k
6
votes
How are sets defined in reverse mathematics?
I'm not sure I've understood your question correctly, but let me take a stab at it:
The short version is that we can develop RCA$_0$ (and any other theory, for that matter) entirely "autonomously,...
- 237k
6
votes
Is there any way to reduce standard second-order logic to first-order logic?
The real inescapable obstacle isn't Lowenheim-Skolem, it's compactness. This prevents any reasonable notion of reduction I can think of, looking purely at how logical implication works within the ...
- 237k
6
votes
What order types can well-ordered proper classes have?
To make things clearer I'm going to rephrase the question as follows (it's not hard to translate between this question, which is asked in the ZFC context, and your question as you've phrased it):
...
- 237k
6
votes
Accepted
What axiom system for the complex numbers is categorical?
In full second-order logic you can characterize $\mathbb{C}$ in the language $(+,\cdot,0,1)$ up to isomorphism using the following axioms:
First-order axioms stating that $(M,+,\cdot,0,1)$ forms an ...
- 9,185
6
votes
Accepted
Is existential second-order logic 'closed' under negation?
Yes, your intuition is right: existential second-order logic is not closed under negation.
In my opinion, the easiest way to see this is to note that ultrapowers preserve existential second-order ...
- 237k
6
votes
Accepted
Is infinitary first-order logic strictly more expressive than weak second-order logic?
To avoid a triviality, I'll restrict to finite signatures below. In an infinite signature we get a silly affirmative answer, since we can whip up an $\mathcal{L}_{\omega_1,\omega}$-sentence saying ...
- 237k
6
votes
Accepted
The complexity of finiteness
As you discussed in the comments, $\Pi_1^1$ formulas $\varphi(X)$ in the empty language are equivalent to statements of the form 'there is no model of $\psi$ whose underlying set is $X$,' where $\...
- 3,783
6
votes
Accepted
What axiom system for the rational numbers is categorical?
Take the first-order theory of fields of characteristic zero (in the language of rings) and add to it the following second-order axiom:
The only subfield is the whole field.
The only field of ...
- 88.7k
6
votes
Accepted
Does the logical system with the "there exist uncountably many"-quantifier satisfy a variant of upwards Löwenheim-Skolem
No, it doesn't.
Consider $\omega_1$, thought of as a linear order. This satisfies - in addition to the usual axioms of linear order - the axioms "The universe is uncountable" and "For ...
- 237k
6
votes
Accepted
Is there a model of $\operatorname{Th}(\mathbb{R})$ which is not a complete ordered field?
Actually $\mathbb{R}$ is the only complete ordered field, see this MO thread; basically it's because order completeness implies that the order must be archimedean, and any archimedean ordered field is ...
- 563
5
votes
Accepted
Finitely axiomatized second-order theory without a model, which is consistent for reasonable deductive systems
No, though perhaps only because your criteria for "reasonable" are too weak. Consider the following "deductive system". Given a set of axioms $\Gamma$, a sentence $\sigma$ can be deduced from $\...
- 323k
5
votes
Accepted
What are Henkin models
There are two things one could plausibly mean by the phrase "Henkin model." The first is the sort of structure that emerges during the usual proof of Godel's Completeness Theorem (no, that's not a ...
- 237k
5
votes
Accepted
Formally what is the first and second order induction axiom?
First order:
For any first order formula $\phi$ in the language of arithmetic, the following is an axiom: $$ (\phi(0) \land\forall x(\phi(x)\to\phi(S x)))\to \forall x\phi(x).$$
Second ...
- 55.5k
5
votes
Accepted
What ordinals are computable using $\Sigma^1_2$ and $\Pi^1_2$ truth?
The set $Th_{\Pi^1_2}(\mathbb{N})$ (which I'll call "$X_2$") computes really really big ordinals; so big, in fact, that there's a decent argument that their supremum $\omega_1^{CK}(X_2)$ is "...
- 237k
5
votes
Accepted
Is there a specific infinitary sentence second-order logic can't capture?
Here's a partial positive answer:
It's easy to show that for $X\subseteq\omega$ the (isomorphism class of) structure $$Set_X:=(\omega; <,X)$$ is characterizable by a single second-order sentence ...
- 237k
5
votes
Accepted
How strong is this second-order version of ZFC?
This is not a full answer to the question $``$What are the set-sized models of $ZFC^{scheme}_2?"$ however we will see that $ZFC^{scheme}_2$ is not significantly weaker than second order $ZFC$.
I ...
- 3,471
5
votes
Why second order logic is more expressive that the first order logic?
You're misunderstanding what second-order logic does. I think part of this is due to the use of the term "predicate," which is unfortunate since it has connotations which are not relevant ...
- 237k
5
votes
Accepted
Limitation of Henkin sematics in second order logic
In a Henkin model, the second-order quantifiers are not required to range over all possible properties/relations over the domain of objects. In other words, the domain of the second-order quantifiers ...
- 53.1k
Only top scored, non community-wiki answers of a minimum length are eligible