*This was [asked and bountied](https://math.stackexchange.com/questions/3885238/are-these-finite-ish-sets-closed-under-union) 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](https://math.stackexchange.com/q/3765978/28111), 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.



Is this notion of finiteness closed under unions?
No, that class doesn't need to be closed under unions. I’ll describe a permutation model with two $\Pi\_1^1$-pseudofinite sets whose disjoint union is not $\Pi\_1^1$-pseudofinite. You can use Jech-Sochor to get a ZF model.


Fix a finite field $K.$ Consider the class of tuples $M=(X^M,Y^M,e^M)$ such that $X^M$ and $Y^M$ are finite $K$-vector spaces, and $e^M$ is a bilinear map $X^M\times (K\oplus Y^M)\to K.$ This data can be encoded in a language $\mathcal L.$ I think any encoding would be slightly unwieldy so I’ll just call these 3-tuples $\mathcal L$-structures.


I claim this class satisfies the conditions of Fraïssé's theorem. There is an initial object “$0$” defined by $X^0=Y^0=\{0\}$ and $e^0(0,(\lambda,0))=0.$ So the joint embedding property will follow from amalgamation. For amalgamating $A\to B$ and $A\to C,$ by choosing a splitting $X^B\cong X^A\oplus X\_1$ etc we can assume $B$ is $(X^A\oplus X\_1,Y^A\oplus Y\_1,e^B)$ and $C$ is $(X^A\oplus X\_2,Y^A\oplus Y\_2,e^C),$ with the embedding maps being the direct sum inclusions. An amalgamation $D$ is defined by $X^D=X^A\oplus X\_1\oplus X\_2$ and $Y^D=Y^A\oplus Y\_1\oplus Y\_2,$ with the direct sum inclusions as embeddings from $B$ and $C,$ and
$$e^D((x\_0,x\_1,x\_2),(\lambda,(y\_0,y\_1,y\_2)))=e^B((x\_0,x\_1),(\lambda,(y\_0,y\_1)))+e^C((x\_0,x\_2),(\lambda,(y\_0,y\_2)))-e^A(x\_0,(\lambda,y\_0))$$


The Fraïssé limit of this class gives us a structure $L.$ I’ll drop the superscripts so $(X,Y,e)=(X^L,Y^L,e^L).$ The theory $T\_L$ of $L$ is $\omega$-categorical and, since Fraïssé limits are ultrahomogenous, $T\_L$ has quantifier elimination.


Let $N$ be the permutation model with atoms $X\cup Y,$ automorphism group the $\mathcal L$-automorphisms, with open subgroups $G\_{\bar{s}}$ for each $\bar{s}\in (X\cup Y)^{<\omega},$ consisting of the automorphisms fixing $\bar{s}.$ I’ll always argue externally, using ZFC.


A relation $R\subseteq X^n$ in $N$ is fixed by some $G\_\bar{s}.$ I claim that $R$ is definable in $L$ with parameters $\bar{s}.$ Because $T\_L$ is $\omega$-categorical, there is a partition of $X^n$ into sets $X\_1,\dots,X\_r,$ each defined by a formula with parameters $\bar{s},$ such that any two elements within the same part $X\_j$ have the same complete type over $\bar{s}.$ For any $x,y\in X\_j$ there is an automorphism $\pi\in G\_{\bar{s}}$ with $\pi x=y,$ and hence $x\in R \iff y\in R.$ By taking a conjunction, $R$ is definable with parameters $\bar{s}.$


By quantifier elimination, $R$ is definable by a quantifier free formula. This formula will be in the language $\mathcal L’$ of a $K$-vector space with constants for each $x\in X\_{\bar s}:=X\cap \operatorname{rng}(\bar s),$ and (suitably encoded) unary functions $e\_y(x)=e(x,y),$ for $y\in Y\_{\bar s}:=Y\cap \operatorname{rng}(\bar s).$ The true theory of $X$ in this language is the theory of an infinite vector space with a finite number of constants and certain linear functionals.


I will argue that this is a pseudofinite theory. For any $n,$ pick a finite set of vectors $x\in X$ attaining each realizable combination of values for $(e\_y(x))\_{y\in Y\_{\bar s}},$ and $n$ vectors in $X$ linearly independent from these choices and from $X\_{\bar s}.$ Call the span of these vectors $X’.$ Duplicator can win the $n$-round Ehrenfeucht–Fraïssé game played on $X$ and $X’$ in the language $\mathcal L’$; at each round the choice is either forced by a linear dependency, or we can pick a vector linearly independent from previous choices with the right combinations of $(e\_y(x))\_{y\in Y\_{\bar s}}.$


The above arguments show that $X$ is $\Pi\_1^1$-pseudofinite. A similar argument shows that $Y$ is $\Pi\_1^1$-pseudofinite.


In $N,$ the set $X\cup Y$ is not $\Pi\_1^1$-pseudofinite because $T\_L$ satisfies the non-degeneracy conditions
$$(\forall x\in X)(\exists y\in Y) f(x,(0,y))\neq 0\vee x=0$$
$$(\forall \lambda\in K)(\forall y\in Y)(\exists x\in X)f(x,(\lambda,y))\neq 0\vee (\lambda,y)=(0,0).$$
These force any $\mathcal L$-structure $M$ to satisfy $\dim Y^M\geq \dim X^M\geq 1+\dim Y^M.$


