Options

Exercise 4 - Chapter 1

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}\)?

Comments

  • 1.
    edited April 2
    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.
  • 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.
  • 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!
  • 4.
    edited April 2

    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\\)
  • 5.
    edited April 8

    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.
  • 6.
    edited April 19

    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?
  • 7.
    edited April 19

    Puzzle.

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

    \(\wedge\), meet, is and.

    Comment Source:**Puzzle.** \\(\vee\\), join, is `or`. \\(\wedge\\), meet, is `and`.
  • 8.
    edited April 20

    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?
  • 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).
  • 10.

    Jim: the great antimnemonic is this picture:

    image

    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!
  • 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 :-)
  • 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. :)
  • 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.
  • 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).
  • 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.

    Puzzle 54. What's ironic about the answers to these puzzles?

    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?
  • 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".
  • 17.

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

    image
    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>
  • 18.
    edited April 20

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

    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?
  • 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?
  • 20.
    edited April 22

    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.
  • 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.
  • 22.
    edited September 30
    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
Sign In or Register to comment.