nLab equality

Contents

Context

Equality and Equivalence

Foundations

foundations

The basis of it all

 Set theory

set theory

Foundational axioms

foundational axiom

Removing axioms

Contents

Idea

There is a lot of interesting stuff to be said about equality in logic, higher category theory, and the foundations of mathematics, but it hasn't all been said here yet.

Different kinds of equality

Here is a list of distinctions between different notions of equality, in different contexts, where possibly all the following pairs of notions are, in turn, “the same”, just expressed in terms of different terminologies:

  • the difference between axiomatic and defined equality;
  • the difference between identity and equality,
  • the difference between intensional and extensional equality,
  • the difference between equality judgements, equality propositions, and equality types
  • the difference between equality and isomorphism,
  • the difference between equality and equivalence,
  • the possibility of operations that might not preserve equality.

Notions of equality in type theory

In a formal language such as type theory, one distinguishes various different notions of equality or equivalence of the terms of the language.

In type theory, there are broadly three different notions of equality which could be distinguished: judgmental equality, propositional equality, and typal equality. Judgmental equality is defined as a basic judgment in type theory. Propositional equality is defined as a proposition in any two-layered type theory with a layer of types and a layer of propositions. Typal equality defined as a type in type theory.

Judgmental equality

The first notion of equality is judgmental equality, where we simply judge two elements to be equal to each other. Judgmental equality is expressed in type theory by a separate judgment: in addition to typing judgments Γ(t:A)\Gamma \vdash (t:A), we have equality judgments Γ(t=t):A\Gamma \vdash (t = t'): A. The rules for manipulating such judgments then include reflexivity, symmetry, transitivity, making judgmental equality into a judgmental equivalence relation.

However, not all type theories have judgmental equality; most first-order theories use propositional equality in place of judgmental equality, and objective type theories use typal equality in place of judgmental equality.

Propositional equality

In any two-layer type theory with a layer of types and a layer of propositions, or equivalently a first order logic over type theory or a first-order theory, every type AA has a binary relation according to which two elements xx and yy of AA are related if and only if they are equal; in this case we write x= Ayx =_A y. Since relations are propositions in the context of a term variable judgment in the type layer, this is called propositional equality. Notable examples of propositional equality include the equality in all flavors of set theory, such as ZFC or ETCS.

The presence of propositional equality is part of the axiomatization of first-order theories, although this is usually swept under the rug by including propositional equality by default in all first-order theories. (It has to be made more explicit in a structural set theory such as SEAR, where there is no propositional equality on sets themselves, only on elements of a particular set.) By contrast, in a first order theory without propositional equality, propositional equality is an equivalence relation which has to be put onto a type or preset.

Typal equality

However, not all type theories are first order logic over type theory, nor are they even two-layered type theories. In type theories with only one layer for types, equality is not a relation. Instead, we have what are called typal equality, as equality of both terms and types are represented by types. Typal equality of terms is also called the equality type, identity type, path type, or identification type, and the terms of typal equality are called equalities, identities, identifications, paths. Notable examples of typal equality of terms include the identity type in Martin-Löf type theory and higher observational type theory, and the cubical path type in cubical type theory. Typal equality of types is also called equivalence of types, are written as ABA \simeq B for types AA and BB and are definable in all type theories with typal equality of terms, function types, dependent product types, and dependent sum types.

Type theories with only typal equality are called objective type theories. In type theories with both typal equality and either judgmental equality or propositional equality, one could distinguish between intensional type theories and extensional type theories: extensional type theories are type theories with an equality reflection rule, where one could derive judgmental or propositional equality of terms from typal equality of terms:

Γp:a= AbΓab:AΓ|Φp:a= AbΓ|Φa Abtrue\frac{\Gamma \vdash p:a =_A b}{\Gamma \vdash a \equiv b:A} \qquad \frac{\Gamma \vert \Phi \vdash p:a =_A b}{\Gamma \vert \Phi \vdash a \equiv_A b \; \mathrm{true}}

Intensional type theories are then type theories with typal equality and one of either judgmental or propositional equality without an equality reflection rule. Note that this notion of extensionality is different from the axiom of extensionality or function extensionality.

Comparison of equalities

This table gives the six different notions of equality found in type theory.

Judgmentof typesof terms
Judgmental equalityΓA=Btype\Gamma \vdash A = B \; \mathrm{type}Γa=b:A\Gamma \vdash a = b:A
Propositional equalityΓ|ΦA=Btrue\Gamma \vert \Phi \vdash A = B \; \mathrm{true}Γ|Φa= Abtrue\Gamma \vert \Phi \vdash a =_A b \; \mathrm{true}
Typal equalityΓP:AB\Gamma \vdash P:A \simeq BΓp:a= Ab\Gamma \vdash p:a =_A b

Structural rules of equalities

Reflexivity

The reflexivity of equality is given by the following judgmental, propositional, and typal rules respectively:

  • Reflexivity of judgmental equality
ΓAtypeΓA=Atype\frac{\Gamma \vdash A \; \mathrm{type}}{\Gamma \vdash A = A \; \mathrm{type}}
ΓAtypeΓa:AΓa=a:A\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash a:A}{\Gamma \vdash a = a:A}
  • Reflexivity of propositional equality

    Γ|ΦAtypeΓ|ΦA=Atrue\frac{\Gamma \vert \Phi \vdash A \; \mathrm{type}}{\Gamma \vert \Phi \vdash A = A \; \mathrm{true}}
    Γ|ΦAtypeΓ|Φa:AΓ|Φa= Aatrue\frac{\Gamma \vert \Phi \vdash A \; \mathrm{type} \quad \Gamma \vert \Phi \vdash a:A}{\Gamma \vert \Phi \vdash a =_A a \; \mathrm{true}}
  • Reflexitivity of typal equality (i.e. identity function and identity path)

    ΓAtypeΓid A:AA\frac{\Gamma \vdash A \; \mathrm{type}}{\Gamma \vdash id_{A}:A \simeq A}
    ΓAtypeΓa:AΓrefl A(a):a= Aa\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash a:A}{\Gamma \vdash \mathrm{refl}_{A}(a):a =_A a}

Symmetry

The symmetry of equality is given by the following judgmental, propositional, and typal rules respectively:

  • Symmetry of judgmental equality

    ΓA=BtypeΓB=Atype\frac{\Gamma \vdash A = B \; \mathrm{type}}{\Gamma \vdash B = A \; \mathrm{type}}
    ΓAtypeΓa=b:AΓb=a:A\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash a = b:A}{\Gamma \vdash b = a:A}
  • Symmetry of propositional equality

    Γ|ΦAtypeΓ|ΦBtypeΓ|ΦA=BtrueΓ|ΦB=Atrue\frac{\Gamma \vert \Phi \vdash A \; \mathrm{type} \quad \Gamma \vert \Phi \vdash B \; \mathrm{type} \quad \Gamma \vert \Phi \vdash A = B \; \mathrm{true}}{\Gamma \vert \Phi \vdash B = A \; \mathrm{true}}
    Γ|ΦAtypeΓ|Φa:AΓ|Φb:AΓ|Φa= AbtrueΓ|Φb= Aatrue\frac{\Gamma \vert \Phi \vdash A \; \mathrm{type} \quad \Gamma \vert \Phi \vdash a:A \quad \Gamma \vert \Phi \vdash b:A \quad \Gamma \vert \Phi \vdash a =_A b \; \mathrm{true}}{\Gamma \vert \Phi \vdash b =_A a \; \mathrm{true}}
  • Symmetry of typal equality (i.e. inverse function and inverse path)

    ΓAtypeΓBtypeΓP:ABΓP 1:BA\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash B \; \mathrm{type} \quad \Gamma \vdash P:A \simeq B}{\Gamma \vdash P^{-1}:B \simeq A}
    ΓAtypeΓa:AΓb:AΓp:a= AbΓp 1:b= Aa\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash a:A \quad \Gamma \vdash b:A \quad \Gamma \vdash p:a =_A b}{\Gamma \vdash p^{-1}:b =_A a}

Transitivity

The transitivity of equality is given by the following judgmental, propositional, and typal rules respectively:

  • Transitivity of judgmental equality

    ΓA=BtypeΓB=CtypeΓA=Ctype\frac{\Gamma \vdash A = B \; \mathrm{type} \quad \Gamma \vdash B = C \; \mathrm{type} }{\Gamma \vdash A = C \; \mathrm{type}}
    ΓAtypeΓa=b:Ab=c:AΓa=c:A\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash a = b:A \quad b = c:A }{\Gamma \vdash a = c:A}
  • Transitivity of propositional equality

    Γ|ΦAtypeΓ|ΦBtypeΓ|ΦCtypeΓ|ΦA=BtrueΓ|ΦB=CtrueΓ|ΦA=Ctrue\frac{\Gamma \vert \Phi \vdash A \; \mathrm{type} \quad \Gamma \vert \Phi \vdash B \; \mathrm{type} \quad \Gamma \vert \Phi \vdash C \; \mathrm{type} \quad \Gamma \vert \Phi \vdash A = B \; \mathrm{true} \quad \Gamma \vert \Phi \vdash B = C \; \mathrm{true}}{\Gamma \vert \Phi \vdash A = C \; \mathrm{true}}
    Γ|ΦAtypeΓ|Φa:AΓ|Φb:AΓ|Φc:AΓ|Φa= AbtrueΓ|Φb= ActrueΓ|Φa= Actrue\frac{\Gamma \vert \Phi \vdash A \; \mathrm{type} \quad \Gamma \vert \Phi \vdash a:A \quad \Gamma \vert \Phi \vdash b:A \quad \Gamma \vert \Phi \vdash c:A \quad \Gamma \vert \Phi \vdash a =_A b \; \mathrm{true} \quad \Gamma \vert \Phi \vdash b =_A c \; \mathrm{true}}{\Gamma \vert \Phi \vdash a =_A c \; \mathrm{true}}
  • Transitivity of typal equality (i.e. composition of functions and path concatenation)

    ΓAtypeΓBtypeΓCtypeΓP:ABΓQ:BCΓQP:AC\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash B \; \mathrm{type} \quad \Gamma \vdash C \; \mathrm{type} \quad \Gamma \vdash P:A \simeq B \quad \Gamma \vdash Q:B \simeq C}{\Gamma \vdash Q \circ P:A \simeq C}
    ΓAtypeΓa:AΓb:AΓc:AΓp:a= AbΓq:b= AcΓpq:a= Ac\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash a:A \quad \Gamma \vdash b:A \quad \Gamma \vdash c:A \quad \Gamma \vdash p:a =_A b \quad \Gamma \vdash q:b =_A c}{\Gamma \vdash p \bullet q:a =_A c}

Principle of substituting equals for equals

The principle of substituting equals for equals is given by the following judgmental, propositional, and typal rules respectively:

  • Substitution of judgmentally equal terms:

    ΓAtypeΓa=b:AΓ,x:A,ΔBtypeΓ,Δ[b/x]B[a/x]=B[b/x]type\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash a = b : A \quad \Gamma, x:A, \Delta \vdash B \; \mathrm{type}}{\Gamma, \Delta[b/x] \vdash B[a/x] = B[b/x] \; \mathrm{type}}
    ΓAtypeΓa=b:AΓ,x:A,Δc:BΓ,Δ[b/x]c[a/x]=c[b/x]:B[b/x]\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash a = b : A \quad \Gamma, x:A, \Delta \vdash c:B}{\Gamma, \Delta[b/x] \vdash c[a/x] = c[b/x]: B[b/x]}
  • Substitution of propositionally equal terms:

    Γ|ΦAtypeΓ|Φa:AΓ|Φb:AΓ|Φa= AbtrueΓ,x:A,Δ|ΦBtypeΓ,Δ[b/x]|Φ[b/x]B[a/x]=B[b/x]true\frac{\Gamma \vert \Phi \vdash A \; \mathrm{type} \quad \Gamma \vert \Phi \vdash a : A \quad \Gamma \vert \Phi \vdash b : A \quad \Gamma \vert \Phi \vdash a =_A b \; \mathrm{true} \quad \Gamma, x:A, \Delta \vert \Phi \vdash B \; \mathrm{type}}{\Gamma, \Delta[b/x] \vert \Phi[b/x] \vdash B[a/x] = B[b/x] \; \mathrm{true}}
    Γ|ΦAtypeΓ|Φa:AΓ|Φb:AΓ|Φa= AbtrueΓ,x:A,Δ|Φc:BΓ,Δ[b/x]|Φ[b/x]c[a/x]= B[b/x]c[b/x]true\frac{\Gamma \vert \Phi \vdash A \; \mathrm{type} \quad \Gamma \vert \Phi \vdash a : A \quad \Gamma \vert \Phi \vdash b : A \quad \Gamma \vert \Phi \vdash a =_A b \; \mathrm{true} \quad \Gamma, x:A, \Delta \vert \Phi \vdash c:B}{\Gamma, \Delta[b/x] \vert \Phi[b/x] \vdash c[a/x] =_{B[b/x]} c[b/x] \; \mathrm{true}}
  • Substitution of typally equal terms (i.e. transport and action on identifications):

    ΓAtypeΓa:AΓb:AΓp:a= AbΓ,x:A,ΔBtypeΓ,Δ[b/x]tr(x.B,a,b,p):B[a/x]B[b/x]\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash a:A \quad \Gamma \vdash b:A \quad \Gamma \vdash p:a =_A b \quad \Gamma, x:A, \Delta \vdash B \; \mathrm{type}}{\Gamma, \Delta[b/x] \vdash \mathrm{tr}(x.B, a, b, p):B[a/x] \simeq B[b/x]}
    ΓAtypeΓa:AΓb:AΓp:a= AbΓ,x:A,Δc:BΓ,Δ[b/x]ap(c,x.B,a,b,p):tr(x.B,a,b,p)(c[a/x])= B[b/x]c[b/x]\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash a:A \quad \Gamma \vdash b:A \quad \Gamma \vdash p:a =_A b \quad \Gamma, x:A, \Delta \vdash c:B}{\Gamma, \Delta[b/x] \vdash \mathrm{ap}(c, x.B, a, b, p):\mathrm{tr}(x.B, a, b, p)(c[a/x]) =_{B[b/x]} c[b/x]}

