Options

Exercises and Puzzles 2 - Chapter 1

edited May 2018 in Exercises

Time to get off your butt and get some exercise!

Jared Summers wrote a nice answer to this one, but there are some natural followups:

Puzzle. If \(A\) and \(B\) are possibly infinite sets, and there's an injection \(f: A \to B\) and an injection \(g: B \to A\), is there a bijection between \(A\) and \(B\)?

Puzzle. If \(A\) and \(B\) are possibly infinite sets, and there's a surjection \(f: A \to B\) and an surjection \(g: B \to A\), is there a bijection between \(A\) and \(B\)?

Vladislav Papayan answered this one, but again there's a subsidiary puzzle:

Puzzle. Given two surjections \(f: A \to P\), \(g: A \to Q\), when do they determine the same partition of \(A\)?

I've also created a bunch of numbered puzzles, and we can work through those. The first three are largely obsolete, luckily, because Fong and Spivak fixed their definition of "poset". Borrowing some text from Matthew Doty:

Puzzle 1. What is a "poset" according to the original version of Chapter 1 of Fong and Spivak's book?

They had defined a poset as a set with a preorder, but now they don't.

Puzzle 2. How does their definition differ from the usual definition found in, e.g., Wikipedia or the nLab?

Ordinarily, a poset is a set with a partial order rather than a preorder.

A partial order is a preorder obeying the antisymmetry axiom: if \(x \le y \) and \( y \le x \) then \( x = y \).

Puzzle 3. What do mathematicians usually call the thing that Fong and Spivak called a poset?

They are usually called preordered sets or simply preorders. Modal logicians call them "S4 Kripke Frames".

Puzzle 4. List some interesting and important examples of posets that haven't already been listed in other comments in this thread.

Daniel Cellucci has collected many - but probably not all! - our answers here:

To see all the exercises in Chapter 1, go here.

