Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am seeking a deeper understanding of the representation of set-based objects in terms of Boolean algebras.

Let $\wp(A)$ be the set of subsets of a set $A$. A relation $R \subseteq A \times B$ generates two operators $pre: \wp(B) \to \wp(A)$ and $post: \wp(A) \to \wp(B)$ where $pre$ maps a set $X \subseteq A$ to its preimage with respect to $R$ and $post$ maps $X$ to its image.

In the standard Stone duality between the category of sets and Boolean algebras, a function is represented using the preimage operator. The preimage operator generated by a function turns out to be a Boolean algebra homomorphism but the image operator may not be a homomorphism. I see this as one reason to choose the preimage to represent a function. My first question is: Are there other reasons to choose the preimage representation? I feel like there should be something deeper going on.

If we leave the setting of functions, the preimage operator generated by a relation isn't necessarily a Boolean algebra homomorphism. So, in the representation of a system of relations over a set by a Boolean algebra with operators (in the sense of Jonsson and Tarski) I see no specific motivation for using the preimage, as opposed to image operator. I see why we want to be consistent in convention, and also use the preimage because of its connection to the semantics of modal logic. However, this appears to be an aesthetic choice. My second question is: Is there a specific reason to choose the preimage, rather than image operator, when representing relations as Boolean algebras with operators?

share|improve this question
One thing to realize is that the power set functor is a functor from sets to the opposite category of sets. –  Spice the Bird Jan 9 '13 at 23:35
Also the preimage operator preserves union and intersection whereas the image operator does not. –  Spice the Bird Jan 9 '13 at 23:41
That's what I meant by preimage being a homomorphism while image may not be one. –  Vijay D Jan 10 '13 at 0:12
add comment

3 Answers

up vote 3 down vote accepted

You should think of the preimage as taking the pullback of $\mathbb{F}_2$-valued functions. For any topological space $X$, the space of continuous functions $X \to \mathbb{F}_2$ may be identified with the Boolean algebra / ring of clopen subsets of $X$, the pullback of such a function is another such function, and taking pullbacks corresponds to taking preimages (thinking of subsets via their indicator functions). The natural thing to do with functions is pull them back, both in logic and in geometry. Moreover, pulling back functions is a ring homomorphism, and even in contexts where pushing forward functions can also be done it usually does not preserve multiplication.

Edit: As for relations instead of sets, taking the transpose of a relation gives an equivalence of categories $\text{Rel} \cong \text{Rel}^{op}$ ($\text{Rel}$ is a dagger category) which exchanges inverse image and image, so in that sense there isn't a strong reason to prefer one over the other for relations.

share|improve this answer
I see the homomorphism reason. I was wondering if there are other reasons. Also, the choice of preimage for functions does not seem to justify that choice for relations. –  Vijay D Jan 10 '13 at 0:15
There is no natural choice for relations. The category of sets and relations is self-dual. –  Qiaochu Yuan Jan 10 '13 at 0:24
That comment answers it. It's the insight I was looking for. Thanks! Could you add that to your answer, as answering my second question? –  Vijay D Jan 10 '13 at 3:02
add comment

For a function $f:X\to Y$, the operation "pre-image along $f$" from $\mathcal P(Y)$ to $\mathcal P(X)$ has adjoints on both sides. [I'm viewing the power sets as partially ordered by $\subseteq$ and then viewing these partially ordered sets as categories, so that "adjoint" makes sense.] The left adjoint is the familiar image operator. The right adjoint is its (not so familiar) dual, $A\mapsto Y-f(X-A)$. So from this point of view, "image" has the same level of naturality as its dual, while "pre-image" is "better".

Concerning the claim of equal naturality, note that the left adjoint sends $A$ to $\{y\in Y:(\exists x\text{ with }f(x)=y)\ x\in A\}$ while the right adjoint sends $A$ to $\{y\in Y:(\forall x\text{ with }f(x)=y)\ x\in A\}$. So they correspond to the two familiar (mutually dual) quantifiers.

share|improve this answer
add comment

Having a subset of a set is "the same" as having a function from that set into $\{0,1\}$ (namely, the function which is $1$ on the subset and $0$ on its complement). If I have a function $f: X \to Y$ I can compose it with functions from $Y$ to $\{0,1\}$ and thereby turn subsets of $Y$ into subsets of $X$. I guess that's one explanation for why pre is natural in a way that post is not.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.