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.
27
questions
5
votes
1answer
173 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 ...
5
votes
1answer
190 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
votes
1answer
297 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$-...
6
votes
1answer
246 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}$...
7
votes
1answer
293 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 ...
2
votes
1answer
218 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/...
6
votes
1answer
289 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}'\...
2
votes
1answer
202 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 ...
7
votes
2answers
587 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 ...
7
votes
2answers
234 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} = \...
4
votes
1answer
238 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),...
4
votes
1answer
284 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 ...
8
votes
0answers
217 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 ...
6
votes
2answers
357 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 ...
14
votes
2answers
616 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 "...
5
votes
1answer
180 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-...
6
votes
0answers
156 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 ...
15
votes
1answer
566 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 ...
13
votes
0answers
387 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 ...
7
votes
1answer
572 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
votes
2answers
986 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–...
12
votes
2answers
870 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, ...
15
votes
3answers
818 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 ...
9
votes
2answers
902 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 ...
10
votes
3answers
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 ...
12
votes
4answers
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 ...
18
votes
2answers
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?
