Cartesian closed category

In category theory, a category is Cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in that their internal language is the simply typed lambda calculus. They are generalized by closed monoidal categories, whose internal language, linear type systems, are suitable for both quantum and classical computation.
Etymology.
Named after (1596–1650), French philosopher, mathematician, and scientist, whose formulation of analytic geometry gave rise to the concept of Cartesian product, which was later generalized to the notion of categorical product.
Definition.
The category "C" is called Cartesian closed if and only if it satisfies the following three properties:
The first two conditions can be combined to the single requirement that any finite (possibly empty) family of objects of "C" admit a product in "C", because of the natural associativity of the categorical product and because the empty product in a category is the terminal object of that category.
The third condition is equivalent to the requirement that the functor – ×"Y" (i.e. the functor from "C" to "C" that maps objects "X" to "X" ×"Y" and morphisms φ to φ×id"Y") has a right adjoint, usually denoted –"Y", for all objects "Y" in "C". 
For locally small categories, this can be expressed by the existence of a bijection between the hom-sets
which is natural in both "X" and "Z".
Take care to note that a Cartesian closed category need not have finite limits; only finite products are guaranteed.
If a category has the property that all its slice categories are Cartesian closed, then it is called "locally cartesian closed". Note that if "C" is locally Cartesian closed, it need not actually be Cartesian closed; that happens if and only if "C" has a terminal object.
Basic constructions.
Evaluation.
For each object "Y", the counit of the exponential adjunction is a natural transformation 
called the (internal) evaluation map. More generally, we can construct the partial application map as the composite
In the particular case of the category Set, these reduce to the ordinary operations:
Composition.
Evaluating the exponential in one argument at a morphism "p" : "X" → "Y" gives morphisms
corresponding to the operation of composition with "p". Alternate notations for the operation "p""Z" include "p"* and "p∘-". Alternate notations for the operation "Z""p" include "p"* and "-∘p".
Evaluation maps can be chained as
the corresponding arrow under the exponential adjunction 
is called the (internal) composition map.
In the particular case of the category Set, this is the ordinary composition operation:
Sections.
For a morphism "p":"X" → "Y", suppose the following pullback square exists, which defines the subobject of "X""Y" corresponding to maps whose composite with "p" is the identity:
where the arrow on the right is "p""Y" and the arrow on the bottom corresponds to the identity on "Y". Then Γ"Y"("p") is called the object of sections of "p". It is often abbreviated as Γ"Y"("X").
If Γ"Y"("p") exists for every morphism "p" with codomain "Y", then it can be assembled into a functor Γ"Y" : "C"/"Y" → "C" on the slice category, which is right adjoint to a variant of the product functor:
The exponential by "Y" can be expressed in terms of sections:
Examples.
Examples of Cartesian closed categories include:
Examples of locally Cartesian closed categories include:
Non-examples of locally Cartesian closed categories include:
Applications.
In Cartesian closed categories, a "function of two variables" (a morphism "f" : "X"×"Y" → "Z") can always be represented as a "function of one variable" (the morphism λ"f" : "X" → "Z""Y"). In computer science applications, this is known as currying; it has led to the realization that simply-typed lambda calculus can be interpreted in any Cartesian closed category.
The Curry–Howard–Lambek correspondence provides a deep isomorphism between intuitionistic logic, simply-typed lambda calculus and Cartesian closed categories.
Certain Cartesian closed categories, the topoi, have been proposed as a general setting for mathematics, instead of traditional set theory.
The renowned computer scientist John Backus has advocated a variable-free notation, or Function-level programming, which in retrospect bears some similarity to the internal language of Cartesian closed categories. CAML is more consciously modelled on Cartesian closed categories.
Dependent sum and product.
Let "C" be a locally Cartesian closed category. Then "C" has all pullbacks, because the pullback of two arrows with codomain "Z" is given by the product in "C/Z".
For every arrow "p" : "X" → "Y", let "P" denote the corresponding object of "C/Y". Taking pullbacks along "p" gives a functor "p"* : "C/Y" → "C/X" which has both a left and a right adjoint.
The left adjoint formula_16 is called the dependent sum and is given by composition with "p".
The right adjoint formula_17 is called the dependent product.
The exponential by "P" in "C/Y" can be expressed in terms of the dependent product by the formula formula_18.
The reason for these names is because, when interpreting "P" as a dependent type formula_19, the functors formula_20 and formula_21 correspond to the type formations formula_22 and formula_23 respectively.
Equational theory.
In every Cartesian closed category (using exponential notation), ("X""Y")"Z" and ("X""Z")"Y" are isomorphic for all objects "X", "Y" and "Z". We write this as the "equation"
One may ask what other such equations are valid in all Cartesian closed categories. It turns out that all of them follow logically from the following axioms:
Bicartesian closed categories.
Bicartesian closed categories extend Cartesian closed categories with binary coproducts and an initial object, with products distributing over coproducts. Their equational theory is extended with the following axioms, yielding something similar to Tarski's high school axioms but with additive inverses:
Note however that the above list is not complete; type isomorphism in the free BCCC is not finitely axiomatizable, and its decidability is still an open problem.