Tag Archive

You are currently browsing the tag archive for the ‘principle of duality’ tag.

Basic Category Theory, III: Representability, adjoints, and the Yoneda lemma

July 12, 2008 in Category Theory, Category Theory for Beginners, Exposition | Tags: adjoint functors, principle of duality, representable functors, Yoneda lemma | by Todd Trimble | 9 comments

In our last post on category theory, we continued our exploration of universal properties, showing how they can be used to motivate the concept of natural transformation, the “right” notion of morphism $\phi: F \to G$ between functors $F, G$ . In today’s post, I want to turn things around, applying the notion of natural transformation to explain generally what we mean by a universal construction. The key concept is the notion of representability, at the center of a circle of ideas which includes the Yoneda lemma, adjoint functors, monads, and other things — it won’t be possible to talk about all these things in detail (because I really want to return to Stone duality before long), but perhaps these notes will provide a key of entry into more thorough treatments.

Even for a fanatic like myself, it’s a little hard to see what would drive anyone to study category theory except a pretty serious “need to know” (there is a beauty and conceptual economy to categorical thinking, but I’m not sure that’s compelling enough motivation!). I myself began learning category theory on my own as an undergraduate; at the time I had only the vaguest glimmerings of a vast underlying unity to mathematics, but it was only after discovering the existence of category theory by accident (reading the introductory chapter of Spanier’s Algebraic Topology) that I began to suspect it held the answer to a lot of questions I had. So I got pretty fired-up about it then, and started to read Mac Lane’s Categories for the Working Mathematician. I think that even today this book remains the best serious introduction to the subject — for those who need to know! But category theory should be learned from many sources and in terms of its many applications. Happily, there are now quite a few resources on the Web and a number of blogs which discuss category theory (such as The Unapologetic Mathematician) at the entry level, with widely differing applications in mind. An embarrassment of riches!

Anyway, to return to today’s topic. Way back when, when we were first discussing posets, most of our examples of posets were of a “concrete” nature: sets of subsets of various types, ordered by inclusion. In fact, we went a little further and observed that any poset could be represented as a concrete poset, by means of a “Dedekind embedding” (bearing a familial resemblance to Cayley’s lemma, which says that any group can be represented concretely, as a group of permutations). Such concrete representation theorems are extremely important in mathematics; in fact, this whole series is a trope on the Stone representation theorem, that every Boolean algebra is an algebra of sets! With that, I want to discuss a representation theorem for categories, where every (small) category can be explicitly embedded in a concrete category of “structured sets” (properly interpreted). This is the famous Yoneda embedding.

This requires some preface. First, we need the following fundamental construction: for every category $C$ there is an opposite category $C^{op}$ , having the same classes $O, M$ of objects and morphisms as $C$ , but with domain and codomain switched ( $\mbox{dom}^{op} := \mbox{cod}: M \to O$ , and $\mbox{cod}^{op} := \mbox{dom}: M \to O$ ). The function $O \to M: A \mapsto 1_A$ is the same in both cases, but we see that the class of composable pairs of morphisms is modified:

$(f, g) \in C^{op}_2$ [is a composable pair in $C^{op}$ ] if and only if $(g, f) \in C_2$

and accordingly, we define composition of morphisms in $C^{op}$ in the order opposite to composition in $C$ :

$(g \circ f)^{op} := f \circ g$ in $C$ .

Observation: The categorical axioms are satisfied in the structure $C^{op}$ if and only if they are in $C$ ; also, $(C^{op})^{op} = C$ .

This observation is the underpinning of a Principle of Duality in the theory of categories (extending the principle of duality in the theory of posets). As the construction of opposite categories suggests, the dual of a sentence expressed in the first-order language of category theory is obtained by reversing the directions of all arrows and the order of composition of morphisms, but otherwise keeping the logical structure the same. Let me give a quick example:

Definition: Let $X_1, X_2$ be objects in a category $C$ . A coproduct of $X_1$ and $X_2$ consists of an object $X$ and maps $i_1: X_1 \to X$ , $i_2: X_2 \to X$ (called injection or coprojection maps), satisfying the universal property that given an object $Y$ and maps $f_1: X_1 \to Y$ , $f_2: X_2 \to Y$ , there exists a unique map $f: X \to Y$ such that $f_1 = f \circ i_1$ and $f_2 = f \circ i_2$ . $\Box$

This notion is dual to the notion of product. (Often, one indicates the dual notion by appending the prefix “co” — except of course if the “co” prefix is already there; then one removes it.) In the category of sets, the coproduct of two sets $X_1, X_2$ may be taken to be their disjoint union $X_1 + X_2$ , where the injections $i_1, i_2$ are the inclusion maps of $X_1, X_2$ into $X_1 + X_2$ (exercise).