Variable conversion

The variable conversion rule is given by the following judgmental, propositional, and typal rules respectively:

  • Judgmental variable conversion rule:

    ΓA=BtypeΓ,x:A,Δ𝒥Γ,x:B,Δ𝒥\frac{\Gamma \vdash A = B \; \mathrm{type} \quad \Gamma, x:A, \Delta \vdash \mathcal{J}}{\Gamma, x:B, \Delta \vdash \mathcal{J}}
  • Propositional variable conversion rule:

    Γ|ΦAtypeΓ|ΦBtypeΓ|ΦA=BtrueΓ,x:A,Δ|Φ𝒥Γ,x:B,Δ|Φ𝒥\frac{\Gamma \vert \Phi \vdash A \; \mathrm{type} \quad \Gamma \vert \Phi \vdash B \; \mathrm{type} \quad \Gamma \vert \Phi \vdash A = B \; \mathrm{true} \quad \Gamma, x:A, \Delta \vert \Phi \vdash \mathcal{J}}{\Gamma, x:B, \Delta \vert \Phi \vdash \mathcal{J}}
  • Typal variable conversion rule:

    ΓAtypeΓBtypeΓP:ABΓ,x:A,Δ𝒥Γ,y:B,Δ[P 1(y)/x]𝒥[P 1(y)/x]\frac{\Gamma \vdash A \; \mathrm{type} \quad \Gamma \vdash B \; \mathrm{type} \quad \Gamma \vdash P:A \simeq B \quad \Gamma, x:A, \Delta \vdash \mathcal{J}}{\Gamma, y:B, \Delta[P^{-1}(y)/x] \vdash \mathcal{J}[P^{-1}(y)/x]}

𝒥\mathcal{J} is a generic judgment thesis.

Usages of equality

In definitions of types and terms

The three different notions of equality above could be used in definitions of types and terms, as well as in the rules for the single assignment operator \coloneqq. In Martin-Löf type theory and cubical type theory, judgmental equality is used for definitional equality. In ZFC and ETCS, propositional equality is used for definitional equality, and in objective type theories, typal equality is used for definitional equality.

In conversion rules and inductive definitions

The three different notions of equality above could also be used in the conversion rules for the various type formers, such as beta conversion or eta conversion, where the equality is called conversional equality or computational equality. Computational equality is important because it is the equality used in inductive definitions. In Martin-Löf type theory and cubical type theory, judgmental equality is used for computational equality, and in objective type theories, typal equality is used for computational equality.

Meta-equalities

There are also equalities in type theory which are not internal to the type theory itself, but rather equalties in the metatheroy. These include syntactic equality of expressions, as well as alpha-equivalence and definitional equality of syntactical expressions. When using de Bruijn indices, alpha-equivalence is the same as syntactic equality, but when using variables, alpha-equivalence is different from syntactic equality: rather alpha-equivalence is equality up to the renaming of bound variables. All type theories, like MLTT, cubical type theory, ZFC, and ETCS, have syntactic equality, alpha-equivalence, and definitional equality of syntactical expressions, including the type theories which lack judgmental equality like objective type theories.

Internal equality in set theory

Relations and equality could be internalized in any set theory: the internal equality in set theory is the smallest internal reflexive relation on SS, and it is in fact an internal equivalence relation; it is the only internal equivalence relation on SS that is also a partial order (although that fact is somewhat circular). This relation is often called the identity relation on SS, either because ‘identity’ can mean ‘equality’ or because it is the identity for composition of relations.

In the category of reflexive relations on SS, the equality relation on SS is an initial reflexive relation; when the equality relation is a type family instead of a family of propositions, then the equality relation is the initial type generated by reflexivity or the first law of thought.

As a subset of S×SS \times S, the equality relation is often called the diagonal and written Δ S\Delta_S or similarly. As an abstract set, this subset is isomorphic to SS itself, so one also sees the diagonal as a map, the diagonal function SΔ SS×SS \overset{\Delta_S}\to S \times S, which maps xx to (x,x)(x,x); note that x=xx = x. This is in Set; analogous diagonal morphisms exist in any cartesian monoidal category.

\phantom{-}symbol\phantom{-}\phantom{-}in logic\phantom{-}
A\phantom{A}\inA\phantom{A}element relation
A\phantom{A}:\,:A\phantom{A}typing relation
A\phantom{A}==A\phantom{A}equality
A\phantom{A}\vdashA\phantom{A}A\phantom{A}entailment / sequentA\phantom{A}
A\phantom{A}\topA\phantom{A}A\phantom{A}true / topA\phantom{A}
A\phantom{A}\botA\phantom{A}A\phantom{A}false / bottomA\phantom{A}
A\phantom{A}\RightarrowA\phantom{A}implication
A\phantom{A}\LeftrightarrowA\phantom{A}logical equivalence
A\phantom{A}¬\notA\phantom{A}negation
A\phantom{A}\neqA\phantom{A}negation of equality / apartnessA\phantom{A}
A\phantom{A}\notinA\phantom{A}negation of element relation A\phantom{A}
A\phantom{A}¬¬\not \notA\phantom{A}negation of negationA\phantom{A}
A\phantom{A}\existsA\phantom{A}existential quantificationA\phantom{A}
A\phantom{A}\forallA\phantom{A}universal quantificationA\phantom{A}
A\phantom{A}\wedgeA\phantom{A}logical conjunction
A\phantom{A}\veeA\phantom{A}logical disjunction
symbolin type theory (propositions as types)
A\phantom{A}\toA\phantom{A}function type (implication)
A\phantom{A}×\timesA\phantom{A}product type (conjunction)
A\phantom{A}++A\phantom{A}sum type (disjunction)
A\phantom{A}00A\phantom{A}empty type (false)
A\phantom{A}11A\phantom{A}unit type (true)
A\phantom{A}==A\phantom{A}identity type (equality)
A\phantom{A}\simeqA\phantom{A}equivalence of types (logical equivalence)
A\phantom{A}\sumA\phantom{A}dependent sum type (existential quantifier)
A\phantom{A}\prodA\phantom{A}dependent product type (universal quantifier)
symbolin linear logic
A\phantom{A}\multimapA\phantom{A}A\phantom{A}linear implicationA\phantom{A}
A\phantom{A}\otimesA\phantom{A}A\phantom{A}multiplicative conjunctionA\phantom{A}
A\phantom{A}\oplusA\phantom{A}A\phantom{A}additive disjunctionA\phantom{A}
A\phantom{A}&\&A\phantom{A}A\phantom{A}additive conjunctionA\phantom{A}
A\phantom{A}\invampA\phantom{A}A\phantom{A}multiplicative disjunctionA\phantom{A}
A\phantom{A}!\;!A\phantom{A}A\phantom{A}exponential conjunctionA\phantom{A}

References

In

equality is the subject of volume 1, book 2 “Die Lehre vom Wesen” (The doctrine of essence). As discussed at Science of Logic, one can roughly identify in Hegel’s text there the notion of intensional identity and of the reflector term in identity types.

Texts on type theory typically deal with the subtleties of the notion of equality. For instance

Besides

  • Kurt Gödel, Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes. Dialectica (1958), pp. 280–287,

which might be the first paper to mention intensional equality (and the fact that it should be decidable), there is

where de Bruijn makes a distinction between definitional equality and “book” equality.

Last revised on November 9, 2022 at 03:31:08. See the history of this page for a list of all contributions to it.