Subsection 2.4.1 (005X): Characteristic Functions

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`

2.4.1 Characteristic Functions

Let $X$ be a set.

Definition 2.4.1.1.1 ▶ Characteristic Functions

Let $U\subset X$ and let $x\in X$.

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

defined by

\[ \chi _{x} \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\chi _{\webleft\{ x\webright\} }, \]

i.e. by

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

for each $y\in X$.
The characteristic relation on $X$^[4] is the relation ^[5]
\[ \chi _{X}\webleft (-_{1},-_{2}\webright )\colon X\times X\to \{ \mathsf{t},\mathsf{f}\} \]

on $X$ defined by ^[6]

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

for each $x,y\in X$.
The characteristic embedding^[7] of $X$ into $\mathcal{P}\webleft (X\webright )$ is the function
\[ \chi _{\webleft (-\webright )}\colon X \hookrightarrow \mathcal{P}\webleft (X\webright ) \]

defined by

\[ \chi _{\webleft (-\webright )}\webleft (x\webright ) \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\chi _{x} \]

for each $x\in X$.

Remark 2.4.1.1.2 ▶ Characteristic Functions as Decategorifications of Presheaves

The definitions in Definition 2.4.1.1.1 are decategorifications of co/presheaves, representable co/presheaves, $\textup{Hom}$ profunctors, and the Yoneda embedding:^[8]

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

is a decategorification of a presheaf

\[ \mathcal{F}\colon \mathcal{C}^{\mathsf{op}}\to \mathsf{Sets}, \]

with the characteristic functions $\chi _{U}$ of the subsets of $X$ being the primordial examples (and, in fact, all examples) of these.
The characteristic function
\[ \chi _{x}\colon X\to \{ \mathsf{t},\mathsf{f}\} \]

of an element $x$ of $X$ is a decategorification of the representable presheaf

\[ h_{X}\colon \mathcal{C}^{\mathsf{op}} \to \mathsf{Sets} \]

of an object $x$ of a category $\mathcal{C}$.
The characteristic relation
\[ \chi _{X}\webleft (-_{1},-_{2}\webright )\colon X\times X\to \{ \mathsf{t},\mathsf{f}\} \]

of $X$ is a decategorification of the $\textup{Hom}$ profunctor

\[ \textup{Hom}_{\mathcal{C}}\webleft (-_{1},-_{2}\webright )\colon \mathcal{C}^{\mathsf{op}}\times \mathcal{C}\to \mathsf{Sets} \]

of a category $\mathcal{C}$.
The characteristic embedding
\[ \chi _{\webleft (-\webright )}\colon X\hookrightarrow \mathcal{P}\webleft (X\webright ) \]

of $X$ into $\mathcal{P}\webleft (X\webright )$ is a decategorification of the Yoneda embedding

\[ {\text{よ}}\colon \mathcal{C}^{\mathsf{op}} \hookrightarrow \mathsf{PSh}\webleft (\mathcal{C}\webright ) \]

of a category $\mathcal{C}$ into $\mathsf{PSh}\webleft (\mathcal{C}\webright )$.
There is also a direct parallel between unions and colimits:
- An element of $\mathcal{P}\webleft (X\webright )$ is a union of elements of $X$, viewed as one-point subsets $\webleft\{ x\webright\} \in \mathcal{P}\webleft (A\webright )$.
- An object of $\mathsf{PSh}\webleft (\mathcal{C}\webright )$ is a colimit of objects of $\mathcal{C}$, viewed as representable presheaves $h_{X}\in \text{Obj}\webleft (\mathsf{PSh}\webleft (\mathcal{C}\webright )\webright )$.

Proposition 2.4.1.1.3 ▶ Properties of Characteristic Functions

Let $X$ be a set.

The Inclusion of Characteristic Relations Associated to a Function. Let $f\colon A\to B$ be a function. We have an inclusion ^[9]
Interaction With Unions I. We have
\[ \chi _{U\cup V}=\operatorname*{\text{max}}\webleft (\chi _{U},\chi _{V}\webright ) \]

for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and 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 $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and 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 $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and 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 $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and 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 $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V\in \mathcal{P}\webleft (X\webright )$.
Interaction With Complements. We have
\[ \chi _{U^{\textsf{c}}}=1-\chi _{U} \]

for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and 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}\mod {2} \]

for each $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and each $U,V\in \mathcal{P}\webleft (X\webright )$.
Interaction Between the Characteristic Embedding and Morphisms. Let $f\colon X\to Y$ be a map of sets. The diagram
commutes.

Proof of Proposition 2.4.1.1.3.

Item 1: The Inclusion of Characteristic Relations Associated to a Function

The inclusion $\chi _{B}\webleft (f\webleft (a\webright ),f\webleft (b\webright )\webright )\subset \chi _{A}\webleft (a,b\webright )$ is equivalent to the statement “if $a=b$, then $f\webleft (a\webright )=f\webleft (b\webright )$”, which is true.

Item 2: Interaction With Unions I

This is a repetition of Item 8 of Proposition 2.3.7.1.2 and is proved there.

Item 3: Interaction With Unions II

This is a repetition of Item 9 of Proposition 2.3.7.1.2 and is proved there.

Item 4: Interaction With Intersections I

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

Item 5: Interaction With Intersections II

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

Item 6: Interaction With Differences

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

Item 7: Interaction With Complements

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

Item 8: Interaction With Symmetric Differences

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

Item 9: Interaction Between the Characteristic Embedding and Morphisms

Indeed, we have

\begin{align*} \webleft [f_{*}\circ \chi _{X}\webright ]\webleft (x\webright ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}f_{*}\webleft (\chi _{X}\webleft (x\webright )\webright )\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}f_{*}\webleft (\webleft\{ x\webright\} \webright )\\ & = \webleft\{ f\webleft (x\webright )\webright\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\chi _{X'}\webleft (f\webleft (x\webright )\webright )\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft [\chi _{X'}\circ f\webright ]\webleft (x\webright ),\end{align*}

for each $x\in X$, showing the desired equality.

Footnotes

[1] Further Terminology: Also called the indicator function of $U$.

[2] Further Notation: Also written $\chi _{X}\webleft (U,-\webright )$ or $\chi _{X}\webleft (-,U\webright )$.

[3] Further Notation: Also written $\chi ^{x}$, $\chi _{X}\webleft (x,-\webright )$, or $\chi _{X}\webleft (-,x\webright )$.

[4] Further Terminology: Also called the identity relation on $X$.

[5] Further Notation: Also written $\chi ^{-_{1}}_{-_{2}}$, or $\mathord {\sim }_{\text{id}}$ in the context of relations.

[6] As a subset of $X\times X$, the relation $\chi _{X}$ corresponds to the diagonal $\Delta _{X}\subset X\times X$ of $X$.

[7] The name “characteristic embedding” comes from the fact that there is an analogue of fully faithfulness for $\chi _{\webleft (-\webright )}$: given a set $X$, we have

\[ \textup{Hom}_{\mathcal{P}\webleft (X\webright )}\webleft (\chi _{x},\chi _{y}\webright )=\chi _{X}\webleft (x,y\webright ), \]

for each $x,y\in X$.

[8] These statements can be made precise by using the embeddings

\begin{align*} \webleft (-\webright )_{\mathsf{disc}} & \colon \mathsf{Sets}\hookrightarrow \mathsf{Cats},\\ \webleft (-\webright )_{\mathsf{disc}} & \colon \{ \mathsf{t},\mathsf{f}\} _{\mathsf{disc}} \hookrightarrow \mathsf{Sets}\end{align*}

of sets into categories and of classical truth values into sets.

For instance, in this approach the characteristic function

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

of an element $x$ of $X$, defined by

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

for each $y\in X$, is recovered as the representable presheaf

\[ \textup{Hom}_{X_{\mathsf{disc}}}\webleft (-,x\webright ) \colon X_{\mathsf{disc}} \to \mathsf{Sets} \]

of the corresponding object $x$ of $X_{\mathsf{disc}}$, defined on objects by

\[ \textup{Hom}_{X_{\mathsf{disc}}}\webleft (y,x\webright ) \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\begin{cases} \text{pt}& \text{if $x=y$,}\\ \emptyset & \text{if $x\neq y$} \end{cases} \]

for each $y\in \text{Obj}\webleft (X_{\mathsf{disc}}\webright )$.

[9] This is the $0$-categorical version of Chapter 8: Categories, Definition 8.4.4.1.1.

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

You can also use the contact form below: