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.

October 4, 2024

Axiomatic Set Theory 3: The Axioms, Part Two

Posted by Tom Leinster

Previously: Part 2. Next: Part 4

This week, we finished formulating the axioms of the Elementary Theory of the Category of Sets.

This week’s axioms were the last four:

  • 7. For every function f:X→Yf: X \to Y and element y∈Yy \in Y, we can form the fibre f −1(y)f^{-1}(y).

    Category theorists will recognize this as a special case of the existence of pullbacks. But in the presence of the other axioms, this special case alone is enough to imply the existence of all pullbacks. We’ll also be able to deduce the existence of arbitrary preimages (not just preimages of singletons), and of arbitrary images too.

  • 8. There exists a subset classifier. That is, there’s a set 2\mathbf{2} with the property that for all sets XX, the injections into XX correspond (up to iso) with the functions X→2X \to \mathbf{2}.

    This axiom is very powerful. For instance, it’s proved in this section of the notes that every bijection is invertible and that all empty sets are isomorphic. Neither of those statements seems to have anything to do with the existence of a subset classifier. Nevertheless, we need it in the proofs.

    The axiom does not demand that 2\mathbf{2} is a set with two elements. “2\mathbf{2}” is just notation for now. But we’ll prove next week that the axioms do in fact imply that 2\mathbf{2} is a two-element set.

  • 9. There exists a natural number system.

    We’re not going to need this axiom for several weeks.

  • 10. Every surjection has a section.

    This is the axiom of choice, and we’re not going to need it until nearly the end of the course — Chapter 9 out of 10.

You can find the notes here.

Posted at October 4, 2024 4:16 PM UTC

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



11 Comments & 0 Trackbacks

Re: Axiomatic Set Theory 3: The Axioms, Part Two

In case anyone’s interested in the pedagogical side of this, here’s some information.

There are 51 students enrolled in the class, nearly all of them fourth or fifth year undergraduates. (Our BSc is a four-year programme, and those doing an integrated masters degree — an MMath — do a further year.) Most of them are doing a maths degree, with a few doing joint maths + something degrees, e.g. maths + physics or maths + informatics.

In yesterday’s class, we’d just finished the axioms, so I asked the students to do the following little exercise. They got into pairs, each student chose the topic they’d found hardest so far, and then the other member of the pair tried to explain that topic to them for five minutes. Then they swapped roles.

I went round the room asking everyone what they’d chosen as their topic, and there was a clear winner: function sets (a.k.a. exponentials). In retrospect, I can see that that section of the notes is a bit lacking explanation and examples, but I suspect ot would have been the winner anyway.

From what the students said, I think there were several related difficulties with function sets. One was that they’re not that used to thinking about sets of functions. (Or perhaps they are, but they don’t realize they are?) Another was the correspondence between functions A×X→YA \times X \to Y and functions A→Y XA \to Y^X. A third was the role of the evaluation function Y X×X→YY^X \times X \to Y. And finally, the formal definition of function set, via the universal property, takes some getting used to.

I think all these things are an important part of learning mathematics anyway. For instance, if you don’t understand in your bones how you can collect together functions to form a set, then you’re never going to understand permutation groups. But there’s a more optimistic converse: if you do understand permutation groups, then you do understand that functions can form a set! That’s what I meant when I wrote above that some students might be more familiar with function sets than they realize.

If any of my students are reading this and want to share their thoughts on what they found challenging, I’d very much welcome that.

As I said in class, I wouldn’t be surprised if the previous week or two turns out to be the hardest part of the course. That’s quite unusual: normally the hardest part of a course is at the end. Perhaps it’s like the shape of an introductory analysis course that starts with the definition of continuity — something that many learners need time to get used to. In fact, there are some shared difficulties, in that both the definition of continuity and universal properties both have somewhat complicated quantifiers.

Posted by: Tom Leinster on October 5, 2024 4:17 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 3: The Axioms, Part Two

I imagine also that the notation X YX^Y for the set of functions from YY to XX, which seems so charming and right when we’re used to it, seems mysterious and scary at first — in part because we’ve all seen exponentials of numbers, like 2 3=82^3 = 8, but exponentials of sets are something new.

