You are currently browsing the category archive for the ‘Philosophy & Logic’ category.

Who doesn’t like self-referential paradoxes? There is something about them that appeals to all and sundry. And, there is also a certain air of mystery associated with them, but when people talk about such paradoxes in a non-technical fashion indiscriminately, especially when dealing with Gödel’s incompleteness theorem, then quite often it gets annoying!

Lawvere in ‘Diagonal Arguments and Cartesian Closed Categories‘ sought, among several things, to demystify the incompleteness theorem. To pique your interest, in a self-commentary on the above paper, he actually has quite a few harsh words, in a manner of speaking.

“The original aim of this article was to demystify the incompleteness theorem of Gödel and the truth-definition theory of Tarski by showing that both are consequences of some very simple algebra in the cartesian-closed setting. It was always hard for many to comprehend how Cantor’s mathematical theorem could be re-christened as a“paradox” by Russell and how Gödel’s theorem could be so often declared to be the most significant result of the 20th century. There was always the suspicion among scientists that such extra-mathematical publicity movements concealed an agenda for re-establishing belief as a substitute for science.”

In the aforesaid paper, Lawvere of course uses the language of category theory – the setting is that of cartesian closed categories – and therefore the technical presentation can easily get out of reach of most people’s heads – including myself. Thankfully, Noson S. Yanofsky has written a nice paper, ‘A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points’, that is a lot more accessible and fun to read as well.Yanofsky employs only the notions of sets and functions, thereby avoiding the language of category theory, to bring out and make accessible as much as possible the content of Lawvere’s paper. Cantor’s theorem, Russell’s Paradox, the non-definability of satisfiability, Tarski’s non-definability of truth and Gödel’s (first) incompleteness theorem are all shown to be paradoxical phenomena that merely result from the existence of a cartesian closed category satisfying certain conditions. The idea is to use a single formalism to describe all these diverse phenomena.

(Dang, I just found that John Baez had already blogged on this before, way back in 2006!)

Advertisements

Welcome to the 54th Carnival of Mathematics, and Happy Fourth of July to our American readers! Indeed, the carnival should have been hosted yesterday, and I apologize for being a day late.

Trivia: Today, we have the 234th Independence Day celebrations in the  US, and ours is the 54th carnival. 2+3+4 = 5+4, see? Boy, do I feel so clever!

Ok, let’s begin, now!

We start off with a post, submitted by Shai Deshe, that presents a collection of YouTube videos explaining different kinds of infinities in set theory, causality vs conditionality in probability and some topology. The videos are the kind of ones that “math people” could use to explain a few mathematical concepts to their friends, family members and colleagues who may not be enamored of math very much but may still possess a lingering interest in it.

Experimental philosophy, according to the Experimental Philosophy Society, “involves the collection of empirical data to shed light on philosophical issues“. As such, a careful quantitative analyses of results of experiments are used to shed light on many philosophical issues/debates. Anthony Chemero wrote a post titled, ‘What Situationist Experiments Show‘, that links to a paper with the same title that he coauthored with John Campbell and Sarah Meerschaert. In the paper, the authors, through quantitative analyses of actual experimental data, argue that virtue ethics has not lost to the siuationist side, whose critiques of virtue theory are far from convincing.

Next, I would like to bring the readers’ attention to two math blogs that came into existence somewhat recently and which I think have a lot of really good mathematical content. They are Annoying Precision and A Portion of the Book. In my opinion, their blog posts contain a wealth of mathematical knowledge, especially for undergraduates (and graduate students too!), who, if inclined toward problem-solving, will enjoy the posts even more. Go ahead and dive into them!

At Annoying Precision, a project aimed at the “Generally Interested Lay Audience” that Qiaochu Yuan started aims “to build up to a discussion of the Polya enumeration theorem without assuming any prerequisites other than a passing familiarity with group theory.” It begins with GILA I: Group Actions and Equivalence Relations, the last post of the series being GILA VI: The cycle index polynomials of the symmetric groups.

Usually, undergrads hardly think integrals have much to do with combinatorics. At A Portion of the Book, Masoud Zargar has a very nice post that deals with the intersection of Integrals, Combinatorics and Geometry.

Tom Escent submitted a link to an article titled, “Introduction to Nerds on Wall Street“, which actually provides a very small snapshot of the book named, Nerds on Wall Street: Math, Machines and Wired Markets whose author is David J. Leinweber. I haven’t read the book yet, but based on generally good reviews, it seems like it chronicles the contribution of Quant guys to Wall Street over the past several decades. Should be interesting to Math and CS majors, I think.

Let’s have a post on philosophy and logic, shall we? At Skeptic’s Play, there is a discussion on Gödel’s modal ontological argument regarding the possibility of existence of God. As someone who has just begun a self-study of modal logic, I will recommend Brian K. Chellas’ excellent introduction to the subject, titled Modal Logic: An Introduction.

Then, there is the Daily Integral, a blog dealing with solving elementary integrals and which I think may be particularly useful for high-school students.

Let me close this carnival by asking the reader, “What do you think is the world’s oldest mathematical artifact?” There are several candidates, and according to The Number Warrior, candidate #1 is The Lebombo Bone, found in the Lebombo Mountains of South Africa and Swaziland, that dates back to 35,000 BC!

That’s all for now! Thanks to everyone who made submissons.

After a long hiatus, I’d like to renew the discussion of axiomatic categorical set theory, more specifically the Elementary Theory of the Category of Sets (ETCS). Last time I blogged about this, I made some initial forays into “internalizing logic” in ETCS, and described in broad brushstrokes how to use that internal logic to derive a certain amount of the structure one associates with a category of sets. Today I’d like to begin applying some of the results obtained there to the problem of constructing colimits in a category satisfying the ETCS axioms (an ETCS category, for short).

(If you’re just joining us now, and you already know some of the jargon, an ETCS category is a well-pointed topos that satisfies the axiom of choice and with a natural numbers object. We are trying to build up some of the elementary theory of such categories from scratch, with a view toward foundations of mathematics.)

But let’s see — where were we? Since it’s been a while, I was tempted to review the philosophy behind this undertaking (why one would go to all the trouble of setting up a categories-based alternative to ZFC, when time-tested ZFC is able to express virtually all of present-day mathematics on the basis of a reasonably short list of axioms?). But in the interest of time and space, I’ll confine myself to a few remarks.

As we said, a chief difference between ZFC and ETCS resides in how ETCS treats the issue of membership. In ZFC, membership is a global binary relation: we can take any two “sets” $A, B$ and ask whether $A \in B$. Whereas in ETCS, membership is a relation between entities of different sorts: we have “sets” on one side and “elements” on another, and the two are not mixed (e.g., elements are not themselves considered sets).

Further, and far more radical: in ETCS the membership relation $x \in A$ is a function, that is, an element $x$ “belongs” to only one set $A$ at a time. We can think of this as “declaring” how we are thinking of an element, that is, declaring which set (or which type) an element is being considered as belonging to. (In the jargon, ETCS is a typed theory.) This reflects a general and useful philosophic principle: that elements in isolation are considered inessential, that what counts are the aggregates or contexts in which elements are organized and interrelated. For instance, the numeral ‘2’ in isolation has no meaning; what counts is the context in which we think of it (qua rational number or qua complex number, etc.). Similarly the set of real numbers has no real sense in isolation; what counts is which category we view it in.

I believe it is reasonable to grant this principle a foundational status, but: rigorous adherence to this principle completely changes the face of what set theory looks like. If elements “belong” to only one set at a time, how then do we even define such basic concepts as subsets and intersections? These are some of these issues we discussed last time.

There are other significant differences between ZFC and ETCS: stylistically, or in terms of presentation, ZFC is more “top-down” and ETCS is more “bottom-up”. For example, in ZFC, one can pretty much define a subset $\{x \in X: P\}$ by writing down a first-order formula $P$ in the language; the comprehension (or separation) axiom scheme is a mighty sledgehammer that takes care of the rest. In the axioms of ETCS, there is no such sledgehammer: the closest thing one has to a comprehension scheme in the ETCS axioms is the power set axiom (a single axiom, not an axiom scheme). However, in the formal development of ETCS, one derives a comprehension scheme as one manually constructs the internal logic, in stages, using the simple tools of adjunctions and universal properties. We started doing some of that in our last post. So: with ZFC it’s more as if you can just hop in the car and go; with ETCS you build the car engine from smaller parts with your bare hands, but in the process you become an expert mechanic, and are not so rigidly attached to a particular make and model (e.g., much of the theory is built just on the axioms of a topos, which allows a lot more semantic leeway than one has with ZF).

But, in all fairness, that is perhaps the biggest obstacle to learning ETCS: at the outset, the tools available [mainly, the idea of a universal property] are quite simple but parsimonious, and one has to learn how to build some set-theoretic and logical concepts normally taken as “obvious” from the ground up. (Talk about “foundations”!) On the plus side, by building big logical machines from scratch, one gains a great deal of insight into the inner workings of logic, with a corresponding gain in precision and control and modularity when one would like to use these developments to design, say, automated deduction systems (where there tend to be strong advantages to using type-theoretic frameworks).

Enough philosophy for now; readers may refer to my earlier posts for more. Let’s get to work, shall we? Our last post was about the structure of (and relationships between) posets of subobjects $Sub(X)$ relative to objects $X$, and now we want to exploit the results there to build some absolute constructions, in particular finite coproducts and coequalizers. In this post we will focus on coproducts.

Note to the experts: Most textbook treatments of the formal development of topos theory (as for example Mac Lane-Moerdijk) are efficient but highly technical, involving for instance the slice theorem for toposes and, in the construction of colimits, recourse to Beck’s theorem in monad theory applied to the double power-set monad [following the elegant construction of Paré]. The very abstract nature of this style of argumentation (which in the application of Beck’s theorem expresses ideas of fourth-order set theory and higher) is no doubt partly responsible for the somewhat fearsome reputation of topos theory.

In these notes I take a much less efficient but much more elementary approach, based on an arrangement of ideas which I hope can be seen as “natural” from the point of view of naive set theory. I learned of this approach from Myles Tierney, who was my PhD supervisor, and who with Bill Lawvere co-founded elementary topos theory, but I am not aware of any place where the details of this approach have been written up before now. I should also mention that the approach taken here is not as “purist” as many topos theorists might want; for example, here and there I take advantage of the strong extensionality axiom of ETCS to simplify some arguments.

### The Empty Set and Two-Valued Logic

We begin with the easy observation that a terminal category, i.e., a category $\mathbf{1}$ with just one object and one morphism (the identity), satisfies all the ETCS axioms. Ditto for any category $C$ equivalent to $\mathbf{1}$ (where every object is terminal). Such boring ETCS categories are called degenerate; obviously our interest is in the structure of nondegenerate ETCS categories.

Let $\mathbf{E}$ be an ETCS category (see here for the ETCS axioms). Objects of $\mathbf{E}$ are generally called “sets”, and morphisms are generally called “functions” or “maps”.

Proposition 0: If an ETCS category $\mathbf{E}$ is a preorder, then $\mathbf{E}$ is degenerate.

Proof: Recall that a preorder is a category in which there is at most one morphism $A \to B$ for any two objects $A, B$. Every morphism in a preorder is vacuously monic. If there is a nonterminal set $A$, then the monic $A \to 1$ to any terminal set defines a subset $A \subseteq 1$ distinct from the subset defined by $1 \to 1$, thus giving (in an ETCS category) distinct classifying maps $\chi_A, t: 1 \to P(1)$, contradicting the preorder assumption. Therefore all objects $A$ are terminal. $\Box$

Assume from now on that $\mathbf{E}$ is a nondegenerate ETCS category.

Proposition 1: There are at least two truth values, i.e., two elements $1 \to P(1)$, in $\mathbf{E}$.

Proof: By proposition 0, there exist sets $X, Y$ and two distinct functions $f, g: X \to Y$. By the axiom of strong extensionality, there exists $x: 1 \to X$ such that $fx \neq gx$. The equalizer $E \to 1$ of the pair $fx, gx: 1 \to Y$ is then a proper subset of $1$, and therefore there are at least two distinct elements $\chi_E, \chi_1: 1 \to P(1)$. $\Box$

Proposition 2: There are at most two truth values $1 \to P(1)$; equivalently, there are at most two subsets of $1$.

Proof: If $U, V \subseteq 1$ are distinct subsets of $1$, then either $U \neq U \cap V$ or $V \neq U \cap V$, say the former. Then $1_U: U \subseteq U$ and $U \cap V \subseteq U$ are distinct subsets, with distinct classifying maps $\chi_{1_U}, \chi_{U \cap V}: U \to P(1)$. By strong extensionality, there exists $x: 1 \to U$ distinguishing these classifying maps. Because $1$ is terminal, we then infer $1 \subseteq U$ and $U \subseteq 1$, so $U = 1$ as subsets of $1$, and in that case only $V$ can be a proper subset of $1$. $\Box$

By propositions 1 and 2, there is a unique proper subset of the terminal object $1$. Let $0 \to 1$ denote this subset. Its domain may be called an “empty set”; by the preceding proposition, it has no proper subsets. The classifying map $1 \to P1$ of $0 \subseteq 1$ is the truth value we call “false”.

Proposition 3: 0 is an initial object, i.e., for any $X$ there exists a unique function $0 \to X$.

Proof: Uniqueness: if $f, g: 0 \to X$ are maps, then their equalizer $x: E \to 0$, which is monic, must be an isomorphism since 0 has no proper subsets. Therefore $f = g$. Existence: there are monos

$\displaystyle 0 \to 1 \stackrel{t_X}{\to} PX$

$\displaystyle X \stackrel{\sigma}{\to} PX$

where $t_X$ is “global truth” (classifying the subset $X \subseteq X$) on $X$ and $\sigma$ is the “singleton mapping $x \mapsto \{x\}$” on $X$, defined as the classifying map of the diagonal map $\delta: X \subseteq X \times X$ (last time we saw $\sigma$ is monic). Take their pullback. The component of the pullback parallel to $\sigma$ is a mono $P \to 0$ which again is an isomorphism, whence we get a map $0 \cong P \to X$ using the other component of the pullback. $\Box$

Remark: For the “purists”, an alternative construction of the initial set 0 that avoids use of the strong extensionality axiom is to define the subset $0 \subseteq 1$ to be “the intersection all subsets of $1$“. Formally, one takes the extension $\left[\phi\right] \subseteq 1$ of the map

$\displaystyle \phi = (1 \stackrel{t_{P1}}{\to} PP1 \stackrel{\bigcap}{\to} P1);$

where the first arrow represents the class of all subsets of $P1$, and the second is the internal intersection operator defined at the end of our last post. Using formal properties of intersection developed later, this intersection $0 \subseteq 1$ has no proper subsets, and then the proof of proposition 3 carries over verbatim. $\Box$

Corollary 1: For any $X$, the set $0 \times X$ is initial.

Proof: By cartesian closure, maps $0 \times X \to Y$ are in bijection with maps of the form $0 \to Y^X$, and there is exactly one of these since 0 is initial. $\Box$

Corollary 2: If there exists $f: X \to 0$, then $X$ is initial.

Proof: The composite of $\langle f, 1_X \rangle: X \to 0 \times X$ followed by $\pi_2: 0 \times X \to X$ is $1_X$, and $\pi_2$ followed by $\langle f, 1_X \rangle: X \to 0 \times X$ is also an identity since $0 \times X$ is initial by corollary 1. Hence $X$ is isomorphic to an initial object $0 \times X$. $\Box$

By corollary 2, for any object $Y$ the arrow $0 \to Y$ is vacuously monic, hence defines a subset.

Proposition 4: If $X \not\cong 0$, then there exists an element $x: 1 \to X$.

Proof: Under the assumption, $X$ has at least two distinct subsets: $0 \subseteq X$ and $1_X: X \subseteq X$. By strong extensionality, their classifying maps $\chi_0, \chi_1: X \to P1$ are distinguished by some element $x: 1 \to X$.

### External Unions and Internal Joins

One of the major goals in this post is to construct finite coproducts in an ETCS category. As in ordinary set theory, we will construct these as disjoint unions. This means we need to discuss unions first; as should be expected by now, in ETCS unions are considered locally, i.e., we take unions of subsets of a given set. So, let $A, B \subseteq X$ be subsets.

To define the union $A \cup B \subseteq X$, the idea is to take the intersection of all subsets containing $A$ and $B$. That is, we apply the internal intersection operator (constructed last time),

$\displaystyle \bigcap: PPX \to PX,$

to the element $1 \to PPX$ that represents the set of all subsets of $X$ containing $A$ and $B$; the resulting element $1 \to PX$ represents $A \cup B$. The element $1 \to PPX$ corresponds to the intersection of two subsets

$\{C \in PX: A \subseteq C\} \cap \{C \in PX: B \subseteq C\} \subseteq PX.$

Remark: Remember that in ETCS we are using generalized elements: $C \in PX$ really means a function $C: U \to PX$ over some domain $U$, which in turn classifies a subset $\left[C\right] \subseteq U \times X$. On the other hand, the $A$ here is a subset $A \subseteq X$. How then do we interpret the condition “$A \subseteq C$“? We first pull back $\chi_A: 1 \to PX$ over to the domain $U$; that is, we form the composite $\displaystyle U \stackrel{!}{\to} 1 \stackrel{\chi_A}{\to} PX$, and consider the condition that this is bounded above by $C: U \to PX$. (We will write $\chi_A \leq C$, thinking of the left side as constant over $U$.) Externally, in terms of subsets, this corresponds to the condition $U \times A \subseteq \left[C\right]$.

We need to construct the subsets $\{C \in PX: A \subseteq C\}, \{C \in PX: B \subseteq C\}$. In ZFC, we could construct those subsets by applying the comprehension axiom scheme, but the axioms of ETCS have no such blanket axiom scheme. (In fact, as we said earlier, much of the work on “internalizing logic” goes to show that in ETCS, we instead derive a comprehension scheme!) However, one way of defining subsets in ETCS is by taking loci of equations; here, we express the condition $A \subseteq C$, more pedantically $A \subseteq \left[C\right]$ or $\chi_A \leq C$, as the equation

$(\chi_A \Rightarrow C) = t_X$

where the right side is the predicate “true over $X$“.

Thus we construct the subset $\{C \in PX: A \subseteq C\}$ of $PX$ via the pullback:

{C: A ≤ C} -------> 1
|              |
|              | t_X
V chi_A => -   V
PX -----------> PX

Let me take a moment to examine what this diagram means exactly. Last time we constructed an internal implication operator

$\Rightarrow: P1 \times P1 \to P1$

and now, in the pullback diagram above, what we are implicitly doing is lifting this to an operator

$\Rightarrow_X: PX \times PX \to PX$

The easy and cheap way of doing this is to remember the isomorphism $PX \cong P1^X$ we used last time to uncover the cartesian closed structure, and apply this to

$\displaystyle P1^X \times P1^X \cong (P1 \times P1)^X \stackrel{\Rightarrow^X}{\to} P1^X$

to define $\Rightarrow_X: PX \times PX \to PX$. This map classifies a certain subset of $X \times PX \times PX$, which I’ll just write down (leaving it as an exercise which involves just chasing the relevant definitions):

$\{(x, T, S) \in X \times PX \times PX: x \in_X T \Rightarrow x \in_X S\}$

Remark: Similarly we can define a meet operator $\wedge_X: PX \times PX \to PX$ by exponentiating the internal meet $P1 \times P1 \to P1$. It is important to know that the general Heyting algebra identities which we established last time for $P1$ lift to the corresponding identities for the operators $\wedge_X, \Rightarrow_X$ on $PX$. Ultimately this rests on the fact that the functor $(-)^X$, being a right adjoint, preserves products, and therefore preserves any algebraic identity which can be expressed as a commutative diagram of operations between such products.

Hence, for the fixed subset $A \subseteq X$ (classified by $\chi_A: 1 \to PX$), the operator

$\chi_A \Rightarrow -: PX \to PX$

classifies the subset

$\{(x, S): x \in_X A \Rightarrow x \in_X S\} \hookrightarrow X \times PX$

Finally, in the pullback diagram above, we are pulling back the operator $\chi_A \Rightarrow -$ against $t_X$. But, from last time, that was exactly the method we used to construct universal quantification. That is, given a subset

$R \subseteq X \times Y$

we defined $\forall_Y R \subseteq X$ to be the pullback of $t_Y: 1 \hookrightarrow PY$ along $\chi_R: X \to PY$. Putting all this together, the pullback diagram above expresses the definition

$\{C \in PX: A \subseteq C\} := \{C \in PX: \forall_{x \in X} \ x \in_X A \Rightarrow x \in_X C\}$

that one would expect “naively”.

Now that all the relevant constructions are in place, we show that $A \cup B$ is the join of $A$ and $B$ in the poset $Sub(X)$. There is nothing intrinsically difficult about this, but as we are still in the midst of constructing the internal logic, we will have to hunker down and prove some logic things normally taken for granted or zipped through without much thought. For example, the internal intersection operator was defined with the help of internal universal quantification, and we will need to establish some formal properties of that.

Here is a useful general principle for doing internal logic calculations. Let $\chi_R: X \to PY$ be the classifying map of a subset $R \subseteq X \times Y$, and let $f: U \to X$ be a function. Then the composite $\chi_R f: U \to PY$ classifies the subset

$(f \times 1_Y)^{-1}(R) \subseteq U \times Y$

so that one has the general identity $\chi_R f = \chi_{(f \times 1)^{-1}(R)}$. In passing back and forth between the external and internal viewpoints, the general principle is to try to render “complicated” functions $U \to PY$ into a form $\chi_R f$ which one can more easily recognize. For lack of a better term, I’ll call this the “pullback principle”.

Lemma 1: Given a relation $R \hookrightarrow X \times Y$ and a constant $c: 1 \to Y$, there is an inclusion

$\forall_Y R \subseteq (1_X \times c)^{-1}(R)$

as subsets of $X$. (In traditional logical syntax, this says that for any element $c: 1 \to Y$,

$\forall_{y: Y} R(x, y)$ implies $R(x, c)$

as predicates over elements $x \in X$. This is the type of thing that ordinarily “goes without saying”, but which we actually have to prove here!)

Proof: As we recalled above, $\forall_Y R \subseteq X$ was defined to be $\chi_R^{-1}(t_Y)$, the pullback of global truth $t_Y: 1 \to PY$ along the classifying map $\chi_R: X \to PY$. Hold that thought.

Let

$Pc: PY \to P1$

be the map which classifies the subset $\{S \in PY: c \in_Y S\}$. Equivalently, this is the map

$P1^c: P1^Y \to P1^1$

under the canonical isomorphisms $PY \cong P1^Y$, $P1^1 \cong P1$. Intuitively, this maps $f \mapsto f(c)$, i.e., plugs an element $c \in Y$ into an element $f \in P1^Y$.

Using the adjunction $(- \times Y) \dashv (-)^Y$ of cartesian closure, the composite

$\displaystyle X \stackrel{\chi_R}{\to} PY \stackrel{Pc}{\to} P1$

transforms to the composite

$X \times 1 \stackrel{1_X \times c}{\to} X \times Y \stackrel{\chi_{R}}{\to} P1$

so by the pullback principle, $(Pc)\chi_R: X \times 1 \to P1$ classifies $(1_X \times c)^{-1}(R) \subseteq X \times 1 \cong X$.

Equivalently,

$(1_X \times c)^{-1}(R) = \chi_{R}^{-1} (Pc)^{-1}(t) \qquad (1)$

Also, as subsets of $PY$, we have the inclusion

$(t_Y: 1 \hookrightarrow PY) \subseteq (Pc)^{-1}(t) \qquad (2)$

[this just says that $t_Y$ belongs to the subset classified by $Pc$, or equivalently that $c: 1 \to Y$ is in the subset $Y \subseteq Y$]. Applying the pullback operation $\chi_{R}^{-1}$ to (2), and comparing to (1), lemma 1 follows. $\Box$

Lemma 2: If $R \subseteq S$ as subsets of $X \times Y$, then $\forall_Y R \subseteq \forall_Y S$.

Proof: From the last post, we have an adjunction:

$T \times Y \subseteq S$ if and only if $T \subseteq \forall_Y S$

for any subset of $T \subseteq X$. So it suffices to show $\forall_Y R \times Y \subseteq S$. But

$\forall_Y R \times Y \subseteq R \subseteq S$

where the first inclusion follows from $\forall_Y R \subseteq \forall_Y R$. $\Box$