Exercise: Formulate the notion of coequalizer (by dualizing the notion of equalizer). Describe the coequalizer of two functions $\displaystyle f, g: X \stackrel{\to}{\to} Y$ (in the category of sets) in terms of equivalence classes. Then formulate the notion dual to that of monomorphism (called an epimorphism), and by a process of dualization, show that in any category, coequalizers are epic.

Principle of duality: If a sentence expressed in the first-order theory of categories is provable in the theory, then so is the dual sentence. Proof (sketch): A proof $P$ of a sentence proceeds from the axioms of category theory by applying rules of inference. The dualization of $P$ proves the dual sentence by applying the same rules of inference but starting from the duals of the categorical axioms. A formal proof of the Observation above shows that collectively, the set of categorical axioms is self-dual, so we are done. $\Box$

Next, we introduce the all-important hom-functors. We suppose that $C$ is a locally small category, meaning that the class of morphisms $g: c \to d$ between any two given objects $c, d$ is small, i.e., is a set as opposed to a proper class. Even for large categories, this condition is just about always satisfied in mathematical practice (although there is the occasional baroque counterexample, like the category of quasitopological spaces).

Let $Set$ denote the category of sets and functions. Then, there is a functor

$\hom_C: C^{op} \times C \to Set$

which, at the level of objects, takes a pair of objects $(c, d)$ to the set $\hom(c, d)$ of morphisms $g: c \to d$ (in $C$ ) between them. It takes a morphism $(f: c \to c', h: d \to d')$ of $C^{op} \times C$ (that is to say, a pair of morphisms $(f: c' \to c, h: d \to d')$ of $C$ ) to the function

$\hom_C(f, h): \hom(c, d) \to \hom(c', d'): g \mapsto hgf.$

Using the associativity and identity axioms in $C$ , it is not hard to check that this indeed defines a functor $\hom_C: C^{op} \times C \to Set$ . It generalizes the truth-valued pairing $P^{op} \times P \to \mathbf{2}$ we defined earlier for posets.

Now assume $C$ is small. From last time, there is a bijection between functors

$\displaystyle \frac{h: C^{op} \times C \to Set}{f: C \to Set^{C^{op}}}$

and by applying this bijection to $\hom_C: C^{op} \times C \to Set$ , we get a functor

$y_C: C \to Set^{C^{op}}.$

This is the famous Yoneda embedding of the category $C$ . It takes an object $c$ to the hom-functor $\hom_C(-, c): C^{op} \to Set$ . This hom-functor can be thought of as a structured, disciplined way of considering the totality of morphisms mapping into the object $c$ , and has much to do with the Yoneda Principle we stated informally last time (and which we state precisely below).

Remark: We don’t need $C$ to be small to talk about $\hom_C(-, c)$ ; local smallness will do. The only place we ask that $C$ be small is when we are considering the totality of all functors $C^{op} \to Set$ , as forming a category $\displaystyle Set^{C^{op}}$ .

Definition: A functor $F: C^{op} \to Set$ is representable (with representing object $c$ ) if there is a natural isomorphism $\displaystyle \hom_C(-, c) \stackrel{\sim}{\to} F$ of functors.

The concept of representability is key to discussing what is meant by a universal construction in general. To clarify its role, let’s go back to one of our standard examples.

Let $c_1, c_2$ be objects in a category $C$ , and let $F: C^{op} \to Set$ be the functor $\hom(-, c_1) \times \hom(-, c_2)$ ; that is, the functor which takes an object $b$ of $C$ to the set $\hom(b, c_1) \times \hom(b, c_2)$ . Then a representing object for $F$ is a product $c_1 \times c_2$ in $C$ . Indeed, the isomorphism between sets $\hom(b, c_1 \times c_2) \cong \hom(b, c_1) \times \hom(b, c_2)$ simply recapitulates that we have a bijection

$\displaystyle \frac{b \to c_1 \times c_2}{b \to c_1 \qquad b \to c_2}$

between morphisms into the product and pairs of morphisms. But wait, not just an isomorphism: we said a natural isomorphism (between functors in the argument $b$ ) — how does naturality figure in?

Enter stage left the celebrated

Yoneda Lemma: Given a functor $F: C^{op} \to Set$ and an object $c$ of $C$ , natural transformations $\phi: \hom(-, c) \to F$ are in (natural!) bijection with elements $\xi \in F(c)$ .

Proof: We apply the “Yoneda trick” introduced last time: probe the representing object $c$ with the identity morphism, and see where $\phi$ takes it: put $\xi = \phi_c(1_c)$ . Incredibly, this single element $\xi$ determines the rest of the transformation $\phi$ : by chasing the element $1_c \in \hom(c, c)$ around the diagram

                phi_c
      hom(c, c) -----> Fc
          |            |
hom(f, c) |            | Ff
          V            V
      hom(b, c) -----> Fb
                phi_b

(which commutes by naturality of $\phi$ ), we see for any morphism $f: b \to c$ in $\hom(b, c)$ that $\phi_b(f) = F(f)(\xi)$ . That the bijection

