|logic||category theory||type theory|
|true||terminal object/(-2)-truncated object||h-level 0-type/unit type|
|false||initial object||empty type|
|proposition||(-1)-truncated object||h-level 1-type/h-prop|
|cut elimination for implication||counit for hom-tensor adjunction||beta reduction|
|introduction rule for implication||unit for hom-tensor adjunction||eta conversion|
|disjunction||coproduct ((-1)-truncation of)||sum type (bracket type of)|
|implication||internal hom||function type|
|negation||internal hom into initial object||function type into empty type|
|universal quantification||dependent product||dependent product type|
|existential quantification||dependent sum ((-1)-truncation of)||dependent sum type (bracket type of)|
|equivalence||path space object||identity type|
|equivalence class||quotient||quotient type|
|induction||colimit||inductive type, W-type, M-type|
|higher induction||higher colimit||higher inductive type|
|completely presented set||discrete object/0-truncated object||h-level 2-type/preset/h-set|
|set||internal 0-groupoid||Bishop set/setoid|
|universe||object classifier||type of types|
|modality||closure operator monad||modal type theory, monad (in computer science)|
|linear logic||(symmetric, closed) monoidal category||linear type theory/quantum computation|
|proof net||string diagram||quantum circuit|
|(absence of) contraction rule||(absence of) diagonal||no-cloning theorem|
A function is defined by its association to each input value (belonging to some allowable domain of values) of an output value, usually denoted or . The process of passing from and to is called function application, and one speaks of applying to to produce .
The determination of the allowable domain for , given , depends a bit on foundational choices. In type theory and structural set theory, all functions have a type (a function type, naturally) which specifies their domain and codomain. In material set theory, a function is sometimes defined to be simply a particular sort of set of ordered pairs, with its domain specified implicitly as the set of elements occurring as first components of some such pair. (However, even in material set theory it is sometimes important for a function to come with a specified domain and/or codomain, in which case it can be defined to be an ordered triple.)
In formalized logic and type theory, , , and are terms (or more precisely, metavariables? standing for terms), and the process of function application is a rule of term formation. This is something which belongs to the realm of syntax. On propositions ((-1)-truncated types) this is the modus ponens deduction rule.
Under a denotational semantics, each of these terms denotes a particular object, and we also refer to the object denoted by as the result of applying the object denoted by to the object denoted by . For instance, in a material set-theoretic semantics, would denote a set of ordered pairs such that for any , there is at most one such that , and would denote some such that there does exist such a , and would denote that uniquely specified . The distinction between the terms , , and and what they denote is usually (and harmlessly) blurred in ordinary mathematical practice, but when studying logic and type theory formally it becomes important.
Under an operational semantics, by contrast, the “meaning” of the term lies in how it is “evaluated”. Usually this proceeds by beta-reduction and related rules. For instance, if is the term and is the term (the numeral two?), then is which beta-reduces to . The definition of can then be invoked to cause futher beta-reductions resulting in (the numeral four).