Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

September 27, 2024

Axiomatic Set Theory 2: The Axioms, Part One

Posted by Tom Leinster

Previously: Part 1. Next: Part 3

We’ve just finished the second week of my undergraduate Axiomatic Set Theory course, in which we’re doing Lawvere’s Elementary Theory of the Category of Sets but without mentioning categories.

This week, we covered the first six of the ten axioms: notes here.

The data to which the axioms apply is as follows:

  • some things called sets;

  • for each set XX and set YY, some things called functions from XX to YY, with functions ff from XX to YY written as f:X→Yf: X \to Y;

  • for each set XX, set YY and set ZZ, an operation called composition assigning to each f:X→Yf: X \to Y and g:Y→Zg: Y \to Z a function g∘f:X→Zg \circ f: X \to Z;

  • for each set XX, a function id X:X→Xid_X: X \to X, called an identity function.

The first six axioms:

  1. Composition is associative, and the identity functions act as identities.

  2. There is a terminal set, 1\mathbf{1}.

  3. A function is determined by its effect on elements. That is, define an element of a set SS as a function 1→S\mathbf{1} \to S. Then whenever f,g:X→Yf, g: X \to Y with fx=gxf x = g x for all elements xx of XX, we have f=gf = g.

  4. There is a set with no elements.

  5. For all sets XX and YY, there exists a product of XX and YY. Here “product” is defined by the usual universal property.

  6. For all sets XX and YY, a function set from XX to YY. Here “function set” means what is usually called an exponential in category theory, and again is defined by the usual universal property.

The details of all this, together with lots of explanation, are in the notes.

Posted at September 27, 2024 1:54 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3560



13 Comments & 1 Trackback

Re: Axiomatic Set Theory 2: The Axioms, Part One

I think the empty set axiom is redundant, since empty sets can be constructed from the terminal set, products, inverse images, function sets, and the subobject classifier.

Posted by: Madeleine Birchfield on September 27, 2024 3:40 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

Thanks for the comment.

The empty set axiom is not redundant, as without it, there’s a trivial model of the axioms consisting of a single set and the identity function on it. But with the empty set axiom, that’s no longer a model.

An initial set can be constructed from the ingredients you list. But there’s no guarantee that it’s empty, as that trivial model demonstrates.

Posted by: Tom Leinster on September 27, 2024 3:44 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

Oh right, that axiom corresponds to the nondegeneracy condition for a well-pointed topos. I always seem to forget about that.

Posted by: Madeleine Birchfield on September 27, 2024 6:17 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

Speaking of well-pointedness, in which week if any do you plan on proving that the terminal set is projective and indecomposable?

Posted by: Madeleine Birchfield on September 28, 2024 2:45 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

Let’s see.

1 being projective means that epimorphisms are surjective. I have that noted down as a question I might set on one of the tutorial sheets, but I don’t believe I’ll need it in the main development, so it won’t be in the notes themselves.

As for 1 being indecomposable… Well, we’re going to prove that a diagram

X→Z←Y X \to Z \leftarrow Y

is a coproduct diagram if and only if it’s a “disjoint union diagram”, by which I mean that the two functions are injective and that every element of ZZ either comes from an element of XX or an element of YY, but not both. Once you’ve got that, indecomposability of 11 is immediate, and I think if I stated it explicitly then the students would wonder why I’d bothered.

One of the challenges for me in this course is to realize when it’s possible — and when it’s better — to present things set-theoretically rather than categorically. To take a rather trivial example, if I want to say that g∘f=k∘hg \circ f = k \circ h, do I say that g(f(x))=k(h(x))g(f(x)) = k(h(x)) for all elements xx of the domain, or do I draw a square and say it commutes? But there are less trivial examples of concepts and results that I think about categorically, but which can also be presented in a more set-theoretic manner, and there’s a pedagogical choice to be made every time.

Posted by: Tom Leinster on September 28, 2024 3:05 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

I like this in the notes:

Warning 1.1.2 Mathematicians are human beings!

Who knew?

Posted by: John Baez on September 27, 2024 4:19 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

One point maybe worth mentioning here is that we can’t prove yet that empty sets are initial, nor even that there’s only one empty set (up to iso). By “yet” I mean “using only the axioms so far”.

What we’re going to do next week is the following:

  • Prove that bijections are isomorphisms using the existence of a subset classifier. A little more detail: first prove that the characteristic function of any bijection has constant value “true”, then prove that this implies invertibility.

  • Using this, prove that empty sets are initial. Here’s how: let EE be an empty set and XX any set. Since a function is determined by its effect on elements (well-pointedness), and EE has no elements, there’s at most one function E→XE \to X. To get existence, consider the product diagram E←E×X→X. E \leftarrow E \times X \to X. The leftwards-pointing function is bijective (since both domain and codomain are empty), hence invertible; now compose its inverse with the rightwards-pointing function to get a function E→XE \to X.

  • Since all initial objects are isomorphic, it follows that all empty sets are isomorphic.

Posted by: Tom Leinster on September 28, 2024 12:46 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

So, to summarise, Set is—so far—a cartesian closed category with 1 a separator, and with some set O such that there is no function from 1 to O.

Posted by: David Roberts on September 28, 2024 5:23 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

Right, exactly.

Posted by: Tom Leinster on September 28, 2024 5:35 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

Another thing to note for people ok with categories: assume we have the category Set, and are trying to instead characterise it, rather than axiomatise it.

Assume that the category CC described by the axioms so far is locally small (which will probably follow from later axioms, but for now I have to assume separately). Then the global points functor Hom(1,−):C→SetHom(1,-): C\to Set is faithful, preserves cartesian products and terminal objects, and sends OO to ∅\emptyset. So far the full subcat CC of SetSet consisting of just an initial and a terminal object seems to be a model, as it is cartesian closed subcat.

Posted by: David Roberts on September 30, 2024 7:51 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

Are the workshop questions (for example, the one you mention in Remark 2.1.2) publicly available?

Posted by: Paolo Scarpat on September 28, 2024 5:29 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

Not for now. I might share them after the course is over (early December). There’s a lot for me to write between now and then, and for the time being, I’d prefer to keep it simple in terms of what I’m releasing publicly.

Posted by: Tom Leinster on September 28, 2024 5:34 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 2: The Axioms, Part One

Thanks for your reply. I’m really enjoying your lecture notes!

Posted by: Paolo Scarpat on September 28, 2024 5:44 PM | Permalink | Reply to this
Read the post Axiomatic Set Theory 3: The Axioms, Part Two
Weblog: The n-Category Café
Excerpt: Undergraduate course on the Elementary Theory of the Category of Sets, done without category theory.
Tracked: October 4, 2024 4:30 PM

Post a New Comment