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.

June 29, 2021

Large Sets 7

Posted by Tom Leinster

Previously: Part 6. Next: Part 8

Given a well-ordered set WW, there are at least two ways of manufacturing a plain, unadorned set. You can, of course, take the underlying set U(W)U(W). But you can also take the beth W\beth_W. How do they compare in size?

Let’s look at some of the first few cases, recalling that when nn is a natural number, n\beth_n means W\beth_W for the unique well-ordered set WW with nn elements.

  • 0\beth_0 is \mathbb{N}, the smallest infinite set, whereas 00 is the empty set.

  • 1\beth_1 is the uncountable set 2 2^\mathbb{N}, whereas 11 is the well-ordered set with only one element.

  • 4=2 2 2 2 \beth_4 = 2^{2^{2^{2^{\mathbb{N}}}}} is probably bigger than any specific set used by 95% of mathematicians in a lifetime, whereas 44 has, well, just four elements.

So comparing W\beth_W with U(W)U(W) seems like racing an intercontinental ballistic missile against a snail — or more traditionally, a hare against a tortoise.

Unlike in the fable, our tortoise never overtakes the hare. But it’s conceivable that it does keep catching up, only to fall behind again an instant later. Moments when the tortoise catches the hare are called “beth fixed points”, and they’re our topic for today.

Posted at 3:47 PM UTC | Permalink | Followups (16)

June 24, 2021

Large Sets 6

Posted by Tom Leinster

Previously: Part 5. Next: Part 7

The plan for this series is to talk about ever larger sets and ever stronger axioms. So far we’ve looked at weak limits, strong limits, and alephs. Today we’ll look at beths.

The beths are the sets you get if you start with \mathbb{N} and repeatedly take power sets. They are

0=, 1=2 , 2=2 2 , \beth_0 = \mathbb{N}, \ \beth_1 = 2^\mathbb{N}, \ \beth_2 = 2^{2^{\mathbb{N}}}, \ \ldots

“and so on”, with one set W\beth_W for each well-ordered set WW. The symbol \beth is beth, the second letter of the Hebrew alphabet, after aleph. And like the alephs, the beths aren’t all guaranteed to exist.

Posted at 3:45 PM UTC | Permalink | Followups (6)

June 20, 2021

Large Sets 5

Posted by Tom Leinster

Previously: Part 4. Next: Part 6

Last time, we met the “index” of an infinite set XX, which is the well-ordered set

Index(X)={isomorphism classes of infinite sets <X}. Index(X) = \{ \text{isomorphism classes of infinite sets } \lt X \}.

It cannot be proved in ETCS that every well-ordered set WW is the index of some infinite set XX. However, if such an XX does exist, it’s unique for WW (up to isomorphism). It’s called W\aleph_W: aleph-WW.

Posted at 1:07 PM UTC | Permalink | Followups (8)

June 19, 2021

Optimal Transport and Enriched Categories II

Posted by Simon Willerton

The dual transport problem from general linear programming duality

Last time I described the basic, discrete optimal transport problem in which there are some suppliers wanting to supply certain amounts of some resource (eg loaves of bread) and some receivers wanting to receive a certain amount of that resource. There’s a cost associated to transporting a unit of the resource from a supplier to a receiver, this cost is fixed for each pair of supplier and receiver. You want to plan how much resource to send from each supplier to each receiver so as to minimize the total cost.

I then said that finding this minimum cost was equivalent to finding the maximum revenue of a different problem, where someone, for each supplier, fixes a price that they’re willing to pay for a unit of the resource and, for each receiver, they fix a price that they’ll charge for a unit of resource. These prices are subject to a constraint from the original transportation cost. You’ll see again what that is in the post below.

This time I want to show how this second problem is the ‘linear programming dual’ of the first, ‘primal’ problem – this general theory of such linear programming duality is likely to be in every undergraduate course on optimization. I’ll end with some extra comments on general programming duality.

Posted at 9:49 PM UTC | Permalink | Followups (3)

June 17, 2021

Large Sets 4

Posted by Tom Leinster

Previously: Part 3. Next: Part 5

The alephs are the succession of ever-larger infinite sets, beginning at 0=\aleph_0 = \mathbb{N}, followed by the smallest set larger than 0\aleph_0, which is called 1\aleph_1, and then similarly 2, 3,\aleph_2, \aleph_3, \ldots, up to ω\aleph_\omega and beyond. At least, that’s the usual way the alephs are introduced. But in this post and the next, I’m going to come at the alephs from another angle — the opposite direction, in some sense — which is better suited to ETCS.

Last time, I promised that I’d get to the alephs this time. But in the interests of keeping each post shortish, I’m actually going to split the explanation in two. So right now, I’m going to explain something I call the “index” of a set, and next time we’ll meet the alephs themselves.

Posted at 5:18 PM UTC | Permalink | Followups (10)

June 13, 2021

Large Sets 3

Posted by Tom Leinster

Previously: Part 2. Next: Part 4.

Inherent in set theory is the notion of well-ordered set. If you think about sets for long enough, well-orderings are bound to show up. In this post I’ll explain why, and I’ll summarize some of the fundamental facts about well-orderings — the least standard of which is an adjunction between sets and well-ordered sets.

There are no large sets this time, but what we do here will be needed in later instalments.

Posted at 8:29 PM UTC | Permalink | Followups (4)

June 11, 2021

Data Visualization Course

Posted by John Baez

Are you a student interested in data analysis and sustainability? Or maybe you know some students interested in these things?

Then check this out: my former student Nina Otter, who now teaches at UCLA and Leipzig, is offering a short course on how to analyze and present data using modern methods like topological data analysis — with sustainable fishing as an example!

Students who apply before June 15 have a chance to learn a lot of cool stuff and get paid for it!

In fact Nina has started a new institute, the DeMoS Institute. Here is the basic idea:

The institute carries out research on topics related to anti-democratic tendencies in our society, as well as on meta-scientific questions on how to make the scientific system more democratic. We believe that research must be done in the presence of those who bear their consequences. Therefore, we perform our research while at the same time implementing directly practices that promote inclusivity, interdisciplinarity, and in active engagement with society at large.

But here’s more about the course….

Posted at 12:34 AM UTC | Permalink | Followups (10)

June 10, 2021

Large Sets 2

Posted by Tom Leinster

Previously: Part 1. Next: Part 3

The world of large cardinals is inhabited by objects with names like inaccessible, ineffable and indescribable, evoking the vision of sets so large that they cannot be reached or attained by any means we have available. In this post, I’ll talk about the smallest sets that cannot be reached using the axiom of ETCS: limits.

Posted at 5:29 PM UTC | Permalink | Followups (75)

June 8, 2021

Large Sets 1

Posted by Tom Leinster

Next: Part 2

This is the first of a series of posts on how large cardinals look in categorical set theory.

My primary interest is not actually in large cardinals themselves. What I’m really interested in is exploring the hypothesis that everything in traditional, membership-based set theory that’s relevant to the rest of mathematics can be done smoothly in categorical set theory. I’m not sure this hypothesis is correct (and I suppose no one could ever be sure), which is why I use the words “hypothesis” and “explore”. But I know of no counterexample.

These posts won’t assume very much knowledge of anything. And I’ll try to stick to one topic per post. In this first one, all I’ll do is clear my throat.

Posted at 3:42 PM UTC | Permalink | Followups (51)

June 6, 2021

Optimal Transport and Enriched Categories I

Posted by Simon Willerton

Last year, in an ACT@UCR talk, I spoke about the Fenchel–Legendre transform from a category theoretic perspective and I showed how convex functions arise as a ‘profunctor nucleus’ in the context of categories enriched over the extended real numbers [,][-\infty, \infty]. At the end of the talk I gave four other examples of things which arise as profunctor nuclei, the final one of which was I put in at the last minute and labelled as “tentative”. John Baez took up the scent and asked me to explain why it was “tentative”, the answer was because I hadn’t thought about it for a while. I decided to write it up here at the Café, but the intervening year has had me concentrate on keeping our department running during the you-know-what, so this has been gestating a while!

Anyway in this series of posts I want to explain how aspects of optimal transport problems can be thought of in terms of enriched category theory, profunctors and related constructions. The genesis of this was a conversation following a comment of mine to Mike Shulman’s classic post “Equipments”, in particular Tobias Fritz pointing me to Cédric Villani’s book “Optimal transport: old and new”.

In this first first post I want to state the optimal transport problem (in the finite, discrete setting) and then describe the dual problem. I’ll end with a little digression on Kantorovich and a plug for the book Red Plenty by Francis Spufford.

Posted at 11:42 AM UTC | Permalink | Followups (12)

June 2, 2021

Schur Functors and Categorified Plethysm

Posted by John Baez

It’s done!

This paper has been 14 years in the making. So let me tell you a bit of its history, and then I’ll explain the paper itself.

Posted at 10:15 AM UTC | Permalink | Followups (78)