Next, recall from the last post that the internal intersection of $F: 1 \to PPX$ was defined by interpreting the following formula on the right:

$\displaystyle \bigcap F = \forall_{S \in PX} (S \in_{PX} F) \Rightarrow (x \in_X S)$

Lemma 3: If $F \leq G: 1 \to PPX$, then $\displaystyle \bigcap G \leq \bigcap F: 1 \to PX$.

Proof: $F: 1 \to PPX$ classifies the subset $\{S \in PX: S \in_{PX} F\}$, i.e.,  $F$ is identified with the predicate $S \in_{PX} F$ in the argument $S$, so by hypothesis $(S \in_{PX} F) \leq (S \in_{PX} G)$ as predicates on $S$. Internal implication $a \Rightarrow b$ is contravariant in the argument $a$ [see the following remark], so

$\left[(S \in G) \Rightarrow (x \in S)\right] \leq \left[(S \in F) \Rightarrow (x \in S)\right]$

Now apply lemma 2 to complete the proof. $\Box$

Remark: The contravariance of $- \Rightarrow b$, that is, the fact that

$x \leq y$ implies $(y \Rightarrow b) \leq (x \Rightarrow b),$

is a routine exercise using the adjunction [discussed last time]

$a \wedge c \leq b$ if and only if $c \leq (a \Rightarrow b).$

Indeed, we have

$x \wedge (y \Rightarrow b) \leq y \wedge (y \Rightarrow b) \leq b \qquad (*)$

where the first inequality follows from the hypothesis $x \leq y$, and the second follows from $y \Rightarrow b \leq y \Rightarrow b$. By the adjunction, the inequality (*) implies $(y \Rightarrow b) \leq (x \Rightarrow b)$. $\Box$

Theorem 1: For subsets $A, B$ of $X$, the subset $A \cup B$ is an upper bound of $A$ and $B$, i.e., $A, B \subseteq A \cup B$.

Proof: It suffices to prove that $\displaystyle A = \bigcap \{C \in PX: A \subseteq C\}$, since then we need only apply lemma 3 to the trivially true inclusion

$\{C \in PX: A \subseteq C\} \cap \{C \in PX: B \subseteq C\} \subseteq \{C \in PX: A \subseteq C\}$

to infer $A \subseteq A \cup B$, and similarly $B \subseteq A \cup B$. (Actually, we need only show $\displaystyle A \subseteq \bigcap \{C \in PX: A \subseteq C\}$. We’ll do that first, and then show full equality.)

The condition we want,

$A \subseteq \{x \in X: \forall_{S \in PX} (A \subseteq S) \Rightarrow (x \in_X S)\},$

is, by the adjunction $(- \times PX) \dashv \forall_{PX}: Sub(X \times PX) \to Sub(X)$, equivalent to

$A \times PX \subseteq \{(x, S): A \subseteq S \Rightarrow (x \in_X S)\}$

which, by a $\wedge$$\Rightarrow$ adjunction, is equivalent to

$(A \times PX) \cap (X \times \{S \in PX: A \subseteq S\}) \subseteq \ \in_X \qquad (1)$

as subsets of $X \times PX$. So we just have to prove (1). At this point we recall, from our earlier analysis, that

$\{S \in PX: A \subseteq S\} = \{S \in PX: \forall_{x \in X} x \in_X A \Rightarrow x \in_X S\}$

Using the adjunction $(X \times -) \dashv \forall_X$, as in the proof of lemma 2, we have

$X \times \{S \in PX: \forall_{x \in X} x \in_X A \Rightarrow x \in_X S\}$

$\subseteq \{(x, S): x \in_X A \Rightarrow x \in_X S\} := (A \times PX) \Rightarrow \in_X,$

which shows that the left side of (1) is contained in

$(A \times PX) \cap ((A \times PX) \Rightarrow \in_X) \subseteq \ \in_X,$

where the last inclusion uses another $\wedge$$\Rightarrow$ adjunction. Thus we have established (1) and therefore also the inclusion

$\displaystyle A \subseteq \bigcap \{S \in PX: A \subseteq S\}$

Now we prove the opposite inclusion

$\displaystyle \bigcap \{S \in PX: A \subseteq S\} \subseteq A,$

that is to say

$\{x \in X: \forall_{S \in PX} A \subseteq S \Rightarrow x \in_X S\} \subseteq A \qquad (**)$

Here we just use lemma 1, applied to the particular element $\chi_A: 1 \to PX$: we see that the left side of (**) is contained in

$\{x \in X: A \subseteq \left[\chi_A\right] \Rightarrow x \in_X A\}$

which collapses to $\{x \in X: x \in_X A\} = A$, since $A = \left[\chi_A\right]$. This completes the proof. $\Box$

Theorem 2: $A \cup B$ is the least upper bound of $A, B$, i.e., if $C \subseteq X$ is a subset containing both $A \subseteq X$ and $B \subseteq X$, then $A \cup B \subseteq C$.

Proof: We are required to show that

$\{x \in X: \forall_{S \in PX} \ (A \subseteq S \wedge B \subseteq S) \Rightarrow x \in_X S\} \subseteq C.$

Again, we just apply lemma 1 to the particular element $\chi_C: 1 \to PX$: the left-hand side of the claimed inclusion is contained in

$\{x \in X: (A \subseteq C \wedge B \subseteq C) \Rightarrow x \in_X C\}$

but since $(A \subseteq C \wedge B \subseteq C)$ is true by hypothesis (is globally true as a predicate on the implicit variable $x \in X$), this last subset collapses to

$\{x \in X: t_X \Rightarrow x \in_X C\} = \{x \in X: x \in_X C\} = C$

which completes the proof. $\Box$

Theorems 1 and 2 show that for any set $X$, the external poset $Sub(X)$ admits joins. One may go on to show (just on the basis of the topos axioms) that as in the case of meets, the global external operation of taking joins is natural in $X$, so that by the Yoneda principle, it is classified by an internal join operation

$\vee: P1 \times P1 \to P1,$

namely, the map which classifies the union of the subsets

$\displaystyle \left[\pi_1\right] = P1 \times 1 \stackrel{1 \times t}{\hookrightarrow} P1 \times P1$

$\displaystyle \left[\pi_2\right] = 1 \times P1 \stackrel{t \times 1}{\hookrightarrow} P1 \times P1$

and this operation satisfies all the expected identities. In short, $P1$ carries an internal Heyting algebra structure, as does $PX \cong P1^X$ for any set $X$.

We will come back to this point later, when we show (as a consequence of strong extensionality) that $P1$ is actually an internal Boolean algebra.

### Construction of Coproducts

Next, we construct coproducts just as we do in ordinary set theory: as disjoint unions. Letting $X, Y$ be sets (objects in an ETCS category), a disjoint union of $X$ and $Y$ is a pair of monos

$i: X \hookrightarrow Z \qquad j: Y \hookrightarrow Z$

whose intersection is empty, and whose union or join in $Sub(Z)$ is all of $Z$. We will show that disjoint unions exist and are essentially unique, and that they satisfy the universal property for coproducts. We will use the notation $X + Y$ for a disjoint union.

Theorem 3: A disjoint union of $X$ and $Y$ exists.

Proof: It’s enough to embed $X, Y$ disjointly into some set $C$, since the union of the two monos in $Sub(C)$ would then be the requisite $Z$. The idea now is that if a disjoint union or coproduct $X+Y$ exists, then there’s a canonical isomorphism $P(X + Y) \cong PX \times PY$. Since the singleton map

$\sigma: X + Y \to P(X + Y) \cong PX \times PY$

is monic, one thus expects to be able to embed $X$ and $Y$ disjointly into $PX \times PY$. Since we can easily work out how all this goes in ordinary naive set theory, we just write out the formulas and hope it works out in ETCS.

In detail, define $i_X: X \to PX \times PY$ to be

$\displaystyle X \cong X \times 1 \stackrel{\sigma_X \times \chi_0}{\to} PX \times PY$

where $\sigma_X$ is the singleton mapping and $\chi_0$ classifies $0 \hookrightarrow Y$; similarly, define $i_Y: Y \to PX \times PY$ to be

$\displaystyle Y \cong 1 \times Y \stackrel{\chi_0 \times \sigma_Y}{\to} PX \times PY.$

