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}'\preccurlyeq_\mathcal{L}\mathfrak{C}$, $\mathfrak{B}'\preccurlyeq_\mathcal{L}\mathfrak{C}$ with $\mathfrak{A}\cong\mathfrak{A}',\mathfrak{B}\cong\mathfrak{B}'$. It's a standard exercise to show that $\mathsf{FOL}$ is directed - or more generally, that every compact logic is directed. On the other hand, it's easy to whip up artificial logics demonstrating that this joint embeddability isn't equivalent to compactness.

I'm curious about the situation with second-order logic $\mathsf{SOL}$. It's consistent with $\mathsf{ZF}$ that there are $\mathsf{SOL}$-equivalent structures which do not $\mathsf{SOL}$-elementarily embed into the same structure (see below), but I don't see how to get this result outright in $\mathsf{ZFC}$ (much less $\mathsf{ZF}$). However, I recall seeing an easy argument (due to Mostowski?) that in fact this is a $\mathsf{ZF}$-theorem.

Question: Does $\mathsf{ZF}$ prove that $\mathsf{SOL}$ is not directed?

Here's a proof that the non-directedness of $\mathsf{SOL}$ is consistent with $\mathsf{ZF}$. Suppose there is a family $\mathbb{A}$ of amorphous sets of pairwise incomparable cardinality such that there is no injection from $\mathbb{A}$ into $2^{\aleph_0}$. Thinking of each element of $\mathbb{A}$ as a structure in the empty language, we must have $X,Y\in\mathbb{A}$ with $X\equiv_\mathsf{SOL}Y$ but $X\not\cong Y$. But any set into which both $X$ and $Y$ inject must be non-amorphous, hence cannot satisfy $Th_\mathsf{SOL}(X)=Th_\mathsf{SOL}(Y)$ since amorphousness is second-order-expressible.

Of course this doesn't help at all without a background assumption of lots of amorphous sets, so it's not really relevant to the question I'm asking here, but it's still neat. Note that a positive answer will have to crucially involve uncountable structures, since it's consistent with $\mathsf{ZFC}$ that $\equiv_{\mathsf{SOL}}$ implies $\cong$ for countable structures.

  • 3
    $\begingroup$ Non-directedness of SOL is also consistent with ZFC. Assume ZFC + "there is no strong cardinal". Then a pressing-down argument gives $\lambda$ such that no $\alpha < \lambda$ is $\lambda$-strong. By pigeonhole, there are two structures $A = (V_\lambda; \in, \alpha)$ and $B = (V_\lambda; \in, \beta)$ with the same second-order theory (vocabulary contains $\in$ and a constant symbol.) Given C with the same second-order theory, we may assume wlog $C = (V_\mu; \in, \gamma)$. But A and B can't both elementarily embed into C; one embedding would be non-identity, witnessing $\lambda$-strongness. $\endgroup$ Aug 13 at 22:19
  • 1
    $\begingroup$ @TrevorWilson Ah, nice, I didn't see that. Surely this is an outright $\mathsf{ZF}$-theorem, though, or at least a $\mathsf{ZFC}$-theorem ... right? $\endgroup$ Aug 13 at 22:22
  • 1
    $\begingroup$ Maybe; I haven't thought about it enough to say. I don't have any good reason to think strong cardinals are actually relevant; that was just the first thing that occurred to me. $\endgroup$ Aug 13 at 22:27

The answer to the question is yes.

Let $\alpha_0<\alpha_1$ be the least ordinals (in the reverse lex order, say) such that $V_{\alpha_0}$ and $V_{\alpha_1}$ have the same second order theory $T$. Assume towards a contradiction that $V_{\alpha_0}$ and $V_{\alpha_1}$ are elementarily embeddable into a common structure $M$, which we may assume is transitive. Note that the embeddings fix $T$. Since $V_{\alpha_1}$ satisfies that there is an ordinal $\beta$ such that $V_\beta$ satisfies $T$, so does $M$, and hence so does $V_{\alpha_0}$. But this means that some $\beta < \alpha_0$ has the same theory as $V_{\alpha_0}$, contrary to the minimality of the pair $\alpha_0 < \alpha_1$. (Edit: I now see this is very close to what Trevor was doing.)

  • $\begingroup$ Ah, yes, I missed that - thanks! $\endgroup$ Aug 14 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.