Preimage of generated $\sigma$-algebra

For some collection of sets $A$, let $\sigma(A)$ denote the $\sigma$-algebra generated by $A$.

Let $C$ be some collection of subsets of a set $Y$, and let $f$ be a function from some set $X$ to $Y$. I want to prove:

$$f^{-1}(\sigma(C))=\sigma(f^{-1}(C))$$

I could prove that $$\sigma(f^{-1}(C)) \subset f^{-1}(\sigma(C))$$ since complements and unions are 'preserved' by function inverse. But how do I go the other way?

EDIT: One way to go the other way would be to argue that any set in $\sigma(C)$ must be built by repeatedly applying the complement, union and intersection operations to elements of $C$ and all these operations are preserved when taking the inverse. The problem I am facing with the approach is formalizing the word "repeatedly".

[not-homework]

• If you want to formalize the word "repeatedly" you need to induct on ordinals larger than N, but I think this is unnecessary. – Qiaochu Yuan Oct 26 '10 at 10:20
• @Qiaochu. I could not find another way. Could you please give a hint or suggest a reference? – Jyotirmoy Bhattacharya Oct 26 '10 at 11:09

Yes, we can use transfinite induction to prove this (formalizing the word "repeatedly"). That would be the bottom-up approach. There is also a top-down approach, using the characterization of $\sigma(C)$ as the smallest $\sigma$-algebra containing $C$.

A key fact here is the the preimage operation commutes with all the set algebra operations: if $f \colon X \to Y$ then

• $f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$
• $f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)$
• $f^{-1}(A - B) = f^{-1}(A) - f^{-1}(B)$. In particular $f^{-1}(Y - A) = X - f^{-1}(A)$.

and so forth. So $f^{-1}\colon P(Y) \to P(X)$ is a lattice homomorphism on the powerset lattices, to use that terminology. More importantly for us, the preimage operation even commutes with infinite unions and intersections.

To show that $f^{−1}(\sigma(C)) \subseteq \sigma(f^{−1}(C))$, you could follow this strategy:

• Show that $f^{-1}(C) \in \sigma(f^{-1}(C))$
• Show that if $f^{-1}(A_i) \in \sigma(f^{-1}(C))$ for $i \in \omega$ then $f^{-1}(\bigcup A_i) \in \sigma(f^{-1}(C))$
• Show that if $f^{-1}(A) \in \sigma(f^{-1}(C))$ then $f^{-1}(Y - A) \in \sigma(f^{-1}(C))$

The point here is that, if we let $D$ be the collection of sets $A$ such that $f^{-1}(A) \in \sigma(f^{-1}(C))$, then $D$ is itself a $\sigma$ algebra containing $C$, which means $\sigma(C) \subseteq D$. But by the definition of $D$ this means $f^{-1}(\sigma(C)) \subseteq \sigma(f^{-1}(C))$.

None of the three bullets will require taking forward images under $f$. For example, for the third one, let $A$ be as stated. This means $f^{-1}(A)$ is in $\sigma(f^{-1}(C))$, which means that $X - f^{-1}(A)$ is also in $\sigma(f^{-1}(C))$. But $f^{-1}(Y - A)$ is exactly $X - f^{-1}(A)$, so we see that $f^{-1}(Y - A)$ is indeed in $\sigma(f^{-1}(C))$.

The underlying point here is that the entire proof is algebraic and that a more general theorem is true: you can replace $f^{-1}$ with any other homomorphism of the powerset lattices that preserves countable unions.

