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

- All Categories 2.3K
- Chat 493
- ACT Study Group 5
- Azimuth Math Review 6
- MIT 2020: Programming with Categories 53
- MIT 2020: Lectures 21
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 337
- MIT 2019: Lectures 27
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 64
- Azimuth Code Project 110
- Drafts 1
- Math Syntax Demos 15
- Wiki - Latest Changes 1
- Strategy 110
- Azimuth Project 1.1K

Options

I've been explaining how we can create a version of logic starting from any poset, which we think of as a poset of "propositions". There are various ways to get our hands on such a poset. One way is to start with a set \( X \) and build a poset \( P X \) whose elements are subsets of \( X \). This leads to the most traditional form of logic, called classical logic. But another way is to start with a set \( X \) and build a poset \( \mathcal{E}(X) \) whose elements are "partitions" of \( X \). This leads to another form of logic, called the logic of partitions.

What's a partition? It's a way of chopping the set \( X \) into "parts". We want each part to be a nonempty subset of \( X \), we want these parts to be disjoint, and we want their union to be all of \( X \). For example, here are all 52 partitions of a set with 5 elements:

At the top we see the "coarsest" partition, where all 5 elements are in the same part. At the bottom we see the "finest" partition, where each element is in its own separate part.

How can we think of these partitions as "propositions"? Here's how: each partition gives a proposition saying that two elements in the same part are "equivalent", or the same in some way. The coarser the partition, the more elements are equivalent.

For example, imagine you're a detective trying to solve a case on a small island with 5 people on it. At first you don't know any of them are related, so they're all in separate families, as far as you know:

But then you start digging into their history. Each time you learn that two people are related, you change your partition by putting them into the same part:

You keep doing this as secret family relationships are revealed:

In this example, as you learn more you move to *coarser* partitions, because your goal is to find relationships between people, and lump them in as big bunches as possible. But often people think about partition logic a bit differently, where as you learn more you move to *finer* partitions.

Suppose you are an amateur wine taster learning to distinguish different kinds of wine by their taste. At first all wines taste alike, so they're all lumped together:

When you learn to distinguish red and white wines, you move to a finer partition:

This sort of example will fit our story a bit better. We'll generally say that you know more if your partition is *finer*.

Now it's time to define partitions more carefully! A partition of \(X\) is a bunch of subsets of \(X\). So, it's a subset of \(P(X)\). Please think about that until it makes sense, or ask questions. There are a lot of sets and subsets running around: it can be confusing. But here we go:

**Definition.** A **partition** of a set \(X\) is a set \(P \subseteq P(X)\) such that:

Each set \(S \in P \) is nonempty.

Distinct sets \(S, T \in P\) are disjoint: that is, if \(S \ne T\) then \(S \cap T = \emptyset \).

The union of all the sets \(S \in P\) is \(X\): that is,

$$ X = \bigcup_{S \in P} S .$$
We call the sets \(S \in P\) the **parts** of the partition.

I said that each partition \(P\) gives an equivalence relation, where two elements of \(X\) are "equivalent" if and only if they're in the same part. Let's make that precise too:

**Definition.** An **equivalence relation** on a set \(X\) is a relation \(\sim\) on \(X\) that is:

**Reflexive:**for all \(x \in X\), \(x \sim x\).**Transitive:**for all \(x,y,z \in Z\), \(x \sim y \) and \(y \sim z\) imply \(x \sim z\).**Symmetric:**for all \(x,y \in X\), \(x \sim y\) implies \(y \sim x.\)

**Puzzle 28.** Show that if \(P\) is a partition of a set \(X\), and we define a relation \(\sim_P\) on \(X\) as follows:

$$ x \sim_P y \textrm{ if and only if } x, y \in S \textrm{ for some } S \in P, $$ then \(\sim_P \) is an equivalence relation.

**Puzzle 29.** Show that if \(\sim\) is an equivalence relation on a set \(X\), we can define a partition \(P_\sim\) on \(X\) whose parts are precisely the sets of the form

$$ S_x = \{y \in X : \; y \sim x \} $$
with \(x \in X\). We call \(S_x\) the **equivalence class** of \(x\).

**Puzzle 31.** Show that the previous two puzzles give a one-to-one correspondence between partitions of \(X\) and equivalence relations on \(X\).

**Puzzle 32.** Proposition 1.11 of *Seven Sketches* asserts that there is a one-to-one correspondence between partitions of \(X\) and equivalence relations on \(X\). However, in the current version of the book this proposition is false! Nonetheless, the statement in Puzzle 31 is correct. How is this possible? (Hint: you have to read their definitions quite carefully. This is good practice in reading mathematics.)

**Puzzle 33.** Is an equivalence relation always a preorder?

## Comments

## Puzzle 28

Show that if \(P\) is a partition of a set \(X\), and we define a relation \(\sim_P\) on \(X\) as follows:

$$ x \sim_P y \textrm{ if and only if } x, y \in S \textrm{ for some } S \in P $$ then \(\sim_P \) is an equivalence relation.

To be an equivalence relation we must satisfy the 3 parts of the definition:

## Reflexive

For all \(x \in X\), there exists \(S \in P\) s.t. \(x \in S\). This follows from part 3 of the definition of partitions of a set. By the definition of \(\sim_P\) then \(x \sim_P x\).

## Transitive

Let \(x,y,z \in X\) and assume \(x \sim_P y \wedge y \sim_P z\).

\(x \sim_P y\) implies \(x,y \in S_1\). \(y \sim_P z\) implies \(y,z \in S_2\).

Since every element of \(P\) is pairwise disjoint, either \(S_1 \cap S_2 = \emptyset\) or \(S_1 = S_2\). The intersection is non-empty (contains at least \(y\)). So the second case must be true.

\(x,z \in S_1 = S_2\) implies \(x \sim_P z\) by the definition of \(\sim_P\). Therefore, \(\sim_P\) is transitive.

## Symmetric

Given \(x\sim_P y\) for \(x,y \in X\), there exists \(S \subseteq X\) s.t. \(S \in P\) and \(x,y \in S\). \(y \sim_P x\) follows from the definition of \(\sim_P\).

Given that \(\sim_P\) is reflixive, transitive, and symmetric then we can conclude that it is an equivalence relation.

`#Puzzle 28 Show that if \\(P\\) is a partition of a set \\(X\\), and we define a relation \\(\sim_P\\) on \\(X\\) as follows: $$ x \sim_P y \textrm{ if and only if } x, y \in S \textrm{ for some } S \in P $$ then \\(\sim_P \\) is an equivalence relation. *** To be an equivalence relation we must satisfy the 3 parts of the definition: ##Reflexive For all \\(x \in X\\), there exists \\(S \in P\\) s.t. \\(x \in S\\). This follows from part 3 of the definition of partitions of a set. By the definition of \\(\sim_P\\) then \\(x \sim_P x\\). ##Transitive Let \\(x,y,z \in X\\) and assume \\(x \sim_P y \wedge y \sim_P z\\). \\(x \sim_P y\\) implies \\(x,y \in S_1\\). \\(y \sim_P z\\) implies \\(y,z \in S_2\\). Since every element of \\(P\\) is pairwise disjoint, either \\(S_1 \cap S_2 = \emptyset\\) or \\(S_1 = S_2\\). The intersection is non-empty (contains at least \\(y\\)). So the second case must be true. \\(x,z \in S_1 = S_2\\) implies \\(x \sim_P z\\) by the definition of \\(\sim_P\\). Therefore, \\(\sim_P\\) is transitive. ##Symmetric Given \\(x\sim_P y\\) for \\(x,y \in X\\), there exists \\(S \subseteq X\\) s.t. \\(S \in P\\) and \\(x,y \in S\\). \\(y \sim_P x\\) follows from the definition of \\(\sim_P\\). Given that \\(\sim_P\\) is reflixive, transitive, and symmetric then we can conclude that it is an equivalence relation.`

Re

puzzle 32:The big difference between your definition and the one in Seven Sketches is that in your definition every element of \(P\)

isa subset of \(X\), whereas in Seven Sketches every element of \(P\)labelsa subset of \(X\).The Seven Sketches definition allows you to permute the labels and still get essentially the same partition (ie the same equivalence relationship). Or even switch the set of labels for another set entirely, providing you do this sensibly (ie distinct old labels get replaced with distinct new ones). So it's no longer one-to-one exactly.

`Re **puzzle 32**: The big difference between your definition and the one in Seven Sketches is that in your definition every element of \\(P\\) _is_ a subset of \\(X\\), whereas in Seven Sketches every element of \\(P\\) _labels_ a subset of \\(X\\). The Seven Sketches definition allows you to permute the labels and still get essentially the same partition (ie the same equivalence relationship). Or even switch the set of labels for another set entirely, providing you do this sensibly (ie distinct old labels get replaced with distinct new ones). So it's no longer one-to-one exactly.`

Nice, Jared!

I'm hoping someone will dare to tackle the other puzzles. Puzzle 32, in particular, requires finding a mistake in one of Fong and Spivak's definitions.

