#### Howdy, Stranger!

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

Options

# Exercises and Puzzles 4 - Chapter 1

edited May 2018

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:

1. Setting $$x \leq y$$ if and only if $$x = y$$ gives you a preorder on $$X$$, called the discrete preorder.

2. 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?

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.

• Options
1.
edited April 2018

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. 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.

Comment Source:> **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.
• Options
2.
edited April 2018

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.

Comment Source:> 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.
• Options
3.

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.

Comment Source: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.
• Options
4.
edited April 2018

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.

Comment Source: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.
• Options
5.
edited April 2018

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.

Comment Source:<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. 
• Options
6.

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.

Comment Source: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_.
• Options
7.
edited April 2018

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$$.

Comment Source: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\$$. 
• Options
8.
edited April 2018
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.

Comment Source:>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.
• Options
9.
edited April 2018

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.

Comment Source: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). 
• Options
10.
edited April 2018

Is the codiscrete preorder equivalent to a complete graph?

Comment Source:Is the codiscrete preorder equivalent to a complete graph?
• Options
11.

Yes.

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

Comment Source:Yes. In general, graphs of symmetric preorders have the following property: all of their connected components are completely connected.
• Options
12.

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.

Comment Source: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.
• Options
13.
edited April 2018

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.

Comment Source: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.
• Options
14.
edited April 2018

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.

Comment Source: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.
• Options
15.
edited April 2018

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$$

Comment Source: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$$
• Options
16.
edited April 2018

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:

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 part of your partition.

Comment Source: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.