#### Howdy, Stranger!

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

Options

# Exercise 2 - Chapter 1

edited April 2018

What is the result of joining the following two systems?

(This question only makes sense if you read the book!)

• Options
1.

We would get the partition {{11, 12, 22, 23, 13}, {21}}.

Comment Source:We would get the partition {{11, 12, 22, 23, 13}, {21}}.
• Options
2.

Sorry for the quality.

Comment Source:![12](https://image.ibb.co/iXi4h7/12.png) Sorry for the quality.
• Options
3.
edited April 2018

here is my entry, shows construction of the solution (visually)

Comment Source:here is my entry, shows construction of the solution (visually) <a href="http://ibb.co/i18Uzn"><img src="http://preview.ibb.co/nGmGen/book_chapter1_exersize02_sm.jpg" alt="book_chapter1_exersize02_sm" border="0"></a> 
• Options
4.
edited April 2018

Great! These pictures depict partitions of the set {1,2,3,4,5,6}: that is, ways of writing it as a disjoint union of nonempty subsets called blocks.

The collection of all partitions of a set is partially ordered by 'refinement': we say one partition $$P$$ is finer than another partition $$P'$$ if every block of $$P'$$ is a union of blocks of $$P$$. (One could say "finer than or equal to", but people say just "finer".) We also say, in this situation, that $$P'$$ is coarser than $$P$$.

We write $$P \le P'$$ if $$P$$ is finer than $$P'$$.

Here's a picture of all 15 partitions of a 4-element set, with finer ones nearer the bottom, and edges pointing up from each partition to the next coarser ones. This is called a Hasse diagram:

The picture was drawn by Tilman Piesk on Wikicommons. Click on it for a lot more information.

For any two partitions $$P,P'$$ of a set $$S$$, their meet $$P \vee P'$$ is the finest partition that is coarser than both. That's what this problem is about.

Comment Source:Great! These pictures depict **[partitions](https://en.wikipedia.org/wiki/Partition_of_a_set)** of the set {1,2,3,4,5,6}: that is, ways of writing it as a disjoint union of nonempty subsets called **blocks**. The collection of all partitions of a set is partially ordered by 'refinement': we say one partition \$$P\$$ is **finer** than another partition \$$P'\$$ if every block of \$$P'\$$ is a union of blocks of \$$P\$$. (One could say "finer than or equal to", but people say just "finer".) We also say, in this situation, that \$$P'\$$ is **coarser** than \$$P\$$. We write \$$P \le P'\$$ if \$$P\$$ is finer than \$$P'\$$. Here's a picture of all 15 partitions of a 4-element set, with finer ones nearer the bottom, and edges pointing up from each partition to the next coarser ones. This is called a [Hasse diagram](https://en.wikipedia.org/wiki/Hasse_diagram): <a href = "https://blogs.ams.org/visualinsight/2015/06/15/lattice-of-partitions/"> <img width = "450" src = "https://blogs.ams.org/visualinsight/files/2015/06/lattice_of_partitions.png"> </a> The picture was drawn by [Tilman Piesk](https://commons.wikimedia.org/wiki/File:Set_partitions_4;_Hasse;_circles.svg) on Wikicommons. Click on it for a lot more information. For any two partitions \$$P,P'\$$ of a set \$$S\$$, their **meet** \$$P \vee P'\$$ is the finest partition that is coarser than both. That's what this problem is about. 
• Options
5.

That’s a great picture John, thanks for posting it! I started doing this exercise on my own and understood how to construct the diagram. However, I found it difficult to anticipate exactly how to best lay out the elements to make the structure clear. Are there any techniques available for doing this that are better than experimentation?

Comment Source:That’s a great picture John, thanks for posting it! I started doing this exercise on my own and understood how to construct the diagram. However, I found it difficult to anticipate exactly how to best lay out the elements to make the structure clear. Are there any techniques available for doing this that are better than experimentation?
• Options
6.

Eye crossing works to get a quick view of the union.

Comment Source:Eye crossing works to get a quick view of the union.
• Options
7.
edited April 2018

John #4: After seeing your separate comment that you sometimes confuse meet and join (as in John #4 above) because their standard English meanings are similar, I began confusing them too:-)

I'm trying out the mnemonic that the M in Meet contains two $$\land$$s, and $$\land$$ points upward to the subset elements; while the J in Join is vaguely $$\vee$$-shaped, and $$\vee$$ points downward.

Comment Source:John #4: After seeing your separate comment that you sometimes confuse meet and join (as in John #4 above) because their standard English meanings are similar, I began confusing them too:-) I'm trying out the mnemonic that the M in Meet contains two \$$\land\$$s, and \$$\land\$$ points upward to the subset elements; while the J in Join is vaguely \$$\vee\$$-shaped, and \$$\vee\$$ points downward.
• Options
8.

I think of meet as what is common to the two -- the point at which they meet -- so that's the intersection. Joining implies combining them to make something bigger, which is the union.

Comment Source:I think of meet as what is common to the two -- the point at which they meet -- so that's the intersection. Joining implies combining them to make something bigger, which is the union.
• Options
9.

At first I was overthinking the solution and came up with this:

But after reading the definition of the \/ operator again, realized that since there is a path from 12 to 13 namely 12, 22, 23, 13 that there would, by definition, be a connection between the two.

Comment Source:At first I was overthinking the solution and came up with this: <img src="http://image.ibb.co/bXKYhH/ch1_ex2_soln.png"/> But after reading the definition of the \/ operator again, realized that since there is a path from 12 to 13 namely 12, 22, 23, 13 that there would, by definition, be a connection between the two.
• Options
10.
edited April 2018

My revised mnemonics are:

"meet up (^) and glob intersection" - MUAGI

"join down (v) or lub union" - JoDOLU

Comment Source:My revised mnemonics are: > "meet up (^) and glob intersection" - MUAGI > "join down (v) or lub union" - JoDOLU
• Options
11.

After seeing your separate comment that you sometimes confuse meet and join (as in John #4 above) because their standard English meanings are similar, I began confusing them too:-)

See what a great teacher I am? I can not only transmit my knowledge, I can also transmit my confusion!

I think of meet as what is common to the two -- the point at which they meet -- so that's the intersection. Joining implies combining them to make something bigger, which is the union.

Yes, this feels like the original motivation of those terms. It should help me keep them straight.

Comment Source:[Jerry wrote](https://forum.azimuthproject.org/discussion/comment/16625/#Comment_16625): > After seeing your separate comment that you sometimes confuse meet and join (as in John #4 above) because their standard English meanings are similar, I began confusing them too:-) See what a great teacher I am? I can not only transmit my knowledge, I can also transmit my confusion! [David wrote](https://forum.azimuthproject.org/discussion/comment/16638/#Comment_16638): > I think of meet as what is common to the two -- the point at which they meet -- so that's the intersection. Joining implies combining them to make something bigger, which is the union. Yes, this feels like the original motivation of those terms. It should help me keep them straight. 
• Options
12.

That’s a great picture John, thanks for posting it! I started doing this exercise on my own and understood how to construct the diagram. However, I found it difficult to anticipate exactly how to best lay out the elements to make the structure clear. Are there any techniques available for doing this that are better than experimentation?

I don't know! But when I was a grad student I had a roommate who worked on VLSI design - the design of very large integrated circuits. Part of this amounts to taking a graph and trying to draw it in the plane with the fewest crossing. He developed algorithms for doing this sort of thing. Perhaps some of these could be used for drawing pictures like this... but those algorithms weren't developed for visual beauty, so I don't know if they'd create nice pictures. So, I think people just try stuff and see what works.

Comment Source:[Matthew Johnson wrote](https://forum.azimuthproject.org/discussion/comment/16597/#Comment_16597): > That’s a great picture John, thanks for posting it! I started doing this exercise on my own and understood how to construct the diagram. However, I found it difficult to anticipate exactly how to best lay out the elements to make the structure clear. Are there any techniques available for doing this that are better than experimentation? I don't know! But when I was a grad student I had a roommate who worked on [VLSI](https://en.wikipedia.org/wiki/Very-large-scale_integration) design - the design of very large integrated circuits. Part of this amounts to taking a graph and trying to draw it in the plane with the fewest crossing. He developed algorithms for doing this sort of thing. Perhaps some of these could be used for drawing pictures like this... but those algorithms weren't developed for visual beauty, so I don't know if they'd create nice pictures. So, I think people just try stuff and see what works.
• Options
13.

I'm a bit late to the party! The resulting system would be split into two partitions, {11, 12, 13, 22, 23} and {21}.

Comment Source:I'm a bit late to the party! The resulting system would be split into two partitions, {11, 12, 13, 22, 23} and {21}.
• Options
14.

By definition points $$x$$ and $$y$$ are connected if there are points $$z_{1}...z_{n}$$ where $$x$$ is connected to $$z_{1}$$, $$z_{i}$$ is connected to $$z_{i+1}$$, and $$z_{i+1}$$ is connected to $$y$$. Applying this to the problem: $$11$$ and $$12$$ are connected in first set $$12$$ and $$22$$ are connected in second set $$\implies$$ $$11$$ and $$22$$ are connected

$$22$$ and $$23$$ are connected in first set $$23$$ and $$13$$ are connected in second set $$\implies$$ $$13$$ and $$22$$ are connected

$$21$$ is isolated in both sets

Hence the join operation will result in two partitions, which are {11,12,13,22,23} and {21}

Comment Source:By definition points \$$x\$$ and \$$y\$$ are connected if there are points \$$z_{1}...z_{n}\$$ where \$$x\$$ is connected to \$$z_{1}\$$, \$$z_{i}\$$ is connected to \$$z_{i+1}\$$, and \$$z_{i+1}\$$ is connected to \$$y\$$. Applying this to the problem: \$$11\$$ and \$$12\$$ are connected in first set \$$12\$$ and \$$22\$$ are connected in second set \$$\implies\$$ \$$11\$$ and \$$22\$$ are connected \$$22\$$ and \$$23\$$ are connected in first set \$$23\$$ and \$$13\$$ are connected in second set \$$\implies\$$ \$$13\$$ and \$$22\$$ are connected \$$21\$$ is isolated in both sets Hence the join operation will result in two partitions, which are {11,12,13,22,23} and {21}
• Options
15.

I'm having trouble understanding the definition of the join operation. Near the bottom of page 3 of the book, there is an example showing the join of system A with three "unconnected" elements and system B with two connected elements and an unconnected element, *. The result of joining A with B is given as a two-element system with two the connected elements and one individual element, the *.

A join is defined as: "That is, we shall say the join of systems A and B, denote it A ∨ B, has a connection between points x and y if there are some points z1, . . . , zn such that, in at least one of A or B, it is true that x is connected to z1, zi is connected to zi+1, and zn is connected to y."

So why is * in the resulting joined system?

My working hypothesis is that in order to satisfy the definition of the join, we must assume that * is joined to itself, i.e., in the definition, the point x and the point y are the same point, namely *. In other words, the connection is reflexive in addition to being symmetric and transitive.

Since nobody seems to be having any problems with this, I suspect my hypothesis is unnecessary and I am overlooking some obvious, simple answer to my problem. Maybe I'm misinterpreting the definition of a join.

Comment Source:I'm having trouble understanding the definition of the join operation. Near the bottom of page 3 of the book, there is an example showing the join of system A with three "unconnected" elements and system B with two connected elements and an unconnected element, *. The result of joining A with B is given as a two-element system with two the connected elements and one individual element, the *. A join is defined as: "That is, we shall say the join of systems A and B, denote it A ∨ B, has a connection between points x and y if there are some points z1, . . . , zn such that, in at least one of A or B, it is true that x is connected to z1, zi is connected to zi+1, and zn is connected to y." So why is * in the resulting joined system? My working hypothesis is that in order to satisfy the definition of the join, we must assume that * is joined to itself, i.e., in the definition, the point x and the point y are the same point, namely *. In other words, the connection is reflexive in addition to being symmetric and transitive. Since nobody seems to be having any problems with this, I suspect my hypothesis is unnecessary and I am overlooking some obvious, simple answer to my problem. Maybe I'm misinterpreting the definition of a join.
• Options
16.
edited April 2018

$$\ast$$ is not connected in the joined system to either $$\circ$$ or $$\bullet$$.

Each system has 3 elements and some number of connections. $$A$$ has 3 elements and 0 connections (each element is unconnected from each other element). $$B$$ has 3 elements and 1 connection ($$\bullet$$ and $$\circ$$ are connected, $$\ast$$ is unconnected from them). $$C = A \vee B$$ also has 3 elements, and 1 connection (the same as $$B$$).

Another thing to consider is what is changed by the join? That is, given two systems, do the elements change, or the connections when you join them? (NB: The connections do not have to change, $$A\vee A = A$$).

Originally I used "partition", that's because of how it's drawn. I've updated my description to be about elements and connections.

Comment Source:\$$\ast\$$ is *not* connected in the joined system to either \$$\circ\$$ or \$$\bullet\$$. Each system has 3 elements and some number of connections. \$$A\$$ has 3 elements and 0 connections (each element is unconnected from each other element). \$$B\$$ has 3 elements and 1 connection (\$$\bullet\$$ and \$$\circ\$$ are connected, \$$\ast\$$ is unconnected from them). \$$C = A \vee B\$$ also has 3 elements, and 1 connection (the same as \$$B\$$). Another thing to consider is what is changed by the join? That is, given two systems, do the *elements* change, or the *connections* when you join them? (NB: The connections do not have to change, \$$A\vee A = A\$$). ----- Originally I used "partition", that's because of how it's drawn. I've updated my description to be about elements and connections.
• Options
17.
edited April 2018

I think Jared answered Charlie's question just fine. I find terminology like "systems" and "connections" a bit annoying here because later in the book one sees a more precise treatment of these ideas using more standard, and more precisely defined, terminology.

As Jared already knows, when we get serious we use the term "partition" instead of "system". Charlie: we'll explore partitions in detail here:

However, it would be unwise to read these lectures until you've read the previous ones!

Comment Source:I think Jared answered Charlie's question just fine. I find terminology like "systems" and "connections" a bit annoying here because later in the book one sees a more precise treatment of these ideas using more standard, and more precisely defined, terminology. As Jared already knows, when we get serious we use the term "partition" instead of "system". Charlie: we'll explore partitions in detail here: * [Lecture 10 - Chapter 1: The Logic of Partitions](https://forum.azimuthproject.org/discussion/1963/lecture-10-the-logic-of-partitions/p1) * [Lecture 11 - Chapter 1: The Poset of Partitions](https://forum.azimuthproject.org/discussion/1991/lecture-11-chapter-1-the-poset-of-partitions/p1) * [Lecture 12 - Chapter 1: Generative Effects](https://forum.azimuthproject.org/discussion/1999/lecture-12-chapter-1-generative-effects/p1) * [Lecture 13 - Chapter 1: Pulling Back Partitions](https://forum.azimuthproject.org/discussion/2008/lecture-13-chapter-1-pulling-back-partitions/p1) However, it would be unwise to read these lectures until you've read the previous ones!
• Options
18.

Jared - Thank you for the insights. My hesitation was caused by the fact that the definition of join doesn't seem to require that $$C = A \vee B$$ must have three elements -- it seemed that I had the option of omitting * from C so that C would have only two (connected) elements. Now I see that if A, B, and C all have the same number of elements (i.e., the elements do not change), then the join is much easier to understand. I seem to have a "talent" for overly complicating solutions to relatively straightforward problems. I'll catch on ...

John - Thanks for the preview!

Comment Source:Jared - Thank you for the insights. My hesitation was caused by the fact that the definition of join doesn't seem to require that \$$C = A \vee B\$$ must have three elements -- it seemed that I had the option of omitting * from C so that C would have only two (connected) elements. Now I see that if A, B, and C all have the same number of elements (i.e., the elements do not change), then the join is much easier to understand. I seem to have a "talent" for overly complicating solutions to relatively straightforward problems. I'll catch on ... John - Thanks for the preview! 
• Options
19.

Charles - aim for simplicity; it's more likely to be right. As Einstein said:

Everything should be made as simple as possible, but not simpler.

Comment Source:Charles - aim for simplicity; it's more likely to be right. As Einstein said: > _Everything should be made as simple as possible, but not simpler._ 
• Options
20.
edited September 2018

The join {{11, 12}, {13}, {21}, {22, 23}} v {{11}, {12, 22}, {13, 23}, {21}} is {{11, 12, 13, 22, 23}, {21}}

Comment Source:The join {{11, 12}, {13}, {21}, {22, 23}} v {{11}, {12, 22}, {13, 23}, {21}} is {{11, 12, 13, 22, 23}, {21}}