`Nice, Jared! I'm hoping someone will dare to tackle the other puzzles. Puzzle 32, in particular, requires finding a mistake in one of Fong and Spivak's definitions.`

Here is my slightly verbose solution to

puzzle 29. I'm proving the three properties from the definition of "partition".Each part is non-empty.For any \(x \in X\), the corresponding part \(S_x\) has at least one element: \(x \in S_x\) since \(x \sim x\) (the equivalence relation is reflexive).Distinct parts are disjoint.For any \(x, y \in X\), we show that the corresponding parts, \(S_x\) and \(S_y\), are either the same set, \(S_x = S_y\), or they are disjoint sets, \(S_x \cap S_y = \emptyset\):The union of all the parts is the entire set.Any \(y \in X\) belongs to the union of all the parts, \(\bigcup_{x \in X} S_x\), because \(x \in S_x\) (as we have seen in the first bullet point) and we are iterating over all \(x \in X\).Edit: I think I should have started by showing that the partition, \(\left\{S_x\right\}_{x \in X}\), is included in the power set \(P(X)\), that is, \(S_x \subseteq X\) (this can be seen from the definition of \(S_x\)).

`Here is my slightly verbose solution to **puzzle 29**. I'm proving the three properties from the definition of "partition". - _Each part is non-empty._ For any \\(x \in X\\), the corresponding part \\(S_x\\) has at least one element: \\(x \in S_x\\) since \\(x \sim x\\) (the equivalence relation is reflexive). - _Distinct parts are disjoint._ For any \\(x, y \in X\\), we show that the corresponding parts, \\(S_x\\) and \\(S_y\\), are either the same set, \\(S_x = S_y\\), or they are disjoint sets, \\(S_x \cap S_y = \emptyset\\): 1. Consider there exists a common element \\(z\\), that is, \\(z \in S_x\\) and \\(z \in S_y\\). Then for any \\(x' \in S_x\\), we have \\(x' \sim x\\). We also know that \\(z \sim x\\) (since \\(x \in S_x\\)) and by using the symmetry and transitivity of the equivalence relation, we get that \\(z \sim x'\\). But \\(z \sim y\\) (since \\(z \in S_y\\)), and using again the symmetry and transitivity properties, we get that \\(x' \sim y\\), that is, \\(x' \in S_y\\). Hence, \\(S_x = S_y\\). 2. There is no common element; hence, the parts are disjoint. - _The union of all the parts is the entire set._ Any \\(y \in X\\) belongs to the union of all the parts, \\(\bigcup_{x \in X} S_x\\), because \\(x \in S_x\\) (as we have seen in the first bullet point) and we are iterating over all \\(x \in X\\). Edit: I think I should have started by showing that the partition, \\(\left\\{S_x\right\\}_\{x \in X\}\\), is included in the power set \\(P(X)\\), that is, \\(S_x \subseteq X\\) (this can be seen from the definition of \\(S_x\\)).`

Re

puzzle 33Every equivalence relation is reflexive and transitive by definition and these two properties define a preorder. Being symmetric is a further constraint, but it does not affect neither reflexivity nor transitivity (no idea how to proof this statement formally). So yes every equivalence relation is a preorder.

`Re **puzzle 33** Every equivalence relation is reflexive and transitive by definition and these two properties define a preorder. Being symmetric is a further constraint, but it does not affect neither reflexivity nor transitivity (no idea how to proof this statement formally). So yes every equivalence relation is a preorder.`

Re

puzzle 32There is a difference in defining symmetry.

In the lecture: for all \(x,y \in X\), \(x \sim y\) implies \(y \sim x.\)

In the book (definition 1.8): \(a \sim b\) iff \(b \sim a\), for all \(a,b \in A\)

Implication is weaker than

iff, but to be honest I am not sure if this is the root cause of the problem, as for me theyfeel...equivalentin this particular case. :-O`Re **puzzle 32** There is a difference in defining symmetry. In the lecture: for all \\(x,y \in X\\), \\(x \sim y\\) implies \\(y \sim x.\\) In the book (definition 1.8): \\(a \sim b\\) iff \\(b \sim a\\), for all \\(a,b \in A\\) Implication is weaker than *iff*, but to be honest I am not sure if this is the root cause of the problem, as for me they *feel*... *equivalent* in this particular case. :-O`

That diagram of partitions of a set with 5 elements i first guessed would be 256=2^5. (but you are 'coarse graining ' those--similar to difference between identical and indistinguishable particles and identical and distinguishable particle--seperates bose-einstein from boltzmannn statistics).

But those are 'Bell numbers' (B(5)=52 -reminds me of a b52--a band and a plane). I'm not sure there is a 'closed form solution' except as an approximation. You compute those recursively--need a calculator or computer.

`That diagram of partitions of a set with 5 elements i first guessed would be 256=2^5. (but you are 'coarse graining ' those--similar to difference between identical and indistinguishable particles and identical and distinguishable particle--seperates bose-einstein from boltzmannn statistics). But those are 'Bell numbers' (B(5)=52 -reminds me of a b52--a band and a plane). I'm not sure there is a 'closed form solution' except as an approximation. You compute those recursively--need a calculator or computer.`

Puzzle 32

The definition of a partition in Seven Sketches says:

Maybe this wording is a bit off? This definition is saying a partition is the labeling set P with the subset of A. But this is just a subset of A and not a partition of A. If they are going to use labeling as the means, then the partition should just be the \(\bigcup A_p\)?

`Puzzle 32 The definition of a partition in Seven Sketches says: > If \\(A\\) is a set, a partition of \\(A\\) consists of a set \\(P\\) and, for each \\(p \in A\\), a nonempty subset \\(A_p \subseteq A\\), Maybe this wording is a bit off? This definition is saying a partition is the labeling set P with the subset of A. But this is just a subset of A and not a partition of A. If they are going to use labeling as the means, then the partition should just be the \\(\bigcup A_p\\)?`

Puzzle 31

We use the duality \(x \sim_p y \leftrightarrow \left (x_p,y_p \right ) = S_x\) and use this to translate between partitions and equivalence relations.

`Puzzle 31 We use the duality \\(x \sim_p y \leftrightarrow \left (x_p,y_p \right ) = S_x\\) and use this to translate between partitions and equivalence relations.`

Michael Hong: regarding Puzzle 31, I don't think it makes sense to say \(x \sim_p y \leftrightarrow \left (x_p,y_p \right ) = S_x\) because:

You haven't said what \( x_p \) and \( y_p \) are, and I didn't define them either.

Even if we knew what \( x_p \) and \( y_p \) were, \( (x_p,y_p) \) means the ordered pair consisting of these two points, and it's impossible for that ordered pair to equal \( S_x \). Maybe you meant the subset \( \{x_p , y_p\} \).

The set \(S_x\) consists of

allpoints in \( X \) that are equivalent to \(x\), so it's unlikely to consist of just two points.Maybe you were trying to say

$$ x \sim_P y \textrm{ if and only if } y \in S_x $$ That's true. So is

$$ x \sim_P y \textrm{ if and only if } x \in S_y \textrm{ and } y \in S_x $$ and

$$ x \sim_P y \textrm{ if and only if } S_x = S_y $$ These are some statements that looks sort of like yours but are true.

To prove there's a one-to-one correspondence between equivalence relations and partitions, one natural strategy is to use Puzzles 29 and 30 and then prove

$$ P_{\sim_P} = P $$ and

$$ \sim_{P_\sim} = \sim .$$ In other words, the map sending a partition \(P\) to its equivalence relation \(\sim_P\) is the inverse of the map sending an equivalence relation \(\sim\) to its partition \(P_\sim\).

`Michael Hong: regarding Puzzle 31, I don't think it makes sense to say \\(x \sim_p y \leftrightarrow \left (x_p,y_p \right ) = S_x\\) because: 1. You haven't said what \\( x_p \\) and \\( y_p \\) are, and I didn't define them either. 2. Even if we knew what \\( x_p \\) and \\( y_p \\) were, \\( (x_p,y_p) \\) means the ordered pair consisting of these two points, and it's impossible for that ordered pair to equal \\( S_x \\). Maybe you meant the subset \\( \\{x_p , y_p\\} \\). 3. The set \\(S_x\\) consists of _all_ points in \\( X \\) that are equivalent to \\(x\\), so it's unlikely to consist of just two points. Maybe you were trying to say $$ x \sim_P y \textrm{ if and only if } y \in S_x $$ That's true. So is $$ x \sim_P y \textrm{ if and only if } x \in S_y \textrm{ and } y \in S_x $$ and $$ x \sim_P y \textrm{ if and only if } S_x = S_y $$ These are some statements that looks sort of like yours but are true. To prove there's a one-to-one correspondence between equivalence relations and partitions, one natural strategy is to use Puzzles 29 and 30 and then prove $$ P_{\sim_P} = P $$ and $$ \sim_{P_\sim} = \sim .$$ In other words, the map sending a partition \\(P\\) to its equivalence relation \\(\sim_P\\) is the inverse of the map sending an equivalence relation \\(\sim\\) to its partition \\(P_\sim\\).`

Michael Hong wrote:

This is indeed the key to Puzzle 32. I've added the full definition so we can all stare at it.

There's something "wrong" with this definition. More precisely, it's an okay definition, but it does

notyield a one-to-one correspondence between partitions and equivalence relations. Can someone see the problem?No, it's not saying that. It's saying a partition is the set of

part labels\(P\) and, for each part label \(p \in P\), a subset \(A_p \subseteq A\) called apart, such that each element of \(A\) is in exactly one part.`Michael Hong wrote: > Puzzle 32 > The definition of a partition in _Seven Sketches_ says: > > **Definition.** If \\(A\\) is a set, a partition of \\(A\\) consists of a set \\(P\\) and, for each \\(p \in P\\), a nonempty subset \\(A_p \subseteq A\\), such that $$A=\bigcup_{p\in P}A_p \qquad\text{and}\qquad \text{if }p\neq q\text{ then }A_p\cap A_q=\emptyset $$ > > We refer to \\(P\\) as the set of **part labels** and if \\(p\in P\\) is a part label, we refer to \\(A_p\\) as the **\\(p\\)th part**. The equation above says that each element \\(a\in A\\) is in exactly one part. This is indeed the key to Puzzle 32. I've added the full definition so we can all stare at it. There's something "wrong" with this definition. More precisely, it's an okay definition, but it does _not_ yield a one-to-one correspondence between partitions and equivalence relations. Can someone see the problem? > Maybe this wording is a bit off? This definition is saying a partition is the labeling set \\(P\\) with the subset of \\( A\\). No, it's not saying that. It's saying a partition is the set of **part labels** \\(P\\) and, for each part label \\(p \in P\\), a subset \\(A_p \subseteq A\\) called a **part**, such that each element of \\(A\\) is in exactly one part.`

#11.

A small typo instead of: ...and, for each \(p \in A\)... the book says: ...and, for each \(p \in P\)... .

`\#11. A small typo instead of: ...and, for each \\(p \in A\\)... the book says: ...and, for each \\(p \in P\\)... .`

On

Puzzle 32It seems that they define partition as a pair of some set

Pand family of sets indexed byPsatisfying some conditions. The setPis not defined uniquely. A partition withnparts may be defined byanyset of cardinatlityn, whereas an equivalence relation is defined uniquely as a subset of Cartesian product.`On **Puzzle 32** It seems that they define partition as a pair of some set **P** and family of sets indexed by **P** satisfying some conditions. The set **P** is not defined uniquely. A partition with **n** parts may be defined by *any* set of cardinatlity **n**, whereas an equivalence relation is defined uniquely as a subset of Cartesian product.`

Artur - thanks for catching that typo in #11. I fixed it.

And yes, you solve Puzzle 32. Does everyone understand what Artur said? With Fong and Spivak's definition of partition,

infinitely many different partitionscorrespond to thesameequivalence relation! The reason is that for them, different label sets \(P\) give different partitions, and there are always infinitely many choices of label set.So, I needed to adjust their definition by eliminating the label set. This is a well-known Jedi math trick:

get rid of labels by letting a set label itself!For me, \(P\) is not an arbitrary set labeling the parts of the partition. Itisthe set of parts of the partition.`Artur - thanks for catching that typo in #11. I fixed it. And yes, you solve Puzzle 32. Does everyone understand what Artur said? With Fong and Spivak's definition of partition, _infinitely many different partitions_ correspond to the _same_ equivalence relation! The reason is that for them, different label sets \\(P\\) give different partitions, and there are always infinitely many choices of label set. So, I needed to adjust their definition by eliminating the label set. This is a well-known Jedi math trick: _get rid of labels by letting a set label itself!_ For me, \\(P\\) is not an arbitrary set labeling the parts of the partition. It _is_ the set of parts of the partition.`

For \(A=\{a, b, c\}\) and \(P=\{1, 2\}\), the asignments \(A_1=\{a\}, A_2=\{b, c\}\) and \(A_1=\{b, c\}, A_2=\{a\}\) are different partitions in the book, but the corresponding equivalences are the same.

`For \\(A=\\{a, b, c\\}\\) and \\(P=\\{1, 2\\}\\), the asignments \\(A_1=\\{a\\}, A_2=\\{b, c\\}\\) and \\(A_1=\\{b, c\\}, A_2=\\{a\\}\\) are different partitions in the book, but the corresponding equivalences are the same.`

It prevents counting partitions, or to be a bit cheeky it's too fine grain of a partition of its .. uh is there a name for the range of a definition ?

For example the one element set should have 1 partition, under this definition there are as many partitions of a 1 element set as there are possible labels.

If I was going to define it I would say:

A labeled partition on S is a function P : S -> L, (L being the set of labels) whose range equals it's codomain. A unlabeled partition is a labeled partition where the labeles are the sets { x | x = P ...

Wait that has some circularity issues. Using an function to define its own codomain..

`It prevents counting partitions, or to be a bit cheeky it's too fine grain of a partition of its .. uh is there a name for the range of a definition ? For example the one element set should have 1 partition, under this definition there are as many partitions of a 1 element set as there are possible labels. If I was going to define it I would say: A labeled partition on S is a function P : S -> L, (L being the set of labels) whose range equals it's codomain. A unlabeled partition is a labeled partition where the labeles are the sets { x | x = P ... Wait that has some circularity issues. Using an function to define its own codomain..`

## Puzzle 29

Show that if \(\sim\) is an equivalence relation on a set \(X\), we can define a partition \(P_\sim\) on \(X\) whose parts are precisely the sets of the form

$$ S_x = \{y \in X : \; y \sim x \} $$ with \(x \in X\). We call \(S_x\) the

equivalence classof \(x\).I'm going to start with something I'd realized and John states: $$x \sim y \iff S_x = S_y$$ This follows from the definition of an

equivalence classand that \(\sim\) is symmetric and transitive.Let \(x,y \in X\) and \(x \sim y\)

Three immediate conclusions lead from this:

$$y \sim x\\ x \in S_y\\ y \in S_x$$ The first because \(\sim\) is symmetric. The second two by the definition of

equivalence class.\(\forall z \in S_y, z \sim y\). Given that \(\sim\) is transitive and symmetric, this also means that \(\forall z \in S_y, z \sim x\). Given the definition of \(S_x\), \(\forall z \in S_y, z \in S_x\). This implies that \(S_y \subseteq S_x\). The same reasoning gives us \(S_x \subseteq S_y\).

$$\therefore x \sim y \implies S_x = S_y$$ The reverse (that \(S_x = S_y \implies x \sim y\)) can be shown by similar reasoning but I'll stop here. I don't need it for the proofs below.

Now to the three parts of the definition of a partition:

Each part is non-empty\(\forall x \in X: \exists S_x \in P_\sim\) by definition of \(P_\sim\).

\(\sim\) is reflexive so \(x \sim x\).

By the definition of \(S_x\) with \(x \sim x\), \(x \in S_x\) .

\(\forall S_x \in P_\sim, S_x \neq \emptyset\).

Distinct parts are disjointI'll attempt to do this as a proof by contradiction. (I'm rusty on constructing proofs of this sort so comments and corrections would be appreciated.)

Let \(S_x, S_y \in P_\sim\) and \(S_x \neq S_y\). Assume \(S_x \cap S_y \neq \emptyset\).

Then \(\exists z \in X \text{ s.t. } z \in S_x \wedge z \in S_y\).

\(z \in S_y \implies z \sim y\) and \(z \in S_x \implies z \sim x\).

These in turn give us (using the proposition at the start) that \(S_z = S_y \wedge S_z = S_x\).

This leads to \(S_x = S_y\), a contradiction. So our assumption must be false.

Given \(S_x \neq S_y\) then \(S_x \cap S_y = \emptyset\). So distinct parts are disjoint.

The union of all parts in \(P\) is \(X\)\(\forall x \in X, \exists S_x \in P_\sim s.t. x \in S_x\), from the definition of \(P_\sim\).

Since \(P_\sim\) is the set of all equivalence classes \(S_x\), this means that the union of all parts in \(P\) is the same as \(\bigcup_{x \in X}S_x\).

Since each \(x\) is in its respective \(S_x\), \(\bigcup_{x \in X}S_x = X\).

