Item 3 (01LA) — The Clowder Project

4.5.1 The Characteristic Function of a Subset

Let $X$ be a set and let $U\in \mathcal{P}\webleft (X\webright )$.

Definition 4.5.1.1.1 ▶ The Characteristic Function of a Subset

The characteristic function of $U$¹ is the function$\chi _{U}\colon X\to \{ \mathsf{t},\mathsf{f}\} $² defined by

\[ \chi _{U}\webleft (x\webright ) \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\begin{cases} \mathsf{true}& \text{if $x\in U$,}\\ \mathsf{false}& \text{if $x\not\in U$} \end{cases} \]

for each $x\in X$.

¹Further Terminology: Also called the indicator function of $U$.
²Further Notation: Also written $\chi _{X}\webleft (U,-\webright )$ or $\chi _{X}\webleft (-,U\webright )$.

Remark 4.5.1.1.2 ▶ Characteristic Functions of Subsets as Decategorifications of Presheaves

Under the analogy that $\{ \mathsf{t},\mathsf{f}\} $ should be the $\webleft (-1\webright )$-categorical analogue of $\mathsf{Sets}$, we may view a function

\[ f\colon X\to \{ \mathsf{t},\mathsf{f}\} \]

as a decategorification of presheaves and copresheaves

\begin{gather*} \mathcal{F} \colon \mathcal{C}^{\mathsf{op}} \to \mathsf{Sets},\\ F \colon \mathcal{C} \to \mathsf{Sets}.\end{gather*}

The characteristic functions $\chi _{U}$ of the subsets of $X$ are then the primordial examples of such functions (and, in fact, all of them).

Notation 4.5.1.1.3 ▶ Further Notation for Characteristic Functions

We will often employ the bijection $\{ \mathsf{t},\mathsf{f}\} \cong \left\{ 0,1\right\} $ to make use of the arithmetical operations defined on $\left\{ 0,1\right\} $ when disucssing characteristic functions.

Examples of this include Item 4, Item 5, Item 6, Item 7, Item 8, Item 9, Item 10, and Item 11 of Proposition 4.5.1.1.4 below.

Proposition 4.5.1.1.4 ▶ Properties of Characteristic Functions of Subsets

Let $X$ be a set.

1.
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 ). \]
2.
Bijectivity. The function $\chi _{\webleft (-\webright )}$ from Item 1 is bijective.

3.
Naturality. The collection

\[ \left\{ \chi _{\webleft (-\webright )}\colon \mathcal{P}\webleft (X\webright )\to \mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright )\right\} _{X\in \operatorname {\mathrm{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*{\operatorname {\mathrm{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*{\operatorname {\mathrm{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 )$.

10.

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 )$.

11.

Interaction With Internal Homs. We have

\[ \chi _{\webleft [U,V\webright ]_{\mathcal{P}\webleft (X\webright )}}=\operatorname*{\operatorname {\mathrm{max}}}\webleft (1-\chi _{U}\ (\mathrm{mod}\ 2),\chi _{V}\webright ) \]

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

Proof of Proposition 4.5.1.1.4.

Item 1: Functionality

There is nothing to prove.

Item 2: Bijectivity

We proceed in three steps:

1.
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}}}=}}\left\{ x\in X\ \middle |\ f\webleft (x\webright )=\mathsf{true}\right\} \end{align*}

for each $f\in \mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright )$.
2.
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}}}=}}\left\{ x\in X\ \middle |\ \chi _{U}\webleft (x\webright )=\mathsf{true}\right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ x\in X\ \middle |\ x\in U\right\} \\ & = U\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft [\operatorname {\mathrm{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 )}=\operatorname {\mathrm{id}}_{\mathcal{P}\webleft (X\webright )}. \]
3.
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 [\operatorname {\mathrm{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 =\operatorname {\mathrm{id}}_{\mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright )}. \]

This finishes the proof.

Item 3: Naturality

We proceed in two steps:

1.
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$.
2.
Naturality of $\Phi $. Since $\chi _{\webleft (-\webright )}$ is natural and a componentwise inverse to $\Phi $, it follows from Chapter 11: Categories, Item 2 of Proposition 11.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 4.3.8.1.2 and is proved there.

Item 5: Interaction With Unions II

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

Item 6: Interaction With Intersections I

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

Item 7: Interaction With Intersections II

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

Item 8: Interaction With Differences

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

Item 9: Interaction With Complements

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

Item 10: Interaction With Symmetric Differences

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

Item 11: Interaction With Internal Homs

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

Remark 4.5.1.1.5 ▶ Powersets as Sets of Functions and Un/Straightening

The bijection

\[ \mathcal{P}\webleft (X\webright )\cong \mathsf{Sets}\webleft (X,\{ \mathsf{t},\mathsf{f}\} \webright ) \]

of Item 2 of Proposition 4.5.1.1.4, which

•
Takes a subset $U\hookrightarrow X$ of $X$ and straightens it to a function $\chi _{U}\colon X\to \{ \mathsf{true},\mathsf{false}\} $;
•
Takes a function $f\colon X\to \{ \mathsf{true},\mathsf{false}\} $ and unstraightens it to a subset $f^{-1}\webleft (\mathsf{true}\webright )\hookrightarrow X$ of $X$;

may be viewed as the $\webleft (-1\webright )$-categorical version of the 0-categorical un/straightening isomorphism between indexed and fibred sets

\[ \underbrace{\mathsf{FibSets}_{X}}_{\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\mathsf{Sets}_{/X}}\cong \underbrace{\mathsf{ISets}_{X}}_{\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\mathsf{Fun}\webleft (X_{\mathsf{disc}},\mathsf{Sets}\webright )} \]

of , . Here we view:

•
Subsets $U\hookrightarrow X$ as being analogous to $X$-fibred sets $\phi _{X}\colon A\to X$.
•
Functions $f\colon X\to \{ \mathsf{t},\mathsf{f}\} $ as being analogous to $X$-indexed sets $A\colon X_{\mathsf{disc}}\to \mathsf{Sets}$.

Statistics Cite

Noticed something off, or have any comments? Feel free to reach out!

•Email
•Discord

You can also use the contact form below: