[FOM] Founding math on points and lines [was: Irrational numbers]

[Vaughan Pratt]

(While writing the following I ran across a 1997 FOM posting of mine,

    http://www.cs.nyu.edu/pipermail/fom/1997-October/000097.html

that may provide helpful background for the viewpoint taken below.)

>From: "Dean Buckner" <Dean.Buckner at btopenworld.com>
>Imagine we are given ALL the irrational numbers EXCEPT pi.  How exactly
>would this fact manifest itself?

The continuum would then have two connected components.  (From context it
sounds like you intended to include the rationals.)

>And what would change if pi were added?

The number of connected components would decrease by a factor of two.

>So how is pi actually necessary?
>Doesn't that prove that pi is not "the extension of an infinite decimal
>fraction", that it's just a rule or algorithm of some sort?

Pi allows you to divide the circumference of a circle by its diameter in a
single step to produce a single real number.  Your scenario seems to entail
finding ever better approximations to that ratio.  That might be how one
would go about determining the ratio empirically, but if all irrational
quantities had to be determined empirically, mathematics involving the
continuum would grind to a halt.

It is misleading to understand the continuum as "just" a collection of points.
That omitting just one point out of uncountably many doubles the number of its
connected components should constitute a pretty convincing argument for this!

>"Mathematics is ridden through and through with the pernicious idioms of set
>theory.  *One* example of this is the way people speak of the line as
>composed of points.  A line is a law and isn't composed of anything at all".
>(Wittgenstein, Remarks, XV § 173)

Replacing one dogma (line as composed of points) with another (line as a
law) makes mathematics into a conceptual battleground.  Both viewpoints are
eminently defensible.  "A line is not a square" is perfectly reasonable,
but "a line is not a set of points" is a glove thrown down.  The versatile
mathematician should be able to describe a line from various perspectives.

One insight into the line (i.e. the continuum understood as an open interval)
is that it is homeomorphic to an ordered pair of lines (each itself open
and moreover homeomorphic to the whole) together with a point in between.
This is dual to understanding a finite closed interval as an ordered pair
of points together with a finite open interval in between.  Only the former
provides a suitable basis for an inductive construction of the continuum.
(More precisely, coinductive, as one would expect given the inside-out nature
of the construction and the uncountability of the resulting fixpoint when
understood set theoretically.)

I'd been planning to write about the foundational aspects of universal
algebra, since I'd been getting the impression from Harvey Friedman's
response to my recent posting on "Scope of FOM", and the lack of any other
substantive responses, that FOM is no closer to being interested in such
topics as universal coalgebra than it was three years ago, or for that matter
in 1997 when coalgebras were just starting to warm up in computer science.

But however accessible universal algebra might be relative to universal
coalgebra, the points and lines of Euclidean geometry are surely far more
accessible yet!

Now it is true that today the plane no longer rules geometry.  Air and space
travel have made three-dimensional sophisticates of us, Minkowski space
has stretched us to four dimensions, the matrix approach to statistics,
stress analysis, and many other areas should by now have dispelled whatever
doubts any practicing scientist or engineer might have had as to whether
five dimensions and beyond have any real-world significance, and quantum
mechanics has forced us to understand infinite-dimensional Hilbert space.

Yet the geometry of the plane has been a staple of mathematics for millennia,
and moreover a subject that one can make a start on even in elementary school.
As such it is an ideal starting point for a bottom-up approach to grappling
with foundational issues.

The two fundamental constituents of the plane are its points and its lines.
Absent any higher dimensions, these constituents are equally fundamental:
the point only acquires founding seniority when there are arbitrarily many
dimensions, much as 0 is more fundamental than 1 as an ordinal but not as
an element of the two-element Boolean algebra.

The points and lines of the plane are in fact dual: one can coordinatize the
plane in terms of either.  This duality is both geometric and algebraic.
It is geometric in that two lines determine a point just as two points
determine a line.  (The coordinate "axes" of the plane may be two lines,
as in cartesian geometry, or two points, as in the dual coordinatization.)
And it is algebraic in that R^2 as a two-dimensional vector space whose
maps are linear transformations is self-dual, via the representation of
dual points as functionals, i.e. linear transformations from R^2 to R.

A reminiscent, if not entirely analogous, duality can be demonstrated between
set theory and category theory when viewed as respectively point-based
and line-based.

The objects of set theory (namely sets) are *constituted from* points.
Now on closer inspection an element of a set may turn out to be itself a
set constituted from points, and so is not a point in the sense of being
an atomic dot.  Pointhood in this sense is therefore not an internal or
intrinsic property of the elements of a set.

When it comes to viewing elements as points, pointhood (or perhaps it should
be called elementhood) is outside the point, not inside.  The space between
the elements of a set can be understood as a vacuum.  Contrast this with the
points of the continuum standardly topologized, where the points are packed
solidly.  If you speak of the continuum as just a set, then topologically
speaking you have assigned it the discrete topology and its points no longer
form a continuum, they have become totally disconnected from one another,
like stars separated by the vacuum of outer space.  Certainly there are a lot
of reals, but mere number does not serve to connect them, connection requires
topology when what is being connected is comprised of dimensionless points.

The objects of category theory are *connected by* lines.  Linehood is
internal to the line.  A morphism from A to B connects A to B by a line
independently of any internal structure of that line.  That is, if we can
decompose a line as the concatenation of two lines, that does not make
the whole line any less of a line.  A trip via lines from A to B however
convoluted encounters no vacuum.

These lines are not comprised of points but stand alone conceptually in their
own right.  As such they do not depend on topology to maintain connectedness,
instead connection is what a line between two points accomplishes.

Which makes the better foundation, set theory or category theory?  Confronted
with that question, one could ask for upper bounds on how much better either
could be than the other.  In particular, what is entailed in a simulation
of one by the other?

The passage from points to lines in set theory is traditionally accomplished
via what one might call the von Neumann "tunnel."  The primordial line is
the ordered pair (a,b).  This is constructed by first collecting a and b
symmetrically as the set {a,b}, then breaking this symmetry by collecting
a again, this time on its own as the singleton {a}, and lastly collecting
these two sets as the two-level set {{a,b},{a}} representing the pair (a,b).
>From this primordial line one can then proceed to many other notions of
line via well-travelled passages familiar to the FOM subscribership.

So how to get from lines to points in category theory?  Objects are points in
the sense of being atomic dots, but as noted above we are really looking for
the dual characteristic of points, that they form an unstructured set.  In any
event, however pointlike an object of a category might appear abstractly, its
primary purpose is to abstract some object having both carrier and structure;
objects of categories are not intended to play the role of element (though
they do so in a discrete category, one all of whose morphisms are identities).

The litmus test for absence of structure from an object A is that every
possible rule f:A->B for assigning points f(a) of B to points a of A preserves
the structure of A, regardless of the structure of B.  So how to construct
unstructured sets?

One approach is via the external homfunctor.  The idea that the totality of
morphisms g:A->B might form a set is intuitively clear, and its extension
to a functor Hom(f,h), f:A'->A, h:B->B', defined by Hom(f,h) = \g.hgf
(\ = lambda, g:A->B) as a function mapping Hom(A,B) to Hom(A',B') can be
readily explained by reference to the diagram

            f     {g}     h
	A' ---> A ===> B ---> B'

Furthermore the external homfunctor can in turn be used to develop a notion
of element of an object in terms of the notion of a generator.  An object
G is called a *generator* when for any two distinct maps f,g:A->B there
exists a map a:G->A such that fa and ga are distinct.  (This can be put more
succinctly as "Hom(G,-) is faithful".)  The idea is that the maps a:G->A
constitute "the elements" of A, and the condition says that if f and g are
distinct then it must be because they disagree at some element.  In any
of the categories of sets, posets, topological spaces, directed graphs,
or small categories, the singleton {0} can serve as G; in other categories
something else may be needed, e.g. in the category of abelian groups the
one-element group is not a generator, but the group Z of integers is.

The downside of this homset approach is that it begs the question in the
beginning of what is a set.  One might respond by saying that a set is
whatever can arise as the totality of morphisms between two objects of some
category, but this tells us essentially nothing about the nature of sets.
In contrast the von Neumann construction of (a,b) tells us a lot about
lines, starting with their concatenability.  (Whether it is a natural way
of synthesizing lines from points is another question.)

In the 1960s as a graduate student Bill Lawvere set about axiomatizing
the category of sets and functions.  A decade later mission creep had
led to the beautiful notion of elementary topos as an abstraction of
Grothendieck toposes.  The category of sets remained the prototypical
topos, but many other categories were now admitted.  Objects of a topos
could have both elements and subobjects in such a way that reasoning about
them *constructively* as though these were the elements and subsets of sets
yielded valid conclusions even when they were something else such as graphs
or simplicial sets or cubical sets (but not posets or categories or rings
or vector spaces or Boolean algebras or manifolds or ...).

Directed graphs provide the standard example of a topos materially different
from Set.  The notion of element of a graph is rather boring: just the
vertices of the graph.  What is more interesting is that one can reason about
subgraphs exactly analogously to how one reasons about subsets, provided
the reasoning adheres to certain standards of constructivity.  The graph
playing the role of the doubleton set {0,1} in defining "characteristic
function" of a subgraph has two vertices as one might expect, but five edges!

One very useful class of toposes is that of the presheaf toposes, having
the form Set^C where C is any small category.  The topos of directed graphs
is obtained with such a C having two objects called V and E (for vertices
and edges) and two morphisms s,t:E->V for source and target.  The topos
of simplicial sets is obtained for C the category of finite ordinals and
their monotone functions, while that of cubical sets is obtained by taking
C to be the category of finite bipointed sets.  Familiarity with these
basic examples makes it easy to construct one's own presheaf toposes for
various applications.  Not all interesting toposes are presheaf toposes
however, e.g. Martin Hyland's effective topos, the computability corner of
the topos world.

I personally am not enamored of toposes for one of the (many?) reasons that
Stephen Simpson was objecting to them back when Colin McLarty was defending
them several years ago.  One of Stephen's concerns was that toposes mimicked
the category Set too slavishly.

Now the examples of graphs, complexes of various flavors, etc. show that
this criticism is not entirely fair: a considerably broader class of objects
than just sets can be understood as having set-like behavior.  Moreover the
fact that "topos" is an elementary (i.e. first-order) notion (morphisms
being the elements in question) has a strong appeal.  (Abelian categories,
for which the category Ab of abelian groups plays an analogous role to Set
for toposes, turn out to be similarly elegant, the essential difference
from toposes being that the identity 0=1 holds in abelian categories,
where 0 and 1 are the initial and final objects respectively.  In a topos,
0=1 spells inconsistency and the topos collapses to a point.)

My specific complaint here is that toposes, whether or not accompanied by
abelian categories, presuppose a two-stage assault on foundations in which
one first establishes a logical framework and then proceeds to do mathematics
in that framework, along the lines of the set-theoretic foundations but
tempered by a respect for constructive reasoning while benefiting from the
wider variety of set-like objects.

That this is necessarily two stages follows from the non-topos character of
a great many useful objects: posets, groups, rings, (semi)lattices, small
categories, manifolds, etc.

The appeal of pure category theory, not mediated by toposes, is direct access
to a much greater variety of mathematical objects without having to fit
one's mathematics to the Procrustean bed of constructive intuitionistic logic.

Unfortunately this untrammeled-category picture is morphism-centric, with
the essential structure of the category residing in the composition law.
This is not calculated to give immediate insight into the nature of the
objects of a given category.

Now this criticism is not entirely fair either.  Category theorists work at
higher levels than just the raw categories, making effective use of functors
and natural transformations.  At these levels one obtains a clearer picture
of varieties, homological algebra, and so on.  Category theory is more
effective when permitted to operate at higher dimensions than the point
and the line, starting with the logic of natural transformations which is
intrinsically two-dimensional.

But this capability comes at the price of having to master these tools,
which can take chapters to explain.  Adjunctions, without which category
theory would be a dead subject, are not encountered until Chapter 4 of
Mac Lane's definitive textbook "Categories for the Working Mathematician."

I believe that a less morphism-centric and more object-centric approach
to category theory can bridge the large gap between sets and categories.
(I put universal algebra on the set theory side here.)

The approach I favor can be arrived at starting from either sets
or categories.

The approach via sets depends on the insight that universal topology is
strictly more comprehensive mathematically than universal algebra.  Just as
universal algebra generalizes group theory to other kinds of algebras
without changing the notion of homomorphism, so does universal topology
generalize the axioms of ordinary topological spaces with changing the
notion of continuous function.  The axioms to be dropped are: (i) the closure
requirements on the open sets of a topological space; (ii) the restriction
to only two degrees of membership in an open set - we now allow k degrees
of membership where k is some fixed cardinal; and (iii) extensionality of
open sets - we now allow the open sets to be collected as a multiset.

The approach via categories is dual: instead of relaxing conditions
we impose them.  Starting from the standard axioms of category theory
(associativity of composition and the unit equations), we assume in addition
(i) a rigid bigenerator (G,K); (ii) a fixed cardinality k for Hom(G,K);
and (iii) maximality of the ambient category subject to (i) and (ii).

(An object A is *rigid* when Hom(A,A) is a singleton; a pair of objects is
rigid when both objects are rigid.  A pair (G,K) is a *bigenerator* when
Hom(G,-) and Hom(-,K) are jointly faithful, i.e. given any f,g:A->B, if
for all a:G->A we have fa=ga, *and* for all p:B->K we have pf=pg, then f=g.
Maximality of C is up to categorical equivalence: formally, any extension
of C must be equivalent to C; informally, new objects can be added to C but
must turn out to be isomorphic to existing objects, while any new morphism
f:A->B that one attempts to add to Hom(A,B) must turn out to be equal to
a morphism already present in Hom(A,B).)

The very nice theorem is that these two approaches -- generalized topology
and restricted categories -- define the same category, namely Chu(Set,k),
whose objects can be understood as matrices and whose morphisms as continuous
functions.  The related category chu(Set,k) of biextensional chu spaces is
obtained by suitable axioms restoring extensionality for both open sets (=
predicates) and points.

The fact that Chu(Set,k) is reached by *relaxing* conditions on a basic
set theoretic notion, topology, but by *imposing* conditions on the equally
basic notion of category, suggests that some sort of pleasant middle ground
has been reached.

The benefits of this middle ground are that it grants equal rights to
elements and predicates (or subobjects), permitting both to be understood
pointwise as respectively the rows and columns of a common matrix defining
a given object.  For example if the pointwise disjunction of two rows is
a third row, then any continuous function preserves that relationship,
as an instance of a fundamental theorem of Chu spaces that the continuous
functions are precisely the homomorphisms or property-preserving functions.

In effect Chu spaces distributes the composition law of an arbitrary
category over its "middle objects" (the Y in X->Y->Z when composing g:Y->Z
with f:X->Y) and then representing those middle objects A as a matrix,
namely the matrix of composites G->A->K whose entries are then in Hom(G,K)
(the role of the bound k on Hom(G,K) is in effect to furnish the matrices
with an alphabet).  The elements of A are the morphisms a:G->A in Hom(G,A)
while the open sets or predicates on A are the morphisms p:A->K in Hom(A,K).

Another benefit of this approach is its typelessness.  Except for the
cardinality constraint of k on Hom(G,K), there is just one big universe with
the same typelessness as in ZF set theory, in which one may find embedded all
one's favorite categories.  Compare this with the artificial barriers created
between categories by the traditional separation into Set, Grp, Top, Vct, etc.

My experience with this approach culturally has been that topologists view
it as too liberal while category theorists view it as too constraining.
Furthermore set theorists view the approach as excessively categorical while
category theorists tend to view it as too tied to sets per se (at least
when described starting from sets).  Those sorts of disagreements suggest
that maybe this theory is approaching an ideal foundational middle ground.

See http://chu.stanford.edu/ to read more about Chu spaces, including the
"continuous = homomorphism" theorem and the strict inclusion of universal
algebra in universal topology.

Vaughan Pratt