Math 202B: Lecture 4

***All problems assigned in this lecture are due January 20th at 23:59***

Let us begin this lecture with a physical way of thinking about the function algebra \mathcal{F}(X) of a finite set X. Imagine that X is the set of all possible outcomes of an experiment, for example a chemical reaction whose yield depends on environmental factors, the proportions in which the constituents are mixed, and so forth. After the experiment has been performed, we want to determine what substance has been produced. From this point of view, \mathcal{F}(X) represents the collection of all numerical measurements or “observables” of the yield that can theoretically be computed. For example, T \in \mathcal{F}(X) assigns to each x \in X its temperature T(x), and H \in \mathcal{F}(X) which assigns to each x \in X its specific heat H(x), etc.

In practice (as opposed to in theory), our experiment is performed in a laboratory with limited resources. For example, we may have access to a thermometer but not to a Bunsen burner, so we can compute T(x) but not H(x). The set of all measurements which we can perform in our laboratory is then a proper subalgebra \mathcal{A} of \mathcal{F}(X) which contains T but not H. A natural question now is: given a proper subalgebra \mathcal{A} <\mathcal{F}(X) of accessible observables, can we compute enough measurements to distinguish between any two outcomes? In operational terms, \mathcal{A} separates the points of X if our laboratory is advanced enough that we can perform at least one measurement which distinguishes any two distinct outcomes.

Definition 4.1. We say that \mathcal{A} separates the points of X if, for any distinct x,y \in X, there is A \in \mathcal{A} such that A(x) \neq A(y).

Unfortunately, as soon as our laboratory is limited in any way operationally indistinguishable outcomes exist.

Theorem 4.2. A subalgebra \mathcal{A} \leq \mathcal{F}(X) separates the points of X if and only if \mathcal{A}=\mathcal{F}(X).

Proof: One direction is clear: if \mathcal{A}=\mathcal{F}(X) then we have access to the set \{E_x \colon x \in X\} of all elementary functions, and for any distinct points x,y \in X we have E_x(x)=1 and E_x(y)=0.

Conversely, suppose that \mathcal{A} \leq \mathcal{F}(X) is a subalgebra which separates X. Pick an arbitrary point x \in X. Then, for each y \in X\backslash \{x\} there exists a function F_y \in \mathcal{A} such that

\alpha = F_y(x) \quad\text{and}\quad \beta = F_y(y)

are distinct numbers. The centered and scaled function

\tilde{F}_y(z) = \frac{F_y(z)-\beta}{\alpha-\beta}

then satisfies

\tilde{F}_y(x) =1 \quad\text{and}\quad \tilde{F}_y(y)=0.

We thus have the factorization

E_x =\prod\limits_{y \in X\backslash \{x\}} \tilde{F}_y.

Since \mathcal{A} is closed under products, we have shown that \mathcal{A} contains the elementary function E_x. Since x \in X was arbitrary, we have shown that \mathcal{A} contains the elementary basis \{E_x \colon x \in X\}. \square

The category of finite sets is a full subcategory of the category whose objects are compact Hausdorff spaces and whose morphisms are continuous functions — give a finite sets the discrete topology, in which every singleton set is open. The fact that the algebra of all continuous functions on any Hausdorff topological space can separate any two distinct closed sets holds in this larger topological category (this is Urysohn’s Lemma). The opposite direction, that a separating subalgebra \mathcal{A} is equal to the algebra of continuous functions, has to be weakened to the statement that \mathcal{A} is uniformly dense in the algebra of all continuous functions (this is the Stone-Weierstrass theorem).

Let us now generalize Theorem 4.2 within the category of finite sets.

Definition 4.2. A partition of X is a set \mathfrak{p} of disjoint nonempty subsets of X whose union is X. The elements of \mathfrak{p} are referred to as its “blocks.”

Let \mathfrak{P}(X) denote the set of all partitions of X. Note that \mathfrak{P}(X) is in bijection with the set of equivalence relations on X — a partition \mathfrak{p} defines an equivalence relation on X in which points are equivalent if they are elements of the same block, and conversely an equivalence relation on X defines a partition whose blocks are equivalence classes.

We make \mathfrak{P}(X) into a poset as follows: for each \mathfrak{p},\mathfrak{q} \in \mathfrak{P}(X), we declare \mathfrak{p} \leq \mathfrak{q} if and only if \mathfrak{q} can be obtained by partitioning blocks of \mathfrak{p}. Equivalently, every block of \mathfrak{q} is contained in a block of \mathfrak{p}. This is called the refinement order on \mathfrak{P}(X). If \mathfrak{p} \leq \mathfrak{q}, we say that \mathfrak{q} is finer than \mathfrak{p}, or equivalently that \mathfrak{p} is coarser than \mathfrak{q}. Going one step further, we can make \mathfrak{P}(X) into a lattice, where \max(\mathfrak{p},\mathfrak{q}) is the coarsest partition (weakly) finer than both \mathfrak{p} and \mathfrak{q}, and \min(\mathfrak{p},\mathfrak{q}) is the finest partition (weakly) coarser than both \mathfrak{p} and \mathfrak{q}.

There is a natural mapping from the lattice of partitions of X to the lattice of subalgebras of \mathcal{F}(X) — for each \mathfrak{p} \in \mathfrak{P}(X), declare \mathcal{A}(\mathfrak{p}) to be the set of all functions in \mathcal{F}(X) which are constant on the blocks of \mathfrak{p}.

Problem 4.1. Prove that \mathcal{A}(\mathfrak{p}) really is a subalgebra of \mathcal{A}(X), and moreover that the mapping \mathfrak{p} \to \mathcal{A}(\mathfrak{p}) is injective.

Problem 4.2. Prove that \mathfrak{p} \leq \mathfrak{q} implies \mathcal{A}(\mathfrak{p}) \leq \mathcal{A}(\mathfrak{q}), meaning that our mapping \mathfrak{P}(X) \to \mathcal{F}(X) is an order homomorphism.

Problem 4.3. Work a bit harder and show that the mapping \mathfrak{p} \mapsto \mathcal{A}(\mathfrak{p}) is a lattice homomorphism.

Problem 4.4. Prove that \mathcal{A}(\mathfrak{p}) is isomorphic to \mathcal{F}(\mathfrak{p}).

We can make use of Problem 4.4 as follows. Let us say that a function A \in \mathcal{A}(\mathfrak{p}) separates the blocks of \mathfrak{p} if, for any two distinct blocks P and Q of \mathfrak{p}, the constant functions A|_P and A|_Q are distinct. This generalizes Definition 4.1, which is the case where \mathfrak{p} is the partition of X with |X| blocks. The corresponding generalization of Theorem 4.2 is the following.

Theorem 4.3. If \mathcal{A} is a subalgebra of \mathcal{A}(\mathfrak{p}) which separates the blocks of \mathfrak{p}, then \mathcal{A}=\mathcal{A}(\mathfrak{p}).

Proof: By Problem 4.4, this reduces to Theorem 4.2. (Make sure you understand this). \square

At this point the following classification theorem is essentially complete.

Theorem 4.4. The lattice of subalgebras of \mathcal{F}(X) is isomorphic to the lattice of partitions of X.

Proof: It remains only to show that our method of assigning subalgebras to partitions is surjective. Let \mathcal{A} be an arbitrary subalgebra of \mathcal{F}(X). Define an equivalence relation on X by

x \sim y \quad \iff \quad A(x)=A(y) \text{ for all }A \in \mathcal{A},

and let \mathfrak{p} be the partition of X whose blocks are the corresponding equivalence classes. Then, by definition of \mathfrak{p} we have \mathcal{A} \leq \mathcal{A}(\mathbf{p}). Furthermore, by definition of \mathfrak{p} we have that A separates the blocks of \mathfrak{p}. By Theorem 4.3, we have \mathcal{A}=\mathcal{A}(\mathfrak{p}). \square

Published by Jonathan Novak

Mathematician at UC San Diego.

2 Comments

  1. Andrew Tan says:
    January 13, 2026 at 2:04 pm

    Could you help clarify what it means to be a lattice homomorphism (as stated in Problem 4.3) ?

    Reply
    1. Jonathan Novak says:
      January 13, 2026 at 2:34 pm

      A lattice homomorphism respects partial order, meets (min of two elements), and joins (max of two elements).

      Reply

Leave a Reply