# Questions tagged [higher-order-logics]

For logics which admit quantification over sets/relations/functions/etc. rather than merely over individuals. The most common example is second-order logic.

41 questions
Filter by
Sorted by
Tagged with
383 views

### Topos semantics of constructive higher order logic

I would like to find a reference that describes the semantics of constructive higher order logic with function types in toposes. In particular, it seems that if we are to take function types as ...
• 971
300 views

### What are the simplest sentences which might distinguish Zilber’s field from the complex numbers?

Zilber’s field $\mathbb{B}$ is a field of the same size as the complex numbers $\mathbb{C}$, which satisfies the same first-order sentences about $+$ and $\cdot$. If $\mathbb{B}$ also satisfies the ...
142 views

### Source on equality-free second-order logic (nontrivially construed)

Throughout I'm only interested in the standard semantics for second-order logic, and all structures/languages are relational for simplicity. If defined naively, second-order logic without equality is ...
• 18.7k
349 views

• 8,872
120 views

### At which large cardinal property this second order ordinal arithmetic stops?

Language: Second order logic, with as usual predicates written in upper case, and objects in lower case. Let $<$ be a primitive constant binary relation symbol. Equality between objects is ...
• 8,872
372 views

### Do second-order theories always have irredundant axiomatizations?

It's a standard exercise to show that every countable first-order theory has an irredundant axiomatization. For uncountable first-order theories, the result is much more difficult and was proved by ...
• 18.7k
150 views

• 18.7k
215 views

### Second-order strong minimality and amorphousness, take 2

Recently I asked a question about whether a second-order analogue of strong minimality could correspond to amorphous satisfiability (= having a model whose underlying set cannot be partitioned into ...
• 18.7k
654 views

### Can second-order logic identify "amorphous satisfiability"?

Recall that a set is amorphous iff it is infinite but has no partition into two infinite subsets. I'm interested in the possible structure (in the sense of model theory) which an amorphous set can ...
• 18.7k
268 views

• 18.7k
378 views

### Compactness number for a fragment of second-order logic

Previously asked and bountied without response at MSE. This question is a companion to this one, about a tame(?) fragment of second-order logic with the standard semantics, $\mathsf{SOL}$, motivated ...
• 18.7k
446 views

### How many steps does it take to "Tarski-Vaughtify" second-order logic?

Given a regular logic $\mathcal{L}$, let $\preccurlyeq_\mathcal{L}$ be the usual elementary submodelhood relation for $\mathcal{L}$. There is also a separate submodelhood relation coming from the ...
• 18.7k
478 views

### Analogues of worldly cardinals for (an unusual version of) second-order $\mathsf{ZFC}$

Let $\mathfrak{ZFC}(\mathsf{SOL})$ be the theory in second-order logic (with the standard semantics) gotten from $\mathsf{ZFC}$ by modifying the Separation and Replacement schemes to apply to ...
• 18.7k
971 views

### How special is first-order $\mathsf{PA}$?

This is a modified version of a question which was asked and bountied at MSE without success. Below, "$\mathsf{PA}$" refers to first-order Peano arithmetic. There are various "...
• 18.7k
249 views

### Can a nonstandard model of $\mathsf{PA}$ be "$\Delta^1_1$-well-ordered?"

This was asked and bountied at MSE with no response: My question is the following: Is there a nonstandard model $\mathcal{M}\models\mathsf{PA}$ such that $\mathcal{M}$ has no $\Delta^1_1$-with-...
• 18.7k
182 views

### Reference requestion: theorem guaranteeing self-embeddings of expansions of $\mathit{Ord}$

This is an attempt to locate a theorem I vaguely remember but cannot find (which arose in the context of Consistency of non-trivial elementary embedding $j : \mathit{Ord} \to \mathit{Ord}$ and ...
• 18.7k
757 views

### Can $Ord$ have nontrivial second-order elementary self-embeddings?

I forgot to mention originally: this was motivated by this old MSE question. It's not hard to show in $\mathsf{ZFC}$ that there are nontrivial elementary embeddings from $(Ord; \in)$ to itself - or ...
• 18.7k
243 views

### Number of models vs. complexity for SOL theories

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 ...
• 18.7k
445 views

### Does Foundation increase the strength of second-order logic?

Thinking about the recent threads on structural consequences of the Axiom of Foundation (AF) over ZF-AF, I've been trying to find some conservativity result which explains why AF doesn't seem to have ...
• 3,937
602 views

### Preservation results in abstract logics

In retrospect the original version of this question was impossibly bloated. Here's a better version: There are many results about when first-order sentences are preserved by algebraic operations on ...
• 18.7k
1k views

### What sort of cardinal number is the Löwenheim–Skolem number for second-order logic?

In their paper “On Löwenheim–Skolem–Tarski numbers for extensions of first order logic”, Magidor and Väänänen make the following statement: “For second order logic, $\mathrm{LS}(L^{2})$ [the Löwenheim–...
• 6,024
1k views

### The (non-)absoluteness of second-order elementary equivalence

Elementary equivalence is set-theoretically absolute between any two transitive models of set theory; this is also true for the infinitary logics - e.g., $\mathcal{L}_{\omega_1\omega}$ - at least, ...
• 18.7k
977 views

### Vopěnka's Principle for non-first-order logics

(For simplicity, the background theory for this post is NBG, a set theory directly treating proper classes which is a conservative extension of ZFC.) Vopěnka's Principle ($VP$) states that, given any ...
• 18.7k
988 views

### Are there any complete, first-order and unstable theories which have non-categorical second-order formulations?

Since it's not stable, $PA$ fails at being categorical in a power in the worst possible way, having $2^{\lambda}$ models in any uncountable $\lambda$. But $PA$ regains its categoricity in the move to ...
1k views

### Categoricity in second order logic

Hi, It's shown by an easy cardinality argument that there are complete second-order theories that are not categorical (have more than one model up to isomorphism). Anyone knows of a concrete example ...
• 656
1k views

### ultrapowers and higher order logic

One of the reasons I think ultrapowers are interesting is the following corollary of Łoś's theorem: Let $V$ be a relational structure and $^*V$ an ultrapower of $V$. Then a first order statement ...
• 2,681
2k views

### Algebrization of second-order logic

Is there an algebrization of second-order logic, analogous to Boolean algebras for propositional logic and cylindric and polyadic algebras for first-order logic?
• 415