`#Puzzle 29 Show that if \\(\sim\\) is an equivalence relation on a set \\(X\\), we can define a partition \\(P_\sim\\) on \\(X\\) whose parts are precisely the sets of the form $$ S_x = \\{y \in X : \; y \sim x \\} $$ with \\(x \in X\\). We call \\(S_x\\) the **equivalence class** of \\(x\\). *** I'm going to start with something I'd realized and John states: $$x \sim y \iff S_x = S_y$$ This follows from the definition of an **equivalence class** and that \\(\sim\\) is symmetric and transitive. Let \\(x,y \in X\\) and \\(x \sim y\\) Three immediate conclusions lead from this: $$y \sim x\\\\ x \in S_y\\\\ y \in S_x$$ The first because \\(\sim\\) is symmetric. The second two by the definition of **equivalence class**. \\(\forall z \in S_y, z \sim y\\). Given that \\(\sim\\) is transitive and symmetric, this also means that \\(\forall z \in S_y, z \sim x\\). Given the definition of \\(S_x\\), \\(\forall z \in S_y, z \in S_x\\). This implies that \\(S_y \subseteq S_x\\). The same reasoning gives us \\(S_x \subseteq S_y\\). $$\therefore x \sim y \implies S_x = S_y$$ The reverse (that \\(S_x = S_y \implies x \sim y\\)) can be shown by similar reasoning but I'll stop here. I don't need it for the proofs below. *** Now to the three parts of the definition of a partition: - *Each part is non-empty* \\(\forall x \in X: \exists S_x \in P_\sim\\) by definition of \\(P_\sim\\). \\(\sim\\) is reflexive so \\(x \sim x\\). By the definition of \\(S_x\\) with \\(x \sim x\\), \\(x \in S_x\\) . \\(\forall S_x \in P_\sim, S_x \neq \emptyset\\). - *Distinct parts are disjoint* I'll attempt to do this as a proof by contradiction. (I'm rusty on constructing proofs of this sort so comments and corrections would be appreciated.) Let \\(S_x, S_y \in P_\sim\\) and \\(S_x \neq S_y\\). Assume \\(S_x \cap S_y \neq \emptyset\\). Then \\(\exists z \in X \text{ s.t. } z \in S_x \wedge z \in S_y\\). \\(z \in S_y \implies z \sim y\\) and \\(z \in S_x \implies z \sim x\\). These in turn give us (using the proposition at the start) that \\(S_z = S_y \wedge S_z = S_x\\). This leads to \\(S_x = S_y\\), a contradiction. So our assumption must be false. Given \\(S_x \neq S_y\\) then \\(S_x \cap S_y = \emptyset\\). So distinct parts are disjoint. - *The union of all parts in \\(P\\) is \\(X\\)* \\(\forall x \in X, \exists S_x \in P_\sim s.t. x \in S_x\\), from the definition of \\(P_\sim\\). Since \\(P_\sim\\) is the set of all equivalence classes \\(S_x\\), this means that the union of all parts in \\(P\\) is the same as \\(\bigcup_{x \in X}S_x\\). Since each \\(x\\) is in its respective \\(S_x\\), \\(\bigcup_{x \in X}S_x = X\\).`

Anindya Bhattacharyya and Jesus Lopez neatly killed off Puzzle 32. Christopher Upshaw pointed out some difficulties with climbing out of the trap Fong and Spivak fell into. My definition of partition, which is the usual one, avoids falling into this trap in the first place by never mentioning "labels" for the parts in the partition.

`[ Anindya Bhattacharyya ](https://forum.azimuthproject.org/discussion/comment/16898/#Comment_16898) and [Jesus Lopez](https://forum.azimuthproject.org/discussion/comment/16951/#Comment_16951) neatly killed off Puzzle 32. [Christopher Upshaw](https://forum.azimuthproject.org/discussion/comment/16953/#Comment_16953) pointed out some difficulties with climbing out of the trap Fong and Spivak fell into. My definition of partition, which is the [usual one](https://en.wikipedia.org/wiki/Partition_of_a_set#Definition), avoids falling into this trap in the first place by never mentioning "labels" for the parts in the partition.`

Jared nicely solved Puzzle 29. Good use of proof by contradiction, Jared!

Anyone who isn't used to writing proofs should look at Jared's. This is how you should write proofs when you're being careful. When you get a math degree you do a thousand homework problems involving proofs. I suppose this is also true for some branches of computer science. By the end of this training, you can crank out proofs quite quickly unless they involve a deep and difficult trick. Once you're good at this, you can start slacking off a bit and write proofs that skip some steps. But anyone who hasn't gone through some training like this is likely to screw up when they skip steps!

`Jared nicely solved [Puzzle 29](https://forum.azimuthproject.org/profile/1729/Jared%20Summers). Good use of proof by contradiction, Jared! Anyone who isn't used to writing proofs should look at Jared's. This is how you should write proofs when you're being careful. When you get a math degree you do a thousand homework problems involving proofs. I suppose this is also true for some branches of computer science. By the end of this training, you can crank out proofs quite quickly unless they involve a deep and difficult trick. Once you're good at this, you can start slacking off a bit and write proofs that skip some steps. But anyone who hasn't gone through some training like this is likely to screw up when they skip steps!`

Artur Grezsiak nicely solved Puzzle 33.

Yes, an equivalence relation is a preorder! If I wanted to show off - which luckily I never want to do - I could have said:

Definition.Anequivalence relation\(\sim\) on a set \(X\) is a preorder on \(X\) that issymmetric, meaning that for all \(x,y \in X\), \(x \sim y\) implies \(y \sim x\).It's slightly surprising that equivalence relations are preorders, because often we think about

posets, which are preorders that areantisymmetric, meaning that for all \(x,y \in X\), \(x \le y\) and \(y \le x\) imply \(x = y\).We use the symmetrical symbol \(\sim\) for preorders that are symmetric, and the asymmetric symbol \(\le\) for preorders that are antisymmetric. However, one beauty of preorders is that they put posets and equivalence relations under the same roof! A theorem about preorders is a theorem about both \(\le\) and \(\sim\)!

I posed this puzzle elsewhere, but I'll pose it again:

Puzzle.Can a preorder be both symmetric and antisymmetric? If so, what's it like?`[Artur Grezsiak](https://forum.azimuthproject.org/discussion/comment/16936/#Comment_16936) nicely solved Puzzle 33. Yes, an equivalence relation is a preorder! If I wanted to show off - which luckily I never want to do - I could have said: **Definition.** An **equivalence relation** \\(\sim\\) on a set \\(X\\) is a preorder on \\(X\\) that is **symmetric**, meaning that for all \\(x,y \in X\\), \\(x \sim y\\) implies \\(y \sim x\\). It's slightly surprising that equivalence relations are preorders, because often we think about **posets**, which are preorders that are **antisymmetric**, meaning that for all \\(x,y \in X\\), \\(x \le y\\) and \\(y \le x\\) imply \\(x = y\\). We use the symmetrical symbol \\(\sim\\) for preorders that are symmetric, and the asymmetric symbol \\(\le\\) for preorders that are antisymmetric. However, one beauty of preorders is that they put posets and equivalence relations under the same roof! A theorem about preorders is a theorem about both \\(\le\\) and \\(\sim\\)! I posed this puzzle elsewhere, but I'll pose it again: **Puzzle.** Can a preorder be both symmetric and antisymmetric? If so, what's it like?`

John: Thanks for the kind words. It's been 12 years since I finished my CS and math degrees so I'm a bit rusty on things. Glad to see I'm not making any obvious errors yet.

Regarding latest

puzzle:My first thought is that a preorder that is

bothsymmetricandantisymmetric would be a discrete preorder.Symmetry requires that (using \(\leq\)): if \(x \leq y\) then \(y \leq x\). However, it permits

either\(x = y\)or\(x \neq y\).However, antisymmetry gives us: \(x \leq y \wedge y \leq x \implies x = y\).

Having both, then, forces every pair that is related by \(\leq\) to be equal to each other. This leaves us with only discrete preorders.

I'm expanding my last paragraph a bit. On rereading it I felt it wasn't as clear as could be.

Having both symmetry and antisymmetry, if we have \(x,y \in X\) and \(x \leq y\) then by symmetry we get \(y \leq x\).

With both \(x \leq y \wedge y \leq x\) and antisymmetry we get \(x = y\). This is equivalent to the text's definition for a discrete preorder on page 11.

`John: Thanks for the kind words. It's been 12 years since I finished my CS and math degrees so I'm a bit rusty on things. Glad to see I'm not making any obvious errors yet. Regarding latest **puzzle**: My first thought is that a preorder that is *both* symmetric *and* antisymmetric would be a discrete preorder. Symmetry requires that (using \\(\leq\\)): if \\(x \leq y\\) then \\(y \leq x\\). However, it permits *either* \\(x = y\\) *or* \\(x \neq y\\). However, antisymmetry gives us: \\(x \leq y \wedge y \leq x \implies x = y\\). Having both, then, forces every pair that is related by \\(\leq\\) to be equal to each other. This leaves us with only discrete preorders. *** I'm expanding my last paragraph a bit. On rereading it I felt it wasn't as clear as could be. Having both symmetry and antisymmetry, if we have \\(x,y \in X\\) and \\(x \leq y\\) then by symmetry we get \\(y \leq x\\). With both \\(x \leq y \wedge y \leq x\\) and antisymmetry we get \\(x = y\\). This is equivalent to the text's definition for a discrete preorder on page 11.`

Jared - just for the kids watching this TV show, what's a "discrete preorder"?

`Jared - just for the kids watching this TV show, what's a "discrete preorder"?`

John: a discrete preorder on \(X\) is formed when the only elements related by \(\leq\) are equal to each other. That is \(x \leq y\) if and only if \(x = y\).

(page 11 for anyone wanting to see more, sets are noted there as examples of discrete preorders)