Clearly $i_X$ and $i_Y$ are monic, so to show disjointness we just have to show that their pullback is empty. But their pullback is isomorphic to the cartesian product of the pullbacks of the diagrams

$\displaystyle X \stackrel{\sigma_X}{\to} PX \stackrel{\chi_0}{\leftarrow} 1 \qquad 1 \stackrel{\chi_0}{\to} PY \stackrel{\sigma_Y}{\leftarrow} Y$

so it would be enough to show that each (or just one) of these two pullbacks is empty, let’s say the first.

Suppose given a map $h: A \to X$ which makes the square

  A -------> 1
|          |
h |          | chi_0
V sigma_X  V
X -------> PX

commute. Using the pullback principle, the map $A \to 1 \stackrel{\chi_0}{\to} PX$ classifies

$0 \times A \hookrightarrow X \times A$

which is just the empty subset. This must be the same subset as classified by $\sigma_X h = \chi_{\delta}h$ (where $\delta: X \hookrightarrow X \times X$ is the diagonal), which by the pullback principle is

$(1_X \times h)^{-1}(\delta) \hookrightarrow X \times A.$

An elementary calculation shows this to be the equalizer of the pair of maps

$\pi_1, h\pi_2: X \times A \stackrel{\to}{\to} X$

So this equalizer $E$ is empty. But notice that $\langle h, 1 \rangle: A \to X \times A$ equalizes this pair of maps. Therefore we have a map $A \to E \cong 0$. By corollary 2 above, we infer $A \cong 0$. This applies to the case where $A$ is the pullback, so the pullback is empty, as was to be shown. $\Box$

Theorem 4: Any two disjoint unions of $X, Y$ are canonically isomorphic.

Proof: Suppose $i: X \to Z \leftarrow Y: j$ is a disjoint union. Define a map

$\phi= \langle \phi_1, \phi_2 \rangle: Z \to PX \times PY$

where $\phi_1: Z \to PX$ classifies the subset $\langle 1_X, i \rangle: X \to X \times Z$, and $\phi_2: Z \to PY$ classifies the subset $\langle 1_Y, j \rangle: Y \to Y \times Z$. Applying the pullback principle, the composite $\phi_1 i: X \to PX$ classifies

$(1_X \times i)^{-1}(\langle 1_X, i \rangle) \hookrightarrow X \times X$

which is easily seen to be the diagonal on $X$. Hence $\phi_1 i = \sigma_X$. On the other hand, $\phi_1 j: Y \to PX$ classifies the subset

$(1_X \times j)^{-1}(\langle 1_X, i \rangle) \hookrightarrow X \times Y$

which is empty because $i$ and $j$ are disjoint embeddings, so $\phi_1 j = \chi_0: Y \to PX$. Similar calculations yield

$\phi_2 i = \chi_0: X \to PY \qquad \phi_2 j = \sigma_Y: Y \to PY.$

Putting all this together, we conclude that $\phi i = i_X: X \to PX \times PY$ and $\phi j = i_Y: Y \to PX \times PY$, where $i_X$ and $i_Y$ were defined in the proof of theorem 3.

Next, we show that $\phi$ is monic. If not, then by strong extensionality, there exist distinct elements $c, d: 1 \to Z$ for which $\phi(c) = \phi(d)$; therefore, $\phi_1 c = \phi_1 d: 1 \to PX$ and $\phi_2 c = \phi_2 d: 1 \to PY$. By the pullback principle, these equations say (respectively)

$c^{-1}(i) = d^{-1}(i) \hookrightarrow 1 \qquad c^{-1}(j) = d^{-1}(j) \hookrightarrow 1$

If $c^{-1}(i) = 1$, then both $c, d: 1 \to Z$ factor through the mono $i: X \to Z$. However, since $\phi i = i_{X}$ is monic, this would imply that $\phi (c) \neq \phi (d)$, contradiction. Therefore $c^{-1}(i) = c \cap i = 0$. By similar reasoning, $c \cap j = 0$. Therefore

$i \subseteq \neg c \qquad j \subseteq \neg c$

where $\neg = (- \Rightarrow 0): Sub(Z) \to Sub(Z)$ is the negation operator. But then $i \cup j \subseteq \neg c$. And since $1: Z \hookrightarrow Z$ is the union $i \cup j$ by assumption, $\neg c$ must be the top element $\top \in Sub(Z)$, whence $c: 1 \to Z$ is the bottom element 0. This contradicts the assumption that the topos is nondegenerate. Thus we have shown that $\phi$ must be monic.

The argument above shows that $\phi: Z \hookrightarrow PX \times PY$ is an upper bound of $i_X: X \to PX \times PY$ and $i_Y: Y \to PX \times PY$ in $Sub(PX \times PY)$. It follows that the join $X + Y$ constructed in theorem 3 is contained in $\phi: Z \to PX \times PY$, and hence can be regarded as the join of $X$ and $Y$ in $Sub(Z)$. But $Z$ is their join in $Sub(Z)$ by assumption of being a disjoint union, so the containment $X + Y \subseteq Z$ must be an equality. The proof is now complete. $\Box$

Theorem 5: The inclusions $i_X: X \to X + Y$, $i_Y: Y \to X + Y$ exhibit $X + Y$ as the coproduct of $X$ and $Y$.

Proof: Let $f: X \to B$, $g: Y \to B$ be given functions. Then we have monos

$\langle 1_X, f \rangle: X \hookrightarrow X \times B \qquad \langle 1_Y, g \rangle: Y \hookrightarrow Y \times B \qquad (1)$

Now the operation $- \times B: Sub(C) \to Sub(C \times B)$ certainly preserves finite meets, and also preserves finite joins because it is left adjoint to $\forall_B: Sub(C \times B) \to Sub(C)$. Therefore this operation preserves disjoint unions; we infer that the monos

$X \times B \stackrel{i_X \times B}{\to} (X + Y) \times B \qquad Y \times B \stackrel{i_Y \times B}{\to} (X + Y) \times B \qquad (2)$

exhibit $(X + Y) \times B$ as a disjoint union of $X \times B, Y \times B$. Composing the monos of (1) and (2), we have disjoint embeddings of $X$ and $Y$ in $(X + Y) \times B$. Using theorem 4, $X + Y$ is isomorphic to the join of these embeddings; this means we have an inclusion

$\langle 1, h \rangle: X + Y \hookrightarrow (X + Y) \times B$

whose restriction to $X$ yields $\langle i_X, f \rangle$ and whose restriction to $Y$ yields $\langle i_Y, g \rangle$. Hence $h: X + Y \to B$ extends $f$ and $g$. It is the unique extension, for if there were two extensions $h, h'$, then the equalizer of $\langle 1, h \rangle$ and $\langle 1, h' \rangle$ would be an upper bound of $X, Y$ in $Sub((X + Y) \times B)$, contradicting the fact that $X + Y$ is the least upper bound. This completes the proof. $\Box$

I think that’s enough for one day. I will continue to explore the categorical structure and logic of ETCS next time.

This post is a continuation of the discussion of “the elementary theory of the category of sets” [ETCS] which we had begun last time, here and in the comments which followed. My thanks go to all who commented, for some useful feedback and thought-provoking questions.

Today I’ll describe some of the set-theoretic operations and “internal logic” of ETCS. I have a feeling that some people are going to love this, and some are going to hate it. My main worry is that it will leave some readers bewildered or exasperated, thinking that category theory has an amazing ability to make easy things difficult.

• An aside: has anyone out there seen the book Mathematics Made Difficult? It’s probably out of print by now, but I recommend checking it out if you ever run into it — it’s a kind of extended in-joke which pokes fun at category theory and abstract methods generally. Some category theorists I know take a dim view of this book; I for my part found certain passages hilarious, in some cases making me laugh out loud for five minutes straight. There are category-theory-based books and articles out there which cry out for parody!

In an attempt to nip my concerns in the bud, let me remind my readers that there are major differences between the way that standard set theories like ZFC treat membership and the way ETCS treats membership, and that differences at such a fundamental level are bound to propagate throughout the theoretical development, and impart a somewhat different character or feel between the theories. The differences may be summarized as follows:

• Membership in ZFC is a global relation between objects of the same type (sets).
• Membership in ETCS is a local relation between objects of different types (“generalized” elements or functions, and sets).

