It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.4K
- Chat 502
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 75
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 718

Options

More exercises!

Here are some very important, very basic posets:

One topic from the book I didn't discuss is how we get partitions of a set \(S\) from surjective functions \(f: S \to T\). The basic idea is simple: for each element \(t \in T\) we get one part of our partition, namely the set of all elements that map to \(t\). Here is an exercise to check that you understand this:

Daniel Cicala gave two interesting "degenerate" examples of preorders. Take your favorite set \(X\). Then:

Setting \(x \leq y\) if and only if \(x = y\) gives you a preorder on \(X\), called the

**discrete**preorder.Setting \(x \leq y \) for all \(x,y \in X\) gives you a preorder on \(X\), called the

**codiscrete**preorder.

This led to some puzzles:

**Puzzle 8.** What simple law do Daniel's preorders obey, that does not hold for the real numbers with its usual notion of \(\leq\)?

**Puzzle 9.** What do you call preorders that obey this law?

For answers go here.

And here's an inexhaustible puzzle:

**Puzzle 10.** There are many examples of monotone maps between posets. List a few interesting ones!

You can see some examples in the comments on Lecture 3 starting here.

To see *all* the exercises in Chapter 1, go here.

## Comments

Hopefully preorders are okay.

Consider the set of logical propositions in arithmetic \(\mathcal{L}\). Pick a particular axiomatization of arithmetic \(A\), such as the Peano axioms. We can write "\(A\) proves \(\phi\)" with the shorthand \(\vdash_A \phi\). We can induce a partial order on these via the material conditional. For instance:

$$ \vdash_A (x = y + 1 \, \textrm{and} \, y = 4) \to x = 5 $$ So \( (x = y + 1 \, \textrm{and} \, y = 4) \leq_A x = 5\).

There is a somewhat famous function \(\mathrm{Bew}_A : \mathcal{L} \to \mathcal{L}\) that makes true:

$$ \text{if } \vdash_A \phi \text{ then } \vdash_A \mathrm{Bew}_A (\phi ) $$ This function was invented by Kurt Gödel (1931). The construction is rather intricate.

\(\mathrm{Bew}_A\) is a monotone map on \(\mathcal{L}\) ordered by \(\leq_A\). That is:

$$ \phi \leq_A \psi \text{ implies } \mathrm{Bew}_A (\phi ) \leq_A \mathrm{Bew}_A (\psi ) $$ There's a lot more to say about \(\mathrm{Bew}_A\), of course. I feel it is a nice example of an exotic monotone map.

`> **Puzzle 10.** There are many examples of monotone maps between posets. List a few interesting ones! Hopefully preorders are okay. Consider the set of logical propositions in arithmetic \\(\mathcal{L}\\). Pick a particular axiomatization of arithmetic \\(A\\), such as the [Peano axioms](https://en.wikipedia.org/wiki/Peano_axioms). We can write "\\(A\\) proves \\(\phi\\)" with the shorthand \\(\vdash_A \phi\\). We can induce a partial order on these via the [material conditional](https://en.wikipedia.org/wiki/Material_conditional). For instance: $$ \vdash_A (x = y + 1 \, \textrm{and} \, y = 4) \to x = 5 $$ So \\( (x = y + 1 \, \textrm{and} \, y = 4) \leq_A x = 5\\). There is a somewhat famous function \\(\mathrm{Bew}_A : \mathcal{L} \to \mathcal{L}\\) that makes true: $$ \text{if } \vdash_A \phi \text{ then } \vdash_A \mathrm{Bew}_A (\phi ) $$ This function was invented by [Kurt Gödel (1931)](https://books.google.com/books?id=0R9oDmaqmNUC&lpg=PA37&lr&pg=PA37#v=onepage&q). The construction is rather intricate. \\(\mathrm{Bew}_A\\) is a monotone map on \\(\mathcal{L}\\) ordered by \\(\leq_A\\). That is: $$ \phi \leq_A \psi \text{ implies } \mathrm{Bew}_A (\phi ) \leq_A \mathrm{Bew}_A (\psi ) $$ There's a lot more to say about \\(\mathrm{Bew}_A\\), of course. I feel it is a nice example of an exotic monotone map.`

