\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{subobject classifier}

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{topos_theory}{}\paragraph*{{Topos Theory}}\label{topos_theory}

[[!include topos theory - contents]]

\hypertarget{universes}{}\paragraph*{{Universes}}\label{universes}

[[!include universe - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak
\noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak
\noindent\hyperlink{in_}{In $Set$}\dotfill \pageref*{in_} \linebreak
\noindent\hyperlink{in_a_presheaf_topos}{In a presheaf topos}\dotfill \pageref*{in_a_presheaf_topos} \linebreak
\noindent\hyperlink{in__2}{In $G Set$}\dotfill \pageref*{in__2} \linebreak
\noindent\hyperlink{in_a_nonboolean_topos}{In a non-boolean topos}\dotfill \pageref*{in_a_nonboolean_topos} \linebreak
\noindent\hyperlink{in_a_slice_topos}{In a slice topos}\dotfill \pageref*{in_a_slice_topos} \linebreak
\noindent\hyperlink{in_a_nontopos}{In a non-topos}\dotfill \pageref*{in_a_nontopos} \linebreak
\noindent\hyperlink{properties}{Properties}\dotfill \pageref*{properties} \linebreak
\noindent\hyperlink{johnstones_exercise}{Johnstone's exercise}\dotfill \pageref*{johnstones_exercise} \linebreak
\noindent\hyperlink{categories_with_a_contractible_subobject_classifier}{Categories with a contractible subobject classifier}\dotfill \pageref*{categories_with_a_contractible_subobject_classifier} \linebreak
\noindent\hyperlink{categories_without_subobject_classifiers}{Categories without subobject classifiers}\dotfill \pageref*{categories_without_subobject_classifiers} \linebreak
\noindent\hyperlink{generalizations_object_classifier}{Generalizations: object classifier}\dotfill \pageref*{generalizations_object_classifier} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

Subsets $A$ of a set $X$ correspond precisely to maps from $X$ to the set of truth values of classical logic via their [[characteristic function]] $\chi_A:X\to \{0,1\}$ . The concept of a \textbf{subobject classifier} generalizes this situation to [[toposes]] other than [[Set]]:

A \emph{subobject classifier} in a [[topos]] is a morphism $true : * \to \Omega$ such that every [[monomorphism]] $A \hookrightarrow B$ in the topos (hence every [[subobject]]) is the [[pullback]] of this morphism along a unique morphism (the [[characteristic morphism]] of $A$) $B \to \Omega$.

In this sense $\Omega$ is the [[classifying space|classifying object]] for subobjects and $true : * \to \Omega$ the \emph{generic} subobject.

The existence of a subobject classifier in a category is a powerful property which induces much other structure that lies at the heart of [[topos theory]].

By restricting the class of monomorphism appropriately, the concept can be relativized to the concept of an \emph{\textbf{M}-subobject classifier}\footnote{For \textbf{M} the class of strong monomorphisms, this is called a \emph{weak subobject classifier} in Johnstone (2002, p.120).} : e.g. demanding only classification of strong monomorphisms leads to [[quasitopos|quasitoposes]].

In [[type theory]], a [[type]] closely related to the subobject classifier is the [[type of propositions]], often denoted $Prop$ or (sometimes in [[homotopy type theory]]) $hProp$.

\hypertarget{definition}{}\subsection*{{Definition}}\label{definition}

\begin{defn}
\label{}\hypertarget{}{}
In a [[category]] $C$ with [[finite limit]]s, a \textbf{subobject classifier} is a [[monomorphism]] $true : * \to \Omega$ out of the [[terminal object]], such that for every [[monomorphism]] $U \to X$ in $C$ there is a unique morphism $\chi_U : X \to \Omega$ such that there is a [[pullback]] [[diagram]] of the following form:

\begin{displaymath}
\itexarray{
    U &\to& *   
    \\
    \downarrow && \downarrow^{\mathrlap{true}}
    \\
    X &\stackrel{\chi_U}{\to}& \Omega
  }
  \,.
\end{displaymath}
\end{defn}
See for instance (\hyperlink{MacLaneMoerdijk}{MacLane-Moerdijk, p. 32}).

\begin{remark}
\label{}\hypertarget{}{}
Some terminology:

If it exists, the object $\Omega$ is also called the \textbf{object of [[truth value]]s}, a [[global element]] $K \to \Omega$ is called a \textbf{[[truth value]]} and the element $true : * \hookrightarrow \Omega$ is the truth value \textbf{[[true]]}, where all these terms allude to the [[internal logic]] of the category $C$.

Note that the subobjects classified by the truth values are [[subterminal object]]s.

The morphism $\chi_U$ is also called the \textbf{[[characteristic map]]} or \textbf{[[classifying map]]} of the subobject $U \hookrightarrow X$.

\end{remark}
\begin{prop}
\label{}\hypertarget{}{}
If $C$ has [[finite limit]]s and is in addition a [[locally small category]], then it has a subobject classifier precisely if the [[subobject]]-assigning [[presheaf]]

\begin{displaymath}
Sub : C^{op} \to Set
\end{displaymath}
\begin{displaymath}
X \mapsto \{U \hookrightarrow X\}/\sim
\end{displaymath}
is [[representable functor|representable]]. In this case the representing object is [[generalized the|the]] subobject classifier: there is a [[natural isomorphism]]

\begin{displaymath}
Sub(X) \simeq C(X, \Omega)
\end{displaymath}
in $X \in C$.

Moreover, in this case $C$ is [[well-powered category|well powered]].

\end{prop}
This appears for instance as (\hyperlink{MacLaneMoerdijk}{MacLane-Moerdijk, prop. I.3.1}).

In more detail: given a [[morphism]] $f: c \to d$ in $C$, the function

\begin{displaymath}
Sub(f): Sub(d) \to Sub(c)
\end{displaymath}
takes a [[subobject]] $i: t \hookrightarrow d$ to the subobject of $c$ obtained by [[pullback|pulling back]] $i$ along $f$. (Notice that [[monomorphism]]s, as discussed there, are stable under pullback.)

The representability of this functor means there is an object $\Omega$ together with a subobject $t: T \hookrightarrow \Omega$ which is \emph{[[universal construction|universal]]}, meaning that given any subobject $i: s \hookrightarrow c$, there is a unique morphism $f: c \to \Omega$ such that $i$ is obtained as the pullback of $t$ along $f$.

\begin{proof}
To see that a subobject classifier induces such a natural isomorphism, we need that the morphisms $Sub(f)$ for $f \in Mor(C)$ corresponds to the morphisms $C(f,\Omega)$. This is the [[pasting law]] for [[pullback]]s.

Conversely, to see that a subobjects-representing object $\Omega$ is a subobject classifier, use that by [[natural transformation|naturality]] we have for each morphism $\phi : X \to \Omega$ a [[commuting diagram]]

\begin{displaymath}
\itexarray{
    Sub(\Omega) &\stackrel{\simeq}{\to}& C(\Omega, \Omega)
    \\
    {}^{\mathllap{Sub(\phi)}}\downarrow && \downarrow^{\mathrlap{C(\phi,\Omega)}}
    \\
    Sub(X) &\stackrel{\simeq}{\to}& C(X, \Omega)
  }
\end{displaymath}
whose commutativity says that every element of $Sub(X)$ is the pullback along some $\phi : X \to \Omega$ of the subobject of $\Omega$ corresponding under the natural isomorphism to $Id : \Omega \to \Omega$.

By further playing around with this one finds that this latter subobject of $\Omega$ has to be a [[terminal object]].

\end{proof}
\hypertarget{examples}{}\subsection*{{Examples}}\label{examples}

\hypertarget{in_}{}\subsubsection*{{In $Set$}}\label{in_}

In the category of [[set]]s, the 2-element set $\mathbf{2} = \{f, t\}$ plays the role of $\Omega$; the morphism $t: 1 \to \mathbf{2}$ just names the element $t$. Given a [[subset]] $S \subseteq X$, the characteristic function $\chi_S: X \to \mathbf{2}$ is the function defined by $\chi_S(x) = t$ if $x \in S$, and $\chi_S(x) = f$ if $x \notin S$.

\begin{remark}
\label{}\hypertarget{}{}
It is not usually true in [[toposes]] that $\Omega$ is the [[coproduct]] $\mathbf{2} = 1 + 1$; toposes where that occurs are called \emph{[[Boolean topos|Boolean]]. Thus the category $Set$ of sets is a Boolean topos, as is the [[presheaf]] topos $Set^G$ when $G$ is a [[groupoid]].}

\end{remark}
\hypertarget{in_a_presheaf_topos}{}\subsubsection*{{In a presheaf topos}}\label{in_a_presheaf_topos}

\begin{prop}
\label{}\hypertarget{}{}
The subobject classifier in a [[presheaf topos]] $PSh(S)$ is the [[presheaf]] that sends each [[object]] $U \in S$ to the [[set]] $sieves(U)$ of [[sieves]] on it

\begin{displaymath}
\Omega 
    \;\colon\; 
  U \mapsto sieves(U)
\end{displaymath}
Here $sieves(U)$ is equivalently the set of [[subobjects]] of the [[representable functor|representable]] [[presheaf]] $Y(U)$.

The corresponding morphism $true : * \to \Omega$ of presheaves is the [[natural transformation]] that picks over each object the \emph{maximal sieve} $true_U = maximal_{sieves(U)} : * \to sieves(U)$.

\end{prop}
\begin{remark}
\label{}\hypertarget{}{}
If one views a [[presheaf]] over a [[small category]] $S$ as a set varying (or evolving) over $S$, then the subobject classifier in $PSh(S)$ may be viewed as encapsulating the ways of an element to be in the set ranging from `never' to `always' being in the set.

In $Set = PSh(\ast)$ these two extremes are the only possibilities, but in the general case there are ways to become an element `over time'.

It might be helpful to have a look at the simple example of a subobject classifier in the presheaf topos of directed graphs worked out at [[Quiv]] to get some intuition.

\end{remark}
\hypertarget{in__2}{}\paragraph*{{In $G Set$}}\label{in__2}

As a special case of presheaf toposes, for $G$ a [[discrete group]] and $G Set = [\mathbf{B} G, Set]$ the topos of [[G-sets]], there are precisely two [[sieves]] on the single object of the [[delooping]] [[groupoid]] $\mathbf{B}G$: the trivial one and the empty one. Hence the subobject classifier here is the 2-element set as in [[Set]], but now regarded as a $G$-set with trivial $G$-[[action]].

For toposes of (left) actions of general [[monoid|monoids]] $M$ the picture changes dramatically, since then there will usually exist non-trivial left ideals and, accordingly, the structure of $\Omega$ will become richer: Its underlying set has elements all left ideals, with $m\in M$ acting on a left ideal $L$ by mapping it to the left ideal $\{n\in M| n\cdot m\in L\}$. (Of course, the same description of $\Omega$ applies to the case of groups as well, it is just, that groups lack non-trivial left ideals!)

\hypertarget{in_a_nonboolean_topos}{}\subsubsection*{{In a non-boolean topos}}\label{in_a_nonboolean_topos}

An example of a non-[[Boolean topos]] is the [[category of sheaves]] over a ``typical'' [[topological space]] $X$ such as the [[real line]] $\mathbb{R}$ in its usual [[topology]]. In this case, $\Omega$ is the sheaf where the set of sections over an [[open subset]] $U$ is the set of open subsets of $U$, with the obvious restriction maps; the [[sheaf and topos theory|sheaf topos]] in this case is guaranteed to be non-Boolean provided there are some non-regular open sets in $X$ (a open set is \emph{regular} if it is the interior of its closure). The ``[[internal logic]]'' of such a topos is [[intuitionistic logic|intuitionistic]].

\hypertarget{in_a_slice_topos}{}\subsubsection*{{In a slice topos}}\label{in_a_slice_topos}

\begin{prop}
\label{}\hypertarget{}{}
Let $\mathcal{E}$ be a [[topos]] and $X \in \mathcal{E}$ any object. Write $\mathcal{E}/X$ for the corresponding [[over-topos]].

The subobject classifier of $\mathcal{E}/X$ is $p_2 : \Omega_{\mathcal{E}} \times X \to X$.

\end{prop}
\begin{proof}
This follows for instance from the statement that the [[inverse image]] of any [[base change geometric morphism]] is a [[logical functor]] and hence preserves subobject classifiers: Here we are looking at the base change along $p : X \to *$ and hence $p^* \Omega_{\mathcal{E}}\simeq \Omega_{\mathcal{E}} \times X$.

But the statement is also easily directly checked.

\end{proof}
\hypertarget{in_a_nontopos}{}\subsubsection*{{In a non-topos}}\label{in_a_nontopos}

The category $Set_\ast$ of [[pointed sets]] has a subobject classifier (specified up to unique isomorphism as the pointed set with two elements).

If one is willing to admit non-locally small categories, then the category of [[proper class|classes]] in [[ZFC]] is not a topos (it is not cartesian closed) but has a subobject classifier: any two-element set.

\hypertarget{properties}{}\subsection*{{Properties}}\label{properties}

Suppose a category $\mathbf{C}$ has a subobject classifier; this entails some striking structural consequences for $\mathbf{C}$. We list a few here:

\begin{prop}
\label{regular}\hypertarget{regular}{}
Every [[monomorphism]] in $\mathbf{C}$ is a [[regular monomorphism]], i.e., is an equalizer of some pair of maps.

\end{prop}
\begin{proof}
For $\chi_i: X \to \Omega$ the characteristic map of a mono $i: A \to X$, we find that $i$ is the equalizer of a pair of maps $X \rightrightarrows \Omega$:

\begin{displaymath}
\itexarray{
 & & 1 \\
 & \mathllap{!} \nearrow & \downarrow \mathrlap{t} \\
X & \underset{\chi_i}{\to} & \Omega.
}
\end{displaymath}
\end{proof}
\begin{cor}
\label{}\hypertarget{}{}
$\mathbf{C}$ is balanced, i.e., a morphism in $\mathbf{C}$ is an isomorphism iff it is both [[monomorphism|monic]] and [[epimorphism|epic]].

\end{cor}
\begin{proof}
``Only if'' is trivial. The ``if'' comes from the fact that an epic (epimorphic) equalizer must be an isomorphism, for if $i: A \to X$ is the equalizer of $f, g: X \rightrightarrows Y$ and $i$ is epic, then $f = g$, whence $1_X$ is their equalizer, so $i: A \to X$ must have been an isomorphism.

\end{proof}
\begin{prop}
\label{}\hypertarget{}{}
Any two epi-mono factorizations of a map in $\mathbf{C}$ are canonically isomorphic.

\end{prop}
\begin{proof}
Suppose $i p = j q$ where $p, q$ are epic and $i, j$ are monic. Since $j$ is regular, it is the equalizer of some parallel pair $f, g$ as in the diagram

\begin{displaymath}
\itexarray{
A & \stackrel{p}{\to} & B & & \\ 
\mathllap{q} \downarrow & & \downarrow \mathrlap{i} & & \\ 
C & \underset{j}{\to} & D & \stackrel{\overset{f}{\to}}{\underset{g}{\to}} & E,
}
\end{displaymath}
so that $f i p = f j q = g j q = g i p$, whence $f i = g i$ since $p$ is epic, whence $i$ factors through $j$ as $j$ is the equalizer: $i = j k$ for some $k: B \to C$. Then also $k p = q$ since $j k p = i p = j q$ and $j$ is monic. We have that $k$ is monic since $i$ is, and $k$ is epic since $q$ is. Thus $k$ is an isomorphism.

\end{proof}
Already these results impose some tight restrictions on $\mathbf{C}$. We get some more by exploiting the internal structure of $\Omega$.

The subobject classifier always comes with the structure of an internal [[partial order|poset]]; that is, a relation $\subseteq\, \hookrightarrow \Omega\times\Omega$ which is internally reflexive, antisymmetric, and transitive. This can be constructed directly (see Proposition \ref{implication} below), or obtained via the [[Yoneda lemma]] since the collection of subobjects of any object is an external poset.

Similarly, since we assume that $\mathbf{C}$ is finitely complete, each subobject poset $Sub(X)$ has intersections (gotten as pullbacks or [[fiber products]] of pairs of monics $i: A \to X,j: B \to X$), and the intersection operation

\begin{displaymath}
\cap: Sub(X) \times Sub(X) \to Sub(X)
\end{displaymath}
is natural in $X$. Hence we have a family of maps

\begin{displaymath}
\cap: \hom(X, \Omega \times \Omega) \to \hom(X, \Omega)
\end{displaymath}
natural in $X$; by the [[Yoneda lemma]], we infer the presence of an internal intersection map

\begin{displaymath}
\wedge: \Omega \times \Omega \to \Omega
\end{displaymath}
making $\Omega$ an internal [[meet-semilattice]].

More significantly, $\Omega$ is an internal [[Heyting algebra]]. More accurately, it's a Heyting algebra provided it has joins; without joins it is a [[cartesian closed category|cartesian closed]] poset:

\begin{prop}
\label{implication}\hypertarget{implication}{}
There is an internal implication operator

\begin{displaymath}
\Rightarrow: \Omega \times \Omega \to \Omega
\end{displaymath}
uniquely specified by the internal condition

\begin{displaymath}
w \wedge u \leq v \qquad iff \qquad w \leq u \Rightarrow v.
\end{displaymath}
\end{prop}
\begin{proof}
Construct $\subseteq \hookrightarrow \Omega \times \Omega$ as the equalizer of the pair of maps

\begin{displaymath}
\Omega \times \Omega \stackrel{\overset{\pi_1}{\longrightarrow}}{\underset{\wedge}{\longrightarrow}} \Omega
\end{displaymath}
and then define $\Rightarrow: \Omega \times \Omega \to \Omega$ to be the characteristic map of $\subseteq \hookrightarrow \Omega \times \Omega$. Now if $\chi_u, \chi_v$ are two maps $X \to \Omega$, one calculates that $w \hookrightarrow X$ is contained in the subobject classified by $\chi_u \Rightarrow \chi_v$ iff $w \cap u = w \cap u \cap v$, which is just a way of saying $w \cap u \leq v$.

\end{proof}
\begin{cor}
\label{}\hypertarget{}{}
In every subobject poset $Sub(X)$, meets distribute over any joins that exist.

\end{cor}
\begin{proof}
Because $U \cap -$ is left adjoint to the external operator $U \Rightarrow -$ on $Sub(X)$, it preserves any joins that happen to exist in $Sub(X)$.

\end{proof}
Normally these results are proved in the context of [[toposes]], where we may say for example that $\Omega$ is an internal [[Boolean algebra]] if and only if the topos is [[Boolean topos|Boolean]]. But as the proofs above indicate, we need only exploit the definition of subobject classifier making reference only to finite limit structure.

In a topos, the subobject classifier $\Omega$ is always [[injective object|injective]], and, so is the \emph{power object} $\Omega^X$ for every object $X$ (See at [[injective object\#Exponential\_injectives|injective object]] for some of the details). In particular, every object $X$ embeds into an injective object by the singleton monomorphism $X\to\Omega^X$: `A topos has enough injective objects!'. More generally, injective objects in a topos are precisely the ones that are retracts of some $\Omega^X$ (Cf. \hyperlink{Borceux3}{Borceux 1994}, p.315; \hyperlink{MoerdijkMacLane}{Moerdijk-MacLane 1994}, p.210).

\hypertarget{johnstones_exercise}{}\subsubsection*{{Johnstone's exercise}}\label{johnstones_exercise}

A curiosity from Johnstone's \hyperlink{J77}{Topos Theory}, posed as an exercise, is that any monomorphism $\Omega \to \Omega$ is an isomorphism and even an [[involution]]. Thus $\Omega$ is a [[Hopfian object]].

An online proof may be found \href{https://ncatlab.org/toddtrimble/published/Monic+endomorphisms+on+the+subobject+classifier}{here}.

\hypertarget{categories_with_a_contractible_subobject_classifier}{}\subsection*{{Categories with a contractible subobject classifier}}\label{categories_with_a_contractible_subobject_classifier}

Suppose a [[topos]] $\mathcal{E}$ has a [[connected component|connected components functor]] $\Pi$ [[left adjoint]] to $\Delta\dashv \Gamma$ assigning to an object $X$ the set of it connected components. We call $X$ [[connected object|connected]] if $\Pi(X)$ is a [[singleton]] and [[contractible space|contractible]] if $\Pi(X^Y)$ is connected for all $Y\in\mathcal{E}$. It can be shown that provided $\Pi$ preserves [[finite products]], $\Omega$ is contractible iff $\Omega$ is connected which in turn implies the same for all other [[injective object|injective objects]] (see at [[sufficiently cohesive topos]]).

Now the subobject classifier $\Omega$ has always two disjoint points $\mathsf{true}$, $\mathsf{false}$ whence provided it is connected we can view it (together with its Heyting algebra structure) has a (highly nonlinear) generalized [[interval object]] and define a notion of [[homotopy]] relative to $\Omega$. The intuition here is that [[true|truth]] and [[false|falsity]] are continuously connected in such toposes and blend into each other, endowing (the logic in) $\mathcal{E}$ with a certain [[Hegel|Hegelian]] flavor. The contractability of $\Omega$ was taken as a key property of a [[gros topos]] of spaces by [[William Lawvere]]. Further information on this particular class of [[cohesive topos|cohesive toposes]] and discussion of properties of $\Omega$ relevant in this context is at [[sufficiently cohesive topos]].

\hypertarget{categories_without_subobject_classifiers}{}\subsection*{{Categories without subobject classifiers}}\label{categories_without_subobject_classifiers}

As the previous section indicates, having a subobject classifier is a very strong property of a category and ``most'' categories with finite limits don't have one.

For example, there is an easy condition ensuring a category\footnote{We mean a nontrivial category, obviously, where ``trivial'' here means every object is terminal.}  with a terminal object can't have a subobject classifier: if there are no nonidentity morphisms out of the terminal object. This includes the following examples.

\begin{itemize}%
\item Any top bounded partial order.


\item In $Ring$, the [[category of rings]], there are no nonidentity morphisms out of the terminal object the [[zero ring]].



\end{itemize}
Here's another obstacle:

\begin{itemize}%
\item If an [[abelian category]] had a subobject classifier, every subobject of every object would have to be the kernel of its classifying map. In particular, the subobject $0$ of every object $A$ would have to be the kernel of its classifying map, so that every object in this abelian category would embed into the subobject classifier $\Omega$ (including, say, all small products of $\Omega$ with itself) which in nontrivial cases would cause size issues.

\end{itemize}
But a real killer is the fact that all monos are regular, or its consequences of the category being balanced and uniqueness of epi-mono factorizations:

\begin{itemize}%
\item The categories [[Pos]], [[Cat]], [[Top]] are not balanced (consider the map from a discrete structure on a set to an indiscrete structure on the same set, induced by the identity function). The category [[CMon]] is not balanced (consider the inclusion $\mathbb{N} \hookrightarrow \mathbb{Z}$ which is epic).

\end{itemize}
Even though all monos in [[Grp]] are regular, we can kill off $Grp$ by observing that if $t: 1 \to \Omega$ were a subobject classifier, the proof of Proposition \ref{regular} indicates that every mono $i: A \to X$ would have to be the [[kernel]] of $\chi_i$. But not all monos in $Grp$ are kernels.

Perhaps an even more decisive killer is the observation that meets distribute over (arbitrary) joins in subobject orders. This eliminates many categories from consideration:

\begin{itemize}%
\item Lattices of subobjects in $Grp$ or $Ab$ are rarely distributive.


\item For any nontrivial category with [[biproducts]], there are non-distributive subobject lattices. Take any object $A$, so that we have three subobjects $i_1: A \to A \oplus A$, $i_2: A \to A \oplus A$, and $\Delta: A \to A \oplus A$. Then $i_1 \vee i_2 = \top$, whereas $i_1 \wedge \Delta = \bot = i_2 \wedge \Delta$. Under distributivity we have

\begin{displaymath}
\Delta = \Delta \wedge \top = \Delta \wedge (i_1 \vee i_2) = (\Delta \wedge i_1) \vee (\Delta \wedge i_2) = \bot \vee \bot = \bot
\end{displaymath}
but $\Delta = \bot$ forces $A = 0$. So the only such category that can have a subobject classifier is trivial.



\end{itemize}
\hypertarget{generalizations_object_classifier}{}\subsection*{{Generalizations: object classifier}}\label{generalizations_object_classifier}

In higher topoi the subobject classifiers are the [[generalized universal bundle|universal fibrations]]:

in the [[n-topos|(n+1)-topos]] $n Cat$ of [[n-category|n-categories]] the subobject classifier is the [[stuff, structure, property|forgetful functor]]

\begin{displaymath}
n true : (n-1)Cat_* \to (n-1)Cat
\end{displaymath}
from the $n$-category of [[pointed object|pointed]] $(n-1)$-categories to that of $(n-1)$-categories, which forgets the point.

This is described in more detail at [[generalized universal bundle]]. See also the discussion at [[stuff, structure, property]].

In fact, using the notion of [[(-1)-category]] the subobject classifier in [[Set]] does fit precisely into this pattern:

the 2-element set $\mathbf{2}$ may be regarded as the [[0-category]] of [[(-1)-category|(-1)-categories]] (of which there are two) and the one-element set $*$ is the [[0-category]] of [[pointed object|pointed]] [[(-1)-category|(-1)-categories]], of which there is one.

In the context of [[(∞,1)-topos]] [[Higher Topos Theory|theory]] subobject classifiers are discussed in section 6.1.6 of

\begin{itemize}%
\item [[Jacob Lurie]], \emph{[[Higher Topos Theory]]} , Princeton UP 2009.

\end{itemize}
Whereas for 1-toposes the \emph{subobject classifier} is the key structural ingredient (besides the exactness properties), in [[higher topos theory]] this role is taken over by the [[object classifier]], as pointed out in Lurie (2009).

\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item [[quasitopos]] where a weaker notion of subobject classifier only classifies [[strong monomorphism]]s.


\item [[object classifier]]


\item [[type of propositions]], [[type of types]]


\item [[classifying space]], [[classifying stack]], [[moduli space]], [[moduli stack]], [[derived moduli space]]


\item [[classifying topos]]


\item [[universal principal bundle]], [[universal principal ∞-bundle]]


\item [[classifying morphism]]


\item [[sufficiently cohesive topos]]


\item [[localic topos]]



\end{itemize}
\hypertarget{references}{}\subsection*{{References}}\label{references}

The concept was introduced in

\begin{itemize}%
\item [[William Lawvere]], \emph{Quantifiers and sheaves} , Actes Congrès intern. math. \textbf{1} (1970), pp.329-334. (\href{http://www.mathunion.org/ICM/ICM1970.1/Main/icm1970.1.0329.0334.ocr.pdf}{pdf})

\end{itemize}
Discussion of the concept can be found in the usual suspects

\begin{itemize}%
\item [[Francis Borceux]], \emph{Handbook of Categorical Algebra 3} , Cambridge UP 1994.


\item R. Goldblatt, \emph{Topoi - The Categorical Analysis of Logic}, 2nd ed. North-Holland Amsterdam 1984. (Dover reprint New York 2006; \href{http://projecteuclid.org/euclid.bia/1403013939}{project euclid})


\item [[Peter Johnstone]], \emph{Topos Theory} , Academic Press New York 1977.


\item [[Peter Johnstone]], \emph{Sketches of an Elephant I} , Oxford UP 2002.


\item [[Saunders MacLane]], [[Ieke Moerdijk]], \emph{[[Sheaves in Geometry and Logic]]} , Springer Heidelberg 1994. (section I.3-4)



\end{itemize}
See also

\begin{itemize}%
\item [[Francis Borceux]], \emph{When is $\Omega$ a cogenerator in a topos ?} , Cah. Top. Géom. Diff. Cat. \textbf{XVI} no.1 (1975) pp.3-15. (\href{http://www.numdam.org/item?id=CTGDC_1975__16_1_3_0
}{numdam})

\end{itemize}
[[!redirects subobject classifiers]]



\end{document}