• Thanks. But wouldn't I still need some kind of induction to go from your bullets to showing that for any $A \in \sigma(C)$, $f^{-1}(A) \in \sigma(f^{-1}(C))$? – Jyotirmoy Bhattacharya Oct 26 '10 at 13:06
• No, because if every $A \in \sigma(C)$ is in $D$ then the definition of $D$ tells us that every element $A \in \sigma(C)$ satisfies $f^{-1}(A) \in \sigma(f^{-1}(C))$. So it is enough just to show that $D$ is a $\sigma$ algebra that contains $C$, which in turn implies $D$ contains every element of $\sigma(C)$. The three bullets are what we need to verify for that sufficient condition. – Carl Mummert Oct 26 '10 at 13:13
• The general trick is that if you want to show something (call it $P$) holds for all sets $A$ in a $\sigma$-algebra $\sigma(\mathcal{C})$ generated by a known collection, the obvious approach "let $A \in \sigma(\mathcal{C})$, show $A$ satisfies $P$" is often not helpful, because you don't know what $A$ might look like. Instead, try considering the collection $\mathcal{B}$ of all sets satisfying $P$. If you can show that $\mathcal{B}$ is a $\sigma$-algebra containing $\mathcal{C}$, you will be done. – Nate Eldredge Oct 26 '10 at 15:10
• And I'll add that the monotone class and $\pi$-$\lambda$ theorems are similarly useful: they give you slightly different sets of axioms to verify, which might be easier. – Nate Eldredge Oct 26 '10 at 15:11
• Is not the set $D$ just $f(\sigma(f^{-1}(C)))$? – Hashimoto Jul 21 '18 at 21:31

Edit: The original answer that was here is wrong; Carl Mummert's answer contains the correct way to do what I was trying to do. So instead here is the solution by transfinite induction.

Define a sequence of functions $\sigma_i$ where $i$ is an ordinal as follows. For any subset $C$ of the base set $E$ we take $\sigma_0(C) = C$. If $i$ is a successor ordinal, take $\sigma_i(C)$ to be the set of all countable unions or complements of elements of $\sigma_{i-1}(C)$; otherwise $i$ is a limit ordinal and we take $\sigma_i(C) = \bigcup_{j < i} \sigma_j(C)$. For example, $\sigma_{\omega}(C)$ is the set of all sets that can be obtained from $C$ by performing countable union or complement countably many times.

We would like to say that $\sigma(C)$ is the union of the $\sigma_i(C)$ over all ordinals $i$, but the ordinals don't form a set so we can't actually do this. What I believe is true is that we only need to take ordinals of cardinality at most the cardinality of the powerset of the underlying set.

If that's true, then the proof is as follows. It's enough to show that $f^{-1}(\sigma_i(C)) = \sigma_i(f^{-1}(C))$ for all $i$. This is obvious for $i = 0$. If it's true for all ordinals $j < i$, then it's true for $i$ by the obvious argument. And now we are done by the principle of transfinite induction.

Let me remark that, on the one hand, this is more complicated than Carl Mummert's proof because it requires knowledge of ordinals. On the other hand, getting into the nitty-gritty like this really shows how complicated $\sigma$-algebras can be.

• @Jyotirmoy Bhattacharya: my original answer was wrong, so I've given the proof by transfinite induction instead. – Qiaochu Yuan Oct 26 '10 at 14:18
• Thanks. I will need to read some more to understand this fully. Problem 2.22 of Billingsley's Probability and Measure says that going upto the first uncountable ordinal is enough, but right now that's all Greek to me. – Jyotirmoy Bhattacharya Oct 26 '10 at 14:29
• Yes, it is enough to go to the first uncountable ordinal. The general fact is that if you have a collection of a countable number of functions each of which takes a countable number of arguments, and use transfinite induction to make a set closed under all these functions, you will achieve closure no later than the first uncountable ordinal. – Carl Mummert Oct 26 '10 at 14:39
• Most results in this area can be proved either top-down or bottom-up. The main benefit of the top-down proofs is that they are often shorter and simpler once you see how to do them, because like you say they don't require any knowledge of ordinals. Similarly, many results in analysis can be proved by compactness or by transfinite induction, but the compactness proofs are often much shorter and more elegant. – Carl Mummert Oct 26 '10 at 14:43

This is just a summary of Carl Mummert's answer in a slightly more systematic way.

We are given $f:X \rightarrow Y$. Also, I will use lower-case letters (e.g., $x$) for members of $X$ or $Y$, upper-case letters (e.g., $A$) for subsets of $X$ or $Y$, and script font (e.g., $\mathscr{A}$) for sets of subsets of $X$ or $Y$ .

1. Let's revisit the following definitions:

• $f(A) = \{ f(x) | x\in A\} \text{ for } A \subset X$.

