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

- All Categories 2.2K
- Applied Category Theory Course 348
- Applied Category Theory Seminar 2
- Exercises 149
- Discussion Groups 48
- How to Use MathJax 15
- Chat 475
- Azimuth Code Project 108
- News and Information 145
- Azimuth Blog 148
- Azimuth Forum 29
- Azimuth Project 190
- - Strategy 109
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 708
- - Latest Changes 700
- - - Action 14
- - - Biodiversity 8
- - - Books 2
- - - Carbon 9
- - - Computational methods 38
- - - Climate 53
- - - Earth science 23
- - - Ecology 43
- - - Energy 29
- - - Experiments 30
- - - Geoengineering 0
- - - Mathematical methods 69
- - - Meta 9
- - - Methodology 16
- - - Natural resources 7
- - - Oceans 4
- - - Organizations 34
- - - People 6
- - - Publishing 4
- - - Reports 3
- - - Software 20
- - - Statistical methods 2
- - - Sustainability 4
- - - Things to do 2
- - - Visualisation 1
- General 39

Options

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

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 amonotone mapon \(\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\)

`> **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\\)`

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

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

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.

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

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 therightinverse 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 Choicein ZF set theory states: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 theconverseof 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.

`> **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.`

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

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

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?

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

`> 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`

@Christopher Upshaw Now that I am thinking about it, do you mean

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

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

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

uniquechoice 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))\).`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))\\).`

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

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

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.

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

Oh, I forgot prefix and suffix.

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

`Oh, I forgot prefix and suffix. Do you see why \[ prefix . suffix = suffix . prefix = infix \] ?`