2.5.1 The Characteristic Function of a Subset

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

Definition 2.5.1.1.1 ▶ The Characteristic Function of a Subset

The characteristic function of $U$1 is the function$\chi _{U}\colon X\to \{ \mathsf{t},\mathsf{f}\} $2 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$.

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

Remark 2.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 2.5.1.1.3 ▶ Further Notation for Characteristic Functions

Proposition 2.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
    \[ \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 )$.

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

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

  6. Interaction With Intersections I. We have
    \[ \chi _{U\cap V}=\chi _{U}\chi _{V} \]

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

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

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

  9. 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*{\text{max}}\webleft (1-\chi _{U}\ (\mathrm{mod}\ 2),\chi _{V}\webright ) \]

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

Proof of Proposition 2.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}}}=}}\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 )$.

  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}}}=}}\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 )}. \]
  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 [\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:
  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 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.

Remark 2.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 2.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}$.

Next

View Subsection 2.5.1 as PDF

Statistics Cite

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

You can also use the contact form below: