13
$\begingroup$

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.

$\endgroup$
8
  • $\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$ Commented Nov 9, 2020 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$ Commented Nov 9, 2020 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$ Commented Nov 9, 2020 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
    Commented Nov 9, 2020 at 9:17
  • 1
    $\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$ Commented Nov 9, 2020 at 9:42

1 Answer 1

3
$\begingroup$

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.$

$\endgroup$
1
  • 1
    $\begingroup$ Very nice! I'm glad to see this put to rest. $\endgroup$ Commented Jun 24, 2021 at 19:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .