FOM: Categorical Foundations

Harvey Friedman friedman at
Sun Jan 18 12:06:59 EST 1998

Reply to a message from Mclarty, 10:59AM 1/18/98. The >> are from me.

Mclarty's answer is quite sketchy and cryptic, and so I must read between
the lines for an exact interpretation of what these analogs are that he is
proposing. For this purpose, I use Saunders MacLane and Ieke Moerdijk,
Sheaves in Geometry and Logic, A First Introduction to Topos Theory,
Universitext, Springer-Verlag, 1992. If Mclarty has something other than
what is in this book in mind when he answers me, then he is going to have
to tell us explicitly how he differs from the MacLane/Moerdijk treatment
and discussion.

>>Remember, you are talking to
>>elementary undergraduates who may eventually become statisticians,
>>physicists, business leaders, philosophers, lawyers, etcetera.
>	Absolutely. And so they will not raise objections based on
>any mismatch between what I say and what they expect from prior
>exposure to ZF.

But there is a mismatch between what you will attempt to get away with
saying, and almost all other courses in mathematics, and in fact most
courses in all of science and engineering. At least mismatch in the sense
that you will be using jargon that almost noone else knows or uses, and you
will not be using standard ideas that everybody else knows and uses -
except as modified by you in order to force it into your framework.

There will also be a gross mismatch between the clear intellectual
experiences of childhood - with the idea of a collection of 2 or 3 objects
which can be counted - and the large amount of abstract nonsense that you
need to promulgate.

A summary of the development that you need in order to conduct any kind of
thorough categorical f.o.m. through topos theory is left to the end of this

Before reading on, note that despite a disclaimer I made, I actually gave a
pretty thorough and complete treatment of the primitives, and the axioms
used in the set theoretic foundations of real analysis. Each has a
completely clear meaning on its own. And these axioms go a very very long
way, in that one has to go very very far into any kind of ordinary
undergraduate mathematics in order to run across a statement that cannot be
proved or refuted from these axioms. This is not the case for categorical
foundations. That's one reason why it is not legitimate foundations.

>>1. Sets are equal if and only if they have the same elements. Natural
>>numbers are not sets. Only sets have elements. Every object is either a set
>>or a natural number. Analog?
>	Subsets of a given set A are equal if and only if they have
>	the same elements. There is a set of natural numbers. Only
>	sets have elements. Every object is either a set or a function.
>	An element of a set A is a function 1-->A.

You have three primitive sorts: natural numbers, sets, and functions. You
also have to deal with 1 and arrows and the like. And is 1 also 0? And you
also need domains and codomains. You have a very complicated set of
primitives. This is already going to cause trouble, confusion,
difficulties,  and complications. In partcular, the last sentence above of
yours will strike these students as abstract nonsense. What is 1? What does
the arrows mean? I don't have this kind of trouble. I only worry about x
epsilon y. Remember the little children with their collections of 2 or 3
cards on the table?

>>2. The set N of all natural numbers exists. Analog?
>	There is a set of natural numbers--I included this above.

*A* set of natural numbers? or *the* set of natural numbers? Students
should want to know. By the way, how is this stated formally? I.e., are you
leaving out an axiom of extensionality? If so, this is very bad in that
your axioms don't pin down what you are talking about sufficienctly clear
to provide an honest foundation. If you include the axiom of
extensionality, then you are well on the road of slavishly copying
axiomatic set theory into a hopelessly bad notation.

>>3. The successor of any natural number is a natural number. Only natural
>>numbers have a successor. Analog?
>	There is a successor function from natural numbers to themselves.

>>4. 0 is a natural number which is not the successor of any natural number.
>	The same, verbatim

>>4. Any two natural numbers with the same successor are equal. Analog?
>	The same, verbatim

