TITLE: Compute $\sqrt[7]{0.999}$ to three decimal places.(From Gelfand's Algebra text.)
QUESTION [4 upvotes]: After a brief introduction to roots(imaginary numbers were not introduced yet), this question is asked. I am apparently expected to find the answer using elementary algebraic manipulation. I have tried playing around with the problem and observed
$\sqrt[7]{0.999} = {(1-\frac{1}{1000}})^\frac{1}{7} = (\frac{(3)^3(37)}{10^3})^\frac{1}{7}$
But do not get how to solve the problem.Any helpful ideas will be appreciated.
PS: Inequalities and binomial series were not yet introduced in the text.I have only a rudimentary knowledge of maths, so keep the answers simple and within the scope of elementary algebra.
I have edited this problem,adding context. Do not penalize previous answers which used calculus. :)

REPLY [3 votes]: Rob Arthan wrote in a comment: "What is clear is that Gelfand expected his readers to be prepared to do the long multiplications that show that $0.9995^3<0.999$ (no calculus required!)".
To fill in this gap, I'd like to note that we don't actually have to do the multiplication. Note that $0.9995 = 1 - 0.005$.  Therefore we have
$0.9995^3 = (1-0.005)^3 = 1 - 3 \times 0.005 + 3 \times 0.005^2 - 0.005^3$
by the binomial theorem.  (If one has not seen the binomial theorem, it's not hard to just expand $(1-x)^3$ "by hand" and plug in $x = 0.005$.)  But $3 \times 0.005^2 < 0.005$.  Thus
$1 - 3 \times 0.005 + 3 \times 0.005^2 - 0.005^3 < 1 - 3 \times 0.005 + 0.005 - 0 = 0.999$
which proves the desired result.


TITLE: Does this "local time" type limit exist a.e. for $C^2$ functions?
QUESTION [7 upvotes]: For $f: \mathbb R^n \to \mathbb R$ a locally integrable function, $\varepsilon \in (0, \infty)$, and $x \in \mathbb R^n$, define $I(f, \varepsilon, x)$ to be the averaged integral of $f$ over $B_{\varepsilon} (x)$, the ball of radius $\varepsilon$ around $x$. That is,
$$I(f, \varepsilon, x) := \frac{1}{\mu(B_\varepsilon (x))} \int_{B_\varepsilon (x)} f(y) \, dy$$
Define
$$
K(f, \varepsilon, x) :=
\begin{cases}
1 & \text{if }\; I(f, \varepsilon, x) > f(x),\\
-1 & \text{if }\; I(f, \varepsilon, x) < f(x),\\
0, &\text{if }\; I(f, \varepsilon, x) = f(x).\\
\end{cases}
$$
Finally, let
$$
H(f, \varepsilon, x) = \dfrac{1}{\varepsilon} \int\limits_{(0, \varepsilon]} K(f, s, x) ds
$$
Intuitively, $H$ is the weighted average amount of time a function spends greater than (resp. less than) its value at a point, in an infinitesimal neighbourhood of said point.
Question: Let $f$ be a $C^2$ function. Is it true that $\lim_{\varepsilon \to 0} H(f, \varepsilon, x)$ exists for almost every $x \in \mathbb R^n$?
Remarks:

A sample path of Brownian motion provides a counterexample in the $C^0$ case, as shown here. So $C^2$ is in some sense sharp.

The existence of the limit is immediate on the regions on which $f$ is super/sub-harmonic, as well as on the interior of the region on which $f$ is harmonic.

REPLY [3 votes]: Even $C^\infty$ isn't enough and even on $\mathbb R$. Take any nowhere dense compact set $A\subset\mathbb R$ of positive measure and set $f=0$ on $A$. Now let $I_k$ be the complementary intervals to $A$ (ignore the two rays). Draw some positive bumps on the middle halves of $I_1, I_2,\dots I_n$. If $n$ is large enough, then $K(f,s,x)$ will be $1$ on $[1/10,1]$ for all $x\in A$ and no sufficiently small in $C^0$ perturbation of $f$ will change that. However, the function is still identically $0$ in some small $\delta_1$-neighborhood of $A$. Now draw some much smaller negative bumps still deep inside $I_k$'s but closer to the endpoints on both sides. Then, using finitely many (but sufficiently many) intervals, you'll achieve that $K(f,s,x)=-1$ on $[\delta_1/10,\delta_1]$ for all $x\in A$ and, again, the property is stable and we still have $f=0$ in some $\delta_2$-neighborhood of $A$. Then do it again and again alternating between positive and negative bumps.


TITLE: Bayes Rule in 2 Fair and 1 Biased coin
QUESTION [0 upvotes]: I was watching this video on Khan Academy about condition probability where they demonstrated a problem using a tree. I tried to solve that problem using Bayes rule, but my answer doesn't match the one presented in the video.
The problem: There are $2$ fair coins and 1 biased coin. The biased coin has a $2/3$ probability of landing a heads. All three coins are put in a bag. One coin is picked out of the bag at random and flipped. The result is Heads. What is the probability that the coin picked out of the bag was biased?
The result reported on the video is $4/10$.
I tried to use Bayes rule on this, but this is what I have come with so far...
Let $A$ be the event that the coin picked out of the bag is biased
Let $B$ be the event that a coin flip results in heads
$P(A) = 1/3$ because there are three coins and only one biased coin
$P(B\mid A) = 2/3$ because the biased coin has a $2/3$-rd chance of landing a heads
$P(B) = ?$
$P(A\mid B) = ?$
They're asking for $P(A\mid B)$. I can't figure out $P(B)$. How do I proceed?

REPLY [1 votes]: $$P(B\mid A)\times(P(A)=P(A\cap B)=P(A\mid B)\times P(B)\\
P(A\mid B)=\frac{2}{3}\frac{1}{3}\frac{1}{P(B)}=\frac{2}{9P(B)}\\
P(B)=P(B\mid A)\times P(A) + P(B\mid A^C)\times P(A^C) = \frac{1}{9}+\frac{1}{3}=\frac{4}{9}\\
P(A\mid B) = \frac{2}{9\times \frac{4}{9}}=\frac{1}{2}
$$
Hope it's clear enough.


TITLE: Confusion regarding enthalpy and heat
QUESTION [1 upvotes]: I'm having difficulty resolving three statements from my thermodynamics class.
1) The enthalpy difference, ΔH, between two states of a system can only take one value, since H is a state function.
2) The heat exchanged when taking the system between two states depends on the path, e.g. a reversible transformation will lead to a different quantity of heat being absorbed than an irreversible one, even if the initial and final states are the same.
3) The enthalpy change is equal to the heat exchanged in a transformation at constant pressure.
How can ΔH be a state function and be path-independent, if according to 3. it is numerically equal to a quantity that is, in general, not path-independent?

REPLY [3 votes]: How can ΔH be a state function and be path-independent, if according to 3. it is numerically equal to a quantity that is, in general, not path-independent?

Before getting into the case of change in enthalpy, I would like to introduce a similar confusion, which is more basic. Consider the first law of thermodynamics for a reversible process:
$$\bar{d}Q_{rev}=dU-PdV$$
where the "bar" sign indicates that it is not exactly differentiable, $dU$ is the change in internal energy and $PdV$ is the work done on the system for an infinitesimal change in volume at a constant pressure.
Internal energy is a state function. If there is no change in heat happened during the process as in the case of an adiabatic one, then we get
$$dU=PdV$$
There comes the confusion. The work done on the system depends on the path traversed by the system (as it is interpreted as the area enclosed by the P-V curve). However, $dU$ does not depend on the path the system followed, but only on the initial and final states. Then how the equality holds? The answer to this question gives the answer to your question.
The answer becomes clear if one solves for the expression of work in an adiabatic process:
$$W_{ad}=\frac{K\left(V_f^{1-\gamma}-V_i^{1-\gamma}\right)}{1-\gamma}$$
where, $\gamma$ and $K$ are constants. As you can see, the work done depends on the initial and final states of the volume. Hence in this case, the work done appears as a state function, due to it's equality with change in internal energy.
Now, to your question.
Enthalpy ($H$) is the measure of total heat content of the system. It is defined as
$$H=U+PV$$
the change in enthalpy is hence given by
$$\Delta H=\Delta U+\Delta (PV)$$
At constant pressure,
$$\Delta H=\Delta U+P\Delta V=\bar{d}Q_{rev}$$
Or, in general
$$\Delta H=\bar{d}Q_{rev}+V\Delta P$$
A close look at the above equations reveals that the enthalpy is a state function and as you can see, the enthalpy change depends on the change in internal energy (which is a state function) and on the change in volume between the initial and final states (again another state function as it is a thermodynamic coordinate). Hence the enthalpy change is a state function. However, heat is not. But it doesn't mean that enthalpy change is not a state function. If that's the case, why should we write them as separate quantities even though the equality holds?
The above equation means that any change in the heat supplied to the system (which is not a state function) will be utilized by the system, under suitable conditions, for the change of state of a system from one to another, both being well-defined states. That is, if you reverse the process, by changing enthalpy into heat, the system will give out the heat by dropping back to the initial state.
If you supply heat, the system stores it in such a way that it is moved to another well defined equilibrium state and leaves no trace on which path the process happened. The enthalpy change is a property of the system and it doesn't care what type of energy you supplied to create that change. The right hand side of the equation, on the other hand, is what you give as an external parameter. They are not the property of the system and hence not, by definition, is a state function.
Conclusion: The equality just means only the numerical equivalence between the two quantities on it's either sides. A quantity is a state function if that quantity represents the energy stored in the system. The external supplies are not properties of the system like work, heat etc.


TITLE: How can I prove this property of root's multiplicity, for also non-polynomial function?
QUESTION [1 upvotes]: I have this definition of multiplicity of a root:

A root $x_0$ of the equation $F(x)=0$ has multiplicity k if $F^{k-1}(x_0)=0$ but $F^{[k]}(x_0)\neq 0$. Here $F^{[k]}$ is the $k^{th}$ derivative of $F$ and $F^{[0]}=F$.

From: L. Devaney, A first course in chaotic dynamical systems
I want to demonstrate that also the derivatives from [1] to [k-2] in $x_0$ are 0. How can I prove this property for also non-polynomial function?
My ultimate aim is demonstrate that if $x_0$is a root of multiplicity k for F, then F(x) may be written in the form $F(x)=(x-x_0)^{k}G(x)$.

