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.
50 questions
2 votes
0 answers
118 views
Equivalence among $\tau$-theory, elementary topos and Mitchell-Bénabou language
In Johnstone's book "Sketches of an Elephant: A topos theory compendium, volume 2" (referred as Elephant), he defined a higher-order typed (intuitionistic) signature (simplified as $\tau$-...
- 29
9 votes
0 answers
249 views
Which sets of sentences can be "continuously" decided in an ultraproduct?
Motivated by Łos' theorem, given a countable sequence of structures $\mathscr{A}=(A_i)_{i\in\mathbb{N}}$ each in the same language say that a second-order sentence $\varphi$ in that language is Ł-...
- 19.3k
5 votes
0 answers
120 views
Categorical model of Gordon's higher order logic
Lambek and Scott gives a category theoretic account on higher order logic, for an intuitionistic version in their book. Is there newer work that covers at least some parts of Gordon's higher order ...
- 349
2 votes
0 answers
138 views
Looking for a general definition of "classical" higher-order logic in literature
By "classical," I mean merely not working within the propositions-as-types paradigm. I have been unsuccessfully searching the internet for literature containing a general definition of ...
- 121
6 votes
0 answers
286 views
Whence compactness of automorphism quantifiers?
The following question arose while trying to read Shelah's papers Models with second-order properties I-V. For simplicity, I'm assuming a much stronger theory here than Shelah: throughout, we work in $...
- 19.3k
2 votes
1 answer
242 views
Definability in pure-second order logic
Are the universe and the empty set the only definable sets without parameters in the language of pure second-order logic? TIA
3 votes
0 answers
157 views
Comparing two fragments of SOL with the downward Lowenheim-Skolem property
For $S$ a set of (parameter-free) second-order formulas and $\mathfrak{A},\mathfrak{B}$ structures, write $\mathfrak{A}\trianglelefteq^S\mathfrak{B}$ iff $\mathfrak{A}$ is a substructure of $\mathfrak{...
- 19.3k
5 votes
1 answer
749 views
The "first-order theory of the second-order theory of $\mathrm{ZFC}$"
$\newcommand\ZFC{\mathrm{ZFC}}\DeclareMathOperator\Con{Con}$It is often interesting to look at the theory of all first-order statements that are true in some second-order theory, giving us things like ...
- 5,005
6 votes
1 answer
484 views
Second-order ordinal definability
As is familiar, a set $S$ is ordinal definable ($S \in \mathsf{OD}$) just in case there exists a formula $\varphi(x, \vec{z})$ of the first-order language of set theory with parameters $\vec{z} = z_1, ...
- 1,165
5 votes
2 answers
622 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 ...
- 2,166
7 votes
1 answer
424 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 ...
user44143
4 votes
1 answer
227 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 ...
- 19.3k
8 votes
1 answer
484 views
On the strength of higher-logic analogues of $\mathsf{ZFC}$ + Montague's Reflection Principle
Throughout, I work in $\mathsf{MK}$ in order to be able to conveniently quantify over logics; if one prefers, we can restrict attention to (say) $\Sigma_{17}$-definable logics and work in $\mathsf{ZFC}...
- 19.3k
6 votes
1 answer
321 views
Does second-order logic satisfy Craig interpolation for second-order languages?
(For simplicity, all languages are relational.) In analogy with first-order languages, say that a second-order language is a set of relation symbols of two kinds: first-order relation symbols and ...
- 19.3k
11 votes
1 answer
785 views
Are there quantifiers that require multiple "steps" to define?
(Below I conflate quantifiers and quantifier symbols in a couple places for readability; I can change that if that actually makes things less readable.) For the purposes of this question, an $n$-ary ...
- 19.3k
9 votes
0 answers
303 views
Can "$\exists\mathcal{X}(R\cong C(\mathcal{X}))$" be expressed in "large" infinitary second-order logic?
Originally asked and bountied at MSE without success: Say that a ring $R$ is spatial iff there is some topological space $\mathcal{X}$ such that $R\cong C(\mathcal{X})$, where $C(\mathcal{X})$ is the ...
- 19.3k
1 vote
0 answers
237 views
Can Frege set extensions of second order unary predicates serve as a foundation for mathematics?
To second order logic, add a primitive partial one place function symbol "$\epsilon$" from unary predicate symbols [upper cases] to object symbols [lower cases]. Define: $ x=y \equiv_{df} \...
- 13k
3 votes
0 answers
162 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 ...
- 13k
12 votes
1 answer
446 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 ...
- 19.3k
4 votes
0 answers
171 views
How big a "scaffold" does second-order logic need to detect its own equivalence notion?
(Previously asked and bountied at MSE:) Let $\Sigma$ be the language consisting of a single binary relation symbol. Second-order logic can "detect" second-order-elementary-equivalence of $\...
- 19.3k
4 votes
0 answers
188 views
Can SOL characterize its own equivalence notion, without "scaffolding," for graphs?
Consider the following property $(*)_\mathcal{L}$ of a logic $\mathcal{L}$: $(*)_\mathcal{L}:\quad$ There is no $\mathcal{L}$-sentence $\varphi$ such that for all graphs $\mathcal{A},\mathcal{B}$ we ...
- 19.3k
5 votes
1 answer
338 views
Can the forcing-absolute fragment of SOL have a strong Lowenheim-Skolem property?
Previously asked and bountied at MSE: Let $\mathsf{SOL_{abs}}$ be the "forcing-absolute" fragment of second-order logic - that is, the set of second-order formulas $\varphi$ such that for ...
- 19.3k
5 votes
1 answer
349 views
Does there always exist a categorical extension of $ZFC_2$ with no set models?
$ZFC_2$, i.e. second-order Zermelo-Fraenkel set theory with Choice, has only one proper class model upto isomorphism, namely $V$. But it may or may not also have set models. If $V$ has no ...
- 4,583
8 votes
1 answer
757 views
Can there be no "surprisingly averageable" second-order sentences?
Say that a second-order sentence $\varphi$ is averageable iff there exists some infinite cardinal $\kappa$ and some nonprincipal ultrafilter $\mathcal{U}$ on $\kappa$ such that for every $\kappa$-...
- 19.3k
6 votes
1 answer
398 views
Can $\mathsf{Ord}$ be weakly compact from a second-order perspective?
Working in $\mathsf{ZFC}$ + "There is a weakly compact cardinal" and letting $\kappa$ be the least weakly compact cardinal, say that a logic $\mathcal{L}$ is loraxian iff every $\mathcal{L}$...
- 19.3k
8 votes
1 answer
440 views
Does "agreement on cardinalities" imply second-order elementary substructurehood?
Say that a logic $\mathcal{L}$ satisfies the weak test property iff for all $\mathfrak{A}\subseteq\mathfrak{B}$ we have $(1)\implies(2)$ below: For each $\mathcal{L}$-formula $\varphi$ with ...
- 19.3k
7 votes
1 answer
452 views
Compatibility of Łośian phenomena in second-order logic
(Throughout, all ultrafilters are nonprincipal.) Given a property $P$ - really, a sentence in some appropriate logic - say that a ultrafilter $\mathcal{U}$ on a cardinal $\kappa$ averages $P$ iff for ...
- 19.3k
2 votes
1 answer
517 views
Abstraction logic
As part of my research on building an interactive theorem proving system, I have discovered a new logic that I call Abstraction logic. I have written up the details here: https://doi.org/10.47757/...
- 179
6 votes
1 answer
439 views
Failure of "directedness" for second-order logic?
Say that a logic $\mathcal{L}$ is directed iff whenever $\mathfrak{A}\equiv_\mathcal{L}\mathfrak{B}$ there is some $\mathfrak{C}$ with $\mathcal{L}$-elementary substructures $\mathfrak{A}'\...
- 19.3k
2 votes
1 answer
281 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 ...
- 19.3k
7 votes
2 answers
764 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 ...
- 19.3k
6 votes
2 answers
330 views
Are there structures in a finite signature that are recursively categorically axiomatizable in SOL but not finitely categorically axiomatizable?
Recall that a structure $\mathcal{M} = \langle M, I^\sigma_M \rangle$ in a signature $\sigma$ is categorically axiomatized by a second-order theory $T$ when, for any $\sigma$-structure $\mathcal{N} = \...
- 1,165
4 votes
1 answer
334 views
Candidate "AEC-yielding" fragments of bad logics
Previously asked and bountied on MSE without success: Given a logic $\mathcal{L}$ and a signature $\Sigma$, let the $\Sigma$-system of $\mathcal{L}$ be the pair $Sys_\Sigma(\mathcal{L})=(Struc(\Sigma),...
- 19.3k
4 votes
1 answer
494 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 ...
- 19.3k
9 votes
0 answers
659 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 ...
- 19.3k
8 votes
2 answers
613 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 ...
- 19.3k
16 votes
2 answers
1k 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 "...
- 19.3k
5 votes
1 answer
321 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-...
- 19.3k
6 votes
0 answers
220 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 ...
- 19.3k
16 votes
1 answer
997 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 ...
- 19.3k
6 votes
0 answers
279 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 ...
- 19.3k
14 votes
0 answers
527 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 ...
- 8,398
7 votes
1 answer
658 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 ...
- 19.3k
18 votes
2 answers
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,260
13 votes
2 answers
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, ...
- 19.3k
16 votes
3 answers
1k 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 ...
- 19.3k
9 votes
2 answers
1k 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 ...
- 145
10 votes
3 answers
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 ...
- 676
13 votes
4 answers
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,781
22 votes
3 answers
2k views
Algebraization of second-order logic
Is there an algebraization of second-order logic, analogous to Boolean algebras for propositional logic and cylindric and polyadic algebras for first-order logic?
- 445