Proposition 2.5.1.1.4 (0069): Properties of Characteristic Functions of Subsets

Style	Class	Font	Theorem Environments
Style 1	`book`	Alegreya Sans	`tcbthm`
Style 2	`book`	Alegreya Sans	`amsthm`
Style 3	`book`	Arno*	`amsthm`
Style 4	`book`	Computer Modern	`amsthm`

Let $X$ be a set.

Functionality. The assignment $U\mapsto \chi _{U}$ defines a function
\[ \chi _{\webleft (-\webright )}\colon \mathcal{P}\webleft (X\webright )\to \mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright ). \]
Bijectivity. The function $\chi _{\webleft (-\webright )}$ from Item 1 is bijective.
Naturality. The collection
\[ \webleft\{ \chi _{\webleft (-\webright )}\colon \mathcal{P}\webleft (X\webright )\to \mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright )\webright\} _{X\in \text{Obj}\webleft (\mathsf{Sets}\webright )} \]

defines a natural isomorphism between $\mathcal{P}^{-1}$ and $\mathsf{Sets}\webleft (-,\{ \mathsf{t},\mathsf{f}\} \webright )$. In particular, given a function $f\colon X\to Y$, the diagram

commutes, i.e. we have

\[ \chi _{V}\circ f=\chi _{f^{-1}\webleft (V\webright )} \]

