Say that a set $X$ is $\Pi^1\_1$-pseudofinite if every first-order sentence $\varphi$ with a model with underlying set $X$ has a finite model. The existence of infinite $\Pi^1\_1$-pseudofinite sets is consistent with $\mathsf{ZF}$, since indeed [every amorphous set is $\Pi^1\_1$-pseudofinite](https://math.stackexchange.com/questions/3765978/the-complexity-of-finiteness).


Perhaps surprisingly, it is [not immediately clear](https://mathoverflow.net/questions/376011/is-this-notion-of-finiteness-closed-under-unions) whether the class of $\Pi^1\_1$-pseudofinite sets need be closed under finite unions. My question is what happens when we fix this weakness by brute force:



> 
> Is it consistent with $\mathsf{ZF}$ that there is an infinite *hereditarily* $\Pi^1\_1$-pseudofinite set - that is, an infinite set $X$ such that whenever $Y$ is $\Pi^1\_1$-pseudofinite, $X\cup Y$ is also $\Pi^1\_1$-pseudofinite?
> 
> 
> 


Note that the hereditarily $\Pi^1\_1$-pseudofinite sets *are* closed under finite unions, so this actually does "fix" the situation above. One natural hope is that amorphous sets do the trick again, but I don't see how - certainly the argument linked above doesn't suffice. (Of course there are finiteness notions stricter than amorphousness - e.g. "in any partition into infinitely many pieces, all but finitely many of those pieces are singletons" - but to my knowledge they're all significantly more finicky to work with, so it would be very nice if we didn't have to go there.)



Is the hereditary version of this weak finiteness notion nontrivial?
It is consistent that there are infinite hereditarily $\Pi\_1^1$-pseudofinite sets. I'll just say "pseudofinite" instead of "$\Pi\_1^1$-pseudofinite" for the rest of this post.



> 
> **Theorem 1.** Let $N$ be a model of ZF-Foundation satisfying "pseudofinite violations of choice for pseudofinite sets": there is a pseudofinite set $A$ such that for all **pseudofinite** $X,$ there is an ordinal $\alpha$ and a surjection $A^{<\omega}\times\alpha\to X.$
> 
> 
> In $N,$ the class of pseudofinite sets is closed under finite unions.
> 
> 
> 


The reason I've stated it like this is because not only does the hypothesis hold in permutation models where the set of atoms is pseudofinite but, if I've stated it correctly now, it should also hold in typical ZF embeddings of these permutation models. In particular these hypotheses hold in the basic Fraenkel model, with $A$ being the set of atoms, and in the ZF model you get by applying Jech-Sochor to the basic Fraenkel model.


The theorem will follow from two easy observations. (Proof is at the bottom.)


**Lemma 2.** If $X$ is pseudofinite, $n\in\omega,$ and $f:X^n\to Y$ is a function, then $f[X]$ is pseudofinite.


This is because $f$ defines an [interpretation](https://en.wikipedia.org/wiki/Interpretation_(model_theory)) of $f[X]$ in $X,$ and ZF lets us define the preimages of any relation on $Y.$


**Corollary 3.** If $X$ is pseudofinite then there is no surjection from $X$ to an infinite linearly ordered set.


Corollary 3 is what François G. Dorais' answer mentioned; Tarski's "II-finite". It follows from Lemma 2 with $n=1$ because if a linear order has an $n$'th element for each $n,$ then it contains a copy of $\omega,$ which is not pseudofinite. And if it doesn't have an $n$'th element, it satisfies the statement "has $\geq n$ elements but no $n$'th element" which also contradicts pseudofiniteness.


In terms of order properties, I think every pseudofinite set $X$ is "P-finite" in the terminology of [2]: every partial order on $X$ has a maximal element. This is the strongest notion of finiteness considered there for non-amorphous sets, and you know amorphous is strictly stronger than pseudofinite. But order properties might be a red herring. If you take a permutation model with a homogeneous vector space $V$ over $\mathbb F\_2$ with a generic symmetric bilinear form then $V$ won't be pseudofinite; finite models satisfy $(\exists z)(\forall y) B(y,y)=B(y,z),$ but $V$ won't. A concrete model is $V=\mathbb F\_2^{\oplus\omega}$ with $B(x,y)=\sum\_i x\_iy\_i.$ There doesn't seem to be any ordering involved as far as I can see. And if you instead take a symplectic bilinear form $B$ - so $B$ is non-degenerate and satisfies $B(v,v)=0$ - then I think $V$ will be pseudofinite. Specifically, Duplicator can win an $n$-step Ehrenfeucht–Fraïssé game for $V$ and a $2n$-dimensional symplectic space, by ensuring the chosen elements span isomorphic subspaces at each step.




---


### ZF models


Because of Corollary 3, the statement "if $x$ and $y$ are pseudofinite then so is $x\cup y$" is surjectively boundable and hence injectively boundable in the sense of [1]. So it transfers to ZF.


Ideally I'd want to rule out all models I can think of, not just Pincus'. Here is my sketchy understanding of how this should work for the Jech-Sodor embedding theorem. In these models, sets have a support of the form $(e,E)$ where $e$ is a set of indices for generic subsets of a regular cardinal $\kappa,$ and $E$ is a set of atoms of a permutation model. Not all permutation models have minimal supports, e.g. take an infinite homogenous vector space over $\mathbb F\_3.$ But there is always a minimal set of reals $e.$ That part is where the work is; the section in Jech's "Axiom of Choice" on the embedding theorems has very similar statements though I don't see anything directly quotable. This gives a map $s:X\to \mathcal P^{<\omega}(\kappa)$ taking each $x\in X$ to the minimal set $e$ such that there is a pair $(e,E)$ that is a support for $x.$ The formal statement would be $p\Vdash \dot{r}\in \dot{s}(\dot{x})$ if there is a name $\dot{z}$ fixed by symmetries of the symmetric extension that fix $(e,E),$ satisfying $p\Vdash \dot{z}=\dot{x},$ and $\dot{r}$ is the canonical name for the set indexed by an element of $e,$ and we can't get a smaller set $e$ by refining $p$ and choosing a different $\dot{z}.$ Since the image of $s$ is linearly ordered, it has to be finite when $X$ is pseudofinite. Finite sets can be absorbed into "$\alpha$" so the only parameters that matter are the atoms.




---


**Proof of Theorem 1.**


The following are equivalent for non-empty sets $X\in N$:


1. $X$ is pseudofinite
2. There is a surjection $A^{p\_1}\coprod \dots\coprod A^{p\_k}\to X$ for some $k,p\_1,\dots,p\_k\in\omega.$
3. There is a surjection $A^n\to X$ for some $n$.


**1⇒2**: By our small violations of choice axiom, there is a surjection $f:A^{<\omega}\times \alpha\to X.$ Define $g:X\to \omega\times \alpha$ by $g(x)=\min\{(|w|,\beta):g(w,\beta)=x\},$ using the ordinal product ordering. By Corollary 3, the image of $g$ is a finite set $I\subset\omega\times\alpha.$ After some reindexing, this is of the required form: the surjection is defined on $\coprod\_{i\in I} A^{i\_1}$ by sending $w\in A^{i\_1}$ (in the $i$'th component of the disjoint union) to $f(w,i\_2).$


**2⇒3**: set $n=2k+\max p\_i$ and encode the component index $1\leq i\leq k$ using the equality relation on the first $2k$ variables


**3⇒1**: This is Lemma 2.


The class of sets defined by condition 2 is obviously closed under finite unions, as required. $\square$




---


[1]: David Pincus, *Zermelo-Fraenkel Consistency Results by Fraenkel-Mostowski Methods*, The Journal of Symbolic Logic, Vol. 37, No. 4 (Dec., 1972), pp. 721-743


[2]: Omar De la Cruz, Damir D. Dzhafarov, and Eric J. Hall, *Definitions of finiteness based on order properties*, Fundamenta Mathematicae (2006), Volume: 189, Issue: 2, page 155-172. <https://eudml.org/doc/282771>