`John: a discrete preorder on \\(X\\) is formed when the only elements related by \\(\leq\\) are equal to each other. That is \\(x \leq y\\) if and only if \\(x = y\\). (page 11 for anyone wanting to see more, sets are noted there as examples of discrete preorders)`

Thanks for polishing up your answer, Jared!

You're right. Here's another way to say it: a preorder \(\sim\) that's both symmetric and antisymmetric must be

equality:$$ x \sim y \textrm{ if and only if } x = y $$

`Thanks for polishing up your answer, Jared! You're right. Here's another way to say it: a preorder \\(\sim\\) that's both symmetric and antisymmetric must be _equality_: $$ x \sim y \textrm{ if and only if } x = y $$`

Artur Grzesiak wrote:

As you note, the book's definition implies mine, because "P iff Q" implies "P implies Q".

Puzzle.Prove that my definition implies the book's definition.(I have changed the set \(A\) in your comment to \(X\), so that the two definitions are talking about the same set.)

`[Artur Grzesiak wrote:](https://forum.azimuthproject.org/discussion/comment/16937/#Comment_16937) > There is a difference in defining symmetry. > In the lecture: for all \\(x,y \in X\\), \\(x \sim y\\) implies \\(y \sim x.\\) > In the book (definition 1.8): \\(a \sim b\\) iff \\(b \sim a\\), for all \\(a,b \in X\\) > Implication is weaker than *iff*, but to be honest I am not sure if this is the root cause of the problem, as for me they *feel*... *equivalent* in this particular case. As you note, the book's definition implies mine, because "P iff Q" implies "P implies Q". **Puzzle.** Prove that my definition implies the book's definition. (I have changed the set \\(A\\) in your comment to \\(X\\), so that the two definitions are talking about the same set.)`

Another nice little exercise:

Puzzle.How many partitions does the empty set have, and what are they?`Another nice little exercise: **Puzzle.** How many partitions does the empty set have, and what are they?`

@John Thanks for the pointer. It really helped out a lot. Indeed I was trying to say \(x \sim_P y \Leftrightarrow S_x = S_y\) but didn't know quite how to do it nor how much needed to be said in order to prove it!

@Jared Thanks for showing every step so that even the bottom rung can follow. :)

I have never actually written out a full proof so to practice and also collect all the answers, I took Jared's answers to Puzzle 28,29,31 and tried to rewrite it in my own words. It's quite difficult talking like a mathematician LOL.

Puzzle 28: Show that if \(P\) is a partition of a set \(X\), and we define a relation \(\sim_P\) on \(X\) as follows:$$ x \sim_P y \textrm{ if and only if } x, y \in S \textrm{ for some } S \in P, $$

## then \(\sim_P \) is an equivalence relation.

So we have to check if \(\sim_P\) satisfies

Reflexivity,Transitivity, andSymmetry:ReflexivityFor all \(x \in X\), \(x \sim_P x\) is true if and only if \(x,x \in S\) for some \(S \in P\) which is trivially true by definition of an element of a set.TransitivityFor all \(x,y,z \in X\), \(x \sim_P y\) and \(y \sim_P z\) imply \(x \sim_P z\) with \(x,y \in S_1, y,z \in S_2, x,z \in S_3\) by definition is true if and only if \(S_1 = S_2 = S_3\). This is true since \(S_1 \cap S_2 = y \neq \varnothing\) and therefore not disjoint and by property 2 of a partition, \(S_1 = S_2\). This then implies \(x,y,z,\in S_1\) and since \(x,z \in S_3\), \(S_1 = S_2 = S_3\).SymmetryFor all \(x,y, \in X\), \(x \sim_P y\) implies \(y \sim_P x\) with \(x,y \in S_1, y,x \in S_2\) is true if and only if \(S_1 = S_2\). This is true since \(S_1 \cap S_2 = x,y \neq \varnothing\) and therefore not disjoint and by property 2 of a partition, \(S_1 = S_2\).Puzzle 29: Show that if \(\sim\) is an equivalence relation on a set \(X\), we can define a partition \(P_\sim\) on \(X\) whose parts are precisely the sets of the form$$ S_x = \{y \in X : \; y \sim x \} $$

## with \(x \in X\). We call \(S_x\) the

equivalence classof \(x\).So this time we have to prove that the set above satisfies the definition of a partition.

1. Each set \(s \in P\) is nonemptyFor all \(S_x \in P\), \(S_x \neq \varnothing\) is true if and only if there exists at least one equivalence relation for every \(x \in X\). This is true becauseReflexivitystates that for all \(x \in X\), \(x \sim x\).2. If \(S_x \neq S_y\), then \(S_x \cap S_y = \varnothing\).To prove this, we can just prove if \(S \neq T\) then \(S \cap T \neq \varnothing\) is false.So if \(S_x \cap S_y \neq \varnothing\), then there must exist a \(z\) in both partitions: \(S_x = \{z \in X : z \sim x\} \in \{x,y\}\) \(S_y = \{z \in X : z \sim y\} \in \{y,z\}\)

But through

Symmetrywe get \(S_z=S_x\) and \(S_z=S_y\). Therefore \(S_x=S_y\) and we have a contradiction.3. The union of all the sets \(S \in P\) is X.\(X= \bigcup_{S \in P}S\) if there exists \(S\) for all \(x \in X\) . This is true since \(x \sim x\) for all \(x\) and therefore there exists an \(S_x\) for all \(x\).Puzzle 31: Show that the previous two puzzles give a one-to-one correspondence between partitions of \(X\) and equivalence relations on \(X\).Edited: So to prove an one-to-one correspondence between equivalence relations and partitions we have to prove the following :

given \(S_x\) and \(\sim_P\) which are defined in Puzzle 28 and 29.

If \(x,y \in X\) and \(x \sim y\), then define the set \(S_y = \{ x \in X : x \sim y \}\). By

Symmetrywe also have \(y \sim x \Rightarrow S_x = \{ y \in X : y \sim x \}\). This means \(S_x = S_y\) and \(x,y \in S_x\). Since \(S_x \in P_\sim\) as shown by Puzzle 29, there exists an equivalence relation \(\sim_{P_\sim}\) such that \(x \sim_{P_\sim} y\) as shown by Puzzle 28.If \(x,y \in S\) and \(S \in P\) and \(P\) is a partition on \(X\), then \(x \sim_P y\) is an equivalence relation shown by Puzzle 28. Then there exists a partition \(P_{\sim_P}\) on \(X\) whose parts are sets of the form \(S_y = \{x \in X : x \sim_P y \}\) as shown in Puzzle 29. By