$\displaystyle \frac{\xi: 1 \to F(c)}{\phi: \hom(-, c) \to F}$

is natural in the arguments $F, c$ we leave as an exercise. $\Box$

Returning to our example of the product $c_1 \times c_2$ as representing object, the Yoneda lemma implies that the natural bijection

$\displaystyle \phi_b: \hom(b, c_1 \times c_2) \cong \hom(b, c_1) \times \hom(b, c_2)$

is induced by the element $\xi = \phi_{c_1 \times c_2}(1_{c_1 \times c_2})$ , and this element is none other than the pair of projection maps

$\xi = (\pi_1: c_1 \times c_2 \to c_1, \pi_2: c_1 \times c_2 \to c_2).$

In summary, the Yoneda lemma guarantees that a hom-representation $\phi: \hom(-, c) \cong F$ of a functor is, by the naturality assumption, induced in a uniform way from a single “universal” element $\xi \in F(c)$ . All universal constructions fall within this general pattern.

Example: Let $C$ be a category with products, and let $c, d$ be objects. Then a representing object for the functor $\hom(- \times c, d): C^{op} \to Set$ is an exponential $d^c$ ; the universal element $\xi \in \hom(d^c \times c, d)$ is the evaluation map $d^c \times c \to d$ .

Exercise: Let $\displaystyle f, g: x \stackrel{\to}{\to} y$ be a pair of parallel arrows in a category $C$ . Describe a functor $F: C^{op} \to Set$ which is represented by an equalizer of this pair (assuming one exists).

Exercise: Dualize the Yoneda lemma by considering hom-functors $\hom_C(c, -): C \to Set$ . Express the universal property of the coproduct in terms of representability by such hom-functors.

The Yoneda lemma has a useful corollary: for any (locally small) category $C$ , there is a natural isomorphism

$\displaystyle \frac{\hom_C(-, a) \to \hom_C(-, b)}{a \to b}$

between natural transformations between hom-functors and morphisms in $C$ . Using $C(a, b)$ as alternate notation for the hom-set, the action of the Yoneda embedding functor $y_C$ on morphisms gives an isomorphism between hom-sets

$\displaystyle C(a, b) \stackrel{\sim}{\to} Set^{C^{op}}(y_C a, y_C b);$

the functor $y_C$ is said in that case to be fully faithful (faithful means this action on morphisms is injective for all $a, b$ , and full means the action is surjective for all $a, b$ ). The Yoneda embedding $y_C$ thus maps $C$ isomorphically onto the category of hom-functors $y_C a = \hom_C(-, a)$ valued in the category $Set$ .

It is illuminating to work out the meaning of this last statement in special cases. When the category $C$ is a group $G$ (that is, a category with exactly one object $\bullet$ in which every morphism is invertible), then functors $F: G^{op} \to Set$ are tantamount to sets $X$ equipped with a group homomorphism $G^{op} \to \hom(X, X)$ , i.e., a left action of $G^{op}$ , or a right action of $G$ . In particular, $\hom(-, \bullet): G^{op} \to Set$ is the underlying set of $G$ , equipped with the canonical right action $\rho: G \to \hom(G, G)$ , where $\rho(g)(h) = hg$ . Moreover, natural transformations between functors $G^{op} \to Set$ are tantamount to morphisms of right $G$ -sets. Now, the Yoneda embedding

$y_G: G \to Set^{G^{op}}$

identifies any abstract group $G$ with a concrete group $y_G(G)$ , i.e., with a group of permutations — namely, exactly those permutations on $G$ which respect the right action of $G$ on itself. This is the sophisticated version of Cayley’s theorem in group theory. If on the other hand we take $C$ to be a poset, then the Yoneda embedding is tantamount to the Dedekind embedding we discussed in the first lecture.

Tying up a loose thread, let us now formulate the “Yoneda principle” precisely. Informally, it says that an object is determined up to isomorphism by the morphisms mapping into it. Using the hom-functor $\hom(-, c)$ to collate the morphisms mapping into $c$ , the precise form of the Yoneda principle says that an isomorphism between representables $\hom(-, c) \to \hom(-, d)$ corresponds to a unique isomorphism $c \to d$ between objects. This follows easily from the Yoneda lemma.

But far and away, the most profound manifestation of representability is in the notion of an adjoint pair of functors. “Free constructions” give a particularly ubiquitous class of examples; the basic idea will be explained in terms of free groups, but the categorical formulation applies quite generally (e.g., to free monoids, free Boolean algebras, free rings = polynomial algebras, etc., etc.).

If $X$ is a set, the free group (q.v.) generated by $X$ is, informally, the group $FX$ whose elements are finite “words” built from “literals” $a, b, c, \ldots$ which are the elements of $X$ and their formal inverses, where we identify a word with any other gotten by introducing or deleting appearances of consecutive literals $a a^{-1}$ or $a^{-1}a$ . Janis Joplin said it best:

