Exercise 61 - Chapter 1

Jerry Wedekind

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

Jerry Wedekind

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.

Andrew Ardill

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

John Baez

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

JimStuttard

Jonathan Castello

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.

Jonathan Castello

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!

John Baez

Which book was it? Johnstone's old book Topos Theory?

Jonathan Castello

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

MatthewDoty

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), logic, even voting theory.

Wikipedia 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?

Jonathan Castello

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.

MatthewDoty

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:

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.

MatthewDoty

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} $$

Jonathan Castello

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.

MatthewDoty

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

Jonathan Castello

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.

MatthewDoty

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

Jonathan Castello

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.

MatthewDoty

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

Jonathan Castello

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

MatthewDoty

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.

Jonathan Castello

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.

Jonathan Castello

Ah -- now this is 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.

Dennis Yao

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.

Dennis Yao

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.