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 ...
• 388k

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

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
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 ...
• 80.6k

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

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

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

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

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

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

• 323k
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
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
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
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
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

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