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

- All Categories 2.4K
- Chat 505
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 75
- Azimuth Code Project 111
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 719

Options

**(Pullback map).** Let \(P\) and \(Q\) be preorders, and \(f: P \mapsto Q\) be a monotone map. Then we can define a monotone function

$$f^{*}: \mathcal{U}(Q) \to \mathcal{U}(P) $$
sending an upper set \(U \subseteq Q\) to the upper set \(f^{-1}(U) \subseteq P\). We call this the **pullback along \(f\)**.

Viewing upper sets as monotone functions to \(\mathbb B\) as in Proposition 1.58, the pullback can be understood in terms of composition. Indeed, show that the function \(f^{*}\) is defined by taking \(u: Q \to \mathbb B\) to \(f.u: P \to \mathbb B\).

(Recall that \(\mathcal{U}(Q)\) denotes the set of upper sets of \(Q\).)

## Comments

The upper set \(U \subseteq Q\), corresponding to the monotone map \(u: Q \mapsto \mathbb B\), is the set of elements \(q \in Q\) with \(u(q) = \text{true}\space\color{blue}{[\mathbf{1}]}\). We must show that with \(f^{*}\) as defined in the Exercise, we have \(f^{*}(U) = f^{-1}(U) \subseteq P\).

By definition, \( f^{*}\space\color{red}{[\mathbf{2}]}\) takes \(U\) to that upper set \( T \subseteq P \) which corresponds to the monotone map \(f.u: P \mapsto \mathbb B\space\color{purple}{[\mathbf{3}]}\). But then \(T = \{ p \in P: u(f(p)) = \text{true}\} \) \(= \{p \in P: f(p) \in U\}\space\color{#2C1}{[\mathbf{4}]}\) \(=\) (that which was to be proved) \(f^{-1}( U)\space\color{#D80}{[\mathbf{5}]}\).

UPDATE:I adapted the diagram from Jim #4 (thanks!) and related it to the proof steps. Please let me know if you see mistakes or better ways to do this.`The upper set \\(U \subseteq Q\\), corresponding to the monotone map \\(u: Q \mapsto \mathbb B\\), is the set of elements \\(q \in Q\\) with \\(u(q) = \text{true}\space\color{blue}{[\mathbf{1}]}\\). We must show that with \\(f^{\*}\\) as defined in the Exercise, we have \\(f^{\*}(U) = f^{-1}(U) \subseteq P\\). By definition, \\( f^{*}\space\color{red}{[\mathbf{2}]}\\) takes \\(U\\) to that upper set \\( T \subseteq P \\) which corresponds to the monotone map \\(f.u: P \mapsto \mathbb B\space\color{purple}{[\mathbf{3}]}\\). But then \\(T = \\{ p \in P: u(f(p)) = \text{true}\\} \\) \\(= \\{p \in P: f(p) \in U\\}\space\color{#2C1}{[\mathbf{4}]}\\) \\(=\\) (that which was to be proved) \\(f^{-1}( U)\space\color{#D80}{[\mathbf{5}]}\\). **UPDATE:** I adapted the diagram from Jim #4 (thanks!) and related it to the proof steps. Please let me know if you see mistakes or better ways to do this. ![](https://docs.google.com/drawings/d/e/2PACX-1vR7jV4E1c-bjuKx067oI28Fg_tvZpmCbNTSFujYZ40BPTxhDJow-7P9QQoPGiH2rLvIbvkQ-w-dySn8/pub?w=600&h=450)`

Suppose \(x \in U\), so \(u(x) = true\)

Let \(f^{-1}(x) = m \in P\)

Similarly let \(f^{-1}(y) = n \in P\)

\(u(f(m)) = u(x) = true\)

Suppose \(m \leq n\)

Then \(f(m) \leq f(n)\) as f is monotone

And \(u(f(m)) \leq u(f(n))\)

That is \(true \leq u(f(n)) = true\) as \(true\) is the maximal element of \(\mathbb B\)

And hence \(n \in f^{-1}(U)\)

`Suppose \\(x \in U\\), so \\(u(x) = true\\) Let \\(f^{-1}(x) = m \in P\\) Similarly let \\(f^{-1}(y) = n \in P\\) \\(u(f(m)) = u(x) = true\\) Suppose \\(m \leq n\\) Then \\(f(m) \leq f(n)\\) as f is monotone And \\(u(f(m)) \leq u(f(n))\\) That is \\(true \leq u(f(n)) = true\\) as \\(true\\) is the maximal element of \\(\mathbb B\\) And hence \\(n \in f^{-1}(U)\\)`

Jerry asked:

I don't think there's any font for boldface calligraphic letters in LaTeX... unless you install some fancy fonts. I've never felt a need for boldface calligraphic. If you're merely wanting a bold roman letter you can do

`\\(\mathbf{U}\\)`

and get

\(\mathbf{U}\)

`Jerry asked: > **Question**: Kinduva nit, but how do we draw a bold \\(\mathcal U\\) in MathJax? I don't think there's any font for boldface calligraphic letters in LaTeX... unless you install some fancy fonts. I've never felt a need for boldface calligraphic. If you're merely wanting a bold roman letter you can do `\\(\mathbf{U}\\)` and get \\(\mathbf{U}\\)`

`![Ex1.59](https://docs.google.com/drawings/d/e/2PACX-1vSMKD6tsMweqvx5nGtJFJyovBu0PWoQ-XoXin8prXQ2sgckOxS32rRIMMN1cHwjEptVJloQ4i7WPGa6/pub?w=1105&h=751)`

Observe that treating any set \(U \subseteq P\) as a mapping into \(\mathbb{B}\) is esssentially just taking the indicator function \(\mathbf{1}_U : P \to \{\mathrm{true}, \mathrm{false}\}\), where \(\mathbf{1}_U(x) = \mathrm{true}\) iff \(x \in U\). The fact that this map is monotone just comes from the fact that \(U\) is upper; but this is actually irrelevant for this proof.

Using \(\mathbf{1}_X\) to denote the indicator function of a set \(X\), we can restate our theorem. We want to show that \(\mathbf{1}_{f^*(U)} = \mathbf{1}_U \circ f\), or equivalently, \(\mathbf{1}_{f^*(U)}(x) = \mathbf{1}_U(f(x))\) for all \(x \in P\). Well, \(\mathbf{1}_{f^*(U)}(x) = \mathrm{true}\) iff \(x \in f^*(U)\) iff \(f(x) \in U\) iff \(\mathbf{1}_U(f(x)) = \mathrm{true}\); since \(\mathbb{B}\) is a two-element set, this equivalence suffices.

`Observe that treating any set \\(U \subseteq P\\) as a mapping into \\(\mathbb{B}\\) is esssentially just taking the [indicator function](https://en.wikipedia.org/wiki/Indicator_function) \\(\mathbf{1}_U : P \to \\{\mathrm{true}, \mathrm{false}\\}\\), where \\(\mathbf{1}_U(x) = \mathrm{true}\\) iff \\(x \in U\\). The fact that this map is monotone just comes from the fact that \\(U\\) is upper; but this is actually irrelevant for this proof. Using \\(\mathbf{1}\_X\\) to denote the indicator function of a set \\(X\\), we can restate our theorem. We want to show that \\(\mathbf{1}\_{f^\*(U)} = \mathbf{1}\_U \circ f\\), or equivalently, \\(\mathbf{1}\_{f^\*(U)}(x) = \mathbf{1}\_U(f(x))\\) for all \\(x \in P\\). Well, \\(\mathbf{1}\_{f^\*(U)}(x) = \mathrm{true}\\) iff \\(x \in f^\*(U)\\) iff \\(f(x) \in U\\) iff \\(\mathbf{1}\_U(f(x)) = \mathrm{true}\\); since \\(\mathbb{B}\\) is a two-element set, this equivalence suffices.`

Funnily enough, I found a book on topos theory at my campus library today and leafed through it. Most of it was way above my current level of understanding, but incredibly, I found almost this exact statement in the first few pages, stated in terms of (the analogue of) indicator functions!

`Funnily enough, I found a book on topos theory at my campus library today and leafed through it. Most of it was way above my current level of understanding, but incredibly, I found almost this exact statement in the first few pages, stated in terms of (the analogue of) indicator functions!`

Which book was it? Johnstone's old book

Topos Theory?`Which book was it? Johnstone's old book _Topos Theory_?`

It was actually "Toposes and Local Set Theories: An Introduction", J. L. Bell. Page 53 -- I took pictures :D

`It was actually "Toposes and Local Set Theories: An Introduction", J. L. Bell. Page 53 -- I took pictures :D`

Jonathan wrote:

You've done a great job giving necessary and sufficient conditions for an indicator function to represent an

upset.Another important concept is a

filter. It shows up in lattice theory, topology, ring theory (as its dual, which are called ideals), logic, even voting theory.Wikipedia defines a filter as follows:

Puzzle MD 1. Given a lattice, what other criteria does \(\mathbf{1}_U\) need to satisfy in order for \(U\) to be a filter? Are these criteria necessary and sufficient?`Jonathan wrote: > Using \\(\mathbf{1}\_X\\) to denote the indicator function of a set \\(X\\), we can restate our theorem. We want to show that \\(\mathbf{1}\_{f^\*(U)} = \mathbf{1}\_U \circ f\\), or equivalently, \\(\mathbf{1}\_{f^\*(U)}(x) = \mathbf{1}\_U(f(x))\\) for all \\(x \in P\\). Well, \\(\mathbf{1}\_{f^\*(U)}(x) = \mathrm{true}\\) iff \\(x \in f^\*(U)\\) iff \\(f(x) \in U\\) iff \\(\mathbf{1}\_U(f(x)) = \mathrm{true}\\); since \\(\mathbb{B}\\) is a two-element set, this equivalence suffices. You've done a great job giving necessary and sufficient conditions for an indicator function to represent an *upset*. Another important concept is a *filter*. It shows up in lattice theory, topology, ring theory (as its dual, which are called [ideals](https://en.wikipedia.org/wiki/Ideal_(ring_theory))), logic, even [voting theory](https://doi.org/10.1016%2F0022-0531%2872%2990106-8). [Wikipedia](https://en.wikipedia.org/wiki/Filter_(mathematics)#General_definition) defines a filter as follows: > A subset \\(F\\) of a partially ordered set \\((P,≤)\\) is a *filter* if the following conditions hold: > > - \\( F \\) is nonempty. > - For every \\(x\\), \\(y\\) in \\(F\\), there is some element \\(z\\) in \\(F\\) such that \\(z \leq x\\) and \\(z \leq y\\). (\\(F\\) is a *filter base* (see below), or downward directed set) > - For every \\(x\\) in \\(F\\) and \\(y\\) in \\(P\\), \\(x ≤ y\\) implies that \\(y\\) is in \\(F\\). (\\(F\\) is an *upper set*, or upward closed) **Puzzle MD 1**. Given a lattice, what other criteria does \\(\mathbf{1}_U\\) need to satisfy in order for \\(U\\) to be a filter? Are these criteria necessary and sufficient?`

That's a very interesting puzzle! There's an obvious translation of the "filter base" property:

If \(\mathbf{1}_F(x) = \mathrm{true} = \mathbf{1}_F(y)\), then there exists \(z\) such that \(z \le x\), \(z \le y\), and \(\mathbf{1}_F(z) = \mathrm{true}\).

But this seems like a very boring rephrasing of the same property. With the upper set condition, there was at least a novel phrasing in terms of monotonicity. I'd like to see if there's an alternative formulation -- I'm trying to come up with some examples to explore this with...

For a total order, every nonempty upper set is a filter (and vice versa). This is because for any \(x, y \in F\), we know either \(x \le y \lor y \le x\), so one of the two will be the requisite \(z\). So partiality is necessary to make a distinction.

For a finite poset, every

principal upper setis a filter (and vice versa). There is a finite set of minimal elements in a filter, and if there exist two distinct such elements, we can find one no larger than both due to the filter base property. Thus there can only be one minimal element, and this element generates the filter.Thus, we are left with the case of an infinite poset. Looking back to total orders, we can see that \(\{x \in \mathbb{R} \mid 0 < x\}\) is a non-principal filter of \(\mathbb{R}\). This suggests to me an interesting partial order: the set of reals partially ordered by distance to the nearest one of \(\{-1, 1\}\), where the order between \(x\) and \(y\) is left undefined if a minimum or maximum point of this distance function lies strictly between them. (In this case, 0 lies halfway between \(-1\) and \(1\), so we're working with chains \([-\infty, -1], [0, -1], [0, 1], [\infty, 1]\), with \(-1, 1\) as minima of the poset and \(0\) as a maximal value.)

One filter of this example is the interval \([0, 1)\). It isn't principal for the same reason \((0, \infty)\) isn't principal in the usual (total) ordering. I'm inclined to take this as a general property of filters: there exists some \(x \in P\) such that for all \(x \le y\), \(y\) is in the filter. It doesn't matter if \(x\) itself is in the filter or not; that just determines whether it's principal.

I feel like this should be generalized to antichains instead of single bounds, but the conditions under which that's necessary are... interesting. Consider a filter \(F\) with a greatest-lower-bounding antichain \(A\) as above, and suppose \(A\) is minimal. Now, let \(x, y \in F\). By construction, there are elements (possibly identical) \(x', y'\) in \(A\) such that \(x' \le x\) and \(y' \le y\). Now suppose that \(x' \not\le y\) and \(y' \not\le x\). Since \(F\) is a filter, there must be an element \(z \in F\) such that \(z \le x\) and \(z \le y\). Since \(z\) is a lower bound of \(x\) and \(y\), we know that \(x' \not\le z\) and \(y' \not\le z\). But since \(z \in F\), there must be some

otherelement \(z' \in A\) such that \(z' \le z\). For the purposes of \(x\) and \(y\), then, the antichain elements \(x', y' \in A\) are redundant. But,strangely, this doesn't necessarily violate minimality of \(A\)! It may be possible to have an infinite subset \(F' \subseteq F\) such that all pairs \(x, y \in F'\) are above a single element of \(A\), yet every element of \(A\) is necessary to cover some pair. Whoa!I'm almost positive this is because the definition only requires existence of a lower bound for

pairs, and hence forfinite subsetsof \(F\). If we required a lower bound for any arbitrary subset of \(F\), I think that would allow us to reduce \(A\) to a single element. (And if any single element of the antichain were in \(F\), then that element would be sufficient on its own.)After all this, I've been typing and backspacing a bunch of tentative properties that just feel way more clunky than the original "simple" one. So I guess I'm no closer than where I started.

`That's a very interesting puzzle! There's an obvious translation of the "filter base" property: If \\(\mathbf{1}_F(x) = \mathrm{true} = \mathbf{1}_F(y)\\), then there exists \\(z\\) such that \\(z \le x\\), \\(z \le y\\), and \\(\mathbf{1}_F(z) = \mathrm{true}\\). But this seems like a very boring rephrasing of the same property. With the upper set condition, there was at least a novel phrasing in terms of monotonicity. I'd like to see if there's an alternative formulation -- I'm trying to come up with some examples to explore this with... For a total order, every nonempty upper set is a filter (and vice versa). This is because for any \\(x, y \in F\\), we know either \\(x \le y \\lor y \le x\\), so one of the two will be the requisite \\(z\\). So partiality is necessary to make a distinction. For a finite poset, every _principal upper set_ is a filter (and vice versa). There is a finite set of minimal elements in a filter, and if there exist two distinct such elements, we can find one no larger than both due to the filter base property. Thus there can only be one minimal element, and this element generates the filter. Thus, we are left with the case of an infinite poset. Looking back to total orders, we can see that \\(\\{x \in \mathbb{R} \mid 0 < x\\}\\) is a non-principal filter of \\(\mathbb{R}\\). This suggests to me an interesting partial order: the set of reals partially ordered by distance to the nearest one of \\(\\{-1, 1\\}\\), where the order between \\(x\\) and \\(y\\) is left undefined if a minimum or maximum point of this distance function lies strictly between them. (In this case, 0 lies halfway between \\(-1\\) and \\(1\\), so we're working with chains \\([-\infty, -1], [0, -1], [0, 1], [\infty, 1]\\), with \\(-1, 1\\) as minima of the poset and \\(0\\) as a maximal value.) One filter of this example is the interval \\([0, 1)\\). It isn't principal for the same reason \\((0, \infty)\\) isn't principal in the usual (total) ordering. I'm inclined to take this as a general property of filters: there exists some \\(x \in P\\) such that for all \\(x \le y\\), \\(y\\) is in the filter. It doesn't matter if \\(x\\) itself is in the filter or not; that just determines whether it's principal. I feel like this should be generalized to antichains instead of single bounds, but the conditions under which that's necessary are... interesting. Consider a filter \\(F\\) with a greatest-lower-bounding antichain \\(A\\) as above, and suppose \\(A\\) is minimal. Now, let \\(x, y \in F\\). By construction, there are elements (possibly identical) \\(x', y'\\) in \\(A\\) such that \\(x' \le x\\) and \\(y' \le y\\). Now suppose that \\(x' \not\le y\\) and \\(y' \not\le x\\). Since \\(F\\) is a filter, there must be an element \\(z \in F\\) such that \\(z \le x\\) and \\(z \le y\\). Since \\(z\\) is a lower bound of \\(x\\) and \\(y\\), we know that \\(x' \not\le z\\) and \\(y' \not\le z\\). But since \\(z \in F\\), there must be some _other_ element \\(z' \in A\\) such that \\(z' \le z\\). For the purposes of \\(x\\) and \\(y\\), then, the antichain elements \\(x', y' \in A\\) are redundant. But, _strangely_, this doesn't necessarily violate minimality of \\(A\\)! It may be possible to have an infinite subset \\(F' \subseteq F\\) such that all pairs \\(x, y \in F'\\) are above a single element of \\(A\\), yet every element of \\(A\\) is necessary to cover some pair. Whoa! I'm almost positive this is because the definition only requires existence of a lower bound for _pairs_, and hence for _finite subsets_ of \\(F\\). If we required a lower bound for any arbitrary subset of \\(F\\), I think that would allow us to reduce \\(A\\) to a single element. (And if any single element of the antichain were in \\(F\\), then that element would be sufficient on its own.) After all this, I've been typing and backspacing a bunch of tentative properties that just feel way more clunky than the original "simple" one. So I guess I'm no closer than where I started.`

Hey man, this is really my bad. I'm super sorry.

I am thinking of the special case where the poset is a

meet-semilattice.If it's not a lattice you said what I think is the nicest answer I can come up with:

But if the poset is a meet-semilattice, I see a cute answer.

`> After all this, I've been typing and backspacing a bunch of tentative properties that just feel way more clunky than the original "simple" one. So I guess I'm no closer than where I started. Hey man, this is really my bad. I'm super sorry. I am thinking of the special case where the poset is a [*meet-semilattice*](https://en.wikipedia.org/wiki/Semilattice). If it's not a lattice you said what I think is the nicest answer I can come up with: > If \\(\mathbf{1}_F(x) = \mathrm{true} = \mathbf{1}_F(y)\\), then there exists \\(z\\) such that \\(z \le x\\), \\(z \le y\\), and \\(\mathbf{1}_F(z) = \mathrm{true}\\). But if the poset is a meet-semilattice, I see a cute answer.`

Okay, I guess I'll just say the answer.

For a meet-semi-lattice \((P,\leq, \wedge)\) then \(F\) is a filter if and only if \(\mathbf{1}_F\) preserves meets. Specifically:

$$ \mathbf{1}_F(a \wedge b) = \mathbf{1}_F(a) \wedge \mathbf{1}_F(b) $$ This actually implies that \(\mathbf{1}_F\) is monotone! Since \(a \leq b \Longleftrightarrow a \wedge b = a \) and thus if \(a \leq b\) and \(\mathbf{1}_F(a) = \mathtt{true}\) then

$$ \begin{align} \mathbf{1}_F(a) & = \mathbf{1}_F(a\wedge b) \\ & = \mathbf{1}_F(a) \wedge \mathbf{1}_F(b) \\ & = \mathtt{true} \wedge \mathbf{1}_F(b) \\ & = \mathbf{1}_F(b) \\ & = \mathtt{true} \end{align} $$

`Okay, I guess I'll just say the answer. For a meet-semi-lattice \\((P,\leq, \wedge)\\) then \\(F\\) is a filter if and only if \\(\mathbf{1}_F\\) preserves meets. Specifically: $$ \mathbf{1}_F(a \wedge b) = \mathbf{1}_F(a) \wedge \mathbf{1}_F(b) $$ This actually implies that \\(\mathbf{1}_F\\) is monotone! Since \\(a \leq b \Longleftrightarrow a \wedge b = a \\) and thus if \\(a \leq b\\) and \\(\mathbf{1}_F(a) = \mathtt{true}\\) then $$ \begin{align} \mathbf{1}_F(a) & = \mathbf{1}_F(a\wedge b) \\\\ & = \mathbf{1}_F(a) \wedge \mathbf{1}_F(b) \\\\ & = \mathtt{true} \wedge \mathbf{1}_F(b) \\\\ & = \mathbf{1}_F(b) \\\\ & = \mathtt{true} \end{align} $$`

Ah, sure -- because the lower bound \(z\) in the "boring" property is unique in meet-semilattices, and is denoted by \(a \wedge b\). The rest simplifies for the same reason the argument in #5 simplified: \(\mathcal{B}\) only has two elements.

`Ah, sure -- because the lower bound \\(z\\) in the "boring" property is unique in meet-semilattices, and is denoted by \\(a \wedge b\\). The rest simplifies for the same reason the argument in #5 simplified: \\(\mathcal{B}\\) only has two elements.`

So, what do you call \(F\) if \(\mathbf{1}_F\) preserves both meets and joins?

`So, what do you call \\(F\\) if \\(\mathbf{1}_F\\) preserves both meets and joins?`

Assuming our poset has both meets and joins now, I'd say \(F\) must be a particular kind of sublattice. We know \(F\) must be both an ideal and a filter, and therefore \(F\) is both an upset and a downset. For instance:

(

EDIT:Haha, no, this example is neither an upset nor a downset. It has to be the constant function \(x \mapsto \textrm{true}\), i.e. \(F\) is the whole lattice.`Assuming our poset has both meets and joins now, I'd say \\(F\\) must be a particular kind of sublattice. We know \\(F\\) must be both an ideal and a filter, and therefore \\(F\\) is both an upset and a downset. For instance: (**EDIT:** Haha, no, this example is neither an upset nor a downset. It has to be the constant function \\(x \mapsto \textrm{true}\\), i.e. \\(F\\) is the whole lattice. ![](https://i.imgur.com/6eFBeDu.png)`

I'll give you a little hint - there's an example of a set \(U\) where \(\mathbf{1}_U\) preserves meets and joins kicking around in the construction of the hyperreals.

Specifically, the hyperreals are a quotient algebra just like the graph of connected components of a graph. This particular quotient algebra is called an ultraproduct. Right before you take the quotient algebra, you'll see a very special set \(U\) kicking around...

`I'll give you a little hint - there's an example of a set \\(U\\) where \\(\mathbf{1}_U\\) preserves meets and joins kicking around in the [construction of the hyperreals](https://en.wikipedia.org/wiki/Hyperreal_number#The_ultrapower_construction). Specifically, the hyperreals are a [quotient algebra](https://en.wikipedia.org/wiki/Quotient_algebra) just like the graph of connected components of a graph. This particular quotient algebra is called an [ultraproduct](https://en.wikipedia.org/wiki/Ultraproduct). Right before you take the quotient algebra, you'll see a very special set \\(U\\) kicking around...`

Ah, I see where my reasoning went off the rails before. \(F\) is only a downset if \(\mathbf{1}_F\) is

antitone. Of course, the only functions that are both monotone and antitone are the constant functions.So the key point here is that \(x \vee y\) must be false iff neither \(x\) nor \(y\) are true. If it didn't preserve joins, then \(x \vee y\) could be in the set. In other words, no element in \(F\) can be the join of (a finite number of) elements not in \(F\) -- the entire set \(F\) is unreachable from below in a precise sense. So we're supposedly looking at an ultrafilter.

It isn't clear to me why this property guarantees that \(F\) is maximal. I'll noodle on that a bit more. At the very least, I think it must be true that for finite lattices there are no ultrafilters (since they must be proper filters). It isn't clear whether there are ultrafilters on any finite structures weaker than lattices.

`Ah, I see where my reasoning went off the rails before. \\(F\\) is only a downset if \\(\mathbf{1}\_F\\) is _antitone_. Of course, the only functions that are both monotone and antitone are the constant functions. So the key point here is that \\(x \vee y\\) must be false iff neither \\(x\\) nor \\(y\\) are true. If it didn't preserve joins, then \\(x \vee y\\) could be in the set. In other words, no element in \\(F\\) can be the join of (a finite number of) elements not in \\(F\\) -- the entire set \\(F\\) is unreachable from below in a precise sense. So we're supposedly looking at an ultrafilter. It isn't clear to me why this property guarantees that \\(F\\) is maximal. I'll noodle on that a bit more. At the very least, I think it must be true that for finite lattices there are no ultrafilters (since they must be proper filters). It isn't clear whether there are ultrafilters on any finite structures weaker than lattices.`

All lattices, finite or otherwise, have ultrafilters. If the lattices are bounded below, then they all have

properfilters that do not contain the bottom element.What are the ultrafilters for \(\mathcal{P}(\{1,2,3\})\)?

Well, I admittedly always have lattices in mind when I think about ultrafilters and filters.

However, you can make a general definition of an ultrafilter \(U\) for any poset:

Properties 1 through 3 follow wikipedia's general definition of a filter. Property 4 is just the generalization of

ultraness.I am pretty confident that \(\mathbf{1}_U\) being both (join and) meet preserving is *necessary* if \(U\) is an (ultra)filter. I am not sure if it is sufficient.

Technically, \(x \mapsto \mathtt{true}\) defines an

improperultrafilter.What does \(\mathbf{1}_U\) need to do to ensure \(U\) proper?

`> At the very least, I think it must be true that for finite lattices there are no ultrafilters (since they must be proper filters). All lattices, finite or otherwise, have ultrafilters. If the lattices are bounded below, then they all have *proper* filters that do not contain the bottom element. What are the ultrafilters for \\(\mathcal{P}(\\{1,2,3\\})\\)? > It isn't clear whether there are ultrafilters on any finite structures weaker than lattices. Well, I admittedly always have lattices in mind when I think about ultrafilters and filters. However, you can make a general definition of an ultrafilter \\(U\\) for any poset: 1. \\(U\\) is nonempty 2. For every \\(x,y \in F\\), there is a \\(z \in F\\) such that \\(z \leq x \\) and \\(z \leq y\\) 3. If \\(x \leq y\\) and \\(x \in F\\), then \\(y \in F\\) 4. If \\(z \in F\\) and \\(x \leq z\\) and \\(y \leq z\\), then either \\(x \in F\\) or \\(y \in F\\) Properties 1 through 3 follow [wikipedia's general definition of a filter](https://en.wikipedia.org/wiki/Filter_(mathematics)#General_definition). Property 4 is just the generalization of *ultraness*. I am pretty confident that \\(\mathbf{1}_U\\) being both (join and) meet preserving is *necessary* if \\(U\\) is an (ultra)filter. I am not sure if it is sufficient. ------------------------ Technically, \\(x \mapsto \mathtt{true}\\) defines an *improper* ultrafilter. What does \\(\mathbf{1}_U\\) need to do to ensure \\(U\\) proper?`

Let's look at this lattice again:

Wikipedia says that ultrafilters must be proper (i.e. not the whole set), so that's out. The trivial filter on the uppermost element isn't an ultrafilter because it is the join of two elements not in the filter. The principal upsets on the central horizontal are our only real candidates -- but if we take the join of two other elements on the horizontal, we get an element in the filter, so we do

notpreserve joins. And if we add another element to this upset, we have to close under meets again, which is just going to give us the whole set.What

arethe ultrafilters on this lattice?I can at least answer this. It has to be surjective.

`Let's look at this lattice again: ![](https://i.imgur.com/Zd2otbR.png) Wikipedia says that ultrafilters must be proper (i.e. not the whole set), so that's out. The trivial filter on the uppermost element isn't an ultrafilter because it is the join of two elements not in the filter. The principal upsets on the central horizontal are our only real candidates -- but if we take the join of two other elements on the horizontal, we get an element in the filter, so we do _not_ preserve joins. And if we add another element to this upset, we have to close under meets again, which is just going to give us the whole set. What _are_ the ultrafilters on this lattice? > What does \\(\mathbf{1}_U\\) need to do to ensure \\(U\\) proper? I can at least answer this. It has to be surjective.`

Oh, I guess I was assuming we could have improper ones.

Thanks for the catch.

Here's the correction I would make:

`> Wikipedia says that ultrafilters must be proper (i.e. not the whole set), so that's out. Oh, I guess I was assuming we could have improper ones. Thanks for the catch. Here's the correction I would make: > All **distributive** lattices, finite or otherwise, have (maybe improper) ultrafilters. If the distributive lattices are bounded below, then they all have proper filters that do not contain the bottom element.`

Okay. Just to be clear, my original answer is accurate for lattices in general, going off of Wikipedia's definition?

And there's still the question, which you've expanded on somewhat, of whether structures weaker than lattices have any interesting collections of ultrafilters.

`Okay. Just to be clear, my original answer is accurate for lattices in general, going off of Wikipedia's definition? > At the very least, I think it must be true that for finite lattices there are no ultrafilters (since they must be proper filters). And there's still the question, which you've expanded on somewhat, of whether structures weaker than lattices have any interesting collections of ultrafilters.`

Ah -- now

thisis an ultrafilter on a finite lattice. (Let's call it the Baymax ultrafilter.)Could probably say something about antichains of length 2 here.

Then, we should also have that ultrafilters on \(\mathcal{P}(\{1, 2, 3\})\) are the principal upsets on singleton sets \(\{i\}\). (They're kind of doubly principal.) The join of any pair of elements not in the ultrafilter will not be in the ultrafilter, because neither contains the element of the singleton set.

By extension (multisets!), ultrafilters on the divisiblity lattice of the positive integers are in one-to-one correspondence with prime numbers. This is starting to make some sense.

`Ah -- now _this_ is an ultrafilter on a finite lattice. (Let's call it the [Baymax ultrafilter](http://disney.wikia.com/wiki/Baymax).) ![](https://i.imgur.com/muagFNF.png) Could probably say something about antichains of length 2 here. Then, we should also have that ultrafilters on \\(\\mathcal{P}(\\{1, 2, 3\\})\\) are the principal upsets on singleton sets \\(\\{i\\}\\). (They're kind of doubly principal.) The join of any pair of elements not in the ultrafilter will not be in the ultrafilter, because neither contains the element of the singleton set. By extension (multisets!), ultrafilters on the divisiblity lattice of the positive integers are in one-to-one correspondence with prime numbers. This is starting to make some sense.`

Still catching up on the exercises. Here's a diagrammatic version of the proof.

By proposition 1.60, a choice of \(u\) determines \(UQ\) and a choice of \(z\) determines \(UP\).

We are given \(f\) and \(u\) by the problem, which gives us \(z\) by composition, and therefore \(f^*\) is determined.

`Still catching up on the exercises. Here's a diagrammatic version of the proof. <a href='https://svgshare.com/s/6vh' ><img src='https://svgshare.com/i/6vh.svg' title='1.61' /></a> By proposition 1.60, a choice of \\(u\\) determines \\(UQ\\) and a choice of \\(z\\) determines \\(UP\\). We are given \\(f\\) and \\(u\\) by the problem, which gives us \\(z\\) by composition, and therefore \\(f^*\\) is determined.`

Also, I just realized that in the latest copy of the book, this is now problem 1.65. I thought I had posted to the wrong thread for a moment! Prop 1.60 becomes Prop 1.64.

`Also, I just realized that in the latest copy of the book, this is now problem 1.65. I thought I had posted to the wrong thread for a moment! Prop 1.60 becomes Prop 1.64.`