REPLY [0 votes]: HINT: Thanks to Taylor series, we can express almost all non-polynomial functions as polynomial functions. However one must check beforehand whether the function at all possesses multiple roots.


TITLE: Pizza combinations possible given our options
QUESTION [3 upvotes]: I own a pizza shop and have tried to come up with the different possibilities of pizza options available given our toppings for any given pizza.  We have 4 crust options thin, regular, thick,gluten free we then have six (6) sauces plus no sauce and can be split 1/2 and 1/2, we have three cheese options, plus no cheese and can be split 1/2 and 1/2, 9 meat options 1/2 and 1/2, 9 vegetable options 1/2 and 1/2, 2 fruit options 1/2 and 1/2, 4 fish options 1/2 and 1/2, 4 seasoning options for the crust 1/2 and 1/2.  We also allow for these options to be used on 1/2 of any pizza excluding the 3 crust options for the crust must be the same for the complete pizza no matter what toppings are placed on it.  I am trying to figure out a baseline of just who many combinations we offer of pizza from our menu.  Thank you

REPLY [0 votes]: Total Pizzas (Bold Lines are What I've Assumed): 3 sextillion, 615 quintillion, 561 quadrillion, 838 trillion, 447 billion, 72 million, 116 thousand, 736
Far less than the number of stars in the universe.
Multiply together the number of options in the selected lines below to get these total combinations. For lines with (each half) multiply the number twice.
Crust Options if gluten-free thickness cannot be specified: 4
Crust Options if gluten-free thickness can be specified: 8
Sauce Options if at most 1 Permitted per half (Each Half): $7$
Sauce Options if any number Permitted Per half (Each Half): $2^7=128$
Cheese Options if at most 1 permitted per half (Each Half): $4$
Cheese Options if More than 1 Allowed (Each Half): $2^4=16$
Topping + Seasoning Options assuming any number allowed (Each Half):
$2^{(9+9+2+4+4)}=2^{28}=268435456$


TITLE: How to find the the basis of $W^{\bot}$ if $W=\operatorname{span}\{(1,1,0,0), (0,0,1,1)\}$ is a subspace of $\mathbb R^4$?
QUESTION [1 upvotes]: Find the the basis of $W^{\bot}$ if $W=\operatorname{span}\{(1,1,0,0), (0,0,1,1)\}$ is a subspace of $\mathbb R^4$ using Gram-Shmidt process (GSP).

Let $u_1=(1,1,0,0)$ and $u_2=(0,0,1,1)$.
According to GSP $u_1$ stays as is.
Regarding $u_2$:
$$
u_2=u_2-\frac{u_2u_1}{||u_1||}u_1
$$
But $u_2u_1=0$ so $u_2=u_2$. Which means that $W=W^{\bot}$ which is not true as $W \oplus W^{\bot}=\mathbb R^4$ and the answer is that the basis for $W^{\bot}$ is $\{(1,-1,0,0),(0,0,1,-1)\}$.
What am I doing incorrectly?

REPLY [2 votes]: Suppose you have a basis of $\Bbb R^4$ such that two vector are a basis of $W$. Then if you apply the Gram-Schmidt first to the basis of $W$ you get a new orthonormal basis of $W$.
Then continue applying the Gram-Schmidt procedure to the other two vectors and you get a basis for $W^\bot$.
Because there are a lot of boring calculations you can use wolfram-alpha or some other CAS for this common task. By example take a look here.


TITLE: What is potential of an isolated conductor?
QUESTION [1 upvotes]: I mean potential of any thing requires a reference point to be defined. Potential at a distance r from a point charge q is given by;
V=electrostatic constant × q/r
;but I dont understand how can I calculate potential of an isolated conductor or of any isolated object using this definition.
I have been trying to understand self-capacitance which is the amount of charge to raise the potential of an isolated conductor by one volt. But this needs me to understand what is potential of an isolated conductor. Means, I have got to know how is it defined? Don't direct me to the google or wikipedia for I have tried my best to find about it on these sites already. Although wikipedia got very close to defining the potential of isolated conductor. It also tries to tell about the reference point but I still don't understand the story. I want a very simple illustration.

REPLY [0 votes]: A point in an electric field is associated with electric field intensity and electric potential. The electric potential of the point is the electrostatic potential energy of unit positive charge kept at that point (equal to work done in bringing the unit positive charge from infinity to the point).
An isolated charged conductor will produce an electric field around itself due to its charge. The electric field ranges from its surface to infinity.
Potential of a conductor is simply the potential of the region which it occupies. This potential exists due to its own electric field. We can define a unique potential for a conductor as the potential throughout that region will be the same as electric field inside the conductor is zero (or a conductor can be called as an equipotential object).


text:
\begin{document}

\begin{frontmatter}
\title{Optimization via Low-rank Approximation for Community Detection in Networks}
\runtitle{Optimization via Low-rank Approximation}

\begin{aug}
\author{\fnms{Can M.} \snm{Le},\ead[label=cl]{canle@umich.edu}}
\author{\fnms{Elizaveta} \snm{Levina},\ead[label=el]{elevina@umich.edu}}
\and
\author{\fnms{Roman} \snm{Vershynin}\ead[label=rv]{romanv@umich.edu}}

\runauthor{Le et al.}

\affiliation{University of Michigan}

\address{311 West Hall, 1085 S. University Ave.\\
  Ann Arbor, MI 48109-1107 \\
\printead{cl}
}

\address{311 West Hall, 1085 S. University Ave.\\
  Ann Arbor, MI 48109-1107 \\
\printead{el}
}

\address{2074 East Hall, 530 Church St.\\
Ann Arbor, MI  48109-1043\\
\printead{rv}
}

\end{aug}

\begin{abstract}
Community detection is one of the fundamental problems of network analysis, for which a number of methods have been proposed.  Most model-based or criteria-based methods have to solve an optimization problem over a discrete set of labels to find communities, which is computationally infeasible.
Some fast spectral algorithms have been proposed for specific methods or models, but only on a case-by-case basis.   Here we propose a general approach for maximizing a function of a network adjacency matrix over discrete labels by projecting the set of labels onto a subspace approximating the leading eigenvectors of the expected adjacency matrix. This projection onto a low-dimensional space makes the feasible set of labels much smaller and the optimization problem much easier.   We prove a general result about this method and show how to apply it to several previously proposed community detection criteria, establishing its consistency for label estimation in each case and demonstrating the fundamental connection between spectral properties of the network and various model-based approaches to community detection. Simulations and applications to real-world data are included to
demonstrate our method performs well for multiple problems over a wide range of parameters.
\end{abstract}

\begin{keyword}[class=AMS]
\kwd[Primary ]{62E10}
\kwd[; secondary ]{62G05}
\end{keyword}

\begin{keyword}
\kwd{Community detection}
\kwd{Spectral clustering}
\kwd{Stochastic block model}
\kwd{Social networks}
\end{keyword}

\end{frontmatter}

\section{Introduction}\label{Sec:Intro}
\input{Section1-Introduction}

\section{A general method for optimization via low-rank approximation}\label{Sec:OptViaLRApp}
\input{Section2-GeneralMethod}

\section{Applications to community detection}\label{Sec:AppToComDet}
\input{Section3-ApplicationToNetwork}

\section{Numerical comparisons}\label{Sec:Simulation}
\input{Section4-Simulation}

\section*{Acknowledgments}
We thank the Associate Editor and three anonymous referees for detailed and constructive feedback which led to many improvements.  We also thank Yunpeng Zhao (George Mason University) for sharing his code
for the tabu search,  and Arash A. Amini (UCLA) for sharing his code for the pseudo-likelihood
methods and helpful discussions. E.L. is partially supported by NSF grants DMS-01106772 and
DMS-1159005.  R.V. is partially supported by NSF grants DMS 1161372, 1001829, 1265782 and USAF
Grant FA9550-14-1-0009.

\bibliography{allref}
\bibliographystyle{abbrv}
\appendix
\input{Section5-Appendix}
\input{supplement}

\end{document}

config: arxiv


TITLE: Proof that an $n \times n$ real symmetric matrix has $n$ real eigenvalues
QUESTION [4 upvotes]: How to show that an $n \times n$ real symmetric matrix has $n$ real eigenvalues
$$
\lambda_n \geqslant \dots \geqslant  \lambda_1
$$
with corresponding eigenvectors $\mathbf v_n, \dots,\mathbf v_1$ such that
$$
\mathbf v_i^T \mathbf v_j = \delta_{ij}.
$$
I am struggling a bit on how to start this proof. I tried looking online but could not find anything. Perhaps I am looking in the wrong direction, would it be the same to prove that such a matrix would have $n$ real orthogonal eigenvectors and thus $n$ real eigenvalues? Hints on where to start this proof would be appreciated.

REPLY [3 votes]: Since $|\lambda I-A|$ is of degree $n$, it has $n$ roots and so $A$ has $n$ eigenvalues.
Let $\lambda_i$ be any eigenvalue of $A$ and $x\ne 0$ be an eigenvector for $\lambda_i$. Then $Ax=\lambda_i x$. So $\overline{x}^TAx=\lambda_i \overline{x}^Tx$. By taking conjugate transpose of it, we have
$$
\overline{x}^T\overline{A}^Tx=\overline{x}^TAx=\overline{\lambda_i}\overline{x}^Tx=\lambda_i \overline{x}^Tx
$$
So $\overline{\lambda_i}={\lambda_i}$ for $\overline{x}^Tx>0$. Thus $\lambda_i$ is real.
Since all eigenvalues of $A$ are real, so are eigenvectors of $A$. Let $x_1$ be a real normalized eigenvector for $\lambda_1$, i.e. $Ax_1=\lambda_1 x_1$. Then $x_1$ can be expanded to an orthonormal base of $x_1, \cdots, x_n$. Let $S=(x_1, \cdots, x_n)$. Then $S^{-1}=S^T$. Note that
$$
AS=A(x_1,x_2,\cdots, x_n)=S\pmatrix{\lambda_1 & *\\ 0& B_1}=SB
$$
So $S^{-1}AS=S^TAS=B$. Moreover, since $A$ is symmetric, $B^T=B$, i.e.
$$
B=\pmatrix{\lambda_1 & 0\\ 0& B_1}
$$
where $B_1$ is $(n-1)\times (n-1)$ and symmetric. By induction hypothesis, there is an orthogonal matrix $S_1$ that $B_1S_1=S_1\Lambda_1$, where $\Lambda_1$ is diagonal. Hence
$$
\pmatrix{\lambda_1 & 0\\ 0& B_1}\pmatrix{1 & 0\\ 0& S_1}=\pmatrix{1 & 0\\ 0& S_1}\pmatrix{\lambda_1 & 0\\ 0& \Lambda_1}
$$
Let
$$
B=\pmatrix{\lambda_1 & 0\\ 0& B_1}\quad\text{}\quad Q=\pmatrix{1 & 0\\ 0& S_1}\quad\text{}\quad \Lambda=\pmatrix{1 & 0\\ 0& \Lambda_1}
$$
Then $BQ=Q\Lambda$. Let $P=SQ$. Then $P$ is orthogonal. Thus we have
$$P^TAP=\Lambda$$
Clearly, $\Lambda=\operatorname{Diag}{(\lambda_1, \cdots, \lambda_n)}$ and each column of $P$ is an eigenvector of $A$.


TITLE: How can I find the analytical solution for this optimization problem?
QUESTION [1 upvotes]: How to find the analytical solution for this optimization problem?
$$
\begin{align}
& \underset{x,y,z}{\text{maximize}} & (1+\frac{x}{1+z})(1+\frac{y}{1+z})\\
& \text{such that} & 0\leq x\leq x^+\\
&& 0\leq y\leq y^+\\
&& 0\leq z\leq z^+\\
&& x,y,z\in\mathbb{R}\\
\end{align}
$$
where $x^+$,$x^+$ and $z^+$ are positive numbers.

REPLY [3 votes]: $$(1+\frac{x}{1+z})(1+\frac{y}{1+z})\le (1 + x) (1 +y) \le (1 + x^+)(1 + y^+)$$
The function achieves the maximum at $(x^+, y^+, 0)$


text:
\chapter{Semantic enrichment of data science code}
\label{ch:semantic-enrichment}

Compared to the programs from which they are derived, the raw flow graphs
generated by the program analysis system are more readily inspected, reasoned
about, and manipulated by machines. However, each flow graph is still expressed
in the vernacular of a specific programming language and set of libraries. This
state of affairs is unsatisfactory because the computations made by data
analyses are rarely inseparable from the idioms of particular languages and
packages; rather, the data analysis and its software dependencies are thought to
\emph{instantiate}, in a concrete, computable form, the abstract mathematical,
statistical, and algorithmic concepts of data science. The detailed way in which
this instantiation happens is in many respects arbitrary, depending on
conventions adopted by the authors and the community at large.

Semantic enrichment aims to bring out the abstract concepts that underlie data
science code, in a manner that is transparent to machines and insensitive to
implementation details. Specifically, semantic enrichment is the process of
transforming the raw flow graphs from the previous chapter into \emph{semantic
  flow graphs}, whose types and functions belong to the controlled vocabulary of
the Data Science Ontology. This process was outlined in the Introduction, where
the semantic flow graph corresponding to all three of
\cref{fig:toy-kmeans-scipy,fig:toy-kmeans-sklearn,fig:toy-kmeans-r} was shown in
\cref{fig:toy-kmeans-semantic}. Revisiting another small example,
\cref{fig:toy-regression-sklearn-semantic} below shows the semantic flow graph
derived from the previous chapter's raw flow graph of
\cref{fig:toy-regression-sklearn-raw}. Another, more realistic example will be
shown later.

\begin{figure}
  \centering
  \input{wiring-diagrams/semantic-enrichment/regression-sklearn-metrics.semantic}
  \caption{Semantic flow graph for \cref{lst:toy-regression-sklearn} and
    \cref{fig:toy-regression-sklearn-raw}}
  \label{fig:toy-regression-sklearn-semantic}
\end{figure}

In this chapter, the Data Science Ontology and its use in semantic enrichment
are introduced and informally described. The ontology and the semantic
enrichment process are then formalized mathematically. The concepts in the
ontology form a cartesian closed category with implicit conversion, while the
ontology's code annotations partially define a functor between two such
categories. Finally, the raw and semantic flow graphs are formalized as
morphisms in categories of elements.

\section{The Data Science Ontology}
\label{sec:dso}

The Data Science Ontology is a nascent knowledge base about statistics, machine
learning, and data processing. It aims to support automated reasoning about data
science software.

The ontology is comprised of concepts and annotations. \emph{Concepts} catalog
the abstract entities of data science, such as data tables and statistical
models, as well as the processes that manipulate them, such as loading data from
a file or fitting a model to data. Reflecting the intuitive distinction between
``things'' and ``processes,'' concepts bifurcate into two kinds: types and
functions. The terminology agrees with that of functional programming. Thus, a
\emph{type} represents a kind or species of thing in the domain of data science.
A \emph{function} is a functional relation or mapping from an input type, the
\emph{domain}, to an output type, the \emph{codomain}. In this terminology, the
concepts of a data table and of a statistical model are types, whereas the
concept of fitting a predictive model is a function that maps an unfitted
predictive model, together with predictors and response data, to a fitted
predictive model.

As a modeling assumption, software packages for data science, such as Pandas and
Scikit-learn, are regarded as instantiating the concepts of the ontology.
\emph{Annotations} say how this instantiation occurs by mapping types and
functions in software packages onto type and function concepts in the ontology.
To avoid confusion between levels of abstraction, we call the former
``concrete'' and the latter ``abstract.'' Thus, a type annotation maps a
concrete type---a primitive type or user-defined class in Python or R---onto an
abstract type---a type concept. Likewise, a function annotation maps a concrete
function onto an abstract function. As in \cref{ch:program-analysis}, concrete
function are construed in the broadest possible sense to include any programming
language construct that ``does something'': standalone functions, instance
methods, attribute getters and setters, and so on.

The division of the ontology into concepts and annotations on the one hand, and
into types and functions on the other, leads to a two-way classification.
\cref{tbl:ontology-classification} lists several examples of each of the four
combinations, drawn from the Data Science Ontology.

\begin{table}
  \centering
  \caption{Example concepts and annotations from the Data Science Ontology}
  \label{tbl:ontology-classification}
  \begin{tabular}{lp{2in}p{2in}}
    & \textbf{Concept} & \textbf{Annotation} \\ \toprule
    \textbf{Type} &
      data table &
      pandas data frame \\ \cmidrule{2-3}
    & statistical model &
      scikit-learn estimator \\ \cmidrule{2-3}
    \textbf{Function} &
      reading a tabular data file &
      \texttt{read\_csv} function in pandas \\ \cmidrule{2-3}
    & fitting a statistical model to data &
      \texttt{fit} method of scikit-learn estimators \\ \bottomrule
  \end{tabular}
\end{table}

Significant modeling flexibility is needed to faithfully translate the widely
varying interfaces of statistical software into a single set of concepts.
\cref{lst:toy-kmeans-scipy,lst:toy-kmeans-sklearn,lst:toy-kmeans-r} show, for
example, that the concept of $k$-means clustering can be instantiated in
software in many different ways. To accommodate this diversity, function
annotations may map a single concrete function onto an arbitrary abstract
``program'' comprised of function concepts. Three function annotations related
to the fitting of $k$-means clustering models are shown in
\cref{fig:annotations-kmeans}.

\begin{figure}
  \begin{subfigure}[b]{0.5\textwidth}
    \centering
    \input{wiring-diagrams/semantic-enrichment/annotation-python-scipy-kmeans2}
    \caption{\texttt{kmeans2} in SciPy}
    \label{fig:annotation-python-scipy-kmeans}
  \end{subfigure}
  \begin{subfigure}[b]{0.25\textwidth}
    \centering
    \input{wiring-diagrams/semantic-enrichment/annotation-python-sklearn-fit}
    \caption{\texttt{fit} in Scikit-learn}
    \label{fig:annotation-python-sklearn-fit}
  \end{subfigure}
  \begin{subfigure}[b]{0.25\textwidth}
    \centering
    \input{wiring-diagrams/semantic-enrichment/annotation-r-stats-kmeans}
    \caption{\texttt{kmeans} in R}
    \label{fig:annotation-r-stats-kmeans}
  \end{subfigure}
  \caption{Selected function annotations from the Data Science Ontology: (a)
    \texttt{kmeans2} function in SciPy (see \cref{lst:toy-kmeans-scipy});
    \texttt{fit} method of \texttt{BaseEstimator} class in Scikit-learn (see
    \cref{lst:toy-kmeans-sklearn}); (c) \texttt{kmeans} function in R's built-in
    \texttt{stats} package (see \cref{lst:toy-kmeans-r}).}
  \label{fig:annotations-kmeans}
\end{figure}

An \emph{ontology language} specifies what kind of abstract ``program'' is
allowed to appear in a function annotation. It can be helpful to think of the
ontology language as a minimalistic, typed, functional programming language. The
analogy is imperfect because the ontology language is simpler than any commonly
used programming language, being designed for knowledge representation rather
than actual computing.

The ontology language has a minimalistic type system, supporting product and
unit types as well as a simple form of subtyping. A \emph{basic type} is a type
that cannot be decomposed into simpler types. Basic types must be explicitly
defined. All other types are \emph{composite}. The \emph{product} of two types
$X$ and $Y$ is another type $X \times Y$. It has the usual meaning: an element
of type $X \times Y$ is an element of type $X$ \emph{and} an element of type
$Y$, in that order. Products of three or more types are defined similarly.
Product types are similar to record types in conventional programming languages,
such as a tuple or a named tuple in Python. There is also a \emph{unit type} $1$
inhabited by a single element. It is analogous to the \verb|NoneType| type in
Python (whose sole inhabitant is \verb|None|) and the \verb|NULL| type in R
(whose sole inhabitant is also called \verb|NULL|).

A type can be declared a \emph{subtype} of one or more other types. To a first
approximation, subtyping establishes an ``is-a'' relationship between types. In
the Data Science Ontology, matrices are a subtype of both arrays (being arrays
of rank 2) and data tables (being tables whose columns all have the same data
type). As this example illustrates, subtyping in the ontology differs from
inheritance in a typical object-oriented programming language. Subtyping should
instead be understood through \emph{implicit conversion}, also known as
\emph{coercion} \cite{reynolds1980}. The idea is that if a type $X$ is a subtype
of $X'$, then there is a canonical way to convert elements of type $X$ into
elements of type $X'$. Elaborating the example, a matrix simply \emph{is} an
array (of rank 2), hence can be trivially converted into an array. A matrix is
not strictly speaking a data table but can be converted into one (of homogeneous
data type) by assigning numerical names to the columns.

A function $f: X \to Y$ in the ontology language has an input type $X$, its
\emph{domain}, and an output type $Y$, its \emph{codomain}. Like types,
functions are either basic or composite. The two basic ways of constructing
composite functions are composition and products, corresponding to the vertical
and horizontal directions in wiring diagrams. The \emph{composite} of a function
$f: X \to Y$ with $g: Y \to Z$ is a new function $f \cdot g: X \to Z$, with the
usual meaning. Algorithmically speaking, $f \cdot g$ computes \emph{in series}:
first $f$ and then $g$. The \emph{product} of functions $f: X \to Y$ and
$g: W \to Z$ is another function $f \times g: X \times W \to Y \times Z$.
Algorithmically, $f \times g$ computes $f$ and $g$ \emph{in parallel}, taking
the inputs, and returning the outputs, of both $f$ and $g$. The language also
contains special functions for permuting tuples of data, duplicating data, and
discarding data; for a more precise account, see
\cref{sec:cartesian-categories}.

Besides serving as the ``is-a'' relation ubiquitous in knowledge representation
systems, the subtype relation for objects enables \emph{ad hoc polymorphism} for
functions. The type restrictions in function composition are relaxed to allow
implicit conversion, namely, to compose a function $f: X \to Y$ with
$g: Y' \to Z$, it is not required that $Y$ equals $Y'$, but only that $Y$ be a
subtype of $Y'$. Operationally, to compute $f \cdot g$, one first computes $f$,
then coerces the result from type $Y$ to $Y'$, and finally computes $g$.
Diagrammatically, a wire connecting two boxes has valid types if and only if the
source port's type is a subtype of the target port's type. Thus implicit
conversions truly are implicit in the graphical syntax.

The ontology language also supports ``is-a'' relations between functions, called
\emph{subfunctions} in analogy to subtypes. In the Data Science Ontology, the
function concept \textsf{read-tabular-file} of reading a table from a tabular
file is a subfunction of the function concept \textsf{read-data} of reading data
from a generic data source. The meaning of this statement is as follows. The
domain of \textsf{read-tabular-file}, a tabular file, is a subtype of the domain
of \textsf{read-data}, a generic data source. The codomain of
\textsf{read-tabular-file}, a table, is a subtype of the codomain of
\textsf{read-data}, generic data. Now consider two possible computational paths
that take a tabular file and return generic data. We could apply
\textsf{read-tabular-file}, then coerce the resulting table to generic data.
Alternatively, we could coerce the tabular file to a generic data source, then
apply \textsf{read-data}. The subfunction relation asserts that these two
computations are equivalent. The definition of the subfunction relation for
general functions $f: X \to Y$ and $f': X' \to Y'$ is analogous and is stated
formally in \cref{sec:concepts-as-category}.

\section{Semantic enrichment algorithm}
\label{sec:semantic-enrichment}

The semantic enrichment algorithm, transforming raw flow graphs into semantic
flow graphs, proceeds in two independent stages, one expansionary and the other
contractionary. The expansion stage makes essential use of code annotations in
the ontology.

\paragraph{Expansion}

In the expansion stage, the annotated parts of the raw flow graph are replaced
by their abstract definitions. Each annotated box---that is, each box referring
to a concrete function annotated by the ontology---is replaced by the
corresponding abstract function. Likewise, the concrete type of each annotated
port is replaced by the corresponding abstract type. This stage of the algorithm
is ``expansionary'' since a function annotation's definition can be an arbitrary
program in the ontology language. In other words, a single box in the raw flow
graph can become an arbitrarily large subdiagram in the semantic flow graph.

The expansion procedure is \emph{functorial}, to use the jargon of category
theory. Informally, this means two things. First, notice that concrete types are
effectively annotated twice, explicitly by type annotations and implicitly by
the domain and codomain types in function annotations. Functorality requires
that these abstract types be compatible, ensuring the logical consistency of
type and function annotations. Second, expansion preserves the structure of the
ontology language, including composition and products. The expansion of a wiring
diagram is thus completely determined by its action on individual boxes (basic
functions). Functorality is a modeling decision that greatly simplifies the
semantic enrichment algorithm, at the expense of imposing restrictions on how
the raw flow graph can be transformed.

\paragraph{Contraction}

It is practically infeasible to annotate every reusable unit of data science
source code. Even if the Data Science Ontology were to grow significantly, most
real-world data analyses would use concrete types and functions without
annotations. This unannotated code has unknown semantics, so properly speaking
it does not belong in the semantic flow graph. However, it usually cannot be
deleted without altering the data flow of the wiring diagram.

As a compromise, in the contraction stage, the unannotated parts of the raw flow
graph are simplified to the extent possible. All references to unannotated types
and functions are removed, leaving behind unlabeled wires and boxes.
Semantically, the unlabeled wires are interpreted as arbitrary ``unknown'' types
and the unlabeled boxes as arbitrary ``unknown'' functions (which could have
known domain and codomain types). The diagram is then simplified by
\emph{encapsulating} unlabeled boxes. Specifically, every maximal connected
subdiagram of unlabeled boxes is encapsulated by a single unlabeled box. The
interpretation is that any composition of unknown functions is just another
unknown function. This stage is ``contractionary'' because it can only decrease
the number of boxes in the diagram.

\paragraph{Examples revisited}

To reprise the small example from the Introduction, semantic enrichment
transforms all three raw flow graphs of
\cref{fig:toy-kmeans-scipy,fig:toy-kmeans-sklearn,fig:toy-kmeans-r} into the
semantic flow graph of \cref{fig:toy-kmeans-semantic}. Expansions related to
$k$-means clustering occur in all three programs.

In the first Python program (\cref{lst:toy-kmeans-scipy} and
\cref{fig:toy-kmeans-scipy}), the \verb|kmeans2| function from SciPy expands to
a compound function that creates a $k$-means clustering model, fits it to data,
and extracts its cluster assignments and centroids, as specified by the
annotation in \cref{fig:annotation-python-scipy-kmeans}. Note that the abstract
$k$-means clustering model does \emph{not} correspond to any concrete object in
the original program. This design pattern is used throughout the ontology to
cope with functions that are not object-oriented with respect to models.

By contrast, the second Python program is written in object-oriented style
(\cref{lst:toy-kmeans-sklearn} and \cref{fig:toy-kmeans-sklearn}). The
\verb|KMeans| class from Scikit-learn expands to an abstract type
\textsf{k-means}. The \verb|fit| method of this class is not annotated in the
Data Science Ontology. However, the \verb|fit| method of its superclass
\verb|BaseEstimator| \emph{is} annotated
(\cref{fig:annotation-python-sklearn-fit}), so the expansion is performed using
this annotation. In general, subtyping and polymorphism are indispensable for
annotating object-oriented libraries parsimoniously.

The R program is intermediate between these two styles (\cref{lst:toy-kmeans-r}
and \cref{fig:toy-kmeans-r}). The \verb|kmeans| function, annotated in
\cref{fig:annotation-r-stats-kmeans}, directly receives the data and the number
of clusters, but returns an object of class \verb|kmeans|. The cluster
assignments and centroids are slots of this object, annotated separately. This
design pattern is typical in R, due to its informal type system.

Contractions also occur in the three programs. In the first Python program, the
only unannotated box is NumPy's \verb|delete| function. Contracting this box
does not reduce the size of the wiring diagram. A contraction involving multiple
boxes occurs in the second Python program. The subdiagram consisting of the
Pandas method \verb|NDFrame.drop| composed with the attribute accessor
\verb|values| is encapsulated into a single unlabeled box.

\begin{figure}
  \centering
  \resizebox{\textwidth}{!}{
    \input{wiring-diagrams/semantic-enrichment/dream-ra.semantic}}
  \caption{Semantic flow graph for data analysis from Rheumatoid Arthritis DREAM
    Challenge (\cref{lst:dream-ra} and \cref{fig:dream-ra-raw})}
  \label{fig:dream-ra-semantic}
\end{figure}

As a more realistic example, recall the data analysis for the Rheumatoid
Arthritis DREAM Challenge presented in the previous chapter. The R code was
displayed in \cref{lst:dream-ra} and the raw flow graph in
\cref{fig:dream-ra-raw}. The semantic flow graph is now shown in
\cref{fig:dream-ra-semantic}. The two models fit by the analysis, one involving
a feature selection step and the other not, appear as the left and right
branches of the semantic flow graph. As in the $k$-means clustering example,
most of the unlabeled nodes in \cref{fig:dream-ra-semantic}, including the wide
node at the top, refer to code for data preprocessing or transformation. It is a
commonplace among data scientists that such ``data munging'' is a crucial aspect
of data analysis. There is no fundamental obstacle to representing its
semantics; it so happens that the relevant portion of the Data Science Ontology
has not yet been developed.

\section{Concepts as a category}
\label{sec:concepts-as-category}

The Data Science Ontology is formalized as a finitely presented category of a
certain kind. The type and function concepts in the ontology are, respectively,
the objects and morphisms that generate the category. Abstract programs
expressed in the language of concepts are arbitrary morphisms in the category,
constructed from the object and morphism generators through composition,
monoidal products, and other operations. In this section, we develop a
categorical structure suitable for the Data Science Ontology by augmenting
cartesian closed categories with a form of subtyping based on implicit
conversion. Ultimately, an ontology is defined to be a finite presentation of a
cartesian closed category with implicit conversion.

Cartesian closed categories are perhaps the simplest model of typed, functional
computing. Cartesian categories, reviewed in \cref{sec:cartesian-categories},
have a type system with product and unit types, while closed categories, defined
below, also have function types. In our experience, augmenting the type system
with some form of polymorphism is a practical necessity, for the sake of both
knowledge representation and parsimonious annotation of code. Our aim is not to
give a sophisticated account of polymorphism but to define the minimal
practically useful system. The following approach to polymorphism is adapted
from the works of Goguen and Reynolds \cite{goguen1978,reynolds1980}.

\begin{definition}[Implicit conversion]
  A \emph{category with implicit conversion} is a category $\cat C$ with a
  distinguished subcategory $\cat{C}_0$ that is wide as a subcategory but thin
  as a category. That is, $\cat{C}_0$ contains all the objects of $\cat{C}$ but
  contains at most one morphism between any two objects. If there exists a
  morphism $X \to X'$ in $\cat{C}_0$, we write $X \leq X'$ and say that $X$ is a
  \emph{subtype} of $X'$. The morphism $X \to X'$ itself is called an
  \emph{implicit conversion} or \emph{coercion}.\footnote{To be consistent in
    the usage of categorical and programming terminology, one might wish to say
    that $X$ is a \emph{subobject} of $X'$. However, the term ``subobject''
    already has an established meaning in categorical logic that is related to,
    but different than, the usage of ``subtype'' here.}
\end{definition}

The informal interpretation of subtyping and implicit conversion was explained
in \cref{sec:dso}. One subtle point should be noted: even when types are
interpreted as sets, implicit conversions are not necessarily set inclusions or
even injections. In the motivating example, matrices are a subtype of data
tables, yet the set of matrices is \emph{not} a subset of the set of data tables
under any plausible formalization of a data table. The implicit conversion
function must add names to the columns of the matrix, among other possible
obstructions. Hence, to the slogan that ``types are not sets'' \cite{morris1973}
it may be added that ``subtypes are not subsets.''

Mathematically speaking, the subtype relation defines a preorder on the objects
of $\cat C$. Thus, every type $X$ is a subtype of itself. If $X$ is a subtype of
$X'$ and $X'$ a subtype of $X''$, then $X$ is a subtype of $X''$. The
corresponding implicit conversions are given by identities and by composition,
respectively. In what follows, there is no mathematical obstruction to allowing
the conversions $\cat{C}_0$ to form an arbitrary category, not necessarily a
preorder. That would, however, defeat the purpose: conversions would have to be
disambiguated by \emph{name} and hence would cease to be implicit.

When a category $\cat C$ with implicit conversion is also a monoidal category,
the implicit conversions should be compatible with the monoidal product.

\begin{definition}[Monoidal implicit conversion]
  A \emph{monoidal category with implicit conversion} is a monoidal category
  $(\cat{C},\otimes,I)$ whose underlying category $\cat{C}$ has implicit
  conversions $\cat{C}_0$, such that $\cat{C}_0$ forms a \emph{monoidal}
  subcategory of $\cat{C}$.

  A symmetric monoidal category has implicit conversions if its underlying
  monoidal category does. Likewise, a cartesian category has implicit
  conversions if its underlying monoidal category $(\cat{C},\times,1)$ does.
\end{definition}

The definition requires that subtyping be compatible with product types, in the
sense that if $X \leq X'$ and $Y \leq Y'$, then $X \times Y \leq X' \times Y'$,
where the corresponding implicit conversion is given by the product of
morphisms. The subtype relation thus makes $\cat{C}_0$ into a \emph{monoidal
  preorder}.

\begin{remark}[Implicit versus explicit conversion]
  If $\cat{C}$ is a non-strict cartesian category, then the requirement that the
  implicit conversions form a monoidal subcategory implies that the associators
  and unitors belong to $\cat{C}_0$. Therefore,
  $(X \times Y) \times Z \approx X \times (Y \times Z)$ and
  $X \times 1 \approx X \approx 1 \times X$ for all objects $X,Y,Z \in \cat{C}$,
  where we write $X \approx Y$ for the equivalence relation that $X \leq Y$ and
  $Y \leq X$. It is natural to require that the associators and unitors be
  implicit conversions, since one does not typically wish to distinguish between
  different bracketings of products. In particular, the implicit conversions
  $\cat{C}_0$ do \emph{not} form a partial order when the monoidal category
  $\cat{C}$ is not strict (and need not form a partial order even when $\cat{C}$
  is strict).

  It may seem strange that $\cat{C}_0$ is not asked to inherit the cartesian or
  even the symmetric monoidal structure of $\cat{C}$. However, this leads to
  unwanted implicit conversions and to strictification of the original category.
  Namely, if $\cat{C}_0$ is a symmetric monoidal subcategory of $\cat C$, then
  the braidings $\Braid_{X,Y}: X \times Y \to Y \times X$ in $\cat C$ must
  satisfy $\Braid_{X,X} = 1_{X \times X}$. This is false under the set-theoretic
  interpretation and implies that $\cat{C}$ is symmetrically monoidally
  equivalent to a strictly commutative symmetric monoidal category
  \cite{kim2016}. The braidings must therefore be treated as \emph{explicit}
  conversions.
\end{remark}

Because the notion of subtyping is operationalized by the implicit conversions,
it can be extended from objects to morphisms through naturality squares.

\begin{definition}[Submorphism]
  Let $\cat C$ be a category with implicit conversion. A morphism $f$ in
  $\cat C$ is a \emph{submorphism} (or \emph{subfunction}) of another morphism
  $f'$, written $f \leq f'$, if in the arrow category $\cat C^\to$ there exists
  a (unique) morphism $f \to f'$ whose components are implicit conversions.

  Explicitly, if $f: X \to Y$ and $f': X' \to Y'$ are morphisms in $\cat C$,
  with $X \leq X'$ and $Y \leq Y'$, then $f \leq f'$ if and only if the diagram
  commutes:
  \begin{equation*}
    \begin{tikzcd}
      X \arrow[r, "f"] \arrow[d, "\leq"'] & Y \arrow[d, "\leq"] \\
      X' \arrow[r, "f'"] & Y'
    \end{tikzcd}
  \end{equation*}
\end{definition}

Again, see \cref{sec:dso} for the informal interpretation and examples of this
notion. Just as subtypes define a preorder on the objects of $\cat C$,
submorphisms define a preorder on the morphisms of $\cat C$. Moreover,
submorphisms respect the compositional structure of $\cat C$. They are closed
under identities, i.e., $1_X \leq 1_{X'}$ whenever $X \leq X'$, and under
composition, i.e., if $f \leq f'$ and $g \leq g'$ are composable, then
$fg \leq f'g'$. All these statements are easy to prove. To illustrate,
transitivity and closure under composition are proved by pasting commutative
squares vertically and horizontally:
\begin{equation*}
  \begin{tikzcd}
    X \arrow[r, "f"] \arrow[d, "\leq"'] & Y \arrow[d, "\leq"] \\
    X' \arrow[r, "f'"] \arrow[d, "\leq"'] & Y' \arrow[d, "\leq"] \\
    X'' \arrow[r, "f''"] & Y''
  \end{tikzcd}
  \qquad\qquad
  \begin{tikzcd}
    X \arrow[r, "f"] \arrow[d, "\leq"']
      & Y \arrow[r, "g"] \arrow[d, "\leq"']
      & Z \arrow[d, "\leq"] \\
    X' \arrow[r, "f'"] & Y' \arrow[r, "g'"] & Z'
  \end{tikzcd}
\end{equation*}
When $\cat C$ is a \emph{cartesian} category with implicit conversion,
submorphisms are also closed under products: if $f \leq f'$ and $g \leq g'$,
then $f \times g \leq f' \times g'$, because, by functorality, monoidal products
preserve commutative diagrams.

As an aside, we note that this structure is succinctly captured by the notion of
a monoidal double category \cite{bruni2002,shulman2010,hansen2019}.

\begin{proposition}
  A (monoidal) category $\cat{C}$ with implicit conversions forms a (monoidal)
  double category, in which the objects are the objects of $\cat{C}$, the
  horizontal 1-morphisms are the morphisms of $\cat{C}$, the vertical
  1-morphisms are the implicit conversions, and the 2-morphisms are the
  submorphisms.
\end{proposition}

\noindent Compared to a general monoidal double category, the one here is quite
simple, being thin with respect to both vertical 1-morphisms and 2-morphisms.

In a functional programming language, functions are treated as data and as such
they can be passed as arguments to other functions. The type for functions
$X \to Y$ is the \emph{function type}, or \emph{exponential type}, $Y^X$.
Algebraically, the existence of function types corresponds to the property of a
monoidal category of being \emph{closed}.

\begin{definition}[Closed monoidal category]
  A symmetric monoidal category $(\cat{C}, \otimes, I)$ is \emph{closed} if for
  every object $X \in \cat{C}$, the product functor
  $- \otimes X: \cat{C} \to \cat{C}$ has a right adjoint, denoted
  $[X,-]: \cat{C} \to \cat{C}$. That is, for all objects $W,X,Y \in \cat{C}$,
  there is a bijection of hom-sets
  \begin{equation*}
    \cat{C}(W \otimes X, Y) \cong \cat{C}(W, [X,Y]),
  \end{equation*}
  natural in $W$ and $Y$. The object $[X,Y]$ is called an \emph{internal hom}.

  A \emph{cartesian closed category} is a cartesian category that is also
  closed. In this case, the internal hom $[X,Y]$ is called an \emph{exponential
    object} and is often denoted $Y^X$.
\end{definition}

Taking $W$ to be the monoidal unit, the adjunction establishes a one-to-one
correspondence between morphisms $f: X \to Y$ in $\cat{C}$ and generalized
elements of type $[X,Y]$. More generally, each morphism $f: W \times X \to Y$
corresponds to a unique morphism $\lambda(f): W \to [X,Y]$, the \emph{currying}
of $f$. The inverse transformation associates each morphism $g: W \to [X,Y]$
with its \emph{uncurrying} $\lambda^{-1}(g): W \times X \to Y$.

Let $\cat{C}$ be any closed monoidal category. By the parameterized adjunction
theorem \cites[Theorem IV.7.3]{maclane1998}[Proposition 4.3.6]{riehl2016}, the
family of internal hom functors $[X,-]: \cat{C} \to \cat{C}$, parameterized by
objects $X \in \cat{C}$, assembles into a bifunctor
$[-,-]: \cat{C}^\opposite \times \cat{C} \to \cat{C}$ such that the bijection of
hom-sets $\cat{C}(W \otimes X, Y) \cong \cat{C}(W, [X,Y])$ is natural not just
in $W$ and $Y$ but also in $X$. When the category $\cat{C}$ has implicit
conversions, the conversions should be preserved by this bifunctor.

\begin{definition}[Closed implicit conversion]
  A \emph{closed monoidal category with implicit conversion} is a symmetric
  monoidal category with implicit conversion that is also closed, in such a way
  that the internal hom bifunctor
  $[-,-]: \cat{C}^\opposite \times \cat{C} \to \cat{C}$ restricts to a bifunctor
  $\cat{C}_0^\opposite \times \cat{C}_0 \to \cat{C}_0$ of implicit conversions.
  Equivalently, $[X',Y] \leq [X,Y']$ whenever $X \leq X'$ and $Y \leq Y'$.

  A cartesian closed category has implicit conversions if its underlying closed
  monoidal category does. We denote by $\CCC_\leq$ the category whose objects
  are the (small) cartesian closed categories with implicit conversion and whose
  morphisms are the cartesian closed functors that preserve implicit
  conversions. When no confusion will result, the morphisms are simply called
  ``functors.''
\end{definition}

The subtype relation $[X',Y] \leq [X,Y']$, where $X \leq X'$ and $Y \leq Y'$,
has the interpretation that any morphism $f: X' \to Y$ can be implicitly
converted to a morphism $\tilde f: X \to Y'$ by ``restricting the domain'' and
``expanding the codomain'':
\begin{equation*}
  \begin{tikzcd}
    X' \arrow[r, "f"] & Y \arrow[d, "\leq"] \\
    X \arrow[r, dashed, "\tilde f"] \arrow[u, "\leq"] & Y'.
  \end{tikzcd}
\end{equation*}
Subtypes of function types should not be confused with subfunctions. The former
is a relation between the objects and the latter between morphisms; moreover,
the former is contravariant with respect to the domain object, while the latter
is covariant.

The submorphism relation is, however, compatible with currying and uncurrying,
as the following proposition shows.

\begin{proposition}
  Let $(\cat{C}, \otimes, I)$ be a closed monoidal category with implicit
  conversions and let $W \leq W'$, $X \leq X'$, and $Y \leq Y'$ be objects of
  $\cat{C}$. For any morphisms $f: W \otimes X \to Y$ and
  $f': W' \times X \to Y'$, one has $f \leq f'$ if and only if
  $\lambda(f) \leq \lambda(f')$. Moreover, for any morphisms
  $g: W \otimes X \to Y$ and $g': W \otimes X' \to Y$, one has $g \leq g'$ if
  and only if $\lambda(g') \leq \lambda(g)$.
\end{proposition}
\begin{proof}
  The two statements are the equivalences
  \begin{equation*}
    \begin{tikzcd}
      W \otimes X \arrow[r, "f"] \arrow[d, "\leq"'] & Y \arrow[d, "\leq"] \\
      W' \otimes X \arrow[r, "f'"] & Y'
    \end{tikzcd}
    \qquad\leftrightsquigarrow\qquad
    \begin{tikzcd}
      W \arrow[r, "\lambda f"] \arrow[d, "\leq"'] & {[X,Y]} \arrow[d, "\leq"] \\
      W' \arrow[r, "\lambda f'"] & {[X,Y']}
    \end{tikzcd}
  \end{equation*}
  and
  \begin{equation*}
    \begin{tikzcd}
      W \times X \arrow[r, "g"] \arrow[d, "\leq"'] & Y \arrow[d, equal] \\
      W \times X' \arrow[r, "g'"] & Y
    \end{tikzcd}
    \qquad\leftrightsquigarrow\qquad
    \begin{tikzcd}
      W \arrow[r, "\lambda g"] \arrow[d, equal] & {[X,Y]} \\
      W \arrow[r, "\lambda g'"] & {[X',Y]}  \arrow[u, "\leq"']
    \end{tikzcd},
  \end{equation*}
  meaning that the left square commutes if and only if the right square does.
  The first equivalence follows from the naturality of the adjunction with
  respect to $W$ and $Y$ \cite[Lemma 4.1.3]{riehl2016}, while the second
  equivalence follows from the naturality of the adjunction with respect to $X$
  \cite[Theorem IV.7.3]{maclane1998}.
\end{proof}

With these preliminaries on implicit conversion, an ontology is now defined to
be nothing other than a \emph{finitely presented} cartesian closed category with
implicit conversion.

\begin{definition}[Ontology]
  An \emph{ontology} is a cartesian closed category with implicit conversion,
  given by a finite presentation. That is, it is the cartesian closed category
  with implicit conversion generated by finite sets of:
  \begin{itemize}[nosep]
  \item \emph{basic types}, or \emph{object generators}, $X$
  \item \emph{basic functions}, or \emph{morphism generators}, $f: X \to Y$,
    where $X$ and $Y$ are objects
  \item \emph{basic subtypes}, or \emph{subtype generators}, $X \leq X'$, where
    $X$ and $X'$ are objects
  \item \emph{basic subfunctions}, or \emph{submorphism generators},
    $f \leq f'$, where $f: X \to Y$ and $f': X' \to Y'$ are morphisms satisfying
    $X \leq X'$ and $Y \leq Y'$
  \item \emph{function equations}, or \emph{morphism equations}, $f=g$, where
    $f,g: X \to Y$ are morphisms with equal domains and codomains.
  \end{itemize}
  If the set of morphism equations is empty, the ontology is called \emph{free}
  or \emph{freely generated}.
\end{definition}

Strictly speaking, a finite presentation of a category is not the same as the
category it presents. The former is a finitary object that can be represented
on, and manipulated by, a machine. The latter is an algebraic structure of
infinite size, convenient for mathematical reasoning. However, we will abuse
terminology by calling both finitely presented categories, and particular
presentations thereof, ``ontologies.''

At the time of this writing, the Data Science Ontology is freely generated.
Inference in a freely generated ontology is straightforward. Assuming that the
generating subtypes and subfunctions are between basic objects and basic
functions, deciding the subtype or subfunction relations amounts to computing a
reflexive transitive closure. Deciding equality of objects is trivial. Deciding
equality of morphisms is the \emph{word problem} in a free cartesian closed
category. In the cartesian case, this problem can be solved by the congruence
closure algorithm for term graphs \cite[\S 4.4]{baader1999}. In the future, the
Data Science Ontology may include knowledge in the form of morphism equations,
creating a need for new inference procedures. If arbitrary morphism equations
are allowed, the word problem becomes undecidable.

\section{Annotations as a functor}
\label{sec:annotations-as-functor}

If the concepts form a category, then surely the annotations ought to assemble
into a functor. Let $\cat C$ be a cartesian closed category with implicit
conversion, viewed as the concepts of an ontology. Suppose $\cat L$ is another
such category, modeling a programming language and a collection of modules
written in that language. The annotations ought to define a functor
$F: \cat L \to \cat C$, saying how to translate programs in $\cat L$ into
programs in $\cat C$.

This tidy story does not quite survive contact with reality. A fairly small set
of formal concepts cannot be to exhaust the supply of informal concepts found in
real-world programs. Consequently, any ``functor'' $F: \cat L \to \cat C$
annotating $\cat L$ must be \emph{partial}, in a sense that must be made
precise. There will be both objects and morphisms in $\cat L$ on which $F$
cannot be defined, because the category $\cat C$ is not rich enough to fully
interpret $\cat L$.

Before turning to partial functors, consider the simpler case of partial
functions. In accordance with mathematical custom, the pre-theoretical idea of
``partial function'' can be reduced to the standard notion of total function.
There are two common ways to do this, the first based on pointed sets and the
second on spans. They are equivalent as far as sets and functions are concerned
but suggest different generalizations to categories and functors.

The category of pointed sets leads to one viewpoint on partiality, popular in
programming language theory. Given a set $X$, let $X_\bot := X \sqcup \{\bot\}$
be the set $X$ with a freely adjoined base point $\bot$. A \emph{partial
  function} from $X$ to $Y$ is then a function $f: X_\bot \to Y_\bot$ preserving
the base point, so that $f(\bot) = \bot$. The function $f$ is regarded as
``undefined'' on the points $x \in X$ with $f(x) = \bot$. This notion of
partiality can be transported from sets to categories using enriched category
theory. Categories enriched in pointed sets, where each hom-set has a base
morphism $\bot$, have been proposed as a qualitative model of incomplete
information \cite{marsden2016}. Such categories make partiality an
all-or-nothing affair, because their composition laws satisfy
$\bot \cdot f = f \cdot \bot = \bot$ for all morphisms $f$. That is far too
stringent. If this composition law were adopted, the semantic flow graphs would
rarely be anything besides the trivial morphism $\bot$.

A partial function can also be defined as a special kind of span of total
functions. On this view, a \emph{partial function} from $X$ to $Y$ is a span in
$\Set$
\begin{equation*}
  \begin{tikzcd}[column sep=small, row sep=small]
    & J \arrow[dl, tail, "\iota"'] \arrow[dr, "f"] & \\
    X & & Y
  \end{tikzcd}
\end{equation*}
whose left leg $\iota: J \to X$ is monic (injective). The partial function's
domain of definition is $J$, regarded as a subset of $X$. Although we shall not
need it here, we note that partial functions, and partial morphisms generally,
can be composed by taking pullbacks whenever they exist \cite[\S
5.5]{borceux1994c}.

The span above can be interpreted as \emph{partially} defining a function $f$ on
$X$, via a set of equations indexed by $J$:
\begin{equation*}
  f(x_j) := y_j, \qquad j \in J.
\end{equation*}
It is then natural to ask: what is the most general way to define a \emph{total}
function on $X$ obeying these equations? The answer is given by the pushout in
$\Set$:
\begin{equation*}
  \begin{tikzcd}
    & J \arrow[dl, tail, "\iota"'] \arrow[dr, "f"]
      \arrow[dd, phantom, very near end, "\ucorner"] & \\
    X \arrow[dr, "f_*"'] & & Y \arrow[dl, tail, "\iota_*"] \\
    & Y_* &
  \end{tikzcd}
\end{equation*}
Because $\iota: J \to X$ is monic, so is $\iota_*: Y \to Y_*$, and $Y$ can be
regarded as a subset of $Y_*$. The commutativity of the diagram says that $f_*$
satisfies the set of equations indexed by $J$. The \emph{universal property}
defining the pushout says that any other function $f': X \to Y'$ satisfying the
equations factors uniquely through $f_*$, meaning that there exists a unique
function $g: Y_* \to Y'$ making the diagram commute:
\begin{equation*}
   \begin{tikzcd}
    & J \arrow[dl, "\iota"'] \arrow[dr, "f"] & \\
    X \arrow[r, "f_*"] \arrow[dr, "f'"'] & Y_* \arrow[d, dashed, "g"] &
      Y \arrow[l, "\iota_*"] \arrow[dl, "\iota'"] \\
    & Y' &
  \end{tikzcd}
\end{equation*}
The codomain of the function $f_*: X \to Y_*$ consists of $Y$ plus a ``formal
image'' $f(x)$ for each element $x$ on which $f$ is undefined. Contrast this
with the codomain of a function $X \to Y_\bot$, which consists of $Y$ plus a
single element $\bot$ representing \emph{all} the undefined values.

This viewpoint on partiality generalizes effortlessly from $\Set$ to any
category with pushouts. Annotations can be defined as a span in $\CCC_\leq$
\begin{equation*}
   \begin{tikzcd}[column sep=small, row sep=small]
    & \cat{J} \arrow[dl, tail, "\iota"'] \arrow[dr, "F"] & \\
    \cat{L} & & \cat{C}
  \end{tikzcd}
\end{equation*}
whose left leg $\iota: \cat{J} \to \cat{L}$ is monic. We then form the pushout
in $\CCC_\leq$:
\begin{equation*}
  \begin{tikzcd}
    & \cat{J} \arrow[dl, tail, "\iota"'] \arrow[dr, "F"]
      \arrow[dd, phantom, very near end, "\ucorner"] & \\
    \cat{L} \arrow[dr, "F_*"'] & & \cat{C} \arrow[dl, "\iota_*"] \\
    & \cat{C}_* &
  \end{tikzcd}
\end{equation*}
Given a morphism $f$ in $\cat L$, which represents a concrete program, its image
$F_*(f)$ in $\cat{C}_*$ is a partial translation of the program into the
language defined by the ontology's concepts.

The universal property of the pushout in $\CCC_\leq$, stated above in the case
of $\Set$, gives an appealing intuitive interpretation to program translation.
The category $\cat C$ is not rich enough to fully translate $\cat L$ via a
functor $\cat L \to \cat C$. As a modeling assumption, we suppose that $\cat C$
has some ``completion'' $\overline{\cat C}$ for which a full translation
$\overline F: \cat L \to \overline{\cat C}$ \emph{is} possible. We do not know
$\overline{\cat C}$, or at the very least we cannot feasibly write it down.
However, if we take the pushout functor $F_*: \cat{L} \to \cat{C}_*$, we can at
least guarantee that, no matter what the complete translation $\overline{F}$ is,
it will factor through $F_*$. Thus $F_*$ defines the most general possible
translation, given the available information.

The properties of partial functions largely carry over to partial functors, with
one important exception: the ``inclusion'' functor
$\iota_*: \cat{C} \to \cat{C}_*$ need not be monic, even though
$\iota: \cat{J} \to \cat{L}$ is. Closely related is the fact that $\CCC_\leq$
(like its cousins $\Cat$, $\Cart$, and $\CCC$, but unlike $\Set$) does not
satisfy the \emph{amalgamation property} \cite{macdonald2009}. To see how
$\iota_*$ can fail to be monic, suppose that the equation $f_1 \cdot f_2 = f_3$
holds in $\cat{L}$ and that the defining equations include $F(f_i) := g_i$ for
$i=1,2,3$. Then, by the functorality of $F_*$, we must have
$g_1 \cdot g_2 = g_3$ in $\cat{C}_*$, even if $g_1 \cdot g_2 \neq g_3$ in
$\cat{C}$. Thus the existence of $F_*$ can force equations between morphisms in
$\cat{C}_*$ that do not hold in $\cat{C}$.

When the categories in question are finitely presented, the pushout functor also
admits a finitary, equational presentation, suitable for computer algebra. Just
as an ontology is defined to be a finitely presented category, an ontology with
annotations is defined to be a finitely presented functor.

\begin{definition}[Annotations]
  An \emph{ontology with annotations} is a functor between cartesian closed
  categories with implicit conversion, defined by a finite presentation.
  Explicitly, it is generated by:
  \begin{itemize}[nosep]
  \item a finite presentation of a category $\cat C$ in $\CCC_\leq$, the
    ontology category;
  \item a finite presentation of a category $\cat L$ in $\CCC_\leq$, the
    programming language category; and
  \item a finite set of equations partially defining a functor $F$ from $\cat L$
    to $\cat C$.
  \end{itemize}
\end{definition}

The equations partially defining the functor $F$ may be indexed by a category
$\cat{J}$, in which case they take the form
\begin{equation*}
  F(X_j) := Y_j \qquad\text{where}\qquad
    X_j \in \cat L, \quad Y_j \in \cat C,
\end{equation*}
for each $j \in \cat{J}$, and
\begin{equation*}
  F(f_k) := g_k \qquad\text{where}\qquad
    f_k \in \cat L(X_j, X_{j'}), \quad g_k \in \cat C(Y_j, Y_{j'}),
\end{equation*}
for each $j,j' \in \cat{J}$ and $k \in \cat{J}(j,j')$. The equations present a
span
$\cat{L} \overset{\iota}\leftarrowtail \cat{J} \overset{F}\rightarrow \cat{C}$
whose left leg is monic and the functor generated by the equations is the
pushout functor $F_*: \cat{L} \to \cat{C}_*$ described above.

\begin{remark}[Formalizing presentations]
  The two definitions involving finite presentations can be made completely
  formal using generalized algebraic theories \cite{cartmell1978,cartmell1986}.
  There is a generalized algebraic theory of cartesian closed categories with
  implicit conversion, whose category of models is $\CCC_\leq$, and a theory of
  functors between them, whose category of models is the arrow category
  $\CCC_\leq^\to$. Cartmell gives as simpler examples the theory of categories,
  with models $\Cat$, and the theory of functors, with models $\Cat^\to$
  \cite{cartmell1986}. Lambek and Scott give an equational theory of $\cat{CCC}$
  \cite[\S I.3]{lambek1986}. Any category of models of a generalized algebraic
  theory is cocomplete and admits free models defined by finite presentations.
\end{remark}

\section{Flow graphs and categories of elements}
\label{sec:categories-of-elements}

To a first approximation, the raw and semantic flow graphs are morphisms in the
categories $\cat L$ and $\cat C_*$, respectively. The expansion stage of the
semantic enrichment algorithm simply applies the annotation functor
$F_*: \cat L \to \cat C_*$ to a morphism in $\cat L$. The contraction stage,
purely syntactical, groups together morphisms in $\cat C_*$ that are not images
of $\cat C$ under the inclusion functor $\iota_*: \cat C \to \cat C_*$.

To complete the formalization of semantic enrichment, the observed elements in
the raw and semantic flow graphs must be accounted for. Flow graphs capture not
only the types and functions comprising a program, but also the values computed
by the program. In category theory, values can be bundled together with objects
and morphisms using a device called the \emph{category of elements}. The raw and
semantic flow graphs are formalized as morphisms in categories of elements.

The objects and morphisms in the ontology category $\cat C$ can, at least in
principle, be interpreted as sets and functions. Extending the definition in
\cref{sec:cartesian-categories}, a set-theoretic \emph{model} of $\cat C$ is a
cartesian closed functor $M_{\cat C}: \cat C \to \Set$. In programming language
terms, $M_{\cat C}$ is a \emph{denotational semantics} for $\cat C$. Suppose the
concrete language $\cat L$ also has a model $M_{\cat L}: \cat L \to \Set$.
Assuming that the equations partially defining the annotation functor hold in
the models of $\cat{C}$ and $\cat{L}$, the diagram
\begin{equation*}
  \begin{tikzcd}
    & \cat{J} \arrow[dl, tail, "\iota"'] \arrow[dr, "F"] & \\
    \cat{L} \arrow[dr, "M_{\cat L}"'] & & \cat{C} \arrow[dl, "M_{\cat C}"] \\
    & \Set &
  \end{tikzcd}
\end{equation*}
commutes. By the universal property of the annotation functor $F_*$, there
exists a unique model $M_{\cat C_*}: \cat C_* \to \Set$ making the diagram
commute:
\begin{equation*}
  \begin{tikzcd}
    \cat{L} \arrow[r, "F_*"] \arrow[dr, "M_{\cat L}"']
      & \cat{C}_* \arrow[d, dashed, pos=0.33, "M_{\cat{C}_*}"]
      & \cat{C} \arrow[l, "\iota_*"'] \arrow[dl, "M_{\cat C}"] \\
    & \Set &
  \end{tikzcd}
\end{equation*}

Each of these three interpretations yields a category of elements, also known as
a ``Grothendieck construction'' \cites[\S 12.2]{barr1990}[\S 2.4]{riehl2016}.
\begin{definition}
  The \emph{category of elements} of a cartesian functor $M: \cat C \to \Set$
  has as objects, the pairs $(X,x)$, where $X \in \cat C$ and $x \in M(X)$, and
  as morphisms $(X,x) \to (Y,y)$, the morphisms $f: X \to Y$ in $\cat C$
  satisfying $M(f)(x) = y$.
\end{definition}

The category of elements of a cartesian functor $M: \cat C \to \Set$ is itself a
cartesian category. Composition and identities are inherited from $\cat C$.
Products are defined on objects by
\begin{equation*}
  (X,x) \times (Y,y) := (X \times Y, (x,y))
\end{equation*}
and on morphisms exactly as in $\cat C$, and the unit object is $(1,*)$, where
$*$ is the single element of $M(1) = \{*\}$. The braidings and the supply of
commutative comonoids are also inherited from $\cat C$, the latter as
\begin{equation*}

  \Copy_{(X,x)}: (X,x) \to (X \times X, (x,x)), \qquad
  \Delete_{(X,x)}: (X,x) \to (1,*).
\end{equation*}
The category of elements of a cartesian \emph{closed} functor
$M: \cat{C} \to \Set$ also contains objects of the form $(Y^X, g)$, where $g$ is
any function $M(X) \to M(Y)$. However, the category of elements is generally not
closed, because for any pair of elements $x \in M(X)$ and $y \in M(Y)$ there can
be many functions $g \in M(Y^X)$ such that $g(x) = y$.

A \emph{raw flow graph} is finally defined to be a morphism in the category of
elements of $M_{\cat L}$. Likewise, a \emph{semantic flow graph} is a morphism
in the category of elements of $M_{\cat C_*}$. Note that the models of $\cat L$,
$\cat C$, and $\cat C_*$ are conceptual devices; we do not actually construct a
denotational semantics for the language $\cat L$ or the ontology $\cat C$.
Instead, the program analysis system observes a \emph{single} computation and
produces a \emph{single} morphism $f$ in the category of elements of
$M_{\cat L}$. By the construction of the model $M_{\cat C_*}$, applying the
annotation functor $F_*: \cat L \to \cat C_*$ to this morphism $f$ yields a
morphism $F_*(f)$ belonging to the category of elements of $M_{\cat C_*}$.

In summary, semantic enrichment amounts to applying the annotation functor in
the category of elements. The expansion stage simply computes the functor, while
the contraction stage is entirely syntactical. Contraction computes a new
syntactic expression for the expanded morphism by grouping together morphisms
that are not images under the inclusion $\iota_*: \cat{C} \to \cat{C}_*$ of the
ontology category.

\section{Notes and references}

Most of the content of this chapter recapitulates previous work by the author
and collaborators, principally from \cite{patterson2018} and its abridgment in
\cite{patterson2018demo}. The discussion of implicit conversion is here extended
from cartesian categories to cartesian closed categories.

\paragraph{Knowledge representation and program analysis}

The raw flow graphs forming the input to semantic enrichment are products of
computer program analysis, as described in the previous chapter. The history of
artificial intelligence is replete with interactions between knowledge
representation and program analysis. In the late 1980s and early 1990s,
automated planning and ruled-based expert systems figured in ``knowledge-based
program analysis'' \cite{johnson1985,harandi1990,biggerstaff1994}. Other early
systems were based on description logic \cite{devanbu1991,welty2007} and graph
parsing \cite{wills1992}. These systems were designed to help software
developers maintain large codebases (exceeding, say, a million lines of code) in
specialized industrial domains like telecommunications. In data science, the
code tends to be much shorter, the control flow more linear, and the underlying
concepts better defined. Our methodology for combining program analysis with
knowledge representation is accordingly quite different from those of the older
literature.

\paragraph{Ontologies for data science}

There already exist several ontologies and schemas related to data science, such
as the Statistics Ontology (STATO), an OWL ontology about basic statistics
\cite{gonzalez-beltran2016}; the Data Mining OPtimization Ontology (DMOP), an
OWL ontology for the data mining process \cite{keet2015}; the Predictive
Modeling Markup Language (PMML), an XML schema for data mining models
\cite{guazzelli2009}; and ML-Schema, a schema for data mining and machine
learning workflows developed by a W3C community group \cite{publio2018}. The
Data Science Ontology distinguishes itself from previous efforts by attempting
to systematically code for data analysis. This does not appear to be a design
criterion of the existing standards. For example, in STATO, concepts
representing statistical methods may have designated inputs and outputs, but
they are too imprecisely specified to map onto code, among other obstacles. PMML
is a purely static format, designed for serializing fitted models. To
successfully model computer programs, special attention must be paid to the
algebraic and logical structure of programs. For this reason, the ontology
language of the Data Science Ontology is based on cartesian closed categories,
whereas the description logic of OWL more closely resembles bicategories of
relations \cite{patterson2017relations}.

\paragraph{Ontology languages and programming languages}

The cartesian closed categories forming the basis of the ontology language are
deeply connected to the simply typed lambda calculus (see Notes to
\cref{ch:category-theory}). The latter system is a fundamental model of
functional computing. Implicit conversion, comprising the other half of the
ontology language, is a form of \emph{ad hoc polymorphism} well known in
programming language theory. Building on Goguen's work on order-sorted algebras
\cite{goguen1978,goguen1992}, Reynolds gave a categorical treatment of implicit
conversion for an Algol-like language \cite{reynolds1980}. A brief textbook
account of Reynolds' work appears in \cite[\S 3.2]{pierce1991}. The approach to
implicit conversion in this chapter differs from Reynold's in being entirely
algebraic, not dependent on any particular syntax or type theory. The algebraic
formulation leads to shorter definitions and an easy treatment of implicit
conversion for product and function types.


TITLE: Restricted degree function of an endomorphism of a Jacobian to its theta divisor for genus 2 curves
QUESTION [2 upvotes]: I hope my question is not too vague or basic to be here.
I have been constructing a setting to count points on a curve, but I am stucked solving one part of my problem for some time. Now I would like to have some advise from experts. I hope someone can give me a hint, it is related to genus 2 curves and degrees of morphisms to the Kummer surface of its jacobian.
What I am doing in some sense is constructing the 2:1 map from a hyperelliptic curve $H$ to $\mathbb{P}^1$ in a little complicated way but in order to get it explicitly.
Let $H$ be a hyperelliptic curve of genus 2 over $\mathbb{F}_q$ defined by $y^2=x^5 + a_3x^3 + a_2x^2 + a_1x+a_0=f(x)$ and consider $J$ its jacobian and $Kum(J)\subset \mathbb{P}^3_{\mathbb{F}_q}$ its Kummer surface .
Let $\theta=\lbrace (P-\infty) \in J : P\in H\rbrace$ be its theta divisor.
Let $\phi,\tau,[n]\in End_{\mathbb{F}_q}(J)$ be the frobenius, the involution in the jacobian induced by the hyperelliptic involution and the $n$ map respectively.
Consider the following divisor on $J$ given by a generic point $P\in C$.
$D_n := ((P^{\phi}-\infty)+[n](P^{\tau}-\infty))$
This divisor can be thought as the Frobenius - nIdentity in $End_{\mathbb{F}_q}(J)$
Consider the map from the theta divisor (the curve in this case) to Kummer Surface
$\psi_n:\theta \to Kum(J) $
$(P-\infty) \mapsto [1:\kappa_2(D_n): \kappa_3(D_n) : \kappa_4(D_n)]$
As the Kummer identifies $\pm 1$ divisors, this is going to be a 2:1 map, and is similar to the 2:1 map from the curve $H$ to $\mathbb{P}^1$ (except for the torsion prime divisors in $J$)
I am trying to measure the degree of the map to the fourth coordinate for every $n$ i.e.:
$\hat\psi_n:\theta\to \mathbb{P}^{1}_{\mathbb{F}_q}$
$(P-\infty)\mapsto \kappa_4(D_n)$
This fourth coordinate is the one that determines the quotient by $\pm 1$
which can be found explicitly for general divisors in page five of:
http://www.math.uni-hamburg.de/home/js.mueller/general_kummer.pdf
My main problem here is that as $H$ does not form a group, I cannot explore the morphism structure, and some values for my degree function fail.
I am interested in the positive integer $deg(\psi_n)$, which is the degree of the map.
I have made some calculations and the degree seems for every $n\in \mathbb{Z}$ to behave as a quadratic function $Q(n)$ where the trace of frobenius is involved in the structure of $Q(n)$, but for some $n$ it fails, for example if the coefficient $a_0$ in the equation of $H$ is a square then $Q(2)$ and $deg(\psi_n)$ differ by 2, so maybe $\psi_n$ is not well defined at some points or I am measuring degree over a singularity, but I am not sure.
If its not a square the same happens, but for $Q(-2)$, which is expected as the twist will have in its equation the coefficient $a_0'$ as a square.
Another thing is that if $a_0=0$ I have at every even integer $n$ an error also of -2 with respect of $Q(n)$.
I have been exploring a lot of cases with/without $\mathbb{F}_q$-rational Weierstrass points but I have not been able to deduce what happen at my errors, sometimes the degree function seems to not have errors (except for n=-2,2 which always appears as an error by 2), and sometimes it has more errors, If I pic up a translation of the curve, I can make some errors disappear, and the values are the same. So I am trying to deduce which representative of the isomorphism class has less errors.
Of course for $Q(1)$ and $Q(-1)$ I get interesting values, never seem to fail which give me information of the number of points in the curve and its twist directly without passing to the Jacobian.
But well I have been trying to solve this via intersection theory or even thinking what it means for $\Psi_n:=\phi-[n]$ the set $\Psi_n^{-1}(\infty)\subset \theta$  (As I cannot talk about kernel here because $\theta$ is not an abelian variety).
So $\Psi_n^{-1}(\infty)$ is like "All the elements in $\theta$ (which is isomorphic to $H$) such that the frobenius action in them, behaves exactly as $n$ map on them"
Thanks

REPLY [3 votes]: The degree of ${\hat \psi}_n$ is the intersection number of the image of $\psi_n$ with the divisor on the Kummer surface defined by $\kappa_4 = 0$. Maybe the issues you are having are because the model of the surface in $\mathbb{P}^3$ is singular. It should be easier to work in the Jacobian instead. I think the calculation you are trying to do is essentially the same as the one done in my paper with Stohr (Proc LMS 52 (1986) 1-19) in the appendix.


TITLE: union of two simply connected open , with open and non empty intersection in $R^2$
QUESTION [7 upvotes]: Let $D_1,D_2$ be two simply connected open subsets of $\mathbb{R}^2$. Let's suppose that it's intersection is nonempty and connected. Then $ D_1\cup D_2$ is simply connected.
I have no idea how can I do this.

REPLY [4 votes]: The following argument uses a "known fact" from complex analysis, namely: A domain $\Omega\subset{\mathbb C}$ is simply connected iff for any $a\notin \Omega$ the function $f_a(z):={1\over z-a}$ has a primitive $F:\ \Omega\to{\mathbb C}$ . (Intuitively: If $\Omega$ has no holes were a "bad" $a$ can be placed.)
Fix an $a\notin D_1\cup D_2$. Then $f_a\restriction D_i$ has primitives $F_i:\ D_i\to{\mathbb C}$, since the $D_i$ are simply connected.   The function $\phi:\ z\mapsto F_1(z)-F_2(z)$ is well defined on $D_1\cap D_2$ and has zero derivative. Since  $D_1\cap D_2$ is connected we conclude that $\phi(z)\equiv c$ for some $c\in{\mathbb C}$. Then
$$F(z):=\cases{F_1(z) &$\quad(z\in D_1)$\cr F_2(z)+c&$\quad(z\in D_2)$\cr}$$
is a well defined primitive of $f_a$ on $D_1\cup D_2$.
As $a\notin D_1\cup D_2$ was arbitrary, the conclusion follows.
Addendum: The connectedness of $D_1\cap D_2$ was essential here. Without it we only can say that $\phi$ is a constant $c_\alpha$ on each component $C_\alpha$ of $D_1\cap D_2$. As a consequence there is no obvious way to define the above  $F$ on $D_1\cup D_2$, and in most cases there is no such $F$ at all. An example: Let
$$D_1:=\Bigl\{z\in{\mathbb C}\>\Bigm|\> z\ne0,\ |{\rm Arg}\> z|<{2\pi\over3}\Bigr\},\quad D_2:=\{-z\>|\>z\in D_1\}\ .$$
Here $D_1\cap D_2$ is not connected, but all the other assumptions are fulfilled. And sure enough, the union $D_1\cup D_2$ is not simply connected, nor does the function $f(z):={1\over z}$ have a primitive on $D_1\cup D_2$.