This was asked and bountied at MSE without success.

Throughout, we work in $\mathsf{ZF}$.

Say that a set $X$ is $\Pi^1_1$-pseudofinite if for every first-order sentence $\varphi$, if $\varphi$ has a model with underlying set $X$ then $\varphi$ has a finite model. (See here, and the answer and comments, for background.) Every $\Pi^1_1$-pseudofinite set is Dedekind-finite basically trivially, and with some model theory we can show that every amorphous set is $\Pi^1_1$-pseudofinite. Beyond that, however, things are less clear.

In particular, I noticed that I can't seem to prove a very basic property of this notion:

Is the union of two $\Pi^1_1$-pseudofinite sets always $\Pi^1_1$-pseudofinite?

I'm probably missing something simple, but I don't see a good way to get a handle on this. A structure on $X=A\sqcup B$ might not "see" that partition at all, and so none of the simple tricks I can think of work.

  • $\begingroup$ It does not matter if $X$ sees the partition or not. (You could expand it with $A$ as a new predicate, if you really needed it, but you don’t.) As long as you are in a finite relational language, for any $n$, you can find finite $A'$ and $B'$ that are $n$-equivalent to the restrictions of the structure on $X$ to $A$ and $B$ respectively, and then $A'\sqcup B'$ is $n$-equivalent to $X$ by an Ehrenfeucht–Fraïssé argument. $\endgroup$ – Emil Jeřábek Nov 9 at 8:51
  • $\begingroup$ (I’m assuming that the $\sqcup$ notation refers to disjoint union. Of course, since $\Pi^1_1$-pseudofiniteness is stable under subsets, this is equivalent to the general case.) $\endgroup$ – Emil Jeřábek Nov 9 at 8:55
  • $\begingroup$ No, wait, this only works if the structure on $X$ is a disjoint union of its restrictions to $A$ and $B$, not if there are nontrivial relations between elements of $A$ and $B$. $\endgroup$ – Emil Jeřábek Nov 9 at 9:09
  • $\begingroup$ At least in the amorphous case it's fine. The union of two amorphous sets is amorphous or they ad a finite intersection. Does that help? $\endgroup$ – Asaf Karagila Nov 9 at 9:17
  • $\begingroup$ I think one might hope to prove that the finite union of amorphous sets is psuedo-finite, using the same model theoretic arguments that Noah mentioned. $\endgroup$ – Joel David Hamkins Nov 9 at 9:42

Your Answer

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

Browse other questions tagged or ask your own question.