Freedom’s just another word for nothin’ left to lose…

— there are no relations between the generators of $FX$ beyond the bare minimum required by the group axioms.

Categorically, the free group $FX$ is defined by a universal property; loosely speaking, for any group $G$ , there is a natural bijection between group homomorphisms and functions

$\displaystyle \frac{FX \to G}{X \to UG}$

where $UG$ denotes the underlying set of the group. That is, we are free to assign elements of $G$ to elements of $X$ any way we like: any function $f: X \to UG$ extends uniquely to a group homomorphism $\hat{f}: FX \to G$ , sending a word $x_1 x_2 \ldots x_n$ in $FX$ to the element $f(x_1)f(x_2) \ldots f(x_n)$ in $G$ .

Using the usual Yoneda trick, or the dual of the Yoneda trick, this isomorphism is induced by a universal function $i: X \to UFX$ , gotten by applying the bijection above to the identity map $id: FX \to FX$ . Concretely, this function takes an element $x \in X$ to the one-letter word $x \in UFX$ in the underlying set of the free group. The universal property states that the bijection above is effected by composing with this universal map:

$\displaystyle \hom_{Grp}(FX, G) \to \hom_{Set}(UFX, UG) \stackrel{\hom(i, UG)}{\to} \hom_{Set}(X, UG)$

where the first arrow refers to the action of the underlying-set or forgetful functor $U: Grp \to Set$ , mapping the category of groups to the category of sets ( $U$ “forgets” the fact that homomorphisms $f: G \to H$ preserve group structure, and just thinks of them as functions $Uf: UG \to UH$ ).

Remark: Some people might say this a little less formally: that the original function $f: X \to G$ is retrieved from the extension homomorphism $\hat{f}: FX \to G$ by composing with the canonical injection of the generators $X \to FX$ . The reason we don’t say this is that there’s a confusion of categories here: properly speaking, $FX \to G$ belongs to the category of groups, and $X \to G$ to the category of sets. The underlying-set functor $U: Grp \to Set$ is a device we apply to eliminate the confusion.

In different words, the universal property of free groups says that the functor $\hom_{Set}(X, U-): Grp \to Set$ , i.e., the underlying functor $U: Grp \to Set$ followed by the hom-functor $\hom(X, -): Set \to Set$ , is representable by the free group $FX$ : there is a natural isomorphism of functors from groups to sets:

$Grp(FX, -) \stackrel{\sim}{\to} Set(X, U-).$

Now, the free group $FX$ can be constructed for any set $X$ . Moreover, the construction is functorial: defines a functor $F: Set \to Grp$ . This is actually a good exercise in working with universal properties. In outline: given a function $f: X \to Y$ , the homomorphism $Ff: FX \to FY$ is the one which corresponds bijectively to the function

$\displaystyle X \stackrel{f}{\to} Y \stackrel{i_Y}{\to} UFY,$

i.e., $Ff$ is defined to be the unique map $h$ such that $Uh \circ i_X = i_Y \circ f$ .

Proposition: $F: Set \to Grp$ is functorial (i.e., preserves morphism identities and morphism composition).

Proof: Suppose $f: X \to Y$ , $g: Y \to Z$ is a composable pair of morphisms in $Set$ . By universality, there is a unique map $h: FX \to FZ$ , namely $F(g \circ f)$ , such that $Uh \circ i_X = i_Z \circ (g \circ f)$ . But $Fg \circ Ff$ also has this property, since

$U(Fg \circ Ff) \circ i_X = UFg \circ UFf \circ i_X = UFg \circ i_Y \circ f = i_Z \circ g \circ f$

(where we used functoriality of $U$ in the first equation). Hence $F(g \circ f) = Fg \circ Ff$ . Another universality argument shows that $F$ preserves identities. $\Box$

Observe that the functor $F$ is rigged so that for all morphisms $f: X \to Y$ ,

$UFf \circ i_X = i_Y \circ f.$

That is to say, that there is only one way of defining $F$ so that the universal map $i_X$ is (the component at $X$ of) a natural transformation $1_{Set} \to UF$ !

The underlying-set and free functors $U: Grp \to Set$ , $F: Set \to Grp$ are called adjoints, generalizing the notion of adjoint in truth-valued matrix algebra: we have an isomorphism

$\hom_{Grp}(FX, Y) \cong \hom_{Set}(X, UY)$

natural in both arguments $X, Y$ . We say that $F$ is left adjoint to $U$ , or dually, that $U$ is right adjoint to $F$ , and write $F \dashv U$ . The transformation $i: 1 \to UF$ is called the unit of the adjunction.

Exercise: Define the construction dual to the unit, called the counit, as a transformation $\varepsilon: FU \to 1$ . Describe this concretely in the case of the free-underlying adjunction $F \dashv U$ between sets and groups.

