# [FOM] finite choice question

A.P. Hazen a.hazen at philosophy.unimelb.edu.au
Wed Nov 16 23:14:20 EST 2005

```Stephen Fenner writes:
>This is a basic question about ZF set theory.

...

>  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}."
Yes.  Lead quantifier is over natural numbers, so use mathematical
induction (derivable in ZF).  Base case (every "sequence" of zero or
one non-empty set(s)has an appropriate C)  trivial.  For induction,
assume there is a C for every sequence, <x1,...,xn>, of n pairwise
disjoint non-empty sets, and consider a sequence of n+1 such sets,
<x1,...,xn,xn+1>.  By hypothesis of induction there is a choice-set C
for the subsequence consisting of the first n sets.  So CU{y} for any
y belonging to xn+1 will be a choice set for the whole sequence.
Key thing, in making the proof possible, is that the finitude
(inductiveness: having a natural number as cardinal) of the  sequence
is explicitly STATED as part of the antecedent of the theorem.
((Something I don't know: In ZF without choice, can you prove the
existence of a choice set for a Dedekind-finite [but in the absence
of Choice not necessarily  inductive!] family of disjoint non-empty
sets?  My guess would be NO, but i don't think I am a very good
guesser.))
--
Allen Hazen
Philosophy Department
University of Melbourne
```

More information about the FOM mailing list