Axiomatic Set Theory 1: Introduction

September 22, 2024

Axiomatic Set Theory 1: Introduction

Posted by Tom Leinster

I’m teaching Edinburgh’s undergraduate Axiomatic Set Theory course, and the axioms we’re using are Lawvere’s Elementary Theory of the Category of Sets — with the twist that everything’s going to be done directly in terms of sets and functions, without invoking categories. That is, I’ll neither assume nor teach the general notion of category.

I thought I’d share my notes so far.

Here are the planned chapter headings for the course:

Introduction
The axioms, part one
The axioms, part two
Subsets
Relations
Coproducts and families
Number systems
Well ordered sets
The axiom of choice
Cardinal arithmetic.

It’s one chapter per week, and we’re one week in, which means that so far we’ve just covered the introduction.

I’m really excited to be teaching this course, because as far as I know, nothing like it has ever been done before.

Plus, lots of people — even category theorists and set theorists — don’t realize it can be done! For example, two people I know who are knowledgeable in both subjects assumed I’d have to get into toposes, and didn’t realize it was possible to do everything in a completely elementary way. I want the world to know!

I like to explain this point by analogy with number theory and rings. If you’re going to teach an introductory number theory course, you have a choice. You could say:

“the integers form a ring, number theory eventually needs rings other than the integers, and rings are important throughout mathematics anyway, so I’m going to begin my course by introducing rings and then specialize to the integers”.

Alternatively, you could say:

“basic number theory doesn’t require the general notion of ring, so let’s just talk directly about addition, subtraction and multiplication of integers without ever mentioning rings”.

Both kinds of course are valuable. The first is like teaching ETCS via the general notion of category, more or less as in Lawvere and Rosebrugh’s book Sets for Mathematics. The second is like my course: no categories, just sets and functions done directly.

The classes are based on the students’ questions; each student brings one written question to each class, and I try to answer them all. It’s always fascinating to discover what things the students find challenging, easy, instinctive, counterintuitive, or puzzling, and what captures their imagination. They’ve asked some excellent questions so far.

But I thought it might also be interesting to share the notes here and see what others make of them. So here they are:

Tom Leinster, Axiomatic Set Theory, undergraduate lecture notes in progress.

If all goes well, I’ll keep sharing here every week as I add new chapters. But I’m not entirely sure: the notes are for my students, and it may be that sharing them publicly distorts how I write, in which case I’ll have to pull the plug. (But even so, I’d hope to share the notes once the course is over.) Let’s see how it goes.

Posted at September 22, 2024 9:15 AM UTC

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

20 Comments & 1 Trackback

Re: Axiomatic Set Theory 1: Introduction

Thanks, this is great! I’m teaching a course that’s new to me: modern Geometry. I’m starting with Hilbert’s axioms, but that requires sets and relations, so we did some review.

That led to Foundations, and there is a lot of foundational set theory going on these days! First there is Version 10 of this paper proving consistency of Quine’s New Foundations (NF). My quick elevator pitch for NF is that it avoids Russell’s paradox by requiring stratified formulas. The stratification of formulas prevents x not in x, since for x in y, y must be a strata above x.

Then I started reading this new series of papers by Quinn, with more of the categorical approach that your notes are (barely) hiding: he defines sets as “logical domains that support quantification.”

So I am looking forward to hearing more!

Posted by: Stefan on September 22, 2024 2:39 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

By the way, the proof that NF is relatively consistent with ZFC has been formally verified!

Posted by: David Roberts on September 23, 2024 12:00 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

Thanks, Stefan!

I’m teaching a course that’s new to me: modern Geometry. I’m starting with Hilbert’s axioms, but that requires sets and relations, so we did some review.

That reminds me a bit of the story that Lawvere came up with ETCS in order to get first-year students at a liberal arts college ready for calculus the following year…

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

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

Or that Dedekind came up with his approach to the real numbers when needing to teach a basic calculus class in Zurich….

Posted by: David Roberts on September 24, 2024 1:11 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

In page 12 of your notes you write, “Every calculus book defines a sequence as a function with domain

\mathbb{N}

. Now, we don’t usually think of sequences as functions, and that’s reflected in the notation. No one says ‘let

f

be a sequence’; we say ‘let

(x_n)_{n=0}^\infty

be a sequence’, and write

x_n

instead of

f(n)

. But that’s how sequences are formally defined, and it’s hard to think of any other possible definition.” There is another definition of a sequence in the set

A

, as an element of the terminal coalgebra of the endofunctor

(-) \mapsto A \times (-)

\mathrm{Set}

Posted by: Madeleine Birchfield on September 22, 2024 11:01 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

I think that most mathematicians, and almost certainly all of the students in Tom’s course, would indeed find that definition hard to think of.

Posted by: Mark Meckes on September 23, 2024 12:47 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

It looks really good. I wish I could take that course, actually. I often felt in my first year of studying math more seriously that so many math textbooks bombard you with formal definitions and proofs and do not take the time to investigate all these really subtle questions of conceptual interpretation which to me are what completely makes the difference between understanding something competently and not doing so. The lecture notes actually go into those small details which I think is really important for beginners. I also like that the course is based on students bringing a written question to class; I myself sometimes imagined giving a very different kind of math course in the future where instead of just running through definitions and proofs it would be a totally open ended discussion type class where you can ask any question you want about math. I’ll definitely be following these notes.

Posted by: Julius Hamilton on September 23, 2024 2:50 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

Thanks!

I should probably have said that the first chapter is very unrepresentative. The rest will be structured around definitions, theorems and proofs, like a standard maths text. Of course, definitions, theorems and proofs won’t be the only things. There will be explanations, examples, exercises, digressions, etc. But it will still look quite unlike the first chapter.

Posted by: Tom Leinster on September 23, 2024 9:32 PM | Permalink | Reply to this

Read the post Axiomatic Set Theory 2: The Axioms, Part One
Weblog: The n-Category Café
Excerpt: The first batch of axioms in the Elementary Theory of the Category of Sets, stated without mention of categories.
Tracked: September 27, 2024 1:58 PM

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

Just a thought: Would it be a good idea to include a link to the Arxiv version of your article Revisiting Set Theory in the above? Maybe also a link to the Cafe post where you introduced that. There were plenty of comments there.

Posted by: Keith Harbaugh on October 1, 2024 9:40 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

Can do! Thanks for the thought. Here we go: Rethinking set theory is linked from the notes themselves — just the paper, not the associated post. However, there’s a difference of emphasis between that article and post on the one hand and my course on the other. Both the article and the post are partly a critique of ZFC, whereas ZFC isn’t mentioned in my course at all except in one optional section of the introduction. The course is purely about ETCS.

By the way, you can include links in comments like this:

[Sumatran Orangutan Society](https://www.orangutans-sos.org/)

Posted by: Tom Leinster on October 1, 2024 9:50 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

I’m confused about Axiom 1 and Definition 2.2.2. What does it mean for two functions to be equal? At this point in the axiomatization, how should I understand this equality? Is this equality of functions a “primitive relation” (I don’t know if this expression makes sense)?

Posted by: Paolo Scarpat on November 3, 2024 9:58 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

Some of my students asked a similar question.

We’re taking the notion of equality for granted. Part of the data for the axiomatization is “for any set $X$ and set $Y$ , some things called functions from $X$ to $Y$ ”. And it’s implicit that if we have things called functions from $X$ to $Y$ , we can talk about equality between functions from $X$ to $Y$ .

Another answer is that because this is a course on set theory rather than logic, we’re not addressing this kind of question. So yes, we’re taking equality as a kind of primitive or given.

I had another question in the same spirit a couple of days ago: how do we know that

$(\forall x \in X)(\forall y \in Y) something$

is the same as

$(\forall y \in Y)(\forall x \in X) something?$

And the answer is that it’s just something we’re assuming about the logic of the world in which we’re operating.

The set-theoretic analogue of that question asks why we should have

$\bigcap_{x \in X} \bigcap_{y \in Y} S_{x y} = \bigcap_{y \in Y} \bigcap_{x \in X} S_{x y}$

for any family $(S_{x y})_{(x, y) \in X \times Y}$ of subsets of some set. We can prove it, but to do so, we’d probably use the logical principle about universal quantifiers mentioned above.

Posted by: Tom Leinster on November 3, 2024 12:37 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

Thank you!

Posted by: Paolo Scarpat on November 3, 2024 12:56 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

One might argue that this is a pedagogical and philosophical weak point, though. Section 2.1 begins with an intuitive definition of function in terms of assignment, Axiom 1 in section 2.2 is motivated in relation to this intuitive definition, and then Axiom 3 in section 2.4 is justified by appeal to an assertion (not explained) that this intuition bears little relation to the notion of function hitherto defined. What equality actually means is therefore rather a good question.

If one wished to give a from-scratch formal treatment of set theory in the spirit of these lecture notes, but which actually was built upon the element-based intuition of set theory, where equality was meaningful, one would likely end up with something close to a type-theoretic presentation. I think it would be difficult to achieve something really satisfactory with ETCS: one could motivate the function axioms without reference to elements, but Axiom 3 will then be completely out of the blue (it is really unavoidably ‘arbitrary’ from that point of view; it is not much different to axiomatising that sets are determined by their elements, which would rather undermine the flavour of the course!).

Posted by: quibble on November 3, 2024 10:45 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

Just in response to this for now:

it is not much different to axiomatising that sets are determined by their elements, which would rather undermine the flavour of the course!

I have no reservations about doing things that resemble ZFC, if that’s what you mean about undermining the flavour. There’s no intention to be wilfully different from traditional set theory for the sake of it. (I know you weren’t saying this, but I guess I want to make it clear.)

There are two forms of extensionality that appear in this course.

One is indeed Axiom 3, “a function is determined by its effect on elements”. Or formally put, if $f, g: X \to Y$ with $f(x) = g(x)$ for all $x \in X$ , then $f = g$ . Let’s call this “function extensionality”.

The other is subset extensionality (Proposition 4.1.20). This says, slightly loosely, that two subsets of a set $X$ are equal if and only if they have the same elements. A more exact way of saying it is that two subsets $A$ and $B$ are equal just when the following condition holds: an element of $X$ belongs to $A$ if and only if it belongs to $B$ .

What we don’t have, of course, is “set extensionality”: two sets are equal if and only if they have the same elements. But function extensionality and subset extensionality are absolutely in the spirit of the venture.

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

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

By the way, when I replied to Paolo that some of my students have asked me about equality, what I didn’t mention is that because the classes are run in a way that’s based on students’ questions, they’ve asked me literally hundreds of questions by now. As far as I remember, only two have been about equality. And as far as I remember, the students were satisfied with my answers. So my experience is that this is not a pedagogical hurdle.

There are other pedagogical challenges, to be sure, and I don’t want to minimize that. Maybe one day, when I’ve got my breath back, I’ll write a post detailing them. But for the kind of students I’ve got, explaining equality really isn’t one of them.

I’m puzzled by some parts of your comment:

Section 2.1 begins with an intuitive definition of function in terms of assignment […] and then Axiom 3 in section 2.4 is justified by appeal to an assertion (not explained) that this intuition bears little relation to the notion of function hitherto defined

What assertion do you mean? What isn’t explained? I can’t see anything in Section 2.4 where I’ve asserted that some intuition about something bears little relation to some notion of function. Or am I misunderstanding you?

If one wished to give a from-scratch formal treatment of set theory in the spirit of these lecture notes, but which actually was built upon the element-based intuition of set theory, where equality was meaningful

Equality is meaningful in these notes—that is, equality of functions with the same domain and the same codomain. In particular, equality of elements of the same set is meaningful (because elements of a set $X$ are functions $1 \to X$ ). And that’s the kind of equality you mean, isn’t it? But again, maybe I’m not getting you.

Posted by: Tom Leinster on November 3, 2024 11:22 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

What assertion do you mean? What isn’t explained? I can’t see anything in Section 2.4 where I’ve asserted that some intuition about something bears little relation to some notion of function.

I was referring to “Nothing in our axioms so far guarantees that this is the case.”, which is asserted without any explanation (i.e. no justification of the fact that function extensionality may not hold given only the previous axioms is given).

And that’s the kind of equality you mean, isn’t it?

I was referring to the use of equality between functions without reference to elements in Axioms 1, 2, and 3 for example. That the domains and co-domains are the same is not really relevant to this, that is just a matter of being able to ask the question of whether the functions are equal; the point I am bringing up is, given that we can ask the question, what their equality actually means. The text surrounding Axioms 1 and 2 justifies their formulation in terms of what functions do to elements, but a priori (until Axiom 3) what functions do to elements has nothing to do with their equality.

To put it another way, consider models of a theory involving just Axioms 1, 2, and 3. They could be almost anything, including ordinary set theory, in which function extensionality for functions from a one-point set to some set of sets (or groups, or whatever) recovers equality of sets (or groups), the avoidance of which is one of things you give as motivation for proceeding via ETCS in the notes. If one further drops Axiom 3, one obviously has models in which equality of functions will correspond to things that look nothing like the intuition in terms of elements of sets.

As I say, I do think that category-theoretic thinking can be primordially motivated, in particular that Axioms 1 and 2 can be made meaningful without any reference to elements; there are plenty of graph-native technologies around, for example things like RDF. But then Axiom 3 really has no relevance to that semantics, once one has Axiom 3, one could just as well have said that we have sets, elements of sets, and functions between sets which are defined by taking take elements to elements as primitive, which is basically how a type-theoretic treatment will look.

Posted by: quibble on November 4, 2024 12:43 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

In short, the overall point I am making is that I am not sure that the pedagogical treatment of the ETCS axioms in the lecture notes ultimately really stands up. Of course the students will acquire the intuition they need for the course from making use of the axioms, and can in the end largely or completely ignore how they were introduced/motivated, just taking them as given. But I think an ideal pedogogical and philosophical approach would be one grounded in meaning (i.e. where the axioms are not just syntactical formalities, they arise from a consistently meaningful motivating picture which a person can relate them to), and what I am suggesting is that ETCS does not seem well-suited to this, because there is a fundamental divide between category-theoretic thinking and sets-as-defined-by-their-elements thinking, which seems only really possible to bridge by fiat.

Posted by: quibble on November 4, 2024 1:28 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

On a different note, with regard to the efficacy of ETCS, would any of the students at the end of the course be in a position to rigorously define a group, or a vector space…?

Posted by: quibble on November 4, 2024 1:41 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 1: Introduction

$MathML-enabled post (click for more details).$

For the record, as there was maybe a possibility of it being misunderstood, this question was a serious one: what I had in mind was there is no problem in ZFC to rigorously say that a group consists of an ordered pair of a set and a binary relation on it satisfying certain axioms, whereas unless I’m missing something this is not (naturally at least, i.e. in line with the methodology taught in the course) possible in ETCS without introducing at least one universe, or some other addition which achieves the same, and I would guess that you were not planning to do this (even though you do have cardinal arithmetic as a scheduled chapter). I.e. it is one thing to work internally to the world of sets, and it is true that the title of the course is ‘Axiomatic set theory’, but as a foundation for mathematics one needs to step outside of that, and at least in equivalent courses at some universities, it would be expected of one’s set theory course to have that perspective.

One might argue that there is no real issue here, and that a student taking a first course in group theory can simply take ‘a pair of a set and a binary relation on it’ as informal. That’s probably a defensible point of view, but in general it would mean that everything except pure set theory would be informal, in defiance of the idea of a formal foundations; even though it that is to a large extent the case anyhow with ZFC in a mathematician’s day to day work, I think most mathematicians would feel uncomfortable with that state of affairs.

Of course one could alternatively treat groups purely axiomatically too, but one would have to motivate the necessary categorical constructions from scratch and introduce some ‘constructors’ by fiat in order to obtain examples; again, probably defensible, but very far removed from today’s pedagogy.

Posted by: quibble on November 9, 2024 1:14 AM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

September 22, 2024