FOM: finite sets

Stephen G Simpson simpson at math.psu.edu
Thu Apr 29 18:39:40 EDT 1999


Lawrence N. Stout writes:

 > Let me ask a foundational question: is there an axiomatization
 > which completely specifies the category of _finite_ sets?
 > Characterization of what finite means becomes quite complicated in
 > the absence of the axiom of infinity (so that finite cardinals are
 > not available for comparison) and in the absence of choice.  (This
 > was pointed out by Tarski in the 20's.)  

In the absence of the axiom of choice, the most useful of the various
inequivalent definitions of finite set is: a set that is equinumerous
with a von Neumann ordinal less than the first limit ordinal.  In the
absence of the axiom of infinity, change that to: not greater than or
equal to any limit ordinal.  This is a pretty specific notion of
finite set, and it allows you to derive the standard properties.

But maybe this does not ``completely specify'' the finite sets in the
sense you want, because any theory of finite sets is subject to the
G"odel incompleteness phenomenon.

 > Working in an intuitionist setting makes the matter even more
 > complicated (a paper by Troelstra gives several infinite families
 > of defintions of finite).

Yes, I can well believe that there are many intuitionistically
inequivalent definitions of finiteness that are classically equivalent
to the standard one.

This kind of intuitionistic explosion also happens for many other
basic mathematical concepts, not just finiteness.  For example, under
intuitionism, the Cauchy sequence definition of the real numbers is
not equivalent to the Dedekind cut definition of the real numbers.

-- Steve




More information about the FOM mailing list