Part of what we meant by “local” is that an element per se is always considered relative to a particular set to which it belongs; strictly speaking, as per the discussion last time, the same element is never considered as belonging to two different sets. That is, in ETCS, an (ordinary) element of a set $A$ is defined to be a morphism $x: 1 \to A$; since the codomain is fixed, the same morphism cannot be an element $1 \to B$ of a different set $B$. This implies in particular that in ETCS, there is no meaningful global intersection operation on sets, which in ZFC is defined by:

$A \cap B = \{x: (x \in A) \wedge (x \in B)\}$

Instead, in ETCS, what we have is a local intersection operation on subsets $A \hookrightarrow X, B \hookrightarrow X$ of a set. But even the word “subset” requires care, because of how we are now treating membership. So let’s back up, and lay out some simple but fundamental definitions of terms as we are now using them.

Given two monomorphisms $i: A \to X, j: B \to X$, we write $i \subseteq j$ ($A \subseteq B$ if the monos are understood, or $A \subseteq_X B$ if we wish to emphasize this is local to $X$) if there is a morphism $k: A \to B$ such that $i = j k$. Since $j$ is monic, there can be at most one such morphism $k$; since $i$ is monic, such $k$ must be monic as well. We say $i, j$ define the same subset if this $k$ is an isomorphism. So: subsets of $X$ are defined to be isomorphism classes of monomorphisms into $X$. As a simple exercise, one may show that monos $i, j$ into $X$ define the same subset if and only if $i \subseteq j$ and $j \subseteq i$. The (reflexive, transitive) relation $\subseteq_X$ on monomorphisms thus induces a reflexive, transitive, antisymmetric relation, i.e., a partial order on subsets of $X$.

Taking some notational liberties, we write $A \subseteq X$ to indicate a subset of $X$ (as isomorphism class of monos). If $x: U \to X$ is a generalized element, let us say $x$ is in a subset $A \subseteq X$ if it factors (evidently uniquely) through any representative mono $i: A \to X$, i.e., if there exists $x': U \to A$ such that $x = i x'$. Now the intersection of two subsets $A \subseteq X$ and $B \subseteq X$ is defined to be the subset $A \cap B \subseteq X$ defined by the pullback of any two representative monos $i: A \to X, j: B \to X$. Following the “Yoneda principle”, it may equivalently be defined up to isomorphism by specifying its generalized elements:

$A \cap B :=_i \{x \in X: (x \mbox{ is in } A) \wedge (x \mbox{ is in } B)\}.$

Thus, intersection works essentially the same way as in ZFC, only it’s local to subsets of a given set.

While we’re at it, let’s reformulate the power set axiom in this language: it says simply that for each set $B$ there is a set $P(B)$ and a subset $\in_B \subseteq B \times P(B)$, such that for any relation $R \subseteq B \times A$, there is a unique “classifying map” $\chi_R: A \to P(B)$ whereby, under $1_B \times \chi_R: B \times A \to B \times P(B)$, we have

$R = (1_B \times \chi_R)^{-1}(\in_B).$

The equality is an equality between subsets, and the inverse image on the right is defined by a pullback. In categorical set theory notation,

$R = \{\langle b, a \rangle \in B \times A: b \in_B \chi_R(a)\}.$

Hence, there are natural bijections

$\displaystyle \frac{R \subseteq B \times A}{A \to P(B)} \qquad \frac{R \subseteq B \times A}{B \to P(A)}$

between subsets and classifying maps. The subset corresponding to $\phi: A \to P(B)$ is denoted $\left[\phi\right] \subseteq B \times A$ or $\left[\phi\right] \subseteq A \times B$, and is called the extension of $\phi$.

The set $P(1)$ plays a particularly important role; it is called the “subset classifier” because subsets $A \subseteq X$ are in natural bijection with functions $\chi: X \to P(1)$. [Cf. classifying spaces in the theory of fiber bundles.]

In ordinary set theory, the role of $P(1)$ is played by the 2-element set $\{f, t\}$. Here subsets $A \subseteq X$ are classified by their characteristic functions $\chi_A: X \to \{f, t\}$, defined by $\chi_A(x) := t$ iff $x \in A$. We thus have $A = \chi_A^{-1}(t)$; the elementhood relation $\in_1 \hookrightarrow 1 \times P(1)$ boils down to $t: 1 \to P(1)$. Something similar happens in ETCS set theory:

Lemma 1: The domain of elementhood $\in_1 \to 1 \times P(1) \cong P(1)$ is terminal.

Proof: A map $X \to \in_1$, that is, a map $\chi: X \to P(1)$ which is in $\in_1 \subseteq P(1)$, corresponds exactly to a subset $\chi^{-1}(\in_1) \subseteq X$ which contains all of $X$ (i.e., the subobject $1_X: X \subseteq X$). Since the only such subset is $1_X$, there is exactly one map $X \to \in_1$. $\Box$

Hence elementhood $\in_1 \subseteq 1 \times P(1)$ is given by an element $t: 1 \to P(1)$. The power set axiom says that a subset $A \subseteq X$ is retrieved from its classifying map $\chi_A: X \to P(1)$ as the pullback $\chi^{-1}_A(t) \subseteq X$.

Part of the power of, well, power sets is in a certain dialectic between external operations on subsets and internal operations on $P(1)$; one can do some rather amazing things with this. The intuitive (and pre-axiomatic) point is that if $C$ has finite products, equalizers, and power objects, then $P(1)$ is a representing object for the functor

$Sub: C^{op} \to Set$

which maps an object $X$ to the collection of subobjects of $X$, and which maps a morphism (“function”) $f: X \to Y$ to the “inverse image” function $f^{-1}: Sub(Y) \to Sub(X)$, that sends a subset $j: B \subseteq Y$ to the subset $f^{-1}(B) \subseteq X$ given by the pullback of the arrows $f: X \to Y$, $j: B \subseteq Y$. By the Yoneda lemma, this representability means that external natural operations on the $Sub(X)$ correspond to internal operations on the object $P(1)$. As we will see, one can play off the external and internal points of view against each other to build up a considerable amount of logical structure, enough for just about any mathematical purpose.

• Remark: A category satisfying just the first three axioms of ETCS, namely existence of finite products, equalizers, and power objects, is called an (elementary) topos. Most or perhaps all of this post will use just those axioms, so we are really doing some elementary topos theory. As I was just saying, we can build up a tremendous amount of logic internally within a topos, but there’s a catch: this logic will be in general intuitionistic. One gets classical logic (including law of the excluded middle) if one assumes strong extensionality [where we get the definition of a well-pointed topos]. Topos theory has a somewhat fearsome reputation, unfortunately; I’m hoping these notes will help alleviate some of the sting.

To continue this train of thought: by the Yoneda lemma, the representing isomorphism

$\displaystyle \theta: \hom(-, P(1)) \stackrel{\sim}{\to} Sub(-)$

is determined by a universal element $\theta_{P(1)}(1_{P(1)})$, i.e., a subset of $P(1)$, namely the mono $t: 1 \to P(1)$. In that sense, $t: 1 \to P(1)$ plays the role of a universal subset. The Yoneda lemma implies that external natural operations on general posets $Sub(X)$ are completely determined by how they work on the universal subset.

### Internal Meets

To illustrate these ideas, let us consider intersection. Externally, the intersection operation is a natural transformation

$\cap_X: Sub(X) \times Sub(X) \to Sub(X).$

This corresponds to a natural transformation

$\hom(X, P(1)) \times \hom(X, P(1)) \to \hom(X, P(1))$

which (by Yoneda) is given by a function $\wedge: P(1) \times P(1) \to P(1)$. Working through the details, this function is obtained by putting $X = P(1) \times P(1)$ and chasing

$\langle \pi_1, \pi_2\rangle \in \hom(P(1) \times P(1), P(1)) \times \hom(P(1) \times P(1), P(1))$

through the composite

$\displaystyle \hom(X, P(1)) \times \hom(X, P(1))$

$\displaystyle \stackrel{\sim}{\to} Sub(X) \times Sub(X) \stackrel{\cap}{\to} Sub(X) \stackrel{\sim}{\to} \hom(X, P(1)).$

Let’s analyze this bit by bit. The subset $\left[\pi_1\right] = \pi_{1}^{-1}(t) \subseteq P(1) \times P(1)$ is given by

