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

- All Categories 2.3K
- Chat 500
- Study Groups 19
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 68
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 713

Options

Now that we're about to dip our toe into the sea of logic, it's good to do an exercise involving the **Booleans**:

$$ \mathbb{B} = \{ \tt{true}, \tt{false} \} . $$ This set becomes a poset where \(\tt{false}\leq\tt{false}\), \(\tt{false}\leq\textrm{true}\), and \(\tt{true}\leq\tt{true}\), but \(\tt{true}\not\leq\tt{false}\). In other words \(A\leq B\) in the poset if \(A\) implies \(B\), often denoted \(A\implies B\).

In any poset \(A \vee B\) stands for the **join** of \(A\) and \(B\): the least element of the poset that is greater than both \(A\) and \(B\). The join may not exist, but it is unique.

In the poset \(\mathbb{B}\), what is

- \(\tt{true}\lor\tt{false}\)?
- \(\tt{false}\lor\tt{true}\)?
- \(\tt{true}\lor\tt{true}\)?
- \(\tt{false}\lor\tt{false}\)?

## Comments

For any A, B in \(\mathbb{B} = \{\tt{true}, \tt{false}\}\), we can again write \(\tt{A}\lor\tt{B}\) to mean the least element that is greater than both A and B.

`1. \\(\tt{true}\lor\tt{false} \implies \tt{true}\\) 2. \\(\tt{false}\lor\tt{true} \implies \tt{true}\\) 3. \\(\tt{true}\lor\tt{true} \implies \tt{true}\\) 4. \\(\tt{false}\lor\tt{false} \implies \tt{false}\\) For any A, B in \\(\mathbb{B} = \\{\tt{true}, \tt{false}\\}\\), we can again write \\(\tt{A}\lor\tt{B}\\) to mean the least element that is greater than both A and B.`

Just some mnemonics:

To remember the difference between \(\wedge\) and \(\vee\), I imagine the arrows in the Hasse diagram all pointing down, so the "smaller" elements are at the top. Then if \(a\) and \(b\) are arbitrary elements in the set, then the paths through the Hasse diagram from \(a\) to \(a\vee b\) and from \(b\) to \(a\vee b\) (probably) form a \(\vee\) shape. Similar for \(\wedge\).

To remember "meet" and "join", I imagine its two people taking a trip through the poset, and so they meet before they start, and then join up at the end. So the meet is the last time they were together, and the join is the next time they will be together.

`Just some mnemonics: To remember the difference between \\(\wedge\\) and \\(\vee\\), I imagine the arrows in the Hasse diagram all pointing down, so the "smaller" elements are at the top. Then if \\(a\\) and \\(b\\) are arbitrary elements in the set, then the paths through the Hasse diagram from \\(a\\) to \\(a\vee b\\) and from \\(b\\) to \\(a\vee b\\) (probably) form a \\(\vee\\) shape. Similar for \\(\wedge\\). To remember "meet" and "join", I imagine its two people taking a trip through the poset, and so they meet before they start, and then join up at the end. So the meet is the last time they were together, and the join is the next time they will be together.`

Joseph - I like your "visual" mnemonics for "meet" and "join" very much!

`Joseph - I like your "visual" mnemonics for "meet" and "join" very much!`

I like it as well \(\vee = \searrow\swarrow\) and \(\wedge = \swarrow\searrow\)

`I like it as well \\(\vee = \searrow\swarrow\\) and \\(\wedge = \swarrow\searrow\\)`

With this exercise, I'd shrink the phrase "the least element that is greater than both A and B" to simply "least greatest". In the context of \( \tt{b} \) I would paraphrase again as "first occurrence of true". So we'd just say the expression short circuits on true and is otherwise false. So much like Fredrick's answer:

I'm sure there's a nicer way to do this with the lambda calculus; I don't know it.

`With this exercise, I'd shrink the phrase "the least element that is greater than both A and B" to simply "least greatest". In the context of \\( \tt{b} \\) I would paraphrase again as "first occurrence of true". So we'd just say the expression short circuits on true and is otherwise false. So much like Fredrick's answer: 1. \\( \tt{true} \lor \text{_} \implies \tt{true} \\) 2. \\( \text{_} \lor \tt{true} \implies \tt{true} \\) 3. follows from answer to 1 above 4. exhausted without any occurrence of \\( \tt{true} \\), and so is \\( \tt{false} \\) I'm sure there's a nicer way to do this with the lambda calculus; I don't know it.`

Puzzle.What are the commonly used names for \(\vee\) and \(\wedge\) in this particular poset?`**Puzzle.** What are the commonly used names for \\(\vee\\) and \\(\wedge\\) in this particular poset?`

Puzzle.\(\vee\), join, is

`or`

.\(\wedge\), meet, is

`and`

.`**Puzzle.** \\(\vee\\), join, is `or`. \\(\wedge\\), meet, is `and`.`

We've been working out lots of "joins", or "least upper bounds", so it's good to emphasize that they don't always exist!

Puzzle 26.What is the simplest poset that contains two elements \(x\) and \(y\) that have no least upper bound?Puzzle 27.What is the simplest poset that contains a subset that has no least upper bound?`We've been working out lots of "joins", or "least upper bounds", so it's good to emphasize that they don't always exist! **Puzzle 26.** What is the simplest poset that contains two elements \\(x\\) and \\(y\\) that have no least upper bound? **Puzzle 27.** What is the simplest poset that contains a subset that has no least upper bound?`

I'm transferring some comments from another thread to this one. Jim Stuttard wrote:

`I'm transferring some comments from another thread to this one. Jim Stuttard wrote: > Q. Are these mnemonics correct even if not useful? > * Meet up (^) and greatest intersect (MUAGI). > * Join down (v) or least disjunct (JDOLD).`

Jim: the great

antimnemonicis this picture:The meet \(\wedge\) is at the bottom and the join \(\vee\) is at the top, exactly opposite from how their symbols look!

`Jim: the great _antimnemonic_ is this picture: <center><img src = "https://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Join_and_meet.svg/500px-Join_and_meet.svg.png"></center> The meet \\(\wedge\\) is at the bottom and the join \\(\vee\\) is at the top, exactly opposite from how their symbols look!`

Jerry Wedekind wrote:

`Jerry Wedekind wrote: > For me it's mnemonic*; I think of the Meet (Join) symbol as pointing up (down) to the elements in the subset (and the up-arrow occurs twice in M, while the down-arrow is vaguely J-shaped). > *I hope this doesn't cancel w/ the anti-mnemonic; you should probably try to forget at least one of these :-)`

Grant Roy wrote:

`Grant Roy wrote: > I think of it as diving crocodile and soaring crocodile. :)`

Regarding mnemonics for these symbols. I recall them as their logic equivalents (where I first encountered the symbols) of

`and`

and`or`

, and set equivalents of`intersect`

and`union`