Symmetry, we also get \(S_x = \{y \in X : y \sim_P x \}\) and therefore \(S_x = S_y\) and \(x,y \in S_x\).`@John Thanks for the pointer. It really helped out a lot. Indeed I was trying to say \\(x \sim_P y \Leftrightarrow S_x = S_y\\) but didn't know quite how to do it nor how much needed to be said in order to prove it! @Jared Thanks for showing every step so that even the bottom rung can follow. :) I have never actually written out a full proof so to practice and also collect all the answers, I took Jared's answers to Puzzle 28,29,31 and tried to rewrite it in my own words. It's quite difficult talking like a mathematician LOL. ###**Puzzle 28** : Show that if \\(P\\) is a partition of a set \\(X\\), and we define a relation \\(\sim_P\\) on \\(X\\) as follows: $$ x \sim_P y \textrm{ if and only if } x, y \in S \textrm{ for some } S \in P, $$ ###then \\(\sim_P \\) is an equivalence relation. So we have to check if \\(\sim_P\\) satisfies **Reflexivity**, **Transitivity**, and **Symmetry** : **Reflexivity** For all \\(x \in X\\), \\(x \sim_P x\\) is true if and only if \\(x,x \in S\\) for some \\(S \in P\\) which is trivially true by definition of an element of a set. **Transitivity** For all \\(x,y,z \in X\\), \\(x \sim_P y\\) and \\(y \sim_P z\\) imply \\(x \sim_P z\\) with \\(x,y \in S_1, y,z \in S_2, x,z \in S_3\\) by definition is true if and only if \\(S_1 = S_2 = S_3\\). This is true since \\(S_1 \cap S_2 = y \neq \varnothing\\) and therefore not disjoint and by property 2 of a partition, \\(S_1 = S_2\\). This then implies \\(x,y,z,\in S_1\\) and since \\(x,z \in S_3\\), \\(S_1 = S_2 = S_3\\). **Symmetry** For all \\(x,y, \in X\\), \\(x \sim_P y\\) implies \\(y \sim_P x\\) with \\(x,y \in S_1, y,x \in S_2\\) is true if and only if \\(S_1 = S_2\\). This is true since \\(S_1 \cap S_2 = x,y \neq \varnothing\\) and therefore not disjoint and by property 2 of a partition, \\(S_1 = S_2\\). ### **Puzzle 29** : Show that if \\(\sim\\) is an equivalence relation on a set \\(X\\), we can define a partition \\(P_\sim\\) on \\(X\\) whose parts are precisely the sets of the form $$ S_x = \\{y \in X : \; y \sim x \\} $$ ###with \\(x \in X\\). We call \\(S_x\\) the **equivalence class** of \\(x\\). So this time we have to prove that the set above satisfies the definition of a partition. **1. Each set \\(s \in P\\) is nonempty** For all \\(S_x \in P\\), \\(S_x \neq \varnothing\\) is true if and only if there exists at least one equivalence relation for every \\(x \in X\\). This is true because **Reflexivity** states that for all \\(x \in X\\), \\(x \sim x\\). **2. If \\(S_x \neq S_y\\), then \\(S_x \cap S_y = \varnothing\\).** To prove this, we can just prove if \\(S \neq T\\) then \\(S \cap T \neq \varnothing\\) is false. So if \\(S_x \cap S_y \neq \varnothing\\), then there must exist a \\(z\\) in both partitions: \\(S_x = \\{z \in X : z \sim x\\} \in \\{x,y\\}\\) \\(S_y = \\{z \in X : z \sim y\\} \in \\{y,z\\}\\) But through **Symmetry** we get \\(S_z=S_x\\) and \\(S_z=S_y\\). Therefore \\(S_x=S_y\\) and we have a contradiction. **3. The union of all the sets \\(S \in P\\) is X.** \\(X= \bigcup_{S \in P}S\\) if there exists \\(S\\) for all \\(x \in X\\) . This is true since \\(x \sim x\\) for all \\(x\\) and therefore there exists an \\(S_x\\) for all \\(x\\). ### **Puzzle 31** : Show that the previous two puzzles give a one-to-one correspondence between partitions of \\(X\\) and equivalence relations on \\(X\\). Edited: So to prove an one-to-one correspondence between equivalence relations and partitions we have to prove the following : 1. For any \\(x,y \in X\\) where \\(x \sim y\\), there exists an equivalence relation \\(x \sim_{P_\sim} y\\). 2. For any \\(x,y \in S\\) where \\(S \in P\\) and \\(P\\) is a partition on \\(X\\), there exists a \\(P_{\sim_P}\\) where \\(S_x \in P_{\sim_P}\\) and \\(x,y \in S_x\\). given \\(S_x\\) and \\(\sim_P\\) which are defined in Puzzle 28 and 29. 1. If \\(x,y \in X\\) and \\(x \sim y\\), then define the set \\(S_y = \\{ x \in X : x \sim y \\}\\). By **Symmetry** we also have \\(y \sim x \Rightarrow S_x = \\{ y \in X : y \sim x \\}\\). This means \\(S_x = S_y\\) and \\(x,y \in S_x\\). Since \\(S_x \in P_\sim\\) as shown by Puzzle 29, there exists an equivalence relation \\(\sim_{P_\sim}\\) such that \\(x \sim_{P_\sim} y\\) as shown by Puzzle 28. 2. If \\(x,y \in S\\) and \\(S \in P\\) and \\(P\\) is a partition on \\(X\\), then \\(x \sim_P y\\) is an equivalence relation shown by Puzzle 28. Then there exists a partition \\(P_{\sim_P}\\) on \\(X\\) whose parts are sets of the form \\(S_y = \\{x \in X : x \sim_P y \\}\\) as shown in Puzzle 29. By **Symmetry**, we also get \\(S_x = \\{y \in X : y \sim_P x \\}\\) and therefore \\(S_x = S_y\\) and \\(x,y \in S_x\\).`

Puzzle.How many partitions does the empty set have, and what are they?There is one partition of the empty set, and it is the empty set itself.

Checking from definition:

Definition.Apartitionof a set \(X\) is a set \(P \subseteq P(X)\) such that:Each set \(S \in P \) is nonempty.

Distinct sets \(S, T \in P\) are disjoint: that is, if \(S \ne T\) then \(S \cap T = \emptyset \).

The union of all the sets \(S \in P\) is \(X\): that is,

$$ X = \bigcup_{S \in P} S $$ Clearly \(\varnothing \subseteq P(\varnothing)\), as the empty set is a subset of any other set.

is true as all elements of the empty set are nonempty.

is true as there are no distinct sets belonging to the empty set.

\(\varnothing = \bigcup_{S \in \varnothing} S\) is true provided we defined the union of an empty family of sets to be the empty set (which is probably the only reasonable definition)

Now what left to be done is to prove that the empty set is the only partition of the empty set. Let's make use of one-to-one correspondence between partitions of a set and its equivalence relations. Since \(\varnothing \times \varnothing = \varnothing\) and \(\varnothing\) is the only subset of \(\varnothing\), \(\varnothing\) is the only binary relation defined on \(\varnothing\). All properties of equivalence relation are trivially true in case of the empty relation since they start with

for alland there are no elements in the empty set. Since there is only one equivalence relation of the empty set there has to be exactly one partition.`**Puzzle.** How many partitions does the empty set have, and what are they? There is one partition of the empty set, and it is the empty set itself. Checking from definition: **Definition.** A **partition** of a set \\(X\\) is a set \\(P \subseteq P(X)\\) such that: 1. Each set \\(S \in P \\) is nonempty. 2. Distinct sets \\(S, T \in P\\) are disjoint: that is, if \\(S \ne T\\) then \\(S \cap T = \emptyset \\). 3. The union of all the sets \\(S \in P\\) is \\(X\\): that is, $$ X = \bigcup_{S \in P} S $$ Clearly \\(\varnothing \subseteq P(\varnothing)\\), as the empty set is a subset of any other set. 1. is true as all elements of the empty set are nonempty. 2. is true as there are no distinct sets belonging to the empty set. 3. \\(\varnothing = \bigcup_{S \in \varnothing} S\\) is true provided we defined the union of an empty family of sets to be the empty set (which is probably the only reasonable definition) Now what left to be done is to prove that the empty set is the only partition of the empty set. Let's make use of one-to-one correspondence between partitions of a set and its equivalence relations. Since \\(\varnothing \times \varnothing = \varnothing\\) and \\(\varnothing\\) is the only subset of \\(\varnothing\\), \\(\varnothing\\) is the only binary relation defined on \\(\varnothing\\). All properties of equivalence relation are trivially true in case of the empty relation since they start with _for all_ and there are no elements in the empty set. Since there is only one equivalence relation of the empty set there has to be exactly one partition.`

@Artur – re "prove that the empty set is the only partition of the empty set", we can get this directly by noting that the only other subset of \(P(\varnothing )\) is \(\{\varnothing \}\), and that can't be a partition because it fails criterion 1.

`@Artur – re "prove that the empty set is the only partition of the empty set", we can get this directly by noting that the only other subset of \\(P(\varnothing )\\) is \\(\\{\varnothing \\}\\), and that can't be a partition because it fails criterion 1.`

apropos of nothing, you could replace criteria 1 and 2 with: for all \(S, T\in P\) we have \(S\ne T \iff S \cap T = \varnothing \)

`apropos of nothing, you could replace criteria 1 and 2 with: for all \\(S, T\in P\\) we have \\(S\ne T \iff S \cap T = \varnothing \\)`

For Boolean algebras, the non-triviality or non-degeneracy assumption is that the zero is distinct from the one so for powerset BAs, that means taking 1 as the smallest set since it has two subsets. For partition algebras in partition logic, the analogous non-degeneracy assumption is that the underlying set \(X\) has at least two elements so the indiscrete partition (one block containing both elements) is distinct from the discrete partition (which distinguishes the two elements). The interesting thing is that the Boolean logic of subsets and the logic of partitions

agreein this minimal case. That is, the powerset BA on the one-element set \(\wp(1)\) using subset operations is isomorphic to the partition algebra \(\prod(2)\) using operations (e.g., join, meet, and implication) on partitions.This isomorphism seems to be the key to understanding what G. Spencer Brown was trying to do in his somewhat cryptic book

