[FOM] Can this problem be done in ZF?

Rupert McCallum rupertmccallum at yahoo.com
Sun May 27 07:05:22 EDT 2007

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.

____________________________________________________________________________________Pinpoint customers who are looking for what you sell. 

More information about the FOM mailing list