[FOM] Can this problem be done in ZF?

[Arnold W. Miller]

On Sun, 27 May 2007, Rupert McCallum wrote:

> I was reading a textbook about first-order logic and it posed the
> problem: Given a first-order language L with equality whose only
> extralogical symbol is a binary predicate P, find a sentence S in L
> with the property that S is not satisfied in any finite model, but for
> any infinite set U, there exists a binary relation R on U such that the
> structure <U,R> is a model for S. I think the solution they had in mind
> was the sentence "P is a partial ordering with no maximal element."
> However, proving that this sentence has the required properties seems
> to require the countable axiom of choice. I was wondering if it could
> be proved that such a sentence exists in ZF alone.


Or R could be the graph of a one-one but not onto function. It needs
the axiom of choice.  For example, suppose U is an infinite set of
atoms and we take the usual Fraenkel-Mostowski permutation model
making U Dedekind finite: permutations G of U with finite support and
subgroups of G which fix finitely many elements of U.

Then for any binary relation R on U in the F-M model there will be a
finite subset F of U such that R is trivial off F:

(1) for all x in F either for all y in U\F (x,y) in R
                       or  for all y in U\F (x,y) notin R

(2) R is trivial on U\F, i.e.
    (a) either for all x in U\F  (x,x) in R
            or for all x in U\F  (x,x) notin R
    (b) either for all x,y in U\V distinct (x,y) in R
            or for all x,y in U\V distinct (x,y) notin R

This is true if F is the support of R, i.e., all permutations
of U which fix F, fix R .

It follows that for any first order sentence theta true in (U,R) there
will be a finite H subset of U such that theta is true in (H,R|H^2).

Same thing works in the standard symmetric submodel for getting a
Dedekind finite set consistent with ZF.

A. Miller