Our aim is to illustrate the meaning of the term “subobject classifier” (Wikipedia, nLab)
by giving some examples of how the set \bftwo = \{\ladjbot, \radjtop\}
serves as a (“the”) subobject classifier in the familiar Boolean topos \Set.
Notation: The symbol “\lrcorner” indicates that (the square in which it is contained) is (a pullback square),
with (the pullback object) being (that which is bounded by the “\lrcorner”).
Basic examples of subobject classification
| \bbox[2ex, border:1px black solid] { \begin{array}{} && \emptyset & \xrightarrow[]{} & \bfone \\ && \llap{\emptyset = 1_\emptyset} \Big\Vert & \mkern-1.8em{\raise2ex\hbox{$\lrcorner$}} & \Big\downarrow\rlap\radjtop & \\ && \emptyset & \xrightarrow[\displaystyle \emptyset]{} &\bftwo \\ \end{array} } | 2^0 = {0 \choose 0} = 1 | |||
| \bbox[2ex, border:1px black solid] { \begin{array}{} & \emptyset & \xrightarrow[]{} & \bfone \\ & \llap{\emptyset}\Big\downarrow & \mkern-1.8em{\raise2ex\hbox{$\lrcorner$}} & \Big\downarrow\rlap\radjtop & \\ & \bfone & \xrightarrow[\displaystyle \ladjbot]{} &\bftwo \\ \end{array} } | \bbox[2ex, border:1px black solid] { \begin{array}{} & \bfone & \xrightarrow[]{} & \bfone \\ & \llap{1_\bfone} \Big\Vert & \mkern-1.8em{\raise2ex\hbox{$\lrcorner$}} & \Big\downarrow\rlap\radjtop & \\ & \bfone & \xrightarrow[\displaystyle \radjtop]{} &\bftwo \\ \end{array} } | 2^1 = {1 \choose 0} + {1 \choose 1} = 1 + 1 = 2 | ||
| \bbox[2ex, border:1px black solid] { \begin{array}{} & \emptyset & \xrightarrow[]{} & \bfone \\ & \llap{\emptyset}\Big\downarrow & \mkern-1.8em{\raise2ex\hbox{$\lrcorner$}} & \Big\downarrow\rlap\radjtop & \\ & \bftwo & \xrightarrow[\displaystyle !\ladjbot]{} &\bftwo \\ \end{array} } | \bbox[2ex, border:1px black solid] { \begin{array}{} \{\radjtop\} \cong \bfone & \xrightarrow[]{} & \bfone \\ \llap{\radjtop}\Big\downarrow & \mkern-1.8em{\raise2ex\hbox{$\lrcorner$}} & \Big\downarrow\rlap\radjtop & \\ \bftwo & \xrightarrow[\displaystyle 1_\bftwo]{} &\bftwo \\ \end{array} } | \bbox[2ex, border:1px black solid] { \begin{array}{} \{\ladjbot\} \cong \bfone & \xrightarrow[]{} & \bfone \\ \llap{\ladjbot}\Big\downarrow & \mkern-1.8em{\raise2ex\hbox{$\lrcorner$}} & \Big\downarrow\rlap\radjtop & \\ \bftwo & \xrightarrow[\displaystyle \neg\vphantom{1_\bftwo}]{} &\bftwo \\ \end{array} } | \bbox[2ex, border:1px black solid] { \begin{array}{} & \bftwo & \xrightarrow[]{} & \bfone \\ & \llap{1_\bftwo} \Big\Vert & \mkern-1.8em{\raise2ex\hbox{$\lrcorner$}} & \Big\downarrow\rlap\radjtop & \\ & \bftwo & \xrightarrow[\displaystyle !\radjtop]{} &\bftwo \\ \end{array} } | \begin{array}{l} 2^2 = (1+1)^2 = (1+1)\cdot(1+1) = \\ = 1\cdot 1 + 1\cdot 1 + 1\cdot 1 + 1\cdot 1 = \\ = 1 + 1 + 1 + 1 = \\ = {2\choose 0} + {2\choose 1} + {2\choose 2} = 1+2+1 =4\\ \bftwo^2 \cong (\ladjbot+\radjtop)^2 = (\ladjbot+\radjtop) \times (\ladjbot+\radjtop) \cong \\ {} \cong \ladjbot\times\ladjbot + \ladjbot\times\radjtop + \radjtop\times\ladjbot + \radjtop\times\radjtop \sim \\ {} \sim {!\ladjbot} + 1_\bftwo + {\neg} + {!\radjtop} \\ \end{array} |
| \bbox[2ex, border:1px black solid] { \begin{array}{lccc} \text{graph} & \radjtop \\ \text{of }\mkern.25em !\ladjbot & \ladjbot & \text{X} & \text{X} \\ \text{output} & & \ladjbot & \ladjbot \\ \text{input} & & \ladjbot & \radjtop \\ \end{array} } | \bbox[2ex, border:1px black solid] { \begin{array}{lccc} \text{graph} & \radjtop & & \class {red} {\text{X}} \\ \text{of }\mkern.25em 1_\bftwo & \ladjbot & \text{X} \\ \text{output} & & \ladjbot & \class {red} {\radjtop} \\ \text{input} & & \ladjbot & \radjtop \\ \end{array} } | \bbox[2ex, border:1px black solid] { \begin{array}{lccc} \text{graph} & \radjtop & \class {red} {\text{X}} \\ \text{of }\mkern.25em \neg & \ladjbot & & \text{X} \\ \text{output} & & \class {red} {\radjtop} & \ladjbot \\ \text{input} & & \ladjbot & \radjtop \\ \end{array} } | \bbox[2ex, border:1px black solid] { \begin{array}{lccc} \text{graph} & \radjtop & \class {red} {\text{X}} & \class {red} {\text{X}} \\ \text{of }\mkern.25em !\radjtop & \ladjbot \\ \text{output} & & \class {red} {\radjtop} & \class {red} {\radjtop} \\ \text{input} & & \ladjbot & \radjtop \\ \end{array} } | |
General theorem: 2 is a subobject classifier for Set
For an arbitrary set \setX\in\Set, there is a bijection \Sub(\setX) \cong \hom \setX \Set \bftwo.The correspondence between (subsets \setA \subseteq \setX, which are also denoted i_\setA : \setA \rightarrowtail \setX) and (\bftwo-valued predicates \functionA : \setX \to \bftwo) is given by:
| From subsets to predicates | From predicates to subsets | |
| \bbox[2ex, border:1px black solid] { \begin{array}{} & \functionA & \xrightarrow[]{\displaystyle !} & \bfone \\ & \llap{i_\setA}\Big\downarrow & \mkern-10em{\raise2ex\hbox{$\lrcorner$}} & \Big\downarrow\rlap\radjtop & \\ & X & \xrightarrow[ \displaystyle \boxed{ \begin{array}{} ?\in\functionA\\ (\exists\elta\in\setA)(?=\elta) \\ (\exists\elta)(\elta\in\setA \wedge {?=\elta} \wedge \radjtop) \\ \int^{\elta\in\setA} \hom ? \setX \elta \otimes {!\radjtop} \\ \Lan_{i_\setA} !\radjtop \\ \end{array} } ]{} &\bftwo \\ \end{array} } | \bbox[2ex, border:1px black solid] { \begin{array}{} & \boxed{ \begin{array}{} \{ \eltx \mid \functionA_\eltx \}\\ \{ \eltx \mid \functionA_\eltx = \radjtop \}\\ \functionA^{-1}\radjtop\\ \end{array} } & \xrightarrow[]{\displaystyle !} & \bfone \\ & \llap{}\Big\downarrow & \mkern-3em{\raise2ex\hbox{$\lrcorner$}} & \Big\downarrow\rlap\radjtop & \\ & X & \xrightarrow[\displaystyle \functionA]{} &\bftwo \\ \end{array} } |
No comments:
Post a Comment