What makes the concept of adjoint functors so compelling is that it combines representability with duality: the manifest symmetry of an adjunction $\hom(FX, Y) \cong \hom(X, GY)$ means that we can equally well think of $GY$ as representing $\hom(F-, Y)$ as we can $FX$ as representing $\hom(X, G-)$ . Time is up for today, but we’ll be seeing more of adjunctions next time, when we resume our study of Stone duality.

[Tip of the hat to Robert Dawson for the Janis Joplin quip.]

Lattices and Duality

April 4, 2008 in Posets and Lattices, Propositional Calculus | Tags: inf-lattices, joins, lattices, principle of duality, sup-lattices | by Todd Trimble | 27 comments

Previously, on “Stone duality”, we introduced the notions of poset and meet-semilattice (formalizing the conjunction operator “and”), as a first step on the way to introducing Boolean algebras. Our larger goal in this series will be to discuss Stone duality, where it is shown how Boolean algebras can be represented “concretely”, in terms of the topology of their so-called Stone spaces — a wonderful meeting ground for algebra, topology, logic, geometry, and even analysis!

In this installment we will look at the notion of lattice and various examples of lattice, and barely scratch the surface — lattice theory is a very deep and multi-faceted theory with many unanswered questions. But the idea is simple enough: lattices formalize the notions of “and” and “or” together. Let’s have a look.

Let $(X, \leq)$ be a poset. If $x, y$ are elements of $X$ , a join of $x$ and $y$ is an element $j$ with the property that for any $a \in X$ ,

$j \leq a$ if and only if ( $x \leq a$ and $y \leq a$ ).

For a first example, consider the poset $PX$ of subsets of $X$ ordered by inclusion. The join in that case is given by taking the union, i.e., we have

$S \cup T \subseteq A$ if and only if ( $S \subseteq A$ and $T \subseteq A$ ).

Given the close connection between unions of sets and the disjunction “or”, we can therefore say, roughly, that joins are a reasonable mathematical way to formalize the structure of disjunction. We will say a little more on that later when we discuss mathematical logic.

Notice there is a close formal resemblance between how we defined joins and how we defined meets. Recall that a meet of $x$ and $y$ is an element $m$ such that for all $a \in X$ ,

$a \leq m$ if and only if ( $a \leq x$ and $a \leq y$ ).

Curiously, the logical structure in the definitions of meet and join is essentially the same; the only difference is that we switched the inequalities (i.e., replaced all instances of $x \leq y$ by $y \leq x$ ). This is an instance of a very important concept. In the theory of posets, the act of modifying a logical formula or theorem by switching all the inequalities but otherwise leaving the logical structure the same is called taking the dual of the formula or theorem. Thus, we would say that the dual of the notion of meet is the notion of join (and vice-versa). This turns out to be a very powerful idea, which in effect will allow us to cut our work in half.

(Just to put in some fine print or boilerplate, let me just say that a formula in the first-order theory of posets is a well-formed expression in first-order logic (involving the usual logical connectives and logical quantifiers and equality over a domain $X$ ), which can be built up by taking $\leq$ as a primitive binary predicate on $X$ . A theorem in the theory of posets is a sentence (a closed formula, meaning that all variables are bound by quantifiers) which can be deduced, following standard rules of inference, from the axioms of reflexivity, transitivity, and antisymmetry. We occasionally also consider formulas and theorems in second-order logic (permitting logical quantification over the power set $PX$ ), and in higher-order logic. If this legalistic language is scary, don’t worry — just check the appropriate box in the End User Agreement, and reason the way you normally do.)

The critical item to install before we’re off and running is the following meta-principle:

Principle of Duality: If a logical formula F is a theorem in the theory of posets, then so is its dual F’.

Proof: All we need to do is check that the duals of the axioms in the theory of posets are also theorems; then F’ can be proved just by dualizing the entire proof of F. Now the dual of the reflexivity axiom, $\forall_{x \in X} x \leq x$ , is itself! — and of course an axiom is a theorem. The transitivity axiom, $\forall_{x, y, z \in X} (x \leq y$ and $y \leq z)$ implies $x \leq z$ , is also self-dual (when you dualize it, it looks essentially the same except that the variables $x$ and $z$ are switched — and there is a basic convention in logic that two sentences which differ only by renaming the variables are considered syntactically equivalent). Finally, the antisymmetry axiom is also self-dual in this way. Hence we are done. $\Box$

So, for example, by the principle of duality, we know automatically that the join of two elements is unique when it exists — we just dualize our earlier theorem that the meet is unique when it exists. The join of two elements $x$ and $y$ is denoted $x \vee y$ .

Be careful, when you dualize, that any shorthand you used to abbreviate an expression in the language of posets is also replaced by its dual. For example, the dual of the notation $x \wedge y$ is $x \vee y$ (and vice-versa of course), and so the dual of the associativity law which we proved for meet is (for all $x, y, z$ ) $(x \vee y) \vee z = x \vee (y \vee z)$ . In fact, we can say

