# Tag Info

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 ...

### 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 ...
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 ...
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 ...

### 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$, ...
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 ...

### 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 ...

### 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-...
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 ...

### 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 ...
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$...

### 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 ...

### 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,...

### 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 ...

### 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): ...
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 ...
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 ...
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 ...
Accepted

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 ...
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 ...
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 "...
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 ...
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 ...