We can always quotient over equivalence to obtain a poset. I think this is what's called the "skeleton" of a category.

Puzzle JMC6:Let \(P, Q\) be preorders, and let \(f : P \to Q\) be a monotone map. Let \(P', Q'\) be the respective posets obtained by identifying all elements \(x, y\) where \(x \le y \land y \le x\). An element of \(P'\) is therefore an equivalence class \([x] = \{y | x \le y \land y \le x\}\). Prove that \(f'([x]) = [f(x)]\) is a well-defined monotone map between \(P'\) and \(Q'\).So any monotone map over preorders lifts to a monotone map over their induced posets.

`> Hopefully preorders are okay. We can always quotient over equivalence to obtain a poset. I think this is what's called the "skeleton" of a category. **Puzzle JMC6:** Let \\(P, Q\\) be preorders, and let \\(f : P \to Q\\) be a monotone map. Let \\(P', Q'\\) be the respective posets obtained by identifying all elements \\(x, y\\) where \\(x \le y \land y \le x\\). An element of \\(P'\\) is therefore an equivalence class \\([x] = \\{y | x \le y \land y \le x\\}\\). Prove that \\(f'([x]) = [f(x)]\\) is a well-defined monotone map between \\(P'\\) and \\(Q'\\). So any monotone map over preorders lifts to a monotone map over their induced posets.`

Hey Jon,

In logic, the induced poset you mention has an old name. For a theory T, it is the Lindenbaum-Tarski algebra for T.

Provability is a rather confusing topic. As I was writing the above I was struggling to remember the formulation. It is hard not to butcher the subject. So I apologize for my clumsy presentation.

`Hey Jon, In logic, the induced poset you mention has an old name. For a theory T, it is the [Lindenbaum-Tarski algebra](https://en.m.wikipedia.org/wiki/Lindenbaum%E2%80%93Tarski_algebra) for T. Provability is a rather confusing topic. As I was writing the above I was struggling to remember the formulation. It is hard not to butcher the subject. So I apologize for my clumsy presentation.`

Neat! It's a common technique across a lot of different fields -- in graph theory for instance, the equivalence classes are called "strongly connected components", and we can collapse a directed graph into a graph on its components. I shouldn't be surprised that this construction has a distinguished name in logic. :)

My point was just to justify your choice of working with the preorder on propositions. The example you give can be lifted to a monotone map, so regardless of whether John expects strictly posets or any preorder, your example still applies in some fashion.

`Neat! It's a common technique across a lot of different fields -- in graph theory for instance, the equivalence classes are called "strongly connected components", and we can collapse a directed graph into a graph on its components. I shouldn't be surprised that this construction has a distinguished name in logic. :) My point was just to justify your choice of working with the preorder on propositions. The example you give can be lifted to a monotone map, so regardless of whether John expects strictly posets or any preorder, your example still applies in some fashion.`

Nice stuff, Jonathan!

Right!

It's a very similar concept, but a bit different.

To get a

skeletonof a category \(C\) we choose one representative of each isomorphism class of objects in \(C\) , and create a new category \(\mathrm{Sk}(C)\) with just these representatives as objects, and all the morphisms in \(C\) between these objects. \(\mathrm{Sk}(C)\) is a subcategory of \(C\).One might try instead to take quotient, forming a category whose objects are isomorphism classes of objects of \(C\). But this fails miserably, because composition of morphisms in this would-be category turns out to be undefined...

...except when \(C\) is a preorder!In this case the quotient construction actually gives a well-defined poset, and this poset is isomorphic to any skeleton of \(C\).So, I wouldn't call the thing you're forming the skeleton, but it's isomorphic to the skeleton, so this is a very nitpicky point, which I only mention for one reason: the true skeleton has the advantage of working for general categories.

Metaphorically speaking: your skeleton sits inside your body, so it's like a subcategory of your body, not a quotient category.