• $f^{-1}(B) = \{ x | f(x) = y \text{ and } y\in B\} \text{ for } B \subset Y$.

• $f(\mathscr A) = \{ f(A) | A\in \mathscr{A} \}$, for $\mathscr A$ a class of subsets of $X$.

• $f^{-1}(\mathscr B) = \{ f^{-1}(B) | B \in \mathscr{B} \}$, for $\mathscr B$ a class of subsets of $Y$.

2. And let's also introduce a new definition:

• $f^{*}(\mathscr A) = \{ f(A) | A \in \mathscr{A} \text{ and } f^{-1}(f(A)) \in \mathscr A \}$, for $\mathscr A$ a class of subsets of $X$. In general, $f^{*}(\mathscr A) \subset f(\mathscr A)$, but the inverse can be wrong.
3. We need to prove the following statements:

• (3.1) If $\mathscr A$ is a $\sigma$-algebra, then so is $f^{*}(\mathscr A)$.
• (3.2) If $\mathscr B$ is a $\sigma$-algebra, then so is $f^{-1}(\mathscr B)$.
• (3.3) $f^{*}(f^{-1}(\mathscr B)) = \mathscr B.$
• (3.4) $f^{-1}(f^{*}(\mathscr A)) \subset \mathscr A.$

Now to prove that $f^{-1}(\sigma(\mathscr B)) \subset \sigma(f^{-1}(\mathscr B))$, we can write:

\begin{aligned} &\mathscr A \subset \mathscr A \Rightarrow \\ \text{from (3.3): } &\mathscr A \subset f^{*}(f^{-1}(\mathscr A)) \Rightarrow \\ \text{since } \mathscr (.) \subset \sigma((.))\text{: } &\mathscr A \subset f^{*}(\sigma(f^{-1}(\mathscr A))) \Rightarrow \\ \text{from (3.1): }&\sigma(\mathscr A) \subset f^{*}(\sigma(f^{-1}(\mathscr A))) \Rightarrow \\ \text{from (3.4): }&f^{-1} (\sigma(\mathscr A)) \subset f^{-1}(f^{*}(\sigma(f^{-1}(\mathscr A)))) \subset \sigma(f^{-1}(\mathscr A)). \quad \blacksquare \end{aligned}

Looks like a homework.

I didn't have time to check the details (I am at work and my boss is watching), however, it seems to me that the following approach should work:

Step 1: prove that $f^{-1}(\sigma(C))$ is a $\sigma$-algebra.

Step 2: you should be able to conclude, if you understand what $\sigma(f^{-1}(C))$ means.

EDIT:

Not sure if this new approach is working, but I would:

1/ consider $f(\sigma(f^{-1}(C)))$ and try to prove it is a $\sigma$-algebra.

2/ when 1/ is done, prove that it is a $\sigma$-algebra that contains $C$.

3/ If 1/ and 2/ are ok, then that means we have $\sigma(C) \subset f(\sigma(f^{-1}(C)))$ and you can then conclude.

It seems to me that 1 is true, I don't have time to do the details however.

EDIT 2:

ok, me second approach doesn't seem to be working either. I decided to do a little bit of research, and you can actually find the proof online. Here it is:

Let $S =${ $B \in \mathcal{P}(Y); f^{-1}(B) \in \sigma(f^{-1}(C))$}.

Then $S$ is a $\sigma$-algebra that contains $C$. Therefore $\sigma(C) \subset S$ and $f^{-1}(\sigma(C)) \subset f^{-1}(S)$. But, by definition, $f^{-1}(S) \subset \sigma(f^{-1}(C))$.

Sorry for my "hints", they were not really useful.

• This is not homework as I'm not a student. Your steps let me conclude the inclusion I have mentioned in my question, but I'd appreciate any hints for proving the opposite inclusion. – Jyotirmoy Bhattacharya Oct 26 '10 at 8:01
• 1/ will not work because in general $f(A^c) \neq [f(A)]^c$. – Jyotirmoy Bhattacharya Oct 26 '10 at 9:04
• @Jyotirmoy: sorry for my wrong answer. I edited it, tell me if this new approach works. – Djaian Oct 26 '10 at 9:05