To help students conquer this fear, I’d point out that there are 88 functions from any 33-element set to any 22-element set. And I’d also point out the meaning of equations like

2 3=2×2×2 2^3 = 2 \times 2 \times 2

That is, an element of X YX^Y is a YY-tuple of elements of XX.

Small examples are a great way to defang scary concepts.

Posted by: John Baez on October 7, 2024 6:03 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 3: The Axioms, Part Two

Thanks for the comment!

Right, overcoming scary notation is a large part of the battle. We do a lot of exercises in class, some of which are the green exercises in the notes and some of which aren’t. (The classes aren’t lectures of the traditional kind.) We did a couple of exercises pretty similar to what you mention, with small examples of counting sets of functions (actually including 2 32^3!), as well as small examples of products, images, etc. I like that kind of thing.

Right now, teaching Chapter 4 and writing Chapter 5, I’m painfully aware that the notational side of the course is far from optimal. This isn’t surprising, as this isn’t a course that’s been taught many times by many people and had the rough edges worn off it, like a pebble that’s been washed smooth by years on a river bed. It’s the first time, and it’s a bit jagged. As we go along, I’m learning how I could have done more to make the notation smoother — and improve other aspects too, of course, but notation is especially on my mind right now.

Teaching is always a learning experience, and in the case of this course, it’s a particularly intense one.

Posted by: Tom Leinster on October 8, 2024 1:27 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 3: The Axioms, Part Two

Nice! I’m not really surprised you chose 2 32^3 as your example, since 2 22^2 could scar someone for life.

Posted by: John Baez on October 8, 2024 2:51 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 3: The Axioms, Part Two

Is it that the exponential notation is a sticking point? I vaguely recall when learning it that the direction of the maps wasn’t obvious, and hence small additional bit of friction, since Y XY^X is pronounced “backwards” (the source is mentioned second). Compare the set theorists’ notation XY{}^X Y for the set of functions from XX to YY.

One alternative (for future?) is to mimic what algebraic geometers do for the internal hom for sheaves: something like Func̲(X,Y)\underline{\mathrm{Func}}(X,Y) for object of functions from XX to YY? They write an underline on Hom or Isom to indicate the Hom-sheaf or the Isom-sheaf, but non-underlined to represent its set of global sections, but this is not really a concern here. But this at least distinguishes it from a naive reading of taking the (external) collection of functions between the two sets.

Just a thought, you know your students better than me!

Posted by: David Roberts on October 8, 2024 12:13 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 3: The Axioms, Part Two

I don’t actually know whether the Y XY^X notation is a sticking point for my students. I should ask.

But today I was chatting with one of them and I asked what made function sets such a difficult topic. Their response was that it was taking them some time simply to get used to thinking about sets of functions at all. I asked whether they were comfortable with symmetric groups, and they immediately said yes, but those somehow don’t feel like sets of functions (even though the student understood that they are, in fact, sets of functions).

I think I get that. A permutation feels like a concrete thing, especially if you write it in cycle notation (or even the two-row matrix notation). But it was only a quick chat. I’d like to find out more about why my students find this topic particularly challenging.

(Nevertheless, I maintain that this struggle is good for them! Getting to grips with sets of functions is an essential stage in one’s mathematical education, with benefits far far beyond set theory.)

When I mentioned notation causing a barrier, it wasn’t particularly Y XY^X that I had in mind, it was other things—too tired to go into that right now!

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

Re: Axiomatic Set Theory 3: The Axioms, Part Two

In my world I’ve seen the difficulty with sets of functions arise when talking about function spaces in functional analysis, and then maps acting on such spaces (thus functions between sets of functions).

My impression is that students subconsciously develop a sort of hierarchy, where we have some basic things which can be elements of sets, then sets of those basic things, then functions between sets. They’re used to elements of sets being things like numbers, or points in space, or things that are formally defined as functions but are thought of as “things” rather than “machines”, like curves in space. And they don’t tend to be given a lot of examples that force them out of that comfort zone early on.

(In my experience, students often think of a permutation — and are encouraged to do so — as a more basic, atomic sort of thing (a “reordering”), and sometimes react with surprise when they are reminded that, as they already know, permutations are indeed functions. That seems to be consistent with what your students said.)

Already the notion of a set whose elements are explicitly sets, like a power set, starts making some students uncomfortable. Sets whose elements are functions scrambles up this things-sets-functions hierarchy even more. Another good example of this sort of thing is automorphism groups of groups.

Posted by: Mark Meckes on October 9, 2024 5:52 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 3: The Axioms, Part Two

In my world I’ve seen the difficulty with sets of functions arise when talking about function spaces in functional analysis, and then maps acting on such spaces (thus functions between sets of functions).

I can imagine!

I agree with everything you wrote. I still remember my shock at learning that there was a vector space whose elements were polynomials. Imagine! I barely could. And I think it’s not just students who see this hierarchy in their internal mathematical world.

So how can we make sets of functions seem less scary?

After discovering how hard many of my students found sets of functions, I started writing a list of places where they come up in different parts of maths. Here I’m talking about maths at an undergraduate-ish level. Some of the following might be helpful for defanging (as John put it) this mysterious notion, some probably not. (That’s not the only reason I started the list.) But let me just splurge out the whole of my list so far.

  • The set of solutions of a differential equation.

  • The set of sequences satisfying some condition, e.g. convergent to 00.

  • The set of integrable/differentiable functions.

  • The set of linear transformations ℝ n→ℝ m\mathbb{R}^n \to \mathbb{R}^m, which my students (should) know is in bijection with the set of m×nm \times n matrices.

  • The set of permutations of {1,…,n}\{1, \ldots, n\}.

  • The set of functions {1,…,n}→ℝ\{1, \ldots, n\} \to \mathbb{R}, otherwise known as ℝ n\mathbb{R}^n!

  • Rings of polynomials in algebra. (Of course, there’s a subtle point about polynomials not exactly being functions, but never mind.)

  • The ring C(X)C(X) of functions on a space XX, from which one can often recover XX.

  • Sets of polynomials from a numerical analysis point of view, e.g. among all polynomials of degree ≤10\leq 10, which one approximates this function best?

What else can we add to this list? The lower the level, the better.

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

Re: Axiomatic Set Theory 3: The Axioms, Part Two

Something like “the set of elementary functions”? Then differentiation restricts to an endofunction on this set (it’s not an endofunction on the set of merely differentiable functions, for instance). That this function is not onto is not an easy theorem, but also knowing when a function is in the image is really important, cf the Risch algorithm.

Also, the field of rational functions (they really are partially-defined functions, so maybe this throws a spanner in the works). Or else something like rational functions on the complex numbers with values in P^1, making them total functions.

Posted by: David Roberts on October 11, 2024 6:52 AM | Permalink | Reply to this

Re: Axiomatic Set Theory 3: The Axioms, Part Two

My favorite examples would be vector spaces of functions, which start appearing implicitly in calculus classes (you mention the most obvious ones), and groups of automorphisms of some kind of object. The latter would include many, maybe most, of the groups you’re likely to encounter “in the wild”: the isometry group of a metric space, the group of Möbius transformations, etc.

Another example I alluded to above is the set of (parametrized) curves in some space, which students may encounter already in calculus classes, and if not there then almost certainly in complex analysis, and certainly certainly in differential geometry or algebraic topology if they’ve take those.

Posted by: Mark Meckes on October 11, 2024 1:25 PM | Permalink | Reply to this

Re: Axiomatic Set Theory 3: The Axioms, Part Two

Have you shown your students the equivalents in set-builder notation? e.g.

X Y={f|f:Y→X}X^Y=\{f|f:Y\rightarrow X\}

ℝ n={f|f:n→ℝ}\mathbb{R}^\mathbf{n}=\{f|f:\mathbf{n}\rightarrow \mathbb{R}\}

This might help highlight that the thing in question really is a set of functions.

Posted by: John Beattie on October 23, 2024 9:33 PM | Permalink | Reply to this

Post a New Comment