`<img width = "150" src = "http://math.ucr.edu/home/baez/mathematical/warning_sign.jpg"> Nice stuff, Jonathan! > We can always quotient over equivalence to obtain a poset. Right! > I think this is what's called the "skeleton" of a category. It's a very similar concept, but a bit different. To get a **skeleton** of a category \\(C\\) we choose one representative of each isomorphism class of objects in \\(C\\) , and create a new category \\(\mathrm{Sk}(C)\\) with just these representatives as objects, and all the morphisms in \\(C\\) between these objects. \\(\mathrm{Sk}(C)\\) is a subcategory of \\(C\\). One might try instead to take quotient, forming a category whose objects are isomorphism classes of objects of \\(C\\). But this fails miserably, because composition of morphisms in this would-be category turns out to be undefined... _...except when \\(C\\) is a preorder!_ In this case the quotient construction actually gives a well-defined poset, and this poset is isomorphic to any skeleton of \\(C\\). So, I wouldn't call the thing you're forming the skeleton, but it's isomorphic to the skeleton, so this is a very nitpicky point, which I only mention for one reason: the true skeleton has the advantage of working for general categories. Metaphorically speaking: your skeleton sits inside your body, so it's like a subcategory of your body, not a quotient category.`

Ah, I think I see. Somehow the fact that preorders don’t distinguish between ways that objects can be related avoids the question of what the composition of two arrows is — all that’s neccessary is to know that they are related

at all.`Ah, I think I see. Somehow the fact that preorders don’t distinguish between ways that objects can be related avoids the question of what the composition of two arrows is — all that’s neccessary is to know that they are related _at all_.`

Exactly! A preorder is exactly the same as a category where there's at most one morphism \(f : x \to y\) for any pair of objects \(x,y\), and this makes it possible to define morphisms between

isomorphism classesof objects without arbitrary choices gumming up the works.You expressed the idea here more succinctly and clearly. But everyone who learns category theory must at some point try to form the quotient you described to see exactly how it fails to give a well-defined category...

except for preorders- or more generally, I now realize, for categories where there's at most one isomorphism \(f : x \to y\) for any pair of objects \(x,y\).`Exactly! A preorder is exactly the same as a category where there's at most one morphism \\(f : x \to y\\) for any pair of objects \\(x,y\\), and this makes it possible to define morphisms between _isomorphism classes_ of objects without arbitrary choices gumming up the works. You expressed the idea here more succinctly and clearly. But everyone who learns category theory must at some point try to form the quotient you described to see exactly how it fails to give a well-defined category... _except for preorders_ - or more generally, I now realize, for categories where there's at most one isomorphism \\(f : x \to y\\) for any pair of objects \\(x,y\\).`

Symmetry.

A set. (Or if you're William Lawvere, the discrete and codiscrete preorders)

Any functor between categories produces a monotone map when the underlying categories are turned into posets.

Generalizing, any n-transfor between n-categories becomes a monotone map when the underlying n-categories are turned into posets.

`>1. Setting \\(x \leq y\\) if and only if \\(x = y\\) gives you a preorder on \\(X\\). 2. Setting \\(x \leq y \\) for all \\(x,y \in X\\) gives you a preorder on \\(X\\). >This led to some puzzles: >**Puzzle 8.** What simple law do Daniel's preorders obey, that does not hold for the real numbers with its usual notion of \\(\leq\\)? Symmetry. >**Puzzle 9.** What do you call preorders that obey this law? A set. (Or if you're William Lawvere, the discrete and codiscrete preorders) >**Puzzle 10.** There are many examples of monotone maps between posets. List a few interesting ones! Any functor between categories produces a monotone map when the underlying categories are turned into posets. Generalizing, any n-transfor between n-categories becomes a monotone map when the underlying n-categories are turned into posets.`

Keith - you got Puzzle 8 right: the

symmetrylaw is$$ x \le y \text{ if and only if } y \le x $$ and this law is obeyed by both

discretepreorder (where \(x \le y\) iff \(x = y\)) and thecodiscretepreorder (where \(x \le y\) for all \(x , y\)).However, many other preorders also obey the symmetry law. A preorder that obeys the symmetry axiom has a special name. Puzzle 9 asks for this name. Matthew Doty revealed the answer here.

`Keith - you got Puzzle 8 right: the **symmetry** law is $$ x \le y \text{ if and only if } y \le x $$ and this law is obeyed by both **discrete** preorder (where \\(x \le y\\) iff \\(x = y\\)) and the **codiscrete** preorder (where \\(x \le y\\) for all \\(x , y\\)). However, many other preorders also obey the symmetry law. A preorder that obeys the symmetry axiom has a special name. Puzzle 9 asks for this name. Matthew Doty revealed the answer [here](https://forum.azimuthproject.org/discussion/comment/16145/#Comment_16145).`

Is the codiscrete preorder equivalent to a complete graph?

`Is the codiscrete preorder equivalent to a complete graph?`

Yes.

In general, graphs of symmetric preorders have the following property: all of their connected components are completely connected.

`Yes. In general, graphs of symmetric preorders have the following property: all of their connected components are completely connected.`

So then an equivalence relation on \( n \) elements that is not discrete can be modelled as (up to equivalence) a complete graph on \( n \) nodes.

`So then an equivalence relation on \\( n \\) elements that is not discrete can be modelled as (up to equivalence) a complete graph on \\( n \\) nodes.`

Or a disjoint union of complete graphs. Consider the equivalence relation identifying all numbers \(\{2^i \mid i \in \mathbb{N}\}\) and leaving all others equivalent only to themselves. This gives a(n infinite) complete graph in a sea of trivial complete graphs.

`Or a disjoint union of complete graphs. Consider the equivalence relation identifying all numbers \\(\\{2^i \mid i \in \mathbb{N}\\}\\) and leaving all others equivalent only to themselves. This gives a(n infinite) complete graph in a sea of trivial complete graphs.`

I don't quite get your construction Jonathan, can you be a bit more explicit on what exactly is being done?

On a side note:

ExtendingJohn Baez's Liberal-Conservative metaphor for adjoints, one could think ofdiscretepreorders as being likeindividualismwhere people keep to themselves, while thecodiscretepreorder is likecollectivismwhere people act as a singular whole.`I don't quite get your construction Jonathan, can you be a bit more explicit on what exactly is being done? On a side note: *Extending* John Baez's Liberal-Conservative metaphor for adjoints, one could think of **discrete** preorders as being like **individualism** where people keep to themselves, while the **codiscrete** preorder is like **collectivism** where people act as a singular whole.`

I'll demonstrate a partition on the natural numbers. Partitions are in one-to-one correspondence with equivalence relations (the parts are the equivalence classes), and equivalence relations correspond with graphs where \(x = y\) iff we have edges \(x \to y \land y \to x\).

Here's the partition: $$P = \{\{2^i : i \in \mathbb{N}\}\} \cup \{\{i\} : 2 \textrm{ does not divide } i\}$$ As an equivalence relation: $$x \sim y \Leftrightarrow x = 2^a \land y = 2^b$$

`I'll demonstrate a partition on the natural numbers. Partitions are in one-to-one correspondence with equivalence relations (the parts are the equivalence classes), and equivalence relations correspond with graphs where \\(x = y\\) iff we have edges \\(x \to y \land y \to x\\). Here's the partition: $$P = \{\{2^i : i \in \mathbb{N}\}\} \cup \{\{i\} : 2 \textrm{ does not divide } i\}$$ As an equivalence relation: $$x \sim y \Leftrightarrow x = 2^a \land y = 2^b$$`

Keith wrote:

Jonathan wrote:

Right. There are lots of different equivalence relations on an \(n\)-element set. They correspond to

partitionsof the \(n\)-element set. For \(n = 5 \) we have 52 of them:We discussed the correspondence between equivalence relations and partitions in Lecture 10.

If you prefer to think of equivalence relations as graphs, they are disjoint unions of complete graphs. Just draw a complete graph on each

partof your partition.`Keith wrote: > So then an equivalence relation on \\(n\\) elements that is not discrete can be modelled as (up to equivalence) a complete graph on \\(n\\) nodes. Jonathan wrote: > Or a disjoint union of complete graphs. Right. There are lots of different equivalence relations on an \\(n\\)-element set. They correspond to _partitions_ of the \\(n\\)-element set. For \\(n = 5 \\) we have 52 of them: <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/partitions_of_5.png"></center> We discussed the correspondence between equivalence relations and partitions in [Lecture 10](https://forum.azimuthproject.org/discussion/1963/lecture-10-the-logic-of-partitions#Head). If you prefer to think of equivalence relations as graphs, they are disjoint unions of complete graphs. Just draw a complete graph on each _part_ of your partition.`