$t \times id: 1 \times P(1) \to P(1) \times P(1),$

and the subset $\left[\pi_2\right] = \pi_{2}^{-1}(t) \subseteq P(1) \times P(1)$ is given by

$id \times t: P(1) \times 1 \to P(1) \times P(1).$

Hence $\left[\pi_1\right] \cap \left[\pi_2\right] \subseteq P(1) \times P(1)$ is given by the pullback of the functions $t \times id$ and $id \times t$, which is just

$t \times t: 1 \times 1 \to P(1) \times P(1).$

The map $\wedge: P(1) \times P(1) \to P(1)$ is thus defined to be the classifying map of $t \times t: 1 \times 1 \subseteq P(1) \times P(1)$.

To go from the internal meet $\wedge: P(1) \times P(1) \to P(1)$ back to the external intersection operation, let $A \subseteq X, B \subseteq X$ be two subsets, with classifying maps $\chi_A, \chi_B: X \to P(1)$. By the definition of $\wedge$, we have that for all generalized elements $x \in X$

$\chi_A(x) \wedge \chi_B(x) = t$ if and only if $\langle \chi_A(x), \chi_B(x) \rangle = \langle t, t \rangle$

(where the equality signs are interpreted with the help of equalizers). This holds true iff $x$ is in the subset $A \subseteq X$ and is in the subset $B \subseteq X$, i.e., if and only if $x$ is in the subset $A \cap B \subseteq X$. Thus $\chi_A \wedge \chi_B$ is indeed the classifying map of $A \cap B \subseteq X$. In other words, $\chi_{A \cap B} = \chi_A \wedge \chi_B$.

A by-product of the interplay between the internal and external is that the internal intersection operator

$\wedge: P(1) \times P(1) \to P(1)$

is the meet operator of an internal meet-semilattice structure on $P(1)$: it is commutative, associative, and idempotent (because that is true of external intersection). The identity element for $\wedge$ is the element $t: 1 \to P(1)$. In particular, $P(1)$ carries an internal poset structure: given generalized elements $u, v: A \to P(1)$, we may define

$u \leq v$ if and only if $u = u \wedge v$

and this defines a reflexive, symmetric, antisymmetric relation $\left[\leq\right] \subseteq P(1) \times P(1)$:

$\left[\leq\right] :=_i \{\langle u, v \rangle \in P(1) \times P(1): u = u \wedge v\},$

equivalently described as the equalizer

$\left[\leq\right] \to P(1) \times P(1) \stackrel{\to}{\to} P(1)$

of the maps $\pi_1: P(1) \times P(1) \to P(1)$ and $\wedge: P(1) \times P(1) \to P(1)$. We have that $u \leq v$ if and only if $\left[u\right] \subseteq \left[v\right]$.

### Internal Implication

Here we begin to see some of the amazing power of the interplay between internal and external logical operations. We will prove that $P(1)$ carries an internal Heyting algebra structure (ignoring joins for the time being).

Let’s recall the notion of Heyting algebra in ordinary naive set-theoretic terms: it’s a lattice $P$ that has a material implication operator $\Rightarrow$ such that, for all $x, y, z \in P$,

$x \wedge y \leq z$ if and only if $x \leq y \Rightarrow z.$

Now: by the universal property of $P(1)$, a putative implication operation $\Rightarrow: P(1) \times P(1) \to P(1)$ is uniquely determined as the classifying map of its inverse image $(\Rightarrow)^{-1}(t) \subseteq P(1) \times P(1)$, whose collection of generalized elements is

$\{\langle u, v \rangle \in P(1) \times P(1): (u \Rightarrow v) = t\}$

Given $\langle u, v \rangle: A \to P(1) \times P(1)$, the equality here is equivalent to

$t \leq u \Rightarrow v$

(because $t: 1 \to P(1)$ is maximal), which in turn is equivalent to

$t \wedge u = u \leq v$

This means we should define $\Rightarrow: P(1) \times P(1) \to P(1)$ to be the classifying map of the subset

$\left[\leq\right] \subseteq P(1) \times P(1).$

Theorem 1: $P(1)$ admits internal implication.

Proof: We must check that for any three generalized elements $u, v, w: A \to P(1)$, we have

$w \leq u \Rightarrow v$ if and only if $w \wedge u \leq v.$

Passing to the external picture, let $\left[u\right], \left[v\right], \left[w\right]$ be the corresponding subsets of $A$. Now: according to how we defined $\Rightarrow,$ a generalized element $e \in A$ is in $\left[u \Rightarrow v\right]$ if and only if $u(e) \leq v(e)$. This applies in particular to any monomorphism $e: \left[w\right] \to A$ that represents the subset $\left[w\right] \subseteq A$.

Lemma 2: The composite

$\displaystyle u(e) = (\left[w\right] \stackrel{e}{\to} A \stackrel{u}{\to} P(1))$

is the classifying map of the subset $\left[w\right] \cap \left[u\right] \subseteq \left[w\right]$.

Proof: As subsets of $\left[w\right]$, $(u e)^{-1}(t) = e^{-1} u^{-1}(t) = e^{-1}(\left[u\right]) = \left[w\right] \cap \left[u\right]$ where the last equation holds because both sides are the subsets defined as the pullback of two representative monos $e: \left[w\right] \to A$, $i: \left[u\right] \to A$. $\Box$

Continuing the proof of theorem 1, we see by lemma 2 that the condition $u(e) \leq v(e)$ corresponds externally to the condition

$\left[w\right] \cap \left[u\right] \subseteq \left[w\right] \cap \left[v\right]$

and this condition is equivalent to $\left[w\right] \cap \left[u\right] \subseteq \left[v\right]$. Passing back to the internal picture, this is equivalent to $w \wedge u \leq v$, and the proof of theorem 1 is complete. $\Box$

### Cartesian Closed Structure

Next we address a comment made by “James”, that a category satisfying the ETCS axioms is cartesian closed. As everything else in this article, this uses only the fact that such a category is a topos: has finite products, equalizers, and “power sets”.

Proposition 1: If $A, B$ are “sets”, then $P(A \times B)$ represents an exponential $P(B)^A.$

Proof: By the power set axiom, there is a bijection between maps into the power set and relations:

$\displaystyle \frac{\phi: X \to P(A \times B)}{R \subseteq X \times (A \times B)}$

which is natural in $X$. By the same token, there is a natural bijection

