[FOM] Foundations Crucial

[mernst at uci.edu]

It has come to my attention that what Harvey may be alluding to here is
some of my recent work on unlimited category theory.

Let me lay out the technical results as clearly and briefly as I can, then
add my own thoughts on their potential significance.

First, my particular result concerns the possibly of the category of all
reflexive graphs, RGRAPH (it can also be establish for GRAPH, the category
of all graphs, but that is not where I prefer to work).

In any presentation of the category of reflexive graphs (hereafter I will
write 'rgraph' in place of 'reflexive graph') ever given it has the
following properties:
1.  It is a topos.
2.  It satisfies the spanning tree principle, i.e., every connected rgraph
has a spanning tree subgraph.

The reason it has these properties is because they are all needed to
actually do graph theory using the category.  Without them the category
would be a pointless posit.


Let K_2 be the complete rgraph on 2 vertices.  Then working in RGRAPH we
can prove the following results:

A) For any rgraph A, there is no rgraph homomorphism from A to (K_2)^A
that is onto for vertices.

This is simply a special case of Lawvere's first result from "Diagonal
Arguments and Cartesian Closed Categories".


B) For any rgraph A and any complete rgraph B, B^A is complete.

There are a number of ways to prove this, but in general it follows
naturally from the definition of the exponential and of completeness.

C) For any rgraph A, for every vertex x of (K_2)^A, there is a graph Q_x
that is a subgraph of (K_2)^A such that Q_x neq Q_y for distinct vertices
x and y of (K_2)^A.

This requires more work.  One uses the completeness of (K_2)^A to build a
spanning subtree of it whose adjacency relation encodes a well-ordering.
Then Q_x  is a subgraph of that spanning tree up to and including the
vertex x.

All three of these results can be proven in RGRAPH using the normal language
of category theory.


In order to reach an inconsistency we have to reflect on the status of
RGRAPH in an unlimited context.  As a category, RGRAPH is itself an rgraph
and since RGRAPH is supposed to be the category of 'all' rgraphs, it is an
object within itself.

Then if we consider (K_2)^RGRAPH, theorem C gives us the correspondence we
need to construct a counterexample to theorem A.  That is, it allows us to
build an rgraph homorphism from RGRAPH to (K_2)^RGRAPH that is onto for
vertices.
This can be done in a number of ways, the simplest is that if we are going
to recognize within the category that RGRAPH is the category of all
reflexive graphs then we need an isomorphism from objects of the category
to homomorphisms from 1 to RGRAPH (i.e. the vertices of RGRAPH).

This gives us a counterexample to a theorem, so an inconsistency of the
system.

I have not discovered a straightforward way to extend this result to the
category of categories, or most other categories (there have been
suggestions about the category of well-orderings, but finding independent
characterizations of the properties the category of well-orderings must
possess has not been straightforward).

Thus ends the technical results, for anyone interested in further details
I can pass along the complete proofs, but withhold from doing so here as I
am in the process of streamlining them.


My thoughts about what this result means:

I think it shows the impossibility of finding a consistent foundation for
what Feferman calls unlimited category theory in "Foundations of Unlimited
Category Theory: What Remains To Be Done".  For those familiar with the
work, there is no consistent foundation that satisfies his (R1)-(R3).  No
foundation can admit the existence of the category of all rgraphs on the
one hand and also for that category to have the necessary strength to be
mathematically useful on the other.

There are two things I take from this fact.  Objections to a foundation
because it fails to deliver on such a category are misguided.  No
foundation can produce such a category.

Second, unlimited category theory cannot itself be a foundation for
mathematics.  While true, the significance of this second claim is
unclear.  As Colin has already mentioned in this thread, nobody has
advanced unlimited category theory as a candidate foundation (or, I would
add, at least it is not clear that anybody ever has).  For that reason,
the fact that it cannot be a foundation does not damage any foundations
people have actually advanced.

-Michael Ernst

mernst at uci.edu
Department of Logic and Philosophy of Science
University of California, Irvine