FOM: an "obvious" observation

Randall Holmes holmes at
Fri Jan 23 16:58:43 EST 1998

Has anyone on the list pointed out that the issue of such things as
"the intersection of e and pi" which McLarty has brought up a number
of times in the discussion of category-theoretical foundations is the
same as the issue of "respecting the interface of an abstract data
type" which arises in computer science?

I don't think that one needs to be an advocate of category-theoretic
foundations to be concerned with this issue.  Take any two
"definitions" of the natural numbers in terms of set theory.  If
mathematician A and mathematician B, who disagree on the best
definition of N (suppose that A likes bounded ZFC (Mac Lane set
theory) while B works in NFU + Infinity and favors the Frege
definition; here A and B have different foundational schemes as well
as different definitions) discuss theorems of arithmetic, they will
find that they agree perfectly and that they understand each other --
as long as they only talk about arithmetic.  They are talking about
the same abstraction via two different implementations.

A simpler example is the definition of the ordered pair.  One learns
the standard definition (x,y) = {{x},{x,y}} and then forgets it.  One
could spend a long time working with a mathematician who favors an
entirely different definition before discovering the fact (for
example, one's heretical colleague might favor Quine's definition,
which has the technical advantage that ranks of the cumulative
hierarchy with infinite index are closed under pairing).  The only
thing that matters about (x,y) for most purposes is that there are
maps p1 and p2 such that p1(x,y) = x and p2(x,y) = y for all x and y.

The question which then arises is "what are the real natural numbers?"
"what is the "true" ordered pair?".  The answer (which can sensibly be
maintained without adopting category theoretic foundations) is that
any implementation of the abstraction will do. Any structure which has
the properties we expect the natural numbers to have will serve.  Any
structure which has the properties we expect of the ordered pair will
serve.  From this standpoint, the great virtue of set theory is that
it is a simple system in which it is easy to implement a great many
abstractions.  The "intersection of e and pi" problem arises because
"intersection" is not a part of the interface of the abstraction "real
number"; it is an operation illicit in the context of real numbers.
In two different implementations of "real number" in set theory, the
"intersection of e and pi" may come out to be something quite
different.  Any theorems about the "intersection of e and pi" are not
results about real numbers, but results about some particular
implementation of real number in set theory (and so actually theorems
of set theory).

Recognizing the virtues of set theory as a foundation for mathematics
does not imply that one confuses implementations with the abstractions
they implement.  It is a good idea to set out to present implementations
of abstractions in terms of a common framework; one makes sure in this
way that a proposed abstraction is consistent (if one trusts one's ultimate

There is another activity which also belongs to the foundations of
mathematics.  This is the study of "abstractions" themselves; that is,
the study of kinds of structure.  Category theory might have a role
here, though I am more inclined to think that model theory is the
appropriate subject.  There seems to be an advantage to foundational
theories which admit quantification over proper classes here (as also
in providing set-theoretical foundations for category theory) since
one wants to be able to talk about arbitrary implementations of
abstractions (i.e., models of theories), including large ones.

There are further complications here:  mathematicians who use different
foundational systems can still communicate about shared abstractions
in many cases (as in my example above); one's own foundational system
(in which one attempts to implement all abstractions) is itself an
"abstraction" which someone else may attempt to implement in their own
favored foundational system; etc.

Comments are invited...

And God posted an angel with a flaming sword at | Sincerely, M. Randall Holmes
the gates of Cantor's paradise, that the       | Boise State U. (disavows all) 
slow-witted and the deliberately obtuse might | holmes at
not glimpse the wonders therein. |

More information about the FOM mailing list