$\displaystyle \frac{R \subseteq (X \times A) \times B}{\phi': X \times A \to P(B)}.$

Putting these together, we have a natural isomorphism

$\hom(-, P(A \times B)) \cong \hom(- \times A, P(B))$

and this representability means precisely that $P(A \times B)$ plays the role of an exponential $P(B)^A$. $\Box$

Corollary 1: $P(A) \cong P(1)^A$. $\Box$

The universal element of this representation is an evaluation map $A \times P(A) \to P(1)$, which is just the classifying map of the subset $\in_A \subseteq A \times P(A)$.

Thus, $P(B)^A \cong P(A \times B)$ represents the set of all functions $\phi: A \to P(B)$ (that is, relations from $A$ to $B$). This is all we need to continue the discussion of internal logic in this post, but let’s also sketch how we get full cartesian closure. [Warning: for those who are not comfortable with categorical reasoning, this sketch could be rough going in places.]

As per our discussion, we want to internalize the set of such relations which are graphs of functions, i.e., maps $\phi$ where each $\phi(a) \subseteq B$ is a singleton, in other words which factor as

$\displaystyle A \to B \stackrel{\sigma}{\to} P(B)$

where $\sigma: B \to P(B)$ is the singleton mapping:

$b \mapsto \{b\} = \{c \in B: b = c\}.$

We see from this set-theoretic description that $\sigma: B \to P(B)$ classifies the equality relation

$\{\langle b, c\rangle \in B \times B: b = c\} \subseteq B \times B$

which we can think of as either the equalizer of the pair of maps $\pi_1, \pi_2: B \times B \to B$ or, what is the same, the diagonal map $\delta_B = \langle 1_B, 1_B \rangle: B \to B \times B$.

Thus, we put $\sigma = \chi_{\delta}: B \to P(B)$, and it is not too hard to show that the singleton mapping $\sigma$ is a monomorphism. As usual, we get this monomorphism as the pullback $\chi_{\sigma}^{-1}(t)$ of $t: 1 \to P(1)$ along its classifying map $\chi_{\sigma}: P(B) \to P(1)$.

Now: a right adjoint such as $(-)^A$ preserves all limits, and in particular pullbacks, so we ought then to have a pullback

       B^A ---------------> 1^A
|                    |
sigma^A |                    | t^A
V                    V
P(B)^A -------------> P(1)^A
(chi_sigma)^A

Of course, we don’t even have $B^A$ yet, but this should give us an idea: define $\sigma^A$, and in particular its domain $B^A$, by taking the pullback of the right-hand map along the bottom map. In case there is doubt, the map on the bottom is defined Yoneda-wise, applying the isomorphism

$\hom(P(B)^A \times A, P(1)) \cong \hom(P(B)^A, P(1)^A)$

to the element in the hom-set (on the left) given by the composite

$\displaystyle P(B)^A \times A \stackrel{ev}{\to} P(B) \stackrel{\chi_\sigma}{\to} P(1).$

The map on the right of the pullback is defined similarly. That this recipe really gives a construction of $B^A$ will be left as an exercise for the reader.

### Universal Quantification

As further evidence of the power of the internal-external dialectic, we show how to internalize universal quantification.

As we are dealing here now with predicate logic, let’s begin by defining some terms as to be used in ETCS and topos theory:

• An ordinary predicate of type $A$ is a function $\phi: A \to P(1)$. Alternatively, it is an ordinary element $\phi': 1 \to P(1)^A \cong P(A)$. It corresponds (naturally and bijectively) to a subset $\left[\phi\right]: S \subseteq A$.
• A generalized predicate of type $A$ is a function $\phi': X \to P(A) \cong P(1)^A$. It may be identified with (corresponds naturally and bijectively to) a function $\phi: X \times A \to P(1)$, or to a subset $\left[\phi\right]: S \subseteq X \times A$.

We are trying to define an operator $\forall_A$ which will take a predicate of the form $\phi: X \times A \to P(1)$ [conventionally written $\phi(x, a)$] to a predicate $\forall_A \phi: X \to P(1)$ [conventionally written $\forall_{a \in A} \phi(x, a)$]. Externally, this corresponds to a natural operation which takes subsets of $X \times A$ to subsets of $X$. Internally, it corresponds to an operation of the form

$\forall_A: P(A) \cong P(1)^A \to P(1).$

This function is determined by the subset $(\forall_A)^{-1}(t) \subseteq P(1)^A$, defined elementwise by

$\{\phi \in P(1)^A: \forall_A \phi = t\}.$

Now, in ordinary logic, $\forall_{a \in A} \phi(a)$ is true if and only if $\phi(a)$ is true for all $a \in A$, or, in slightly different words, if $\phi: A \to P(1)$ is constantly true over all of $A$:

$\displaystyle \phi = (A \stackrel{!}{\to} 1 \stackrel{t}{\to} P(1)).$

The expression on the right (global truth over $A$) corresponds to a function $t_A: 1 \to P(1)^A$, indeed a monomorphism since any function with domain $1$ is monic. Thus we are led to define the desired quantification operator $\forall_A: P(1)^A \to P(1)$ as the classifying map of $t_A: 1 \subseteq P(1)^A$.

Let’s check how this works externally. Let $\phi: X \to P(1)^A$ be a generalized predicate of type $A$. Then according to how $\forall_A$ has just been defined, $\forall_A \phi: X \to P(1)$ classifies the subset

$\displaystyle \{x \in X: \phi(x, -) = t_A: A \to P(1))\} \subseteq X$

There is an interesting adjoint relationship between universal quantification and substitution (aka “pulling back”). By “substitution”, we mean that given any predicate $\psi: X \to P(1)$ on $X$, we can always pull back to a predicate on $X \times A$ (substituting in a dummy variable $a$ of type $A$, forming e.g. $\psi(x) \wedge \left[a=a\right]$) by composing with the projection $\pi: X \times A \to X$. In terms of subsets, substitution along $A$ is the natural external operation

$(\left[\psi\right] \subseteq X) \mapsto (\left[\psi\right]\times A \subseteq X \times A).$

Then, for any predicate $\phi: X \times A \to P(1)$, we have the adjoint relationship

$\left[\psi\right] \times A \subseteq \phi$ if and only if $\left[\psi\right] \subseteq \forall_A \phi$

so that substitution along $A$ is left adjoint to universal quantification along $A$. This is easy to check; I’ll leave that to the reader.

### Internal Intersection Operators

Now we put all of the above together, to define an internal intersection operator

$\bigcap: PPX \to PX$

which intuitively takes an element $1 \to PPX$ (a family $F$ of subsets of $X$) to its intersection $1 \to PX$, as a subset $\bigcap F \subseteq X$.

Let’s first write out a logical formula which expresses intersection:

$x \in \bigcap F \ \ \mbox{if and only if} \ \ \forall_{S \in PX} (S \in F) \Rightarrow (x \in S)\}.$

We have all the ingredients to deal with the logical formula on the right: we have an implication operator $\Rightarrow$ as part of the internal Heyting algebra structure on $P(1)$, and we have the quantification operator $\forall_{PX}$. The atomic expressions $(S \in F)$ and $(x \in S)$ refer to internal elementhood: $(x \in S)$ means $\langle x, S\rangle \in X \times PX$ is in $\ \in_{X}\ \subseteq X \times PX$, and $(S \in F)$ means $\langle S, F\rangle \in PX \times PPX$ is in $\ \in_{PX}\ \subseteq PX \times PPX$.

There is a slight catch, in that the predicates “$(S \in_{PX} F)$” and “$(x \in_X S)$” (as generalized predicates over $PX$, where $S$ lives) are taken over different domains. The first is of the form $\phi_1: PPX \to P(1)^{PX}$, and the second is of the form $\phi_2: X \to P(1)^{PX}$. No matter: we just substitute in some dummy variables. That is, we just pull these maps back to a common domain $PPX \times X$, forming the composites

$\displaystyle \psi_1 = (PPX \times X \stackrel{\pi_1}{\to} PPX \stackrel{\phi_1}{\to} P(1)^{PX})$

and

$\displaystyle \psi_2 = (PPX \times X \stackrel{\pi_2}{\to} X \stackrel{\phi_2}{\to} P(1)^{PX}).$

Putting all this together, we form the composite

$\displaystyle PPX \times X \stackrel{\langle \psi_1, \psi_2\rangle}{\to} P(1)^{PX} \times P(1)^{PX}$

$\displaystyle \cong (P(1) \times P(1))^{PX} \stackrel{(\Rightarrow)^{PX}}{\to} P(1)^{PX} \stackrel{\forall_{PX}}{\to} P(1)$

This composite directly expresses the definition of the internal predicate $(x \in \bigcap F)$ given above. By cartesian closure, this map $PPX \times X \to P(1)$ induces the desired internal intersection operator, $\bigcap: PPX \to PX$.

This construction provides an important bridge to getting the rest of the internal logic of ETCS. Since we can can construct the intersection of arbitrary definable families of subsets, the power sets $PX$ are internal inf-lattices. But inf-lattices are sup-lattices as well; on this basis we will be able to construct the colimits (e.g., finite sums, coequalizers) that we need. Similarly, the intersection operators easily allow us to construct image factorizations: any function $f: X \to Y$ can be factored (in an essentially unique way) as an epi or surjection $X \to I$ to the image, followed by a mono or injection $I \to Y$. The trick is to define the image as the smallest subset of $Y$ through which $f$ factors, by taking the intersection of all such subsets. Image factorization leads in turn to the construction of existential quantification.

As remarked above, the internal logic of a topos is generally intuitionistic (the law of excluded middle is not satisfied). But, if we add in the axiom of strong extensionality of ETCS, then we’re back to ordinary classical logic, where the law of excluded middle is satisfied, and where we just have the two truth values “true” and “false”. This means we will be able to reason in ETCS set theory just as we do in ordinary mathematics, taking just a bit of care with how we treat membership. The foregoing discussion gives indication that logical operations in categorical set theory work in ways familiar from naive set theory, and that basic set-theoretic constructions like intersection are well-grounded in ETCS.

• 329,221 hits

Advertisements