Exercise 1, § 4

This solution was written by nemotron-3-ultra-free and judged by a machine. It is not Bourbaki's and it has not been checked by a person.

(a) We prove that (a) implies (b). Assume that $G$ is a functional graph. Let $X$ and $Y$ be arbitrary sets. We must show $G^{-1}(X \cap Y) = G^{-1}(X) \cap G^{-1}(Y)$. The inclusion $G^{-1}(X \cap Y) \subset G^{-1}(X) \cap G^{-1}(Y)$ holds for every graph: if $x \in G^{-1}(X \cap Y)$, there exists $y \in X \cap Y$ with $(x,y) \in G$; then $y \in X$ and $y \in Y$, so $x \in G^{-1}(X)$ and $x \in G^{-1}(Y)$. For the reverse inclusion, let $x \in G^{-1}(X) \cap G^{-1}(Y)$. Then there exist $y_1 \in X$ and $y_2 \in Y$ such that $(x,y_1) \in G$ and $(x,y_2) \in G$. Because $G$ is functional, $y_1 = y_2$. Denote this common value by $y$. Then $y \in X$ and $y \in Y$, hence $y \in X \cap Y$. Thus $(x,y) \in G$ with $y \in X \cap Y$, which means $x \in G^{-1}(X \cap Y)$. Therefore $G^{-1}(X) \cap G^{-1}(Y) \subset G^{-1}(X \cap Y)$. The two inclusions give the required equality.

(b) We prove that (b) implies (c). Assume that for any two sets $X, Y$ we have $G^{-1}(X \cap Y) = G^{-1}(X) \cap G^{-1}(Y)$. Let $X, Y$ be sets such that $X \cap Y = \varnothing$. Then $G^{-1}(X \cap Y) = G^{-1}(\varnothing)$. By definition of the inverse image, $G^{-1}(\varnothing) = \varnothing$ (no element can be related to an element of the empty set). Using the assumed equality we obtain $\varnothing = G^{-1}(X) \cap G^{-1}(Y)$. Hence $X \cap Y = \varnothing$ implies $G^{-1}(X) \cap G^{-1}(Y) = \varnothing$, which is (c).

(c) We prove that (c) implies (a). Assume that whenever $X \cap Y = \varnothing$ we have $G^{-1}(X) \cap G^{-1}(Y) = \varnothing$. We show that $G$ is functional. Suppose, for a contradiction, that $G$ is not functional. Then there exist $x, y, y'$ with $y \neq y'$ such that $(x,y) \in G$ and $(x,y') \in G$. Define $X = \{y\}$ and $Y = \{y'\}$. Since $y \neq y'$, we have $X \cap Y = \varnothing$. By hypothesis, $G^{-1}(X) \cap G^{-1}(Y) = \varnothing$. But $x \in G^{-1}(X)$ because $(x,y) \in G$ and $y \in X$; similarly $x \in G^{-1}(Y)$ because $(x,y') \in G$ and $y' \in Y$. Hence $x \in G^{-1}(X) \cap G^{-1}(Y)$, contradicting the fact that this intersection is empty. Therefore $G$ must be functional.

The three implications (a)$\Rightarrow$(b), (b)$\Rightarrow$(c), (c)$\Rightarrow$(a) together establish the equivalence of the three propositions.