What kind of equality do you have? The same kind as in set theoretic
foundations? You have more of a problem than set theoretic foundations does
because you have more sorts. How do you state and prove such clear
trivialities as: there is exactly one function from any singleton into any
other singleton. What is a singleton? Or "there are exactly two subsets of
any singleton." What kind of equality is involved in such statements? Or is
this something that you cannot prove?

>>5. For any objects x,y,z: x = x. if x = y then y = x. if x = y and y = z
>>then x = z. Analog?
>	The same, verbatim

Again, putting what I said with slightly different emphasis. What is the
meaning of equality among functions? This has to be explained since
otherwise you leave open trivial questions about functions that are not
answered in your axiomatization, which is deadly for a genuine foundation.
I.e., if you leave this open, it is again even more apparent that you have
not made clear what you are talking about.

>>6. For any condition expressible with for all, there exists, and, or, not,
>>if then, iff, membership, being a natural number, 0, and successor, if it
>>holds of 0, and if whenever it holds at a natural number x, it holds of its
>>successor S(x), then it holds of all natural numbers. Analog?
>	The same, verbatim

How do you write this on the blackboard? Do you write, for all suitable
formulas phi, if phi(0) and if for all natural numbers x, phi(x) implies
phi(S(x)), then for all natural numbers x, phi(x)?

>>7. For any condition expressible as above, and for any set A, there is the
>>set of all elements of A that obey that condition. Analog?
>	For any condition expressible as above, and for any set A, there
>	is the subset of all elements of A that obey that condition.

How do you write this on the blackboard? Do you write, for all suitable
formulas phi, and all sets A, there exists a set B such that for all
objects x, x epsilon B if and only if x eipslon A and phi(x)?

By the way, you have more - and different - primitives than that, and so
this has to be change to account for them.

You have to explain what a subset of a set is, in addition to an element of
a set. This are troublesome, and look like abstract nonsense. In the book I
refer to, there is no index entry for subset, but there is for subobject.
Subset is more primitive than any concept of function. Compare what you
have to do involving subobjects, with the explanation of sets given in
axiomatic set theory!! Little children can take a set of cards on the
table, and throw zero or more away, and get subsets. Your notion of subset
- in terms of categorical subobjects - is arcane in comparison.

Or perhaps you want to use the following foundational monstrosity from p.
236 of the book:

"Thus an arrow x:X arrows A from any object X is called a generalized
element of A or an X-based element or an element defined over X. The use of
such generalized elements in a topos E supports the intention that working
in a topos is like working with sets."

I see that probably you can get away with a lot of what you are claiming to
get away with if you use such a concept of generalized element. But it is
foundationally incoherent. Remember those little children? They didn't
think that the elements of that 3 element collection of cards on the table
was a function!!

You cannot get away with this definition of membership. I won't let you.
And you didn't say you were going to use it, so by default, since you use
the word "verbatim" you aren't going to use it. But now what are you really
going to do?

>>8. For any set A, there is the set of all subsets of A. Analog?
>	The same, verbatim