Theorem: The join operation $\vee$ is associative, commutative, and idempotent.

Proof: Just apply the principle of duality to the corresponding theorem for the meet operation.

Just to get used to these ideas, here are some exercises.

State the dual of the Yoneda principle (as stated here).
Prove the associativity of join from scratch (from the axioms for posets). If you want, you may invoke the dual of the Yoneda principle in your proof. (Note: in the sequel, we will apply the term “Yoneda principle” to cover both it and its dual.)

To continue: we say a poset is a join-semilattice if it has all finite joins (including the empty join, which is the bottom element $\bot$ satisfying $\bot \leq a$ for all $a$ ). A lattice is a poset which has all finite meets and finite joins.

Time for some examples.

The set of natural numbers 0, 1, 2, 3, … under the divisibility order ( $x \leq y$ if $x$ divides $y$ ) is a lattice. (What is the join of two elements? What is the bottom element?))
The set of natural numbers under the usual order is a join-semilattice (the join of two elements here is their maximum), but not a lattice (because it lacks a top element).
The set of subsets of a set $X$ is a lattice. The join of two subsets is their union, and the bottom element is the empty set.
The set of subspaces of a vector space $V$ is a lattice. The meet of two subspaces is their ordinary intersection; the join of two subspaces $U$ , $W$ is the vector space which they jointly generate (i.e., the set of vector sums $u + w$ with $u \in U, w \in W$ , which is closed under addition and scalar multiplication).

The join in the last example is not the naive set-theoretic union of course (and similar remarks hold for many other concrete lattices, such as the lattice of all subgroups of a group, and the lattice of ideals of a ring), so it might be worth asking if there is a uniform way of describing joins in cases like these. Certainly the idea of taking some sort of closure of the ordinary union seems relevant (e.g., in the vector space example, close up the union of $U$ and $W$ under the vector space operations), and indeed this can be made precise in many cases of interest.

To explain this, let’s take a fresh look at the definition of join: the defining property was

$x \vee y \leq a$ if and only if ( $x \leq a$ and $y \leq a$ ).

What this is really saying is that among all the elements $a$ which “contain” both $x$ and $y$ , the element $x \vee y$ is the absolute minimum. This suggests a simple idea: why not just take the “intersection” (i.e., meet) of all such elements $a$ to get that absolute minimum? In effect, construct joins as certain kinds of meets! For example, to construct the join of two subgroups $H \subseteq G$ , $J \subseteq G$ , take the intersection of all subgroups containing both $H$ and $J$ — that intersection is the group-theoretic closure of the union $H \cup J$ .

There’s a slight catch: this may involve taking the meet of infinitely many elements. But there is no difficulty in saying what this means:

Definition: Let $X$ be a poset, and suppose $S \subseteq X$ . The infimum of $S$ , if it exists, is an element $m \in X$ such that for all $a \in X$ , $a \leq m$ if and only if $a \leq s$ for all $s \in S$ .

By the usual Yoneda argument, infima are unique when they exist (you might want to write that argument out to make sure it’s quite clear). We denote the infimum of $S$ by $\inf(S)$ .

We say that a poset $X$ is an inf-lattice if there is an infimum for every subset. Similarly, the supremum of $S \subseteq X$ , if it exists, is an element $\sup(S)$ such that for all $a \in X$ , $\sup(S) \leq a$ if and only if $s \leq a$ for all $s \in S$ . A poset is a sup-lattice if there is a supremum for every subset. [I’ll just quickly remark that the notions of inf-lattice and sup-lattice belong to second-order logic, since it involves quantifying over all subsets $S \subseteq X$ (or over all elements of $PX$ ).]

Trivially, every inf-lattice is a meet-semilattice, and every sup-lattice is a join-semilattice. More interestingly, we have the

Theorem: Every inf-lattice is a sup-lattice (!). Dually, every sup-lattice is an inf-lattice.

Proof: Suppose $X$ is an inf-lattice, and let $S \subseteq X$ . Let $U = \{u \in X: \forall_{s \in S} s \leq u\}$ be the set of upper bounds of $S$ . I claim that $\inf(U)$ (“least upper bound”) is the supremum of $S$ . Indeed, from $\inf(U) \leq \inf(U)$ and the definition of infimum, we know that $\inf(U) \leq a$ if $a \in U$ , i.e., $\inf(U) \leq a$ if $s \leq a$ for all $s \in S$ . On the other hand, we also know that if $s \in S$ , then $s \leq u$ for every $u \in U$ , and hence $s \leq \inf(U)$ by the defining property of infimum (i.e., $\inf(U)$ really is an upper bound of $S$ ). So, if $\inf(U) \leq a$ , we conclude by transitivity that $s \leq a$ for every $s \in S$ . This completes the proof. $\Box$

