nLab one-to-one correspondence

Contents

 Definition

In set theory

In set theory, there are many ways to say that given the relation or correspondence RR, R(x,y)R(x, y) holds of elements xAx \in A and yBy \in B. In allegorical set theories like SEAR, it is a foundational concept. In categorical set theories like ETCS with elements, we say that R(x,y)R(x, y) holds of elements xAx \in A and yBy \in B if the ordered pair (x,y)(x, y) is in the image of the function (p 1,p 2):RA×B(p_1, p_2):R \to A \times B. In material set theories like ZFC, we say that R(x,y)R(x, y) holds of elements xAx \in A and yBy \in B if the ordered pair (x,y)(x, y) is in RR.

In set theory, a one-to-one correspondence is a relation or correspondence RR between sets AA and BB for which for every element xAx \in A, there is a unique element yBy \in B such that R(x,y)R(x, y) holds, and for every element yBy \in B, there is a unique element xAx \in A such that R(x,y)R(x, y) holds. Equivalently, it is an anafunction RR between sets AA and BB such that for every element yBy \in B, there is a unique element xAx \in A such that R(x,y)R(x, y) holds.

In type theory

In type theory, given types AA and BB, a one-to-one correspondence is a correspondence x:A,y:BR(x,y)x:A, y:B \vdash R(x, y) for which for every element x:Ax:A, there exists a unique element y:By:B such that R(x,y)R(x, y), and for every element y:By:B, there exists a unique element x:Ax:A such that R(x,y)R(x, y). Equivalently, it is an anafunction x:A,y:BR(x,y)x:A, y:B \vdash R(x, y) such that for every element y:By:B, the dependent type x:AR(x,y)\sum_{x:A} R(x, y) is a contractible type.

Given a Tarski universe (U,T)(U, T), the type of all UU-small one-to-one correspondences between AA and BB is given by the type

OneToOneCorr U(A,B) R:A×BU( x:A!y:B.T(R(x,y))×( y:B!x:A.T(R(x,y)))\mathrm{OneToOneCorr}_U(A, B) \coloneqq \sum_{R:A \times B \to U} \left(\prod_{x:A} \exists!y:B.T(R(x, y)\right) \times \left(\prod_{y:B} \exists!x:A.T(R(x, y))\right)

The univalence axiom for UU is given by the equivalence of types

ua U: A:U B:U(A= UB)OneToOneCorr U(T(A),T(B))\mathrm{ua}_U:\prod_{A:U} \prod_{B:U} (A =_U B) \simeq \mathrm{OneToOneCorr}_U(T(A), T(B))

 Properties

By the principle of unique choice, given every one-to-one correspondence, there is a bijection f:ABf:A \cong B. However, in the absence of the principle of unique choice, bijections and one-to-one correspondences are not necessarily the same; this is the same phenomena as the phenomena between functions and anafunctions. However, frequently in material set theories, functions are defined to be anafunctions, and so bijections are similarly defined to be one-to-one correspondences.

Something similar occurs in dependent type theory, where by the principle of unique choice, given every one-to-one correspondence, there is a function with contractible fibers x:Af(x):Bx:A \vdash f(x):B, which becomes a bijection in the context of axiom K or uniqueness of identity proofs. However, in contrast to material set theory, in dependent type theory, there is always a distinction between a function x:Af(x):Bx:A \vdash f(x):B and an anafunction x:A,y:BR(x,y)x:A, y:B \vdash R(x, y), and so there is always a distinction between a function with contractible fibers and a one-to-one correspondence.

See also

Last revised on July 22, 2023 at 06:14:50. See the history of this page for a list of all contributions to it.