For $\Gamma$ a set of second-order sentences in the empty language, say that a set $X$ is **$\Gamma$-pseudofinite** if $X$ is infinite but for every sentence $\varphi\in\Gamma$ which is satisfied in every finite pure set we have $X\models\varphi$. For example, $\mathsf{ZF}$ proves that the sentence "I can be linearly ordered, and every linear ordering of me is discrete" is true of exactly the finite sets, and so $\Sigma^1\_1\wedge\Pi^1\_1$-pseudofinite sets do not exist; in the other direction, $\mathsf{ZF}$ proves that $\omega$ is $\Sigma^1\_1$-pseudofinite.


The interesting case is $\Pi^1\_1$. While $\mathsf{ZFC}$ proves that there are no $\Pi^1\_1$-pseudofinite sets (consider "Every linear ordering of me is discrete"), [James Hanson showed in $\mathsf{ZF}$](https://math.stackexchange.com/a/3767073/28111) that amorphous sets are $\Pi^1\_1$-pseudofinite. My question is whether amorphousness is more-or-less the only way we get $\Pi^1\_1$-pseudofinite sets:



> 
> Over $\mathsf{ZF}$, does "There are no amorphous sets" imply "There are no $\Pi^1\_1$-pseudofinite sets?"
> 
> 
> 


Note that this is a bit weaker than asking whether every $\Pi^1\_1$-pseudofinite set is amorphous. FWIW I think the answer to *that* question is negative (I suspect e.g. that the union of two $\Pi^1\_1$-pseudofinite sets is $\Pi^1\_1$-pseudofinite).



The strength of "There are no $\Pi^1_1$-pseudofinite sets"
My "hunch" in the comments to the question appears to be correct! This model comes from *Howard, Paul E.; Yorke, Mary F.*, [**Definitions of finite**](http://dx.doi.org/10.4064/fm-133-3-169-177), Fundam. Math. 133, No. 3, 169-177 (1989). [ZBL0704.03033](https://zbmath.org/?q=an:0704.03033). The paper has a few confusing typos and, in particular, the proof of Theorem~15 appears insufficient, so I'm sketching the argument in some detail, with another proof of that theorem.




---


$\newcommand{\supp}{\operatorname{supp}\nolimits}
\newcommand{\fix}{\operatorname{fix}\nolimits}$Fix a ground model $\mathfrak{M}$ of ZFA+AC where the set $U$ of atoms is countably infinite and fix a dense linear ordering ${<}$ of $U$ without endpoints.
Let $\mathcal{P}$ be the lattice of finite interval partitions of $U$, i.e., patitions of $U$ into finitely many blocks where each block is an interval of any shape.
This is a lattice under refinement $P \leq Q$ iff every block of $P$ is contained in a block of $Q$.
The meet $P \sqcap Q$ consists of all nonempty intersections of a block from $P$ and a block from $Q$.
The join $P \sqcup Q$ is more complicated: the blocks of $P \sqcup Q$ are maximal unions of the form $B\_1\cup B\_2 \cup \cdots \cup B\_k$ where $B\_1,B\_2,\ldots,B\_k \in P \cup Q$ and $B\_1 \cap B\_2, B\_2 \cap B\_3, \ldots, B\_{k-1} \cap B\_k$ are all nonempty.
Given an interval partition $P$, we write ${\sim\_P}$ for the associated equivalence relation: $x \sim\_P y$ iff $x$ and $y$ belong to the same block of $P$.


Let $G$ be the group of permutations $\pi$ of $U$ with finite support $\supp\pi = \{ x \in U : \pi(x) \neq x \}$.
Given an interval partition $P$ of $U$, let $$G\_P = \{ \pi \in G : (\forall B \in P)(\pi(B) = B) \}.$$
Note the following facts:


1. $G\_{P \sqcap Q} = G\_P \cap G\_Q$.
2. If $\{x\}$ is a block of $P$ for each $x \in \supp\pi$ then $\pi G\_P\pi^{-1} = G\_P$.
3. $G\_{P \sqcup Q}$ is the subgroup generated by $G\_P \cup G\_Q$.


It follows that these subgroups generate a normal filter $\mathcal{F}$ of subgroups of $G$.
Let $\mathfrak{N}$ be the symmetric submodel associated to $\mathcal{F}$:
$$\mathfrak{N} = \{ X \in \mathfrak{M} : \fix(X) \in \mathcal{F} \land X \subseteq \mathfrak{N} \}.$$
Note that by 3, for every $X \in \mathfrak{N}$ there is a coarsest interval partition $\supp(X)$ such that $G\_P \subseteq \fix(X)$, namely $$\supp(X) = \bigsqcup \{ P : G\_P \subseteq \operatorname{fix}(X) \}.$$


**Lemma.** For any set $X$ in $\mathfrak{N}$, if $\pi \in \fix(X)$ then for every $x\_0 \in U$, $\pi(x\_0)$ is not in a block of $\supp(X)$ which is adjacent to that of $x\_0$.


*Proof.* Suppose, for the sake of contradiction, that $A,B$ are adjacent blocks of $\supp(X)$ and $x\_0 \in A$, $\pi(x\_0) \in B$ for some $x\_0$.
We will show that for any $a \in A$ and $b \in B$ the transposition $(a,b)$ fixes $X$. Note that at least one of $A$ or $B$ must be infinite. Let's assume that $B$ is infinite, the other case is symmetric.


1. Suppose $a = x\_0$ and $b \notin \supp\pi$.
Then $(a,b) = (x\_0,b) = \pi^{-1}(\pi(x\_0),b)\pi$.
2. Suppose $a = x\_0$ and $b \in \supp\pi$.
Then pick $b' \in B \setminus \supp\pi$ and note that $(a,b) = (a,b')(b,b')(a,b')$.
3. Suppose $a \neq x\_0$.
Then $(a,b) = (a,x\_0)(x\_0,b)(a,x\_0)$


It follows that any permutation of $A \cup B$ fixes $X$, which contradicts the fact that $\supp(X)$ is the coarsest partition such that $G\_{\supp(X)} \subseteq \fix(X)$.


**Claim 1 (Howard & Yorke, Theorem 15).** $\mathfrak{N}$ contains no amorphous sets.


*Proof.* Suppose $X \in \mathfrak{N}$ is infinite. If $G\_{\supp(X)}$ fixes $X$ pointwise, then $X$ is wellorderable and therefore not amorphous.
Pick $x\_0 \in X$ such that $P\_0 = \supp(x\_0)\sqcap\supp(X)$ properly refines $\supp(X)$.
Let $A,B$ be two adjacent blocks of $P\_0$ which belong to the same block of $\supp(X)$.
Suppose $A$ has a right endpoint $a$; the case where $B$ has a left endpoint is symmetric.


Let $P\_1$ be obtained from $P\_0$ by replacing $A$ with $A\setminus\{a\}$ and $B$ with $B\cup\{a\}$.
Note that for $\phi,\psi \in G\_{P\_1}$, $\phi(x\_0) = \psi(x\_0) \iff \phi(a) = \psi(a)$.
Fix $b \in B$ such that $B\cap(-\infty,b)$ and $B\cap[b,+\infty)$ are both infinite.
Let
$$X\_0 = \{ \pi(x\_0) : \pi \in G\_{P\_1}, \pi(a) < b \}$$
and
$$X\_1 = \{ \pi(x\_0) : \pi \in G\_{P\_1}, \pi(a) \geq b \}.$$
These are two disjoint infinite subsets of $X$.
Moreover, $X\_1, X\_2 \in \mathfrak{N}$ since they are both fixed by $G\_Q$ where $Q$ is a refinement of $P\_0, P\_1$, and $\{(-\infty,b),[b,+\infty)\}$.
Therefore $X$ is not amorphous.


**Claim 2.** $U$ is $\Pi^1\_1$-pseudofinite in $\mathfrak{N}$.


*Sketch.*
Suppose, for the sake of contradiction, that $$(\forall Y \subseteq X^n, Z \subseteq X^m,\ldots )\phi(X,Y,Z,\ldots)$$ is a $\Pi^1\_1$ statement which is true of every finite set $X$ but false for $X = U$.
Let $Y \subseteq U^n, Z \subseteq U^m,\ldots$ be sets in $\mathfrak{N}$ such that $\lnot\phi(U,Y,Z,\ldots)$.
Let $P = \supp(Y)\sqcap\supp(Z)\sqcap\cdots$


Note that there are only finitely many possibilities for $Y, Z, \ldots$
For example, when $n=1$ then $Y$ must be a union of some of the intervals from $P$.
When $n=2$, $Y$ must be a boolean combination of cartesian products of two intervals from $P$ and the diagonal set $\{(x,x) : x \in U\}$. And so on...


By an EF-style argument, if $V \subseteq U$ is a finite set such that that contains all the endpoints of intervals from $P$ each of the sets $P \cap B$ is sufficiently large when $B$ is an infinite interval from $P$, then $\phi(U,Y,Z,\ldots)$ is equivalent to $\phi(V, Y \cap V^n, Z \cap V^m,\ldots)$. It follows that $\lnot\phi(V, Y \cap V^n, Z \cap V^m, \ldots)$ for some finite set $V \subseteq U$, but this contradicts the assumption.




---


Since the ultimate goal is to obtain a more concrete understanding of what $\Pi^1\_1$-pseudofinite means, I will propose an alternate conjecture.


Recall Tarski's notion of II-finite: *every chain of subsets of $X$ has a maximal element*. This is equivalent to the $\Pi^1\_1$ statement: *every total preordering of $X$ has a maximal element*. So every $\Pi^1\_1$-pseudofinite set is II-finite. It seems that the converse might be true but I will only propose the following:


**Conjecture.** There is no infinite $\Pi^1\_1$-pseudofinite set if and only if there is no infinite II-finite set.