(which don't use the same symbols, but have similar shapes).`Join`

suggests connecting things, and keeping both. Ijointwo things together to make a third (potentially distinct) thing, but theymeetat their intersection.`Regarding mnemonics for these symbols. I recall them as their logic equivalents (where I first encountered the symbols) of `and` and `or`, and set equivalents of `intersect` and `union` (which don't use the same symbols, but have similar shapes). `Join` suggests connecting things, and keeping both. I *join* two things together to make a third (potentially distinct) thing, but they *meet* at their intersection.`

John Baez, #8: I believe you want the

`join`

for these puzzles, not the`meet`

.(emphasis mine)

If you mean

join, my answer topuzzle 26:The set, or discrete preorder as defined in the text, of two elements would be an example. It satisfies the requirements to be a poset. And there is no join for those two elements (nor a meet).

`John Baez, #8: I believe you want the `join` for these puzzles, not the `meet`. > We've been working out lots of **"meets"**, or "least upper bounds", so it's good to emphasize that they don't always exist! (emphasis mine) If you mean *join*, my answer to **puzzle 26**: The set, or discrete preorder as defined in the text, of two elements would be an example. It satisfies the requirements to be a poset. And there is no join for those two elements (nor a meet).`

Jared - I'm a bit confused by your comment. I have an annoying habit of mixing up the words "join" and "meet", but least by 10:26 am, before you wrote your comment, I wrote:

So, I don't understand your correction. Had I gotten it backwards before? I don't remember.

Luckily, the answers to Puzzles 26 and 27 don't change if you replace the term "least upper bound" by "greatest lower bound".

Here are some more puzzles:

Puzzle 52.Draw the Hasse diagram of the smallest poset containing two elements that have a meet but not a join.Puzzle 53.Draw the Hasse diagram of the smallest poset containing two elements that have a join but not a meet.Puzzle 54.What's ironic about the answers to these puzzles?`Jared - I'm a bit confused by your comment. I have an annoying habit of mixing up the words "join" and "meet", but least by 10:26 am, before you wrote your comment, I wrote: > We've been working out lots of "joins", or "least upper bounds", so it's good to emphasize that they don't always exist! So, I don't understand your correction. Had I gotten it backwards before? I don't remember. Luckily, the answers to Puzzles 26 and 27 don't change if you replace the term "least upper bound" by "greatest lower bound". Here are some more puzzles: **Puzzle 52.** Draw the Hasse diagram of the smallest poset containing two elements that have a meet but not a join. **Puzzle 53.** Draw the Hasse diagram of the smallest poset containing two elements that have a join but not a meet. **Puzzle 54.** What's ironic about the answers to these puzzles?`

Puzzle 54.They look like what they don't have!As an aside, I always get these backwards. Something about \(\wedge\) makes me think "upward".

`**Puzzle 54.** They look like what they don't have! As an aside, I always get these backwards. Something about \\(\wedge\\) makes me think "upward".`

Jonathan - good answer to puzzle 54! I also get meets and joins backwards, apparently for the same reason you do:

`Jonathan - good answer to puzzle 54! I also get meets and joins backwards, apparently for the same reason you do: <center><img src = "https://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Join_and_meet.svg/500px-Join_and_meet.svg.png"></center>`

My mnemonic is oddly physics-based, involving past and future light cones.

See the hidden \(\wedge\) and \(\vee\) in the picture?

`My mnemonic is oddly physics-based, involving past and future light cones. ![Light cones](https://upload.wikimedia.org/wikipedia/commons/thumb/1/16/World_line.svg/200px-World_line.svg.png) See the hidden \\(\wedge\\) and \\(\vee\\) in the picture?`

Right after exercise 1.3, the book states that the set of booleans has an order \(\tt{false}\leq\textrm{true}\) and shows a Hesse diagram containing only the elements true on the top and false on the bottom. But at this point in the book, we have dealt only with Hesse diagrams of partitions, which would show the order by depicting {{true, false}} on the top and {{true}, {false}} on the bottom.

It appears that the Hesse diagram right after exercise 1.3 in the book is undefined. How is this Hesse diagram defined?

`Right after exercise 1.3, the book states that the set of booleans has an order \\(\tt{false}\leq\textrm{true}\\) and shows a Hesse diagram containing only the elements true on the top and false on the bottom. But at this point in the book, we have dealt only with Hesse diagrams of partitions, which would show the order by depicting {{true, false}} on the top and {{true}, {false}} on the bottom. It appears that the Hesse diagram right after exercise 1.3 in the book is undefined. How is this Hesse diagram defined?`

Charles, Hasse diagrams are a pictorial way of presenting any partial order, not only those on partitions. A Hasse diagram induces a partial order where \(x \le y\) iff there is an upwards-directed path from \(x\) to \(y\) in the Hasse diagram. This is the case regardless of the carrier set that \(x\) and \(y\) are elements of.

`Charles, Hasse diagrams are a pictorial way of presenting any partial order, not only those on partitions. A Hasse diagram induces a partial order where \\(x \le y\\) iff there is an upwards-directed path from \\(x\\) to \\(y\\) in the Hasse diagram. This is the case regardless of the carrier set that \\(x\\) and \\(y\\) are elements of.`

Thank you, Jonathan, for the clarification. I thought that the Hesse diagram for the two-element set in the immediately preceding exercise 1.3 was intended to be an introduction to the set of booleans. That doesn't seem to be the case.

`Thank you, Jonathan, for the clarification. I thought that the Hesse diagram for the two-element set in the immediately preceding exercise 1.3 was intended to be an introduction to the set of booleans. That doesn't seem to be the case.`

`1. true \\(\vee\\) false = true 2. false \\(\vee\\) true = true 3. true \\(\vee\\) true = true 4. false \\(\vee\\) false = false`