Corollary: Every finite meet-semilattice is a lattice.

Even though every inf-lattice is a sup-lattice and conversely (sometimes people just call them “complete lattices”), there are important distinctions to be made when we consider what is the appropriate notion of homomorphism. The notions are straightforward enough: a morphism of meet-semilattices $f: X \to Y$ is a function which takes finite meets in $X$ to finite meets in $Y$ ( $f(x \wedge x') = f(x) \wedge f(x')$ , and $f(1) = 1$ where the 1’s denote top elements). There is a dual notion of morphism of join-semilattices ( $f(x \vee x') = f(x) \vee f(x')$ and $f(0) = 0$ where the 0’s denote bottom elements). A morphism of inf-lattices $f: X \to Y$ is a function such that $f(\inf(S)) = \inf(f(S))$ for all subsets $S \subseteq X$ , where $f(S)$ denotes the direct image of $S$ under $f$ . And there is a dual notion of morphism of sup-lattices: $f(\sup(S)) = \sup(f(S))$ . Finally, a morphism of lattices is a function which preserves all finite meets and finite joins, and a morphism of complete lattices is one which preserves all infs and sups.

Despite the theorem above , it is not true that a morphism of inf-lattices must be a morphism of sup-lattices. It is not true that a morphism of finite meet-semilattices must be a lattice morphism. Therefore, in contexts where homomorphisms matter (which is just about all the time!), it is important to keep the qualifying prefixes around and keep the distinctions straight.

Exercise: Come up with some examples of morphisms which exhibit these distinctions.

Section 5 – Complements and Powers

December 21, 2007 in Exposition, Math Topics, Naive Set Theory | Tags: axiom of powers, complements, naive set theory, Paul Halmos, power set, principle of duality | by Vishal | 2 comments

The difference between sets $A$ and $B$ , also known as the relative complement of $B$ in $A$ , is the set $A - B$ defined by

$A - B = \{ x: x \in A \mbox{ and } x \not\in B \}$ .

If we assume the existence of a universe, $U$ , such that all the sets are subsets of $U$ , then we can considerably simplify our notation. So, for instance, $U - B$ can simply be written as $B'$ , which denotes the complement of $B$ in $U$ . Similarly, $U' = U - U = \emptyset \,$ , $\emptyset ' = U - \emptyset = U$ , and so on. A quick look at a few more facts:

$(A')' = A$ ,
$A \cap A' = \emptyset$ ,
$A \cup A' = U$
$A \subset B$ if and only if $B' \subset A'$ .

The last one is proved as follows. We prove the “if” part first. Suppose $B' \subset A'$ . If $x \in A$ , then clearly $x \not\in A'$ . But, since $B' \subset A'$ , we have $x \not\in B'$ , which implies $x \in B$ . Hence, $A \subset B$ . This closes the proof of the “if” part. Now, we prove the “only if” part. So, suppose $A \subset B$ . Now, if $x \in B'$ , then clearly $x \not\in B$ . But, since $A \subset B$ , we have $x \not\in A$ , which implies $x \in A'$ . Hence, $B' \subset A'$ . This closes the proof of the “only if” part, and, we are done.

The following are the well-known DeMorgan’s laws (about complements):

$(A \cup B)' = A' \cap B'$ , and $(A \cap B)' = A' \cup B'$ .

Let’s quickly prove the first one. Suppose $x$ belongs to the left hand side. Then, $x \not\in A \cup B$ , which implies $x \not\in A$ and $x \not\in B$ , which implies $x \in A'$ and $x \in B'$ , which implies $x \in A' \cap B'$ . This proves that the left hand side is a subset of the right hand side. We can similarly prove the right hand side is a subset of the left hand side, and this closes our proof.

Though it isn’t very apparent, but if we look carefully at the couple of problems whose proofs we did above, we note something called the principle of duality for sets. One encounters such dual principles in mathematics quite often. In this case, this dual principle is stated a follows.

Principle of duality (for sets): If in an inclusion or equation involving unions, intersections and complements of subsets of $U$ (the universe) we replace each set by its complement, interchange unions and intersections, and reverse all set-inclusions, the result is another theorem.

Using the above principle, it is easy to “derive” one of the DeMorgan’s laws from another and vice versa. In addition, DeMorgan’s laws can be extended to larger collections of sets instead of just pairs.

Here are a few exercises on complementation.

$A - B = A \cap B'$ ,
$A \subset B$ if and only if $A - B = \emptyset$ ,
$A - (A - B) = A \cap B$ ,
$A \cap (B - C) = (A \cap B) - (A \cap C)$ ,
$A \cap B \subset (A \cap B) \cup (A \cap C)$ ,
$(A \cup C) \cap (B \cup C') \subset A \cup B$ .

We will prove the last one, leaving the remaining as exercises to the reader. Suppose $x$ belongs to the left hand side. Then, $x \in A \cup C$ and $x \in B \cup C'$ . Now, note that if $x \in C$ , then $x \not\in C'$ , which implies $x \in B$ , which implies $x \in A \cup B$ . If, on the other hand, $x \in C'$ , then $x \not\in C$ , which implies $x \in A$ , which implies $x \in A \cup B$ . Hence, in either case, the left hand side is a subset of $A \cup B$ , and we are done.

We now define the symmetric difference (or Boolean sum) of two sets $A$ and $B$ as follows:

$A \triangle B = (A-B) \cup (B-A)$ .

This is basically the set of all elements in $A$ or $B$ but not in $A \cap B$ . In other words, $A \triangle B = (A \cup B) - (A \cap B)$ . Again, a few facts (involving symmetric differences) that aren’t hard to prove:

$A \triangle \emptyset = A$ ,
$A \triangle A = \emptyset$ ,
$A \triangle B = B \triangle A$ (commutativity),
$(A \triangle B) \triangle C = A \triangle (B \triangle C)$ (associativity),
$(A \triangle B) \triangle (B \triangle C) = A \triangle C$ ,
$A \cap (B \triangle C) = (A \cap B) \triangle (A \cap C)$ .

This brings us now to the axiom of powers, which basically states if $E$ is a set then there exists a set that contains all the possible subsets of $E$ as its elements.

Axiom of powers: If $E$ is a set, then there exists a set (collection) $P$ , such that if $X \subset E$ , then $X \in P$ .

The set $P$ , described above, may be too “comprehens ive”, i.e., it may contain sets other than the subsets of $E$ . Once again, we “fix” this by applying the axiom of specification to form the new set $P = \{ X: X \subset E \}$ . The set $P$ is called the power set of $E$ , and the axiom of extension, again, guarantees its uniqueness. We denote $P$ by $P(E)$ to show the dependence of $P$ on $E$ . A few illustrative examples: $P(\emptyset) = \{ \emptyset \}$ , $P(\{ a \}) = \{ \emptyset, \{ a \} \}$ , $P(\{ a, b \}) = \{ \emptyset, \{ a \}, \{ b \}, \{ a, b \} \}$ , and so on.

Note that if $E$ is a finite set, containing $n$ elements, then the power set $P(E)$ contains $2^n$ elements. The “usual” way to prove this is by either using a simple combinatorial argument or by using some algebra. The combinatorial argument is as follows. An element in $E$ either belongs to a subset of $E$ or it doesn’t: there are thus two choices; since there are $n$ elements in $E$ , the number of all possible subsets of $E$ is therefore $2^n$ . A more algebraic way of proving the same result is as follows. The number of subsets with $k$ elements is $\binom{n}{k}$ . So, the number of subsets of $E$ is $\sum_{k=0}^{n}\binom{n}{k}$ . But, from the binomial theorem, we have $\displaystyle (1 + x)^n = \sum_{k=0}^{n}\binom{n}{k}x^k$ . Putting $x = 1$ , we get $2^n$ as our required answer.

A few elementary facts:

$\bigcap_{X \in P(E)} X = \emptyset$ .
If $E \subset F$ , then $P(E) \subset P(F)$ .
$E = \bigcup P(E)$ .

EXERCISES:

1. Prove that $P(E) \bigcap P(F) = P(E \bigcap F)$ .

2. Prove that $P(E) \bigcup P(F) \subset P(E \bigcup F)$ .

	Strong equidistribut… on Platonic Solids and Euler…
	m.s.mohamed ansari on The 54th Carnival of Math…
	Convictions ·… on Continued fraction for e
	Wayne J. Mann on Solution to POW-12: A graph co…
	erneststephen on The 54th Carnival of Math…
	anhtraisg on p^q + q^p is prime
	prof dr drd horia or… on My first post
	prof drd horia orasa… on My first post
	prof dr mircea orasa… on Inequality with log
	notedscholar on Self-referential Paradoxes, In…
	prof dr mircea orasa… on Inequality with log
	prof dr mircea orasa… on Inequality with log
	prof dr mircea orasa… on 2010 in review
	kenji on Basic category theory, I
	prof dr mircea orasa… on Solution to POW-10: Another ha…

M	T	W	T	F	S	S
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

Tag Archive

Basic Category Theory, III: Representability, adjoints, and the Yoneda lemma

Lattices and Duality

Section 5 – Complements and Powers

Our other blog

Visitors to this blog

Blog Stats

Wikio Ranking

Current Online Readers

Recent Comments

Top Posts

Archives

Categories

Blogroll

chess

Computers and Technology

Elementary Math Problem Solving

Fun, Humor

Higher Mathematics

Math Education

Non-technical

Opinions

People in Computer Science

People in mathematics

Philosophy & Logic

Physics

Politics, News

Sciences

Useful general links

Useful Math Links

Tag Cloud

Admin/Users Login

Pages