#### Howdy, Stranger!

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

Options

# Exercise 4 - Chapter 1

edited April 2018

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

1. $$\tt{true}\lor\tt{false}$$?
2. $$\tt{false}\lor\tt{true}$$?
3. $$\tt{true}\lor\tt{true}$$?
4. $$\tt{false}\lor\tt{false}$$?

• Options
1.
edited April 2018
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.

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

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.

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

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

Comment Source:Joseph - I like your "visual" mnemonics for "meet" and "join" very much!
• Options
4.
edited April 2018

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

Comment Source:I like it as well \$$\vee = \searrow\swarrow\$$ and \$$\wedge = \swarrow\searrow\$$
• Options
5.
edited April 2018

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.

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

Puzzle. What are the commonly used names for $$\vee$$ and $$\wedge$$ in this particular poset?

Comment Source:**Puzzle.** What are the commonly used names for \$$\vee\$$ and \$$\wedge\$$ in this particular poset?
• Options
7.
edited April 2018

Puzzle.

$$\vee$$, join, is or.

$$\wedge$$, meet, is and.

Comment Source:**Puzzle.** \$$\vee\$$, join, is or. \$$\wedge\$$, meet, is and.
• Options
8.
edited April 2018

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?

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

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

Jim: the great antimnemonic is this picture: The meet $$\wedge$$ is at the bottom and the join $$\vee$$ is at the top, exactly opposite from how their symbols look!

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

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 :-)

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

Grant Roy wrote:

I think of it as diving crocodile and soaring crocodile. :)

Comment Source:Grant Roy wrote: > I think of it as diving crocodile and soaring crocodile. :)
• Options
13.

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.

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

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

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

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.

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

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

Comment Source:**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".
• Options
17.

Jonathan - good answer to puzzle 54! I also get meets and joins backwards, apparently for the same reason you do: Comment Source: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>
• Options
18.
edited April 2018

My mnemonic is oddly physics-based, involving past and future light cones. See the hidden $$\wedge$$ and $$\vee$$ in the picture?

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

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?

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

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.

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

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.

Comment Source: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.
• Options
22.
edited September 2018
1. true $$\vee$$ false = true
2. false $$\vee$$ true = true
3. true $$\vee$$ true = true
4. false $$\vee$$ false = false
Comment Source:1. true \$$\vee\$$ false = true 2. false \$$\vee\$$ true = true 3. true \$$\vee\$$ true = true 4. false \$$\vee\$$ false = false