All Questions
26 questions
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 "...
- 21.2k
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 ...
- 21.2k
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, ...
- 21.2k
12
votes
1
answer
394
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 ...
- 21.2k
11
votes
1
answer
655
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 ...
- 21.2k
9
votes
0
answers
528
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 ...
- 21.2k
8
votes
1
answer
392
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 ...
- 21.2k
8
votes
1
answer
396
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}...
- 21.2k
7
votes
2
answers
683
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 ...
- 21.2k
7
votes
1
answer
367
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 ...
- 21.2k
7
votes
1
answer
610
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 ...
- 21.2k
6
votes
1
answer
380
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}'\...
- 21.2k
6
votes
1
answer
242
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 ...
- 21.2k
6
votes
0
answers
251
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 $...
- 21.2k
6
votes
0
answers
189
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 ...
- 21.2k
6
votes
0
answers
249
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 ...
- 21.2k
5
votes
1
answer
597
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 ...
- 4,897
5
votes
1
answer
273
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 ...
- 21.2k
5
votes
1
answer
275
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,597
5
votes
1
answer
627
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$-...
- 21.2k
4
votes
1
answer
411
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 ...
- 21.2k
4
votes
1
answer
292
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),...
- 21.2k
4
votes
0
answers
151
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 $\...
- 21.2k
4
votes
0
answers
171
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 ...
- 21.2k
3
votes
0
answers
133
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{...
- 21.2k
2
votes
1
answer
226
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 ...
- 21.2k