FOM: D-finite choice

Kanovei kanovei at wminf2.math.uni-wuppertal.de
Sun Mar 1 14:03:49 EST 1998

<Date: Sun, 1 Mar 1998 13:12:01 -0500 (EST)
<From: Stephen G Simpson <simpson at math.psu.edu>

<The choice principle for all finite sequences of nonempty sets
<is well known and easily seen to be a single theorem of ZF (or of Z
<for that matter).
<
<[ Here I assume that "finite" means "indexed by a finite ordinal
<number".  Pratt's remark and mine probably both fail if you take
<"finite" in some other sense, e.g. perhaps what the set theorists
<sometimes call D-finite.  Are there any experts here who can confirm
<this?  A set is said to be D-finite if it is not in 1-1 correspondence
<with any proper subset of itself.

The choice for D-finite (alias: Dedekind-finite) sets
fails in the Cohen original model for \neg-AC where
an infinite D-finite set X of reals exists.

For take, for any r\in X, X_r to be the set of all x\in X
strictly smaller than r. A choice function for the family of
sets X_r immediately leads to an \omega-sequence of 2wise
different elements of X, a contradiction with the D-finiteness.