Laws of Form. He develops an algebra based on intuitive reasoning about "the Distinction" (e.g., distinguishing the two elements in \(2\) but ends up with the two-element Boolean algebra as many commentators have pointed out.`For Boolean algebras, the non-triviality or non-degeneracy assumption is that the zero is distinct from the one so for powerset BAs, that means taking 1 as the smallest set since it has two subsets. For partition algebras in [partition logic](http://www.ellerman.org/introduction-to-partition-logic/), the analogous non-degeneracy assumption is that the underlying set \\(X\\) has at least two elements so the indiscrete partition (one block containing both elements) is distinct from the discrete partition (which distinguishes the two elements). The interesting thing is that the Boolean logic of subsets and the logic of partitions _agree_ in this minimal case. That is, the powerset BA on the one-element set \\(\wp(1)\\) using subset operations is isomorphic to the partition algebra \\(\prod(2)\\) using operations (e.g., join, meet, and implication) on partitions. This isomorphism seems to be the key to understanding what G. Spencer Brown was trying to do in his somewhat cryptic book _Laws of Form_. He develops an algebra based on intuitive reasoning about "the Distinction" (e.g., distinguishing the two elements in \\(2\\) but ends up with the two-element Boolean algebra as many commentators have pointed out.`

Michael Hong wrote:

True, at first. But once you learn how, it's very relaxing, sort of like knitting. You just work through things in a systematic, calm and precise way until everything fits neatly into place.

That's not what Puzzle 28 says. I don't even know what this means.

Puzzle 28 tells you to take a partition \(P\) and show that \(\sim_P\) is an equivalence relation. And that's what you actually did!

You started with the definition of \(\sim_P\):

And then you checked that \(\sim_P\) was an equivalence relation:

You also wrote:

That's not what Puzzle 29 says. I don't even know what this means.

Puzzle 29 tells you to take an equivalence relation and show that \(P_\sim\) is a partition. And that's what you actually did. You started with the definition of \P_\sim\), namely the definition of its parts, and worked from there.

After you've done the real Puzzles 28 and 29, it

isvery nice to show that$$ \sim_{P_\sim} = \sim $$ and

$$ P_{\sim_P} = P $$ because these give you the one-to-one correspondence between partitions and equivalence relations.

The first one says that taking an equivalence relation \(\sim\), turning it into the partition \(P_\sim\), and then turning that back into an equivalence relation \(\sim_{P_\sim}\), gets us back where we started. The second one says that taking a partition \(P\), turning it into the equivalence relation \(\sim_P\), and then turning that back into a partition \(P_{\sim_P}\), gets us back where we started. Taken together, these mean we have a one-to-one correspondence.

There are also other ways to show we have a one-to-one correspondence. I didn't check your proof that there's a one-to-one correspondence between partitions and equivalence relations - I got a bit lazy. Someone else, please take a look! Is it okay?

`Michael Hong wrote: > It's quite difficult talking like a mathematician LOL. True, at first. But once you learn how, it's very relaxing, sort of like knitting. You just work through things in a systematic, calm and precise way until everything fits neatly into place. > **Puzzle 28.** Show that \\(\sim_P = \sim\\). That's not what Puzzle 28 says. I don't even know what this means. Puzzle 28 tells you to take a partition \\(P\\) and show that \\(\sim_P\\) is an equivalence relation. And that's what you actually did! You started with the definition of \\(\sim_P\\): > **Definition.** \\(x\sim_Py\\) if and only if \\(x,y \in S\\) for some \\(S \in P\\) And then you checked that \\(\sim_P\\) was an equivalence relation: > So we have to check if \\(\sim_P\\) satisfies **Reflexivity**, **Transitivity**, and **Symmetry** [....] You also wrote: > **Puzzle 29** : Show that \\(P_{\sim P} = P\\). That's not what Puzzle 29 says. I don't even know what this means. Puzzle 29 tells you to take an equivalence relation and show that \\(P_\sim\\) is a partition. And that's what you actually did. You started with the definition of \\P_\sim\\), namely the definition of its parts, and worked from there. After you've done the real Puzzles 28 and 29, it _is_ very nice to show that $$ \sim_{P_\sim} = \sim $$ and $$ P_{\sim_P} = P $$ because these give you the one-to-one correspondence between partitions and equivalence relations. The first one says that taking an equivalence relation \\(\sim\\), turning it into the partition \\(P_\sim\\), and then turning that back into an equivalence relation \\(\sim_{P_\sim}\\), gets us back where we started. The second one says that taking a partition \\(P\\), turning it into the equivalence relation \\(\sim_P\\), and then turning that back into a partition \\(P_{\sim_P}\\), gets us back where we started. Taken together, these mean we have a one-to-one correspondence. There are also other ways to show we have a one-to-one correspondence. I didn't check your proof that there's a one-to-one correspondence between partitions and equivalence relations - I got a bit lazy. Someone else, please take a look! Is it okay?`

Aren't the puzzles giving proofs of univalence of

Partitions? Or perhaps something similar to it?`Aren't the puzzles giving proofs of univalence of **Partitions**? Or perhaps something similar to it?`

I don't know what "univalence of

Partitions" means. I doubt the puzzles are proving that.`I don't know what "univalence of **Partitions**" means. I doubt the puzzles are proving that.`

I clarified my discussion of "finer versus coarser" in the logic of partitions. It will e convenient to say that having a finer partition means you know

more. So:Imagine you're a detective trying to solve a case on a small island with 5 people on it. At first you don't know any of them are related, so they're all in separate families, as far as you know:

But then you start digging into their history. Each time you learn that two people are related, you change your partition by putting them into the same part:

You keep doing this as secret family relationships are revealed:

In this example, as you learn more you move to

coarserpartitions, because your goal is to find relationships between people, and lump them in as big bunches as possible. But often people think about partition logic a bit differently, where as you learn more you move tofinerpartitions.Suppose you are an amateur wine taster learning to distinguish different kinds of wine by their taste. At first all wines taste alike, so they're all lumped together:

When you learn to distinguish red and white wines, you move to a finer partition:

This sort of example will fit our story a bit better. We'll generally say that you know more if your partition is

finer.`I clarified my discussion of "finer versus coarser" in the logic of partitions. It will e convenient to say that having a finer partition means you know _more_. So: <hr/> Imagine you're a detective trying to solve a case on a small island with 5 people on it. At first you don't know any of them are related, so they're all in separate families, as far as you know: <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/partition_of_5_finest.png"></center> But then you start digging into their history. Each time you learn that two people are related, you change your partition by putting them into the same part: <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/partition_of_5_less_fine.png"></center> You keep doing this as secret family relationships are revealed: <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/partition_of_5_coarser.png"></center> In this example, as you learn more you move to _coarser_ partitions, because your goal is to find relationships between people, and lump them in as big bunches as possible. But often people think about partition logic a bit differently, where as you learn more you move to _finer_ partitions. Suppose you are an amateur wine taster learning to distinguish different kinds of wine by their taste. At first all wines taste alike, so they're all lumped together: <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/partition_of_5_coarsest.png"></center> When you learn to distinguish red and white wines, you move to a finer partition: <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/partition_of_5_less_coarse.png"></center> This sort of example will fit our story a bit better. We'll generally say that you know more if your partition is _finer_.`

@John Got it. All names and symbols need to be defined in the formulation of the question. Also, after reading through your comment, I think the proof I gave for Puzzle 31 is insufficient because I haven't stated a couple assumptions I made. I will fix the hole.

`@John Got it. All names and symbols need to be defined in the formulation of the question. Also, after reading through your comment, I think the proof I gave for Puzzle 31 is insufficient because I haven't stated a couple assumptions I made. I will fix the hole.`

Michael Hong:

Yes, this is what mathematicians love.

`Michael Hong: > All names and symbols need to be defined in the formulation of the question. <img src = "http://math.ucr.edu/home/baez/emoticons/love.gif"> Yes, this is what mathematicians love.`

Do you have a similar metaphor for

readingmathematics? It often seems like reading through a solution gives me a long string of easy to follow navigational directions, but after I get there I have no bird's eye view of the space I moved through.(cue: "you never 'just read' mathematics!")

I know you're probably going to say something like: http://www.people.vcu.edu/~dcranston/490/handouts/math-read.html

... but I find it hard to believe that this is how you always do it (that'd take an awful lot of time!)

`Do you have a similar metaphor for _reading_ mathematics? It often seems like reading through a solution gives me a long string of easy to follow navigational directions, but after I get there I have no bird's eye view of the space I moved through. (cue: "you never 'just read' mathematics!") I know you're probably going to say something like: http://www.people.vcu.edu/~dcranston/490/handouts/math-read.html ... but I find it hard to believe that this is how you always do it (that'd take an awful lot of time!)`

Allison wrote:

Reading mathematics is a complicated business. I read mathematics in different ways for different purposes.

That handout does an excellent job of explaining how to read mathematics when you 1) don't yet understand it but 2) want to understand it very well. That

doestake an awful lot of time! It's the complete opposite of passive reading: you have work through all the concepts, see how they interact with the concepts you already understand, let them fight it out, ask yourself lots of questions, answer those questions - sometimes by doing calculations - and go through the reading over and over until the impenetrable murk turns into crystal clarity.Maybe an appropriate metaphor is hiking into the jungle, setting up a network of trails and camps, and exploring deeper and deeper until you know the territory by heart and aren't scared of it anymore.

But I can read math much faster when I already roughly understand what's going on. Since I've been thinking about math for 40 years, that's often the case. For example: I'm writing a paper, I need something Theorem X and I feel it should be true, I look for papers that seem to state a theorem like this, I find one, but I notice it's stating Theorem X' - something a bit than I want. So I need to figure out if Theorem X' implies Theorem X - or perhaps I was confused and Theorem X is false and Theorem X' is the best substitute that's actually true. Here I usually dive straight into the middle of a paper, where I see Theorem X', and then work backwards to make sure I understand the definitions, and dip into the proof of Theorem X' just enough to get a sense of what's going on.

I guess the appropriate metaphor is parachuting into the jungle, in the midst of enemy territory, to save a hostage. Get in and out as fast as possible: just get the job done with minimum damage.

I can also read math quickly if I just want to get a flavor of what's going on, not a deep understanding. Here the metaphor might be a riverboat cruise where you sail past the jungle and admire it, but don't get off the boat.

`Allison wrote: > Do you have a similar metaphor for _reading_ mathematics? Reading mathematics is a complicated business. I read mathematics in different ways for different purposes. [That handout](http://www.people.vcu.edu/~dcranston/490/handouts/math-read.html) does an excellent job of explaining how to read mathematics when you 1) don't yet understand it but 2) want to understand it very well. That _does_ take an awful lot of time! It's the complete opposite of passive reading: you have work through all the concepts, see how they interact with the concepts you already understand, let them fight it out, ask yourself lots of questions, answer those questions - sometimes by doing calculations - and go through the reading over and over until the impenetrable murk turns into crystal clarity. Maybe an appropriate metaphor is hiking into the jungle, setting up a network of trails and camps, and exploring deeper and deeper until you know the territory by heart and aren't scared of it anymore. But I can read math much faster when I already roughly understand what's going on. Since I've been thinking about math for 40 years, that's often the case. For example: I'm writing a paper, I need something Theorem X and I feel it should be true, I look for papers that seem to state a theorem like this, I find one, but I notice it's stating Theorem X' - something a bit than I want. So I need to figure out if Theorem X' implies Theorem X - or perhaps I was confused and Theorem X is false and Theorem X' is the best substitute that's actually true. Here I usually dive straight into the middle of a paper, where I see Theorem X', and then work backwards to make sure I understand the definitions, and dip into the proof of Theorem X' just enough to get a sense of what's going on. I guess the appropriate metaphor is parachuting into the jungle, in the midst of enemy territory, to save a hostage. Get in and out as fast as possible: just get the job done with minimum damage. I can also read math quickly if I just want to get a flavor of what's going on, not a deep understanding. Here the metaphor might be a riverboat cruise where you sail past the jungle and admire it, but don't get off the boat.`

The ideas about "distinctions" on #31 by Prof. Ellerman (how nice to have him here to ask!) have since long looked intriguing to me, and puzzling. Hope the conversation happens to touch that.

`The ideas about "distinctions" on #31 by Prof. Ellerman (how nice to have him here to ask!) have since long looked intriguing to me, and puzzling. Hope the conversation happens to touch that.`

@Jesus, I'm also pretty excited about the comment by prof. Ellerman about distinctions. The laws of form are also picked up by Fransico Varela in order to model biological autonomy using category theory and adjunctions. There was a recent article by Loius Kauffman on this topic.

`@Jesus, I'm also pretty excited about the comment by prof. Ellerman about distinctions. The laws of form are also picked up by Fransico Varela in order to model biological autonomy using category theory and adjunctions. There was a recent [article by Loius Kauffman]( http://www.univie.ac.at/constructivism/journal/13/1/011.kauffman) on this topic.`

Thanks for the reference to the Kauffman paper. He has done much to decipher Spencer-Brown's writings. My analysis of how reasoning about "the Distinction" can lead to the two-element Boolean algebra is further explained in a note that can be downloaded from my site http://www.ellerman.org/a-note-on-spencer-browns-algebra/.

`Thanks for the reference to the Kauffman paper. He has done much to decipher Spencer-Brown's writings. My analysis of how reasoning about "the Distinction" can lead to the two-element Boolean algebra is further explained in a note that can be downloaded from my site http://www.ellerman.org/a-note-on-spencer-browns-algebra/.`

As a side speculation, I wonder what can be made of "continuous relaxation" of partition logic, i.e. defining that two elements a, b of X are linked, or in the same partition, using a real number from [0, 1]. 0 means that a and b are not linked, 1 corresponds to their equivalence and thus being in the same partition, 0.1 somewhere in between. These weak partitions may be arranged in a poset using any suitable <= relation, and also may form a Galois connection to the standard partitions poset of X.

This poset of weak partitions is clearly exploited by evolution, when partition defines some subsystem of an organism, and new elements can be weakly attached or detached to it - for example, a weak version of eye helping a primitive multi-cellular organism to find food more efficiently, thus outperforming its peers. And this works quite well, because in this setup gradient information for efficient navigation in the space of all possible solutions to this optimization problem is available.

`As a side speculation, I wonder what can be made of "continuous relaxation" of partition logic, i.e. defining that two elements a, b of X are linked, or in the same partition, using a real number from [0, 1]. 0 means that a and b are not linked, 1 corresponds to their equivalence and thus being in the same partition, 0.1 somewhere in between. These weak partitions may be arranged in a poset using any suitable <= relation, and also may form a Galois connection to the standard partitions poset of X. This poset of weak partitions is clearly exploited by evolution, when partition defines some subsystem of an organism, and new elements can be weakly attached or detached to it - for example, a weak version of eye helping a primitive multi-cellular organism to find food more efficiently, thus outperforming its peers. And this works quite well, because in this setup gradient information for efficient navigation in the space of all possible solutions to this optimization problem is available.`

I’m enjoying these Lectures, and in particular, the clear explanations and metaphors to deeper understand the meaning of these topics. I was stunned by seeing existential and universal quantifiers arising from right and left quantifiers. Moreover, the metaphor of ‘generous’ and ‘cautious’ for left and right adjoints, respectively, are powerful. Another pair — I don’t remember if it had already been used — could be ‘collective’ versus ‘individual,’ and a bunch of philosophy can start from there.

I’m wondering if we can also connect elements of partitions with right/left adjoints, through quantifiers. With right adjoints, we tend to exclude elements, leading to finer partitions. However, with left adjoints, we tend to include elements, leading to coarser partitions. If we need to create a finer partition, maybe we need to include ‘more information’: thus, if we go deeper into detail, we exclude elements that do not satisfy more precise requirements. Conversely, with left adjoints, if we ‘ignore’ some information, we can reach a higher level of abstraction; thus, our partition will be more inclusive and coarser. In this way, we could also use the pair ‘specialization’ vs. ‘abstraction,’ and we could even see the philosophical pair ‘deductive reasoning’ vs. ‘inductive reasoning’ as two adjoint movements that in principle may arise from broader categorical concepts. I hope that all of this makes sense.

The concepts of adjunction and approximation, discussed in Lecture 3, in my opinion, are very promising also for interdisciplinary applications. For example, a typical musical process is the compositional process: going from an initial idea to a complete piece. The inverse of this process is almost impossible: nobody exactly knows what the composer did, which precise path he or she did follow, what exactly the initial idea was. Two approximations are possible. From one side, there is an approximation from below, that is, a technical analysis to find recurring elements, connections between melodic fragments, and so on. Such a technical analysis, where higher structures are broken down into small, measurable units, could provide less information than needed, though. On the other side, there is an approximation from above, that could include more information than needed: it is the case of a conceptual/intuitive analysis or an analysis that related elements of a piece with style of the composers, drafts of other pieces, writings and poetics of the composer, some documents about his or her lessons or methods. In this composition example, the sought ‘inverse’ should be the analysis, but in general, a perfect analysis simply does not exist. Partitions give equivalence relations: to stay within this example, finer or coarser partitions can characterize in more or less detail elements of the same or more than one musical pieces. Your suggestions and corrections will be so helpful for me!

`I’m enjoying these Lectures, and in particular, the clear explanations and metaphors to deeper understand the meaning of these topics. I was stunned by seeing existential and universal quantifiers arising from right and left quantifiers. Moreover, the metaphor of ‘generous’ and ‘cautious’ for left and right adjoints, respectively, are powerful. Another pair — I don’t remember if it had already been used — could be ‘collective’ versus ‘individual,’ and a bunch of philosophy can start from there. I’m wondering if we can also connect elements of partitions with right/left adjoints, through quantifiers. With right adjoints, we tend to exclude elements, leading to finer partitions. However, with left adjoints, we tend to include elements, leading to coarser partitions. If we need to create a finer partition, maybe we need to include ‘more information’: thus, if we go deeper into detail, we exclude elements that do not satisfy more precise requirements. Conversely, with left adjoints, if we ‘ignore’ some information, we can reach a higher level of abstraction; thus, our partition will be more inclusive and coarser. In this way, we could also use the pair ‘specialization’ vs. ‘abstraction,’ and we could even see the philosophical pair ‘deductive reasoning’ vs. ‘inductive reasoning’ as two adjoint movements that in principle may arise from broader categorical concepts. I hope that all of this makes sense. The concepts of adjunction and approximation, discussed in Lecture 3, in my opinion, are very promising also for interdisciplinary applications. For example, a typical musical process is the compositional process: going from an initial idea to a complete piece. The inverse of this process is almost impossible: nobody exactly knows what the composer did, which precise path he or she did follow, what exactly the initial idea was. Two approximations are possible. From one side, there is an approximation from below, that is, a technical analysis to find recurring elements, connections between melodic fragments, and so on. Such a technical analysis, where higher structures are broken down into small, measurable units, could provide less information than needed, though. On the other side, there is an approximation from above, that could include more information than needed: it is the case of a conceptual/intuitive analysis or an analysis that related elements of a piece with style of the composers, drafts of other pieces, writings and poetics of the composer, some documents about his or her lessons or methods. In this composition example, the sought ‘inverse’ should be the analysis, but in general, a perfect analysis simply does not exist. Partitions give equivalence relations: to stay within this example, finer or coarser partitions can characterize in more or less detail elements of the same or more than one musical pieces. Your suggestions and corrections will be so helpful for me!`