Its not the same, verbatim, if you follow the treatment in the book of a
topos, p.161, we they use PB for any object B. (Here P means "power
object.") So are you going to say: For any set A, there is a set B such
that for all objects x, x epsilon A if and only if x epsilon B?

>>9. For any two objects x,y, there is the set consisting of exactly x and y,
>>written {x,y}. Analog?
>	The same verbatim

Do you say: for any two objects x,y, there exists a set A such that for all
objects z, z epsilon A if and only if z = x or z = y? Verbatim? This has a
completely clear evident meaning. In topos theory, its a theorem, right?
And not easy for undergraduates, right? What does the proof look like?

>>10. For any set x, there is the set consisting of the elements of the
>>elements of x. Analog?
>	The same, verbatim

Do you say: for any set x, there is a set A, such that for all objects y, y
epsilon A if and only if there exists z epsilon A such that y epsilon z?
>>11. The ordered pair <x,y> of two objects x,y, is {{x},{x,y}}. We prove
>>that <x,y> = <z,w> iff x = z & y = w. Analog?
>	No analogue, we have no use for it.

Well, you can only get away without something lik this because you are
taking functions as primitive. You pay a big cost.

>>12. We prove that the Cartesian product AxB of any two sets A,B, exists.
>	We stipulate that the Cartesian product AxB of any two sets
>	A,B exists.

What does *the* mean here? Remember my questions about the notion of
equality you are using. If you have several notions of equality, then you
have yet another bad problem.

>>13. We prove that there are unique functions on NxN into N obeying the
>>usual conditions for addition and multiplication and exponentiation. Analog?
>	The same, verbatim

*Unique?* What are your notions of equality?
>	All the rest are the same, verbatim.

Again, a gross oversimplification.

>>19. We define the concept of Dedekind cut in the concrete rationals and
>>prove basic facts about these cuts. Analog?

>>20. We prove the existence of the set of all Dedekind cuts in the concrete
>>rationals. We call these Dedekind cuts the concrete real numbers. We define
>>the basic ordering, and addition and multiplication on the set of all real
>>numbers. Analog?

On page 342 of the book, there is a treatment of Dedkind cuts and the reals
in an arbitrary topos with natural number object. The topos theoretic
definition of continuous function on (Dedekind) R is given. On page 329, it
is proved that there is such a topos in which all functions on R are
continuous. In particular, in such a topos, there is no function on R which
is 0 when x is a nonnegative real number, and 1 when x is a real number.
Step functions of this kind and more, and removeable discontinuities, are
part of undergraduate analysis.

>>21. We prove the basic equalities and inequalities involving the basic
>>ordering, and addition and multiplication on the set of all real numbers.
>>In particular, we prove the least upper bound principle. Analog?
>>22. We define the complete ordered fields. We prove that any two complete
>>ordered fields are uniquely isomorphic. Analog?
>>23. We define the (finite and infinite) sequences of real numbers as
>>functions from initial segments of N into R = the set of all real numbers.
>>We define Cauchy sequences, monotone sequences, bounded sequences, and
>>prove the fundamental facts such as Cauchy completeness and the existence
>>of limits of bounded infinite sequences. Analog?
>>24. We define the continuous functions from R to R. We prove the
>>intermediate value theorem. We prove the attainment of maxima and minima.

If my experience with intuitionistic analysis is right, you also can't do
the intermediate value theorem and the attainment of maxima and minima
either. And what about the least upper bound principle? This cannot be
done. Not even the least upper bound of a bounded monotone sequence of real
numbers. How about every infinite bounded set of real numbers has a limit
point? Can't do it either.

So you are going to have to add something like "the capital omega of the
topos is Boolean" fairly early in your courses. Plus maybe more. This will
be received as a bunch of abstract nonsense.

Remember, I put down all the axioms I need but you didn't put down all of
the axioms you need.

The more you sugar coat what you need, the more you slavishly translate set
theory into an inferior notation.

Now here is as promised a summary of the concepts that have to be developed
in order to make topos theoretic foundations of mathematics really work in
the way you intend. Note that these concepts are relatively arcane and
abstract for our undergraduates:

category, object, domain, codomain, arrows, functor, power object, 1, 1_C,
composition, Hom, natural isomorphism, pullback, commutative diagrams,
equalizers, right adjoint, left adjoint, natural transformations, diagonal
functor, carestian closed, limits, colimits, subobjects, truth values,
subobject classifier, small Hom-sets, representable, Heyting algebras, epi,
pushout, power object, finite limits, finite colimits, characteristic map,
monic, terminal object, dinatural, exponentials, evaluation map,
projections, direct image, adjoint functors, coequalizers, comparison
functor, split coequalizer, injective, etcetera.

QUESTION: The book cited above only considers a notion of topos that
corresponds in logical strength to that of Zermelo set theory with bounded
separation. What about the axiom scheme of replacement? What does that look
like in category theoretic terms?

More information about the FOM mailing list