for each $V\in \mathcal{P}\webleft (Y\webright )$.
Interaction With Unions I. We have
\[ \chi _{U\cup V}=\operatorname*{\text{max}}\webleft (\chi _{U},\chi _{V}\webright ) \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$.
Interaction With Unions II. We have
\[ \chi _{U\cup V}=\chi _{U}+\chi _{V}-\chi _{U\cap V} \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$.
Interaction With Intersections I. We have
\[ \chi _{U\cap V}=\chi _{U}\chi _{V} \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$.
Interaction With Intersections II. We have
\[ \chi _{U\cap V}=\operatorname*{\text{min}}\webleft (\chi _{U},\chi _{V}\webright ) \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$.
Interaction With Differences. We have
\[ \chi _{U\setminus V}=\chi _{U}-\chi _{U\cap V} \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$.
Interaction With Complements. We have
\[ \chi _{U^{\textsf{c}}}\equiv 1-\chi _{U}\ \ (\mathrm{mod}\ 2) \]

for each $U\in \mathcal{P}\webleft (X\webright )$.
Interaction With Symmetric Differences. We have
\[ \chi _{U\mathbin {\triangle }V}=\chi _{U}+\chi _{V}-2\chi _{U\cap V} \]

and thus, in particular, we have

\[ \chi _{U\mathbin {\triangle }V}\equiv \chi _{U}+\chi _{V}\ \ (\mathrm{mod}\ 2) \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$.
Interaction With Internal Homs. We have
\[ \chi _{\webleft [U,V\webright ]_{\mathcal{P}\webleft (X\webright )}}=\operatorname*{\text{max}}\webleft (1-\chi _{U}\ (\mathrm{mod}\ 2),\chi _{V}\webright ) \]

for each $U,V\in \mathcal{P}\webleft (X\webright )$.

Item 1: Functionality

There is nothing to prove.

Item 2: Bijectivity

We proceed in three steps:

The Inverse of $\chi _{\webleft (-\webright )}$. The inverse of $\chi _{\webleft (-\webright )}$ is the map
\[ \Phi \colon \mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright ) \overset {\scriptstyle \mathord {\sim }}{\dashrightarrow }\mathcal{P}\webleft (X\webright ), \]

defined by

\begin{align*} \Phi \webleft (f\webright ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}U_{f}\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}f^{-1}\webleft (\mathsf{true}\webright )\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft\{ x\in X\ \middle |\ f\webleft (x\webright )=\mathsf{true}\webright\} \end{align*}

for each $f\in \mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright )$.
Invertibility I. We have
\begin{align*} \webleft [\Phi \circ \chi _{\webleft (-\webright )}\webright ]\webleft (U\webright ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\Phi \webleft (\chi _{U}\webright )\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\chi ^{-1}_{U}\webleft (\mathsf{true}\webright )\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft\{ x\in X\ \middle |\ \chi _{U}\webleft (x\webright )=\mathsf{true}\webright\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft\{ x\in X\ \middle |\ x\in U\webright\} \\ & = U\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft [\text{id}_{\mathcal{P}\webleft (X\webright )}\webright ]\webleft (U\webright ) \end{align*}

for each $U\in \mathcal{P}\webleft (X\webright )$. Thus, we have

\[ \Phi \circ \chi _{\webleft (-\webright )}=\text{id}_{\mathcal{P}\webleft (X\webright )}. \]
Invertibility II. We have
\begin{align*} \webleft [\chi _{\webleft (-\webright )}\circ \Phi \webright ]\webleft (U\webright ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\chi _{\Phi \webleft (f\webright )}\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\chi _{f^{-1}\webleft (\mathsf{true}\webright )}\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}[\mspace {-3mu}[x\mapsto \begin{cases} \mathsf{true}& \text{if $x\in f^{-1}\webleft (\mathsf{true}\webright )$}\\ \mathsf{false}& \text{otherwise}\end{cases}]\mspace {-3mu}]\\ & = [\mspace {-3mu}[x\mapsto f\webleft (x\webright )]\mspace {-3mu}]\\ & = f\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft [\text{id}_{\mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright )}\webright ]\webleft (f\webright ) \end{align*}

for each $f\in \mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright )$. Thus, we have

\[ \chi _{\webleft (-\webright )}\circ \Phi =\text{id}_{\mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright )}. \]

This finishes the proof.

Item 3: Naturality

We proceed in two steps:

Naturality of $\chi _{\webleft (-\webright )}$. We have
\begin{align*} \webleft [\chi _{V}\circ f\webright ]\webleft (v\webright ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\chi _{V}\webleft (f\webleft (v\webright )\webright )\\ & = \begin{cases} \mathsf{true}& \text{if $f\webleft (v\webright )\in V$,}\\ \mathsf{false}& \text{otherwise} \end{cases}\\ & = \begin{cases} \mathsf{true}& \text{if $v\in f^{-1}\webleft (V\webright )$,}\\ \mathsf{false}& \text{otherwise} \end{cases}\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\chi _{f^{-1}\webleft (V\webright )}\webleft (v\webright )\end{align*}

for each $v\in V$.
Naturality of $\Phi $. Since $\chi _{\webleft (-\webright )}$ is natural and a componentwise inverse to $\Phi $, it follows from Chapter 9: Preorders, Item 2 of Proposition 9.9.7.1.2 that $\Phi $ is also natural in each argument.

This finishes the proof.

Item 4: Interaction With Unions I

This is a repetition of Item 10 of Proposition 2.3.8.1.2 and is proved there.

Item 5: Interaction With Unions II

This is a repetition of Item 11 of Proposition 2.3.8.1.2 and is proved there.

Item 6: Interaction With Intersections I

This is a repetition of Item 10 of Proposition 2.3.9.1.2 and is proved there.

Item 7: Interaction With Intersections II

This is a repetition of Item 11 of Proposition 2.3.9.1.2 and is proved there.

Item 8: Interaction With Differences

This is a repetition of Item 16 of Proposition 2.3.10.1.2 and is proved there.

Item 9: Interaction With Complements

This is a repetition of Item 4 of Proposition 2.3.11.1.2 and is proved there.

Item 10: Interaction With Symmetric Differences

This is a repetition of Item 15 of Proposition 2.3.12.1.2 and is proved there.

Item 11: Interaction With Internal Homs

This is a repetition of Item 17 of Proposition 2.4.7.1.3 and is proved there.