# [FOM] finite choice question

Robert M. Solovay solovay at Math.Berkeley.EDU
Wed Nov 16 15:24:58 EST 2005

```The answer is YES. The obvious try [using induction on n] will work. If
one is uncomfortable reasoning in first order logic use the Godel
completeness theorem and models to finish off the inductive step.

--Bob Solovay

On Wed, 16 Nov 2005, Stephen Fenner wrote:

> This is a basic question about ZF set theory.
> It's not hard to see that the following is true:
>
> METATHEOREM: For any fixed natural number n, the sentence, "For any
> sequence <X1,...,Xn> of pairwise disjoint, nonempty sets, there is a set C
> such that (C intersect Xi) is a singleton for each i in {1,...,n}" is a
> theorem of ZF.
>
> But is the following a theorem of ZF?
>
> "For any natural number n and any sequence <X1,...,Xn> of pairwise
> disjoint, nonempty sets, there is a set C such that (C intersect Xi) is a
> singleton for each i in {1,...,n}."
>
> Note that, unlike other finite versions of AC, the cardinalities of the Xi
> are unrestricted.
>
> Steve Fenner
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
```