Comments

  • 1.
    edited April 2018

    Puzzle. If \(A\) and \(B\) are possibly infinite sets, and there's an injection \(f:A\to B\) and an injection \(g: B\to A\), is there a bijection between \(A\) and \(B\)?

    Yes. This is the Schröder–Bernstein theorem. My favorite proof uses the Knaster-Tarski Theorem.

    I did the proof back in the comments of Lecture 4, but it's one of my favorites so I am going to repeat myself:

    The Schröder–Bernstein Theorem. Let \(f: X \rightarrowtail Y\) and \(g: Y \rightarrowtail X\) be a pair of injections. There exists a bijection \(h: X \to Y\).

    Proof.

    Let \(f_!(A) := \{f(a)\ :\ a \in A\}\) denote the direct image of \(f\) and similarly let \(g_!\) denote the direct image of \(g\).

    Define \(F: \mathcal{P}(X) \to \mathcal{P}(X)\) as follows:

    $$ F(S) := X \setminus\, g_!(Y \setminus\, f_!(S)) $$ \(F\) is a monotone map on \(\mathcal{P}(X)\) when ordered by set containment.

    Define \(\mu F\) to be:

    $$ \mu F := \bigcap \{A \subseteq X\ :\ F(A) \subseteq A\} $$ Then \(F(\mu F) = \mu F\). This is the Knaster-Tarski Theorem and generalizes to any monotone map on any complete lattice to itself.

    Finally, define \(h: X \to Y\):

    $$h(x) := \begin{cases} f(x) & x \in \mu F \\ g^{-1}(x) & x \not\in \mu F \end{cases} $$ Then \(h\) is the desired bijection, and its inverse is given by:

    $$h^{-1}(y) := \begin{cases} f^{-1}(y) & y \in f_!(\mu F) \\ g(y) & y \not\in f_!(\mu F) \end{cases} $$ It's straight forward to check these are both well defined, injective and indeed inverses. \(\Box\)

    Comment Source:> **Puzzle**. If \\(A\\) and \\(B\\) are possibly infinite sets, and there's an injection \\(f:A\to B\\) and an injection \\(g: B\to A\\), is there a bijection between \\(A\\) and \\(B\\)? Yes. This is the [Schröder–Bernstein theorem](https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem). My favorite proof uses the [Knaster-Tarski Theorem](https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem). I did the proof back in the comments of [Lecture 4](https://forum.azimuthproject.org/discussion/comment/16260/#Comment_16260), but it's one of my favorites so I am going to repeat myself: **The Schröder–Bernstein Theorem**. Let \\(f: X \rightarrowtail Y\\) and \\(g: Y \rightarrowtail X\\) be a pair of injections. There exists a bijection \\(h: X \to Y\\). **Proof**. Let \\(f_!(A) := \\{f(a)\ :\ a \in A\\}\\) denote the direct image of \\(f\\) and similarly let \\(g_!\\) denote the direct image of \\(g\\). Define \\(F: \mathcal{P}(X) \to \mathcal{P}(X)\\) as follows: $$ F(S) := X \setminus\, g_!(Y \setminus\, f_!(S)) $$ *\\(F\\) is a **monotone map** on \\(\mathcal{P}(X)\\) when ordered by set containment.* Define \\(\mu F\\) to be: $$ \mu F := \bigcap \\{A \subseteq X\ :\ F(A) \subseteq A\\} $$ Then \\(F(\mu F) = \mu F\\). This is the [Knaster-Tarski Theorem](https://en.wikipedia.org/wiki/Knaster%E2%80%93Tarski_theorem) and generalizes to any monotone map on any complete lattice to itself. Finally, define \\(h: X \to Y\\): $$h(x) := \begin{cases} f(x) & x \in \mu F \\\\ g^{-1}(x) & x \not\in \mu F \end{cases} $$ Then \\(h\\) is the desired bijection, and its inverse is given by: $$h^{-1}(y) := \begin{cases} f^{-1}(y) & y \in f_!(\mu F) \\\\ g(y) & y \not\in f_!(\mu F) \end{cases} $$ It's straight forward to check these are both well defined, injective and indeed inverses. \\(\Box\\)
  • 2.

    Matthew Doty - very nice! I see you're a master of posets.

    Comment Source:Matthew Doty - very nice! I see you're a master of posets.
  • 3.

    Thank you John! That is very kind to say.

    But there's always room to learn!

    Thank you so much for showing me Bi-Heyting algebras and the work of Ranzato and Rauszer. Along with Ellerman I see I have a lot of reading to do.

    Comment Source:Thank you John! That is very kind to say. But there's always room to learn! Thank you so much for showing me Bi-Heyting algebras and the work of Ranzato and Rauszer. Along with Ellerman I see I have a lot of reading to do.
  • 4.
    edited April 2018

    Puzzle. If \(A\) and \(B\) are possibly infinite sets, and there's a surjection \(f: A \hookrightarrow B\) and an surjection \(g: B \hookrightarrow A\), is there a bijection between \(A\) and \(B\)?

    Yes, but the proof I know is not constructive. It rests essentially on The Axiom of Choice in ZF set theory.

    First, I will use the following lemma, which I guess is a puzzle because

    Lemma. Let \(f: A \to B\) be a function, and let \(\hat{f} : B \to A\) be the right inverse of \(f\) such that \(f(\hat{f}(x)) = x\). Then \(f\) is a surjection and \(\hat{f}\) is an injection.

    MD Puzzle 1. Prove the above lemma.

    According to wikipedia, the Axiom of Choice in ZF set theory states:

    For any set \(X\) of nonempty sets, there exists a choice function \(f\) defined on \(X\).

    Formally, this may be expressed as follows:

    $$ \forall X \left[ \emptyset \notin X \implies \exists f \colon X \rightarrow \bigcup X \quad \forall A \in X \, ( f(A) \in A ) \right] \,. $$

    Theorem. The Axiom of Choice implies for every surjective function \(f : A \hookrightarrow B\), there exists a right inverse function \(\hat{f} : B \rightarrowtail A\) such that \(f(\hat{f}(x)) = x\)

    Proof.

    As we have seen, surjective functions define partitions on their domains. For each \(b \in B\), let \(S(b) := f^\ast (\{b\})\), or in other words:

    $$ S(b) = \{ a \in A \, :\, f(a) = b\} $$ \(S(b)\) is a partition component of \(A\) indexed by \(b\).

    Next, define

    $$ P := \{ \{a \in A\, :\, f(a) = b\}\, :\, b \in B\} $$ This is the partition of \(A\) induced by \(f\).

    By the axiom of choice, there exists a choice function \(c: P \to \bigcup P \) where \(\forall X \in P. c(X) \in X\). Since, \(S(b) \in P\) then \(c(S(b)) \in S(b)\). But since \(\forall a \in S(b). f(a) = b\), then \(f(c(S(b)) = b\), which means that \(\hat{f} = c \circ S\) is the desired right inverse function. \(\Box\)

    MD Puzzle 2. Prove the converse of the above theorem.

    Let's return back to our two surjections \(f: A \hookrightarrow B\) and \(g: B \hookrightarrow A\). With the lemma and the theorem, we have two injections \(\hat{f}: B \rightarrowtail A\), and \(\hat{g}: A \rightarrowtail B\), which are the right inverses of \(f\) and \(g\) respectively. By the Schröder-Bernstein theorem, these two bijections suffice to construct a bijection.


    There's more marvelous things to say about the axiom of choice. It might be nice to discuss it's role Topos theory, and Diaconescu's theorem which is astonishing.

    Comment Source:> **Puzzle.** If \\(A\\) and \\(B\\) are possibly infinite sets, and there's a surjection \\(f: A \hookrightarrow B\\) and an surjection \\(g: B \hookrightarrow A\\), is there a bijection between \\(A\\) and \\(B\\)? Yes, but the proof I know is not constructive. It rests essentially on [The Axiom of Choice](https://en.wikipedia.org/wiki/Axiom_of_choice) in [ZF set theory](https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory). First, I will use the following lemma, which I guess is a puzzle because *Lemma*. Let \\(f: A \to B\\) be a function, and let \\(\hat{f} : B \to A\\) be the *right* inverse of \\(f\\) such that \\(f(\hat{f}(x)) = x\\). Then \\(f\\) is a surjection and \\(\hat{f}\\) is an injection. **MD Puzzle 1**. Prove the above lemma. According to [wikipedia](https://en.wikipedia.org/wiki/Axiom_of_choice#Statement), the *Axiom of Choice* in ZF set theory states: > *For any set \\(X\\) of nonempty sets, there exists a choice function \\(f\\) defined on \\(X\\).* > > Formally, this may be expressed as follows: > > $$ \forall X \left[ \emptyset \notin X \implies \exists f \colon X \rightarrow \bigcup X \quad \forall A \in X \, ( f(A) \in A ) \right] \,. $$ **Theorem.** The Axiom of Choice implies for every surjective function \\(f : A \hookrightarrow B\\), there exists a right inverse function \\(\hat{f} : B \rightarrowtail A\\) such that \\(f(\hat{f}(x)) = x\\) **Proof.** As we have seen, surjective functions define partitions on their domains. For each \\(b \in B\\), let \\(S(b) := f^\ast (\\{b\\})\\), or in other words: $$ S(b) = \\{ a \in A \, :\, f(a) = b\\} $$ *\\(S(b)\\) is a partition component of \\(A\\) indexed by \\(b\\)*. Next, define $$ P := \\{ \\{a \in A\, :\, f(a) = b\\}\, :\, b \in B\\} $$ This is the partition of \\(A\\) induced by \\(f\\). By the axiom of choice, there exists a choice function \\(c: P \to \bigcup P \\) where \\(\forall X \in P. c(X) \in X\\). Since, \\(S(b) \in P\\) then \\(c(S(b)) \in S(b)\\). But since \\(\forall a \in S(b). f(a) = b\\), then \\(f(c(S(b)) = b\\), which means that \\(\hat{f} = c \circ S\\) is the desired right inverse function. \\(\Box\\) **MD Puzzle 2**. Prove the *converse* of the above theorem. Let's return back to our two surjections \\(f: A \hookrightarrow B\\) and \\(g: B \hookrightarrow A\\). With the lemma and the theorem, we have two injections \\(\hat{f}: B \rightarrowtail A\\), and \\(\hat{g}: A \rightarrowtail B\\), which are the right inverses of \\(f\\) and \\(g\\) respectively. By the Schröder-Bernstein theorem, these two bijections suffice to construct a bijection. -------------------------------- There's more marvelous things to say about the axiom of choice. It might be nice to discuss it's role Topos theory, and [Diaconescu's theorem](https://en.wikipedia.org/wiki/Diaconescu%27s_theorem) which is astonishing.
  • 5.
    edited April 2018

    I wonder if the other way is true. That is, is there a Brownian counterexamples to the surjective/surjective case.

    Also unless A and B are countable, I don't see how to construct the inverses (or inverse images) needed to construct h in even in the injective case. That is, given an \(a \in A\) how do you find the \(b \in B\) such that \(a = g(b)\).

    Comment Source:I wonder if the other way is true. That is, is there a Brownian counterexamples to the surjective/surjective case. Also unless A and B are countable, I don't see how to construct the inverses (or inverse images) needed to construct h in even in the injective case. That is, given an \\(a \in A\\) how do you find the \\(b \in B\\) such that \\(a = g(b)\\).
  • 6.
    edited April 2018

    I wonder if the other way is true. That is, is there a Brownian counterexamples to the surjective/surjective case.

    Are you talking about MD Puzzle 2? It' a classic result. If you want a spoiler you can take a peek at Planet Math.

    What are these Brownian counterexamples?

    Also unless A and B are countable, I don't see how to construct the inverses (or inverse images) needed to construct h.

    In ZF set theory functions are just thought of as ordered pairs, so \(f^{-1} = \{(y,x)\, :\, (x,y) \in f\}\).

    Moreover, \(\mu F\) is in the domain of \(f^{-1}\) if you are wondering about that.

    John Harrison has an implementation of the Knaster-Tarski theorem proof of Schröder-Bernstein's theorem in HOL-Light if you are still not sure: https://github.com/jrh13/hol-light/blob/57babc9af09dffe40da5cfdda4e84f5de0432ab8/Library/card.ml#L36

    Comment Source:> I wonder if the other way is true. That is, is there a Brownian counterexamples to the surjective/surjective case. Are you talking about **MD Puzzle 2**? It' a classic result. If you want a spoiler you can take a peek at [Planet Math](http://planetmath.org/SurjectionAndAxiomOfChoice). What are these Brownian counterexamples? > Also unless A and B are countable, I don't see how to construct the inverses (or inverse images) needed to construct h. In ZF set theory functions are just thought of as ordered pairs, so \\(f^{-1} = \\{(y,x)\, :\, (x,y) \in f\\}\\). Moreover, \\(\mu F\\) is in the domain of \\(f^{-1}\\) if you are wondering about that. John Harrison has an implementation of the Knaster-Tarski theorem proof of Schröder-Bernstein's theorem in HOL-Light if you are still not sure: https://github.com/jrh13/hol-light/blob/57babc9af09dffe40da5cfdda4e84f5de0432ab8/Library/card.ml#L36
  • 7.

    What are these Brownian counterexamples?

    @Christopher Upshaw Now that I am thinking about it, do you mean Brouwerian arguments as in LEJ Brouwer's classic Intuitionism and Formalism (1919)? They aren't precisely counter examples. They are just arguments. Moreover, if intuitionistic logic is consistent, classical logic is consistent by Glivenko's theorem.

    It might be possible to construct a model of intuitionistic logic such as a topos where the Schroeder-Bernstein is not true. I don't really know intuitionistic model theory that well.

    There is an analogue of the Schroeder-Bernstein theorem in computability theory: it is called Myhill's Isomorphism Theorem. It can be programmed in Haskell rather concisely. If this is something people would be interested in we can explore it.

    Comment Source:> What are these Brownian counterexamples? [@Christopher Upshaw](https://forum.azimuthproject.org/profile/2188/Christopher%20Upshaw) Now that I am thinking about it, do you mean *Brouwerian* arguments as in LEJ Brouwer's classic [Intuitionism and Formalism (1919)](https://projecteuclid.org/download/pdf_1/euclid.bams/1183422499)? They aren't precisely counter examples. They are just arguments. Moreover, if intuitionistic logic is consistent, classical logic is consistent by [Glivenko's theorem](https://en.wikipedia.org/wiki/Double-negation_translation). It might be possible to construct a model of intuitionistic logic such as a topos where the Schroeder-Bernstein is not true. I don't really know intuitionistic model theory that well. There is an analogue of the Schroeder-Bernstein theorem in computability theory: it is called [Myhill's Isomorphism Theorem](https://en.wikipedia.org/wiki/Myhill_isomorphism_theorem). It can be programmed in Haskell rather concisely. If this is something people would be interested in we can explore it.
  • 8.
    edited April 2018

    I think there is another example of a poset (Puzzle 4) from Owen Biesel's puzzles in the comments of Lecture 17 (OB1 to OB4): the set of galois connections \( \{ (f, g) : f \dashv g \} \) between two posets \(A\) and \(B\) forms a poset.

    A galois connection \( f \dashv g \), \( f : A \to B \) and \( g : B \to A \), between posets induces sub-posets \( A_{closed} = \{ g(f(a)) : a \in A \} \) and \( B_{closed} = \{ f(g(b)) : b \in B \} \), where \(f\) and \(g\) restrict to isomorphisms between \( A_{closed} \) and \( B_{closed} \) [by OB1-OB4]. Then, let \( (f, g) \leq (f', g') \) if and only if the isomorphism between \(A_{closed}'\) and \(B_{closed}'\) extends the isomorphism between \( A_{closed} \) and \( B_{closed} \) [that is, \( A_{closed} \subseteq A_{closed}' \), \( B_{closed} \subseteq B_{closed}' \), \(f(a) = f'(a)\) for all \(a \in A_{closed}\), and \( g(b) = g'(b)\) for all \(b \in B_{closed}\)] . This relation is reflexive and transitive, so it is a preorder.

    But I think the relation is also antisymmetric, and hence a poset, since the induced isomorphism between the sub-posets \(A_{closed}\) and \(B_{closed}\) seems to uniquely determine \(f\) and \(g\). Here is my reasoning:

    Let there be a galois connection \( f \dashv g \) with closed sub-posets \(A_{closed} \cong B_{closed}\), and let \(a \in A\) . We will show that there is a unique choice for \(f(a) \in B\). By puzzle OB2, we know that \( f(a) \in B_{closed}\). But, by the isomorphism between \( A_{closed} \) and \( B_{closed} \), a choice of \( f(a) \in B_{closed} \) is "the same thing" as a choice of \( g(f(a)) \in A_{closed} \), so we'll choose \( g(f(a)) \) instead. Now, since \( a \leq g(f(a)) \) [by adjoints], we know that \( g(f(a)) \in A_{up} = \{ a' \in A_{closed} : a \leq a' \} \). Moreover, \(g(f(a))\) is actually a minimum of \(A_{up}\), since \(a' \in A_{up}\) implies \(a \leq a' \) and \(g(f(a')) = a' \), which together imply \( g(f(a)) \leq g(f(a')) = a' \) [puzzle OB3]. But since \(A\) is a poset, this minimum is unique, and thus so is the choice of \(g(f(a))\).

    Comment Source:I think there is another example of a poset (Puzzle 4) from Owen Biesel's puzzles in the comments of Lecture 17 (OB1 to OB4): the set of galois connections \\( \\{ (f, g) : f \dashv g \\} \\) between two posets \\(A\\) and \\(B\\) forms a poset. A galois connection \\( f \dashv g \\), \\( f : A \to B \\) and \\( g : B \to A \\), between posets induces sub-posets \\( A_{closed} = \\{ g(f(a)) : a \in A \\} \\) and \\( B_{closed} = \\{ f(g(b)) : b \in B \\} \\), where \\(f\\) and \\(g\\) restrict to isomorphisms between \\( A_{closed} \\) and \\( B_{closed} \\) [by OB1-OB4]. Then, let \\( (f, g) \leq (f', g') \\) if and only if the isomorphism between \\(A_{closed}'\\) and \\(B_{closed}'\\) extends the isomorphism between \\( A_{closed} \\) and \\( B_{closed} \\) [that is, \\( A_{closed} \subseteq A_{closed}' \\), \\( B_{closed} \subseteq B_{closed}' \\), \\(f(a) = f'(a)\\) for all \\(a \in A_{closed}\\), and \\( g(b) = g'(b)\\) for all \\(b \in B_{closed}\\)] . This relation is reflexive and transitive, so it is a preorder. But I think the relation is also antisymmetric, and hence a poset, since the induced isomorphism between the sub-posets \\(A_{closed}\\) and \\(B_{closed}\\) seems to uniquely determine \\(f\\) and \\(g\\). Here is my reasoning: Let there be a galois connection \\( f \dashv g \\) with closed sub-posets \\(A_{closed} \cong B_{closed}\\), and let \\(a \in A\\) . We will show that there is a *unique* choice for \\(f(a) \in B\\). By puzzle OB2, we know that \\( f(a) \in B_{closed}\\). But, by the isomorphism between \\( A_{closed} \\) and \\( B_{closed} \\), a choice of \\( f(a) \in B_{closed} \\) is "the same thing" as a choice of \\( g(f(a)) \in A_{closed} \\), so we'll choose \\( g(f(a)) \\) instead. Now, since \\( a \leq g(f(a)) \\) [by adjoints], we know that \\( g(f(a)) \in A_{up} = \\{ a' \in A_{closed} : a \leq a' \\} \\). Moreover, \\(g(f(a))\\) is actually a minimum of \\(A_{up}\\), since \\(a' \in A_{up}\\) implies \\(a \leq a' \\) and \\(g(f(a')) = a' \\), which together imply \\( g(f(a)) \leq g(f(a')) = a' \\) [puzzle OB3]. But since \\(A\\) is a poset, this minimum is unique, and thus so is the choice of \\(g(f(a))\\).
  • 9.

    Yes i did mean those. And being a CS person I fell into a computational context instead of a ZF one. My bad.

    Comment Source:Yes i did mean those. And being a CS person I fell into a computational context instead of a ZF one. My bad.
  • 10.

    There are a ton of preorders and posets in CS. For example on lists you have: Pointwise, alphabetic, infix, sublist, as subset, as multiset, by length. I've used all of these, except pointwise. Alphabetic is the default ordering, because total orders are useful, and alphabetic takes a (total) order into a (total) order.

    Comment Source:There are a ton of preorders and posets in CS. For example on lists you have: Pointwise, alphabetic, infix, sublist, as subset, as multiset, by length. I've used all of these, except pointwise. Alphabetic is the default ordering, because total orders are useful, and alphabetic takes a (total) order into a (total) order.
  • 11.
    edited April 2018

    Oh, I forgot prefix and suffix.

    Do you see why [ prefix . suffix = suffix . prefix = infix ] ?

    Comment Source: Oh, I forgot prefix and suffix. Do you see why \[ prefix . suffix = suffix . prefix = infix \] ?
Sign In or Register to comment.