Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Universal property of the reals as a preorder

Nathaniel Virgo (Aug 27 2023 at 05:46):

Consider the reals or the extended reals as a preorder. (Equivalently the open or closed unit interval.) Do either of these objects have a nice universal property in the category of preorders? (Or in Cat, come to think of it.)

John Baez (Aug 27 2023 at 07:04):

Nathaniel Virgo said:

Consider the reals or the extended reals as a preorder. (Equivalently the open or closed unit interval.) Do either of these objects have a nice universal property in the category of preorders? (Or in Cat, come to think of it.)

It's not exactly a 'universal property', but I will guess that the extended reals is, up to isomorphism, the only linear order with an upper bound and lower bound that's dense (given $a < b$ we can find $c$ with $a < c < b$) and has the cardinality of the continuum.

John Baez (Aug 27 2023 at 07:05):

I'm guessing this based on Cantor's isomorphism theorem.

John Baez (Aug 27 2023 at 07:08):

Whoops, never mind:

Cantor's isomorphism theorem can be expressed by saying that the first-order theory of unbounded dense linear orders is countably categorical: it has only one countable model, up to logical equivalence. However, it is not categorical for higher cardinalities: for any higher cardinality, there are multiple inequivalent dense unbounded linear orders with the same cardinality

John Baez (Aug 27 2023 at 07:11):

Well, Cantor's original theorem is for unbounded linear orders and my tweaked version was ones with an upper bound and lower bound, which might save me... but maybe not. If we take the [[long line]] and throw in an upper bound and lower bound, do we get a dense linear order with upper bound and lower bound with cardinality the continuum that's not isomorphic to $\mathbb{R}$?

John Baez (Aug 27 2023 at 07:11):

Yes, I believe the link I gave has the ingredients for a proof.

John Baez (Aug 27 2023 at 08:41):

Oh, an easier counterexample would be a copy of $\mathbb{R}$ with a copy of $\mathbb{Q}$ put above it, with $-\infty$ and $\infty$ tacked on.

John Baez (Aug 27 2023 at 08:44):

So, the cardinality is nowhere near enough to nail down the structure of a dense linear order (bounded or unbounded) except in the countable case. So one would need some new idea to characterize $\mathbb{R}$ as a poset.

Jade Master (Aug 27 2023 at 14:24):

There is the characterization of the interval as the terminal coalgebra of a certain squaring functor on a category of bi-pointed sets. I think this sort of captures the property that the interval may be subdivided into two pieces indefinitely.

Todd Trimble (Aug 27 2023 at 17:21):

In a vein similar to Jade's example, the interval $[0, \infty)$ is a terminal coalgebra for the functor that takes a poset $X$ to $\mathbb{N} \times X$ ordered lexicographically, as described for example here. There are many ways of realizing this; continued fractions is one. More are described in this paper by Dusko and Vaughan Pratt.

Ben Logsdon (Aug 31 2023 at 19:58):

I believe the original paper behind Jade Master's answer is "Algebraic Real Analysis", by Peter Freyd:

http://www.tac.mta.ca/tac/volumes/20/10/20-10.pdf

I'll summarize the ideas here since I like them, but everything below can be found in that paper.

Broadly speaking, one can think of an algebra as an object equipped with operations that combine (potentially multiple) elements to form a single new element, while one can think of a coalgebra as an object equipped with operations that can unpack an element to form (potentially multiple) elements. One of the simplest examples of a coalgebra are comonoids in the category of sets given by duplication and deletion. Given a set $A$ and an element $a \in A$, we can "unpack" $a$ to form an element of $A \times A$ by simply copying it: $(a,a)$, thus unpacking $a$ into two elements of $A$. Likewise, we can "unpack" $a$ into an element of the terminal set $\mathbf{1}$ simply by forgetting about $a$ entirely, thus unpacking $a$ into zero elements of $A$.

The unit interval is a coalgebra in the following sense. It is a set with two distinguished points, $\bot$ (the number $0$) and $\top$ (the number $1$). It supports a "split" operation which splits the unit interval into two subintervals, one subinterval from $0$ to $\frac12$, and one subinterval from $\frac12$ to $1$. This splitting operation unpacks a single point in the interval into either a point in the left subinterval or a point in the right subinterval. (If we're plugging in $\frac12$, things get more tricky, as it is a member of both subintervals.) Each subinterval is isomorphic to the unit interval itself, and we can continue the splitting process ad infinitum.

In more detail (see the nLab page or the fourth page of Freyd's paper), let $\textnormal{Set}_{**}$ be the category whose objects are sets with two distinguished elements (i.e. bipointed sets), $\bot$ and $\top$ and whose morphisms are functions which preserve these distinguished elements. If $X$ and $Y$ are bipointed sets, then we can define their ordered wedge $X \vee Y$ by taking the disjoint union of the two sets and identifying the top of $X$ with the bottom of $Y$. Then the unit interval is a terminal coalgebra for the cofunctor $X \mapsto X \vee X$. A coalgebra for this endofunctor consists of a map $X \to X \vee X$, which is the splitting operation mentioned in the above paragraph.

Ralph Sarkis (Aug 31 2023 at 20:18):

Very quickly thinking about this, I see how $\mathbb Q \cap [0,1]$ cannot be final because there is no morphism $[0,1] \to \mathbb Q \cap [0,1]$ that can factor through all other morphisms (because of cardinality), but I don't see how we can reject some version of the interval that has even more things in it, call it $\mathsf{SSJ}[0,1]$, and that would lead to the same problem (cardinality) that there is no morphism $\mathsf{SSJ}[0,1] \to [0,1]$ that factors through all other morphisms.

John Baez (Aug 31 2023 at 20:34):

This point is confusing to me too, Ralph. This reminds me of a probably unrelated fact: in ZFC there is no nontrivial upper bound on the cardinality of the continuum. That is, we can show $c < 2^c$ and various "trivial" upper bounds, but we can't show something like $c < \aleph_{\aleph_{\aleph_{17}}}$, or even much weaker "nontrivial" upper bounds.

John Baez (Aug 31 2023 at 20:38):

For more precise statements of this point see the answers here:

• How far wrong could the Continuum Hypothesis be?

John Baez (Aug 31 2023 at 20:39):

But I doubt this stuff is directly relevant to your question about why [0,1] is final!

Spencer Breiner (Aug 31 2023 at 22:08):

I think the idea is that many of those elements in the larger cardinality set would be indistinguishable by splitting, so the homomorphism could them map them to the same real number (binary sequence)

Mike Shulman (Sep 01 2023 at 01:59):

Right. And I wouldn't say that the non-terminality of $\mathbb{Q} \cap [0,1]$ is for cardinality reasons; rather it's because there are elements of $[0,1]$ (irrational ones) whose behavior under splitting can't be captured by any rational.

Ralph Sarkis (Sep 01 2023 at 05:23):

How are the irrational numbers different (in that context) from the rationals with denominators which are not powers of two ?

Cardinality is not the reason, it is what makes the proof work for $\mathbb Q$, but I don't get why it does not work after that.

I guess this is related to the fact that when iterating an endofunctor to find its initial/final (co)algebra, you only need $\omega$ iterations in "good" cases.

Nathaniel Virgo (Sep 01 2023 at 06:44):

Rational numbers (even with denominators that are not powers of two) map to cyclic sequences, e.g.

• $\frac{2}{3}$ is in the interval $[\frac{1}{2},1]$ and it maps back to $2\cdot\frac{2}{3} -1 = \frac{1}{3}$.

• $\frac{1}{3}$ is in the interval $[0,\frac{1}{2}]$ and it maps back to $2\cdot \frac{1}{3} = \frac{2}{3}$.

so $2/3$ maps to the real number (in binary) $0.1010101\dots$. Irrational numbers have nonrepeating binary expansions, so the splitting process ends up not repeating.

Mike Shulman (Sep 01 2023 at 16:45):

If you're familiar with coinductive definitions, you can think of this as saying that the unit interval is like the type of coinductive infinite streams of bits, quotiented by the relation that a tail of $0111111\dots$ anywhere is equivalent to $1000000\dots$.

Madeleine Birchfield (Feb 02 2024 at 21:05):

Are the reals the terminal linearly ordered set $(R, \lt)$ in which the rational numbers $(\mathbb{Q}, \lt)$ are a linearly ordered subset of $R$ and are dense in $R$, in the sense that for all elements $x \in R$ and $y \in R$ there exists $q \in \mathbb{Q}$ such that $x \lt q \lt y$?

John Baez (Feb 02 2024 at 21:10):

I don't think so: there are many different real closed fields that are linearly ordered fields in which the reals are dense.

John Baez (Feb 02 2024 at 21:12):

Here's something about those:

• Wikipedia, Hyperreal number.

John Baez (Feb 02 2024 at 21:14):

And here's more:

• Wikipedia, Real closed field.

Reid Barton (Feb 02 2024 at 21:16):

The reals aren't dense in the hyperreals though, in the above sense. For instance, between two positive infinitesimals there aren't any real numbers.

John Baez (Feb 02 2024 at 21:16):

Not all real closed fields contain $\mathbb{R}$, for example the algebraic reals or computable reals are subfields of $\mathbb{R}$, but there are plenty that properly contain $\mathbb{R}$.

Reid Barton (Feb 02 2024 at 21:16):

I think there is a problem with $\pm \infty$, but the statement might be true if fixed to take that into account.

John Baez (Feb 02 2024 at 21:17):

Reid Barton said:

The reals aren't dense in the hyperreals though, in the above sense. For instance, between two positive infinitesimals there aren't any real numbers.

Whoops. And of course Madeleine wanted something even stronger, namely that the rationals are dense.

John Baez (Feb 02 2024 at 21:18):

So I take back my claim.

John Baez (Feb 02 2024 at 21:20):

Now I'm thinking Madeleine could be right. At least I don't see how to embed the reals in a larger linearly ordered set in which the rationals are dense.

John Baez (Feb 02 2024 at 21:22):

Maybe the Dedekind cut construction can be used to prove her conjecture?

Reid Barton (Feb 02 2024 at 21:22):

The proof should basically be that the only possible map $R \to \mathbb{R}$ is the one that, given $r \in R$, records which rational numbers $r$ is greater than/less than in $R$, and produces the corresponding Dedekind real. So whatever hypotheses are needed to make that work should give the right statement. (E.g. restrict attention to unbounded orders, or require that the image of $\mathbb{Q}$ is "unbounded" in a similar sense to the sense in which it is dense.)

David Michael Roberts (Feb 03 2024 at 01:12):

Isn't the density of the rationals linked to having the Archimedean property? Since it means that for every epsilon > 0, there is some rational between 0 and epsilon, say M/N, and so 1/N is less than epsilon. And the reals are the (unique) terminal Archimedean (ordered) field.

David Michael Roberts (Feb 03 2024 at 01:15):

Hmm, even though you are interested in the terminal linearly ordered set, not ordered field, the latter condition seems enough:

https://ncatlab.org/nlab/show/Archimedean+ordered+field#using_field_homomorphisms_from_the_rationals

Here Archimedieanness is exactly defined as your density condition.

Madeleine Birchfield (Feb 03 2024 at 03:16):

Reid Barton said:

I think there is a problem with $\pm \infty$, but the statement might be true if fixed to take that into account.

You're right. There is no abelian group structure on arbitrary linearly ordered sets which serve to banish the two infinities. I suppose it suffices to add the restriction that every element $x \in F$ is bounded by rational numbers $q, r \in \mathbb{Q}$, where $q \lt x \lt r$.

Alternatively, Nathanael Virgo asked about the universal property of the reals or extended reals, so my original statement could be used as the universal property of the extended reals if the one for (non-extended) reals is true.

Nathaniel Virgo said:

Consider the reals or the extended reals as a preorder. (Equivalently the open or closed unit interval.) Do either of these objects have a nice universal property in the category of preorders? (Or in Cat, come to think of it.)