nLab finite object

Redirected from "Kuratowski finite".
Finite objects

This entry is about finite objects in generalization of finite sets. For generalization of finite-dimensional vector spaces see instead at dualizable object.


Finite objects

Idea

The notion of finite object in a category – notably in a topos – is a generalisation of the notion of finite set in the category of sets.

As there are already at least five distinct notions of finite set in constructive mathematics, so there must be at least five distinct notions of finite object internal to a topos. Additionally, the definitions may also be interpreted in an ‘external’ sense, giving even further notions. Only some are mentioned below.

Also beware that in category theory the term ‘finite object’ is also used in a much more general sense to mean a compact object. Similar finiteness meaning may also be attributed to dualizable objects in monoidal categories and to perfect complexes (of abelian sheaves) in geometry.

Definitions

Consider an ambient topos 𝒯\mathcal{T}. Assume that 𝒯\mathcal{T} is equipped with a natural numbers object NN. Write N <N×NN_{\lt} \hookrightarrow N\times N for its strict total order relation.

External version

A “finite set” in 𝒯\mathcal{T} in the strictest sense is usually called a finite cardinal. This is an object [n]𝒞[n] \in \mathcal{C} which is the pullback of N <NN_{\lt}\to N along some global element n:1Nn:1\to N.

We can then consider subobjects, quotient objects, and subquotient objects of finite cardinals to obtain external versions of subfinite, finitely indexed, and subfinitely indexed sets.

Internal version

The internal version of a “finite set” is an object XX such that “XX is a finite cardinal” is true in the internal logic. This is equivalent to the following

Definition

An object X𝒯X \in \mathcal{T} is locally isomorphic to a finite cardinal, if there is an epimorphism U1U\to 1 and a generalized element n:UNn:U\to N such that U×Xn *(N <)U\times X \cong n^*(N_\lt) over UU. Equivalently, there is a U1U\to 1 such that U×XU\times X is a finite cardinal in the slice topos 𝒯/U\mathcal{T}/U.

An internally finitely indexed object is an object XX which is locally a quotient of a finite cardinal, hence such that there is an epimorphism U*U \to *, a finite cardinal in the slice topos n𝒯 /Un \in \mathcal{T}_{/U} and an epimorphism nU×Xn \to U \times X.

An “internally finitely indexed” object is generally called a Kuratowski-finite object or KK-finite object for short, and an “internally subfinitely indexed” one is called a K˜\tilde{K}-finite object.

There is a more general definition of K-finite objects that does not need to assume the presence of a natural number object. See (Johnstone, theorem D5.4.13).

Since it is still provable in the internal logic that any decidable finitely indexed set is finite, the “internally finite” objects (those that are locally isomorphic to a finite cardinal, as above) can be characterized as the decidable KK-finite objects.

Dedekind finiteness

An object is Dedekind finite or co-Hopfian (in analogy to Hopfian group) if every monic endomorphism is an automorphism. This definition makes sense in any category.

Properties

Closure of finite objects

The following lists closure properties of K-finite objects, def. .

Proposition
  1. The initial object and the terminal object are K-finite.

  2. The image of a K-finite object under an epimorphism is K-finite.

  3. The union of two K-finite subobjects is K-finite.

  4. A coproduct is K-finite precisely if both summands are.

  5. A subterminal object is K-finite precisely if it is a complemented subobject.

  6. A product of two K-finite objects is K-finite.

This appears in (Johnstone) as lemma D5.4.4, corollary D5.4.5, pro. 5.4.8.

Subcategories of finite objects

The full subcategory of finite cardinals in any topos is again a topos, and it is Boolean. Its subobject classifier is 2=112=1\sqcup 1, which in the ambient topos is the classifier only of decidable subobjects. This means that classically valid arguments, including all of finitary combinatorics, can generally be applied easily to finite cardinals, as long as we always interpret “subset” to mean “decidable subset.”

Theorem

The full subcategory 𝒯 dKf𝒯\mathcal{T}_{dKf} \hookrightarrow \mathcal{T} of decidable KK-finite objects in a topos 𝒯\mathcal{T} is a Boolean topos whose subobject classifier is 22.

The category of KK-finite objects is a topos if and only if every KK-finite object is decidable, and the category of K˜\tilde{K}-finite objects is a topos if (but not only if) the subobject classifier is KK-finite.

The first statement appears as (Johnstone, theorem 5.4.18).

Remark

The full subcategory 𝒯 dKf𝒯\mathcal{T}_{dKf} \hookrightarrow \mathcal{T} can be regarded as the “stack completion” of the topos of finite cardinals.

Relation to slice toposes

Proposition

An object X𝒯X \in \mathcal{T} is K-finite precisely if the étale geometric morphism

𝒯 /X𝒯 \mathcal{T}_{/X} \to \mathcal{T}

out of the slice topos is a proper geometric morphism.

(Moerdijk-Vermeulen, examples III 1.4)

Examples

  • In any Boolean topos, all four internal notions coincide. In a well-pointed topos, each internal notion coincides with its external notion. Therefore, in a well-pointed Boolean topos, including the topos Set as usually conceived, all notions of finiteness coincide.

  • In a presheaf topos [C op,Set][C^{op},Set], the finite cardinals are the finite-set-valued functors which are constant on each connected component. In particular, if CC is a group, then the topos of finite cardinals is equivalent to FinSet.

  • Likewise, in the Grothendieck topos Sh(X)Sh(X) of sheaves on a space XX, the finite cardinals are the locally constant functions XNX\to N. So if XX is connected, the topos of finite cardinals in Sh(X)Sh(X) is also equivalent to FinSetFinSet.

  • Examples of such are tiny objects and infinitesimal objects in sheaf toposes.

  • By contrast, the KK-finite objects in [C op,Set][C^{op},Set] are the finite-set-valued functors each of whose transition functions is surjective, and the decidable K-finite objects are the finite-set-valued functors each of whose transition functions is bijective.

  • In particular, if CC is a groupoid, the topos of decidable KK-finite objects is equivalent to [C op,FinSet][C^{op},FinSet]. Since the topos of presheaves on a groupoid is Boolean, this gives an example of a Boolean topos in which the finite cardinals (“externally finite objects”) and the (decidable) KK-finite objects (“internally finite objects”) fail to coincide.

  • In the category of sheaves Sh(X)Sh(X) over a topological space, the decidable K-finite objects are those that are “locally finite;” i.e. there is an open cover of XX such that over each open in the cover, the sheaf is a locally constant function to NN. These are essentially the same as covering spaces of XX with finite fibres.

finite objects:

geometrymonoidal category theorycategory theory
perfect module(fully-)dualizable objectcompact object

References

In

finite cardinal objects are discussed in section D5.2, Kuratowski finite objects in section D5.4

See also

  • O. Acuña-Ortega, Fred Linton, Finiteness and decidability: I , Springer Lecture Notes in Mathematics, (1979), Volume 753, pp.80-100, (DOI: 10.1007/BFb0061813)

  • Peter Johnstone, Fred Linton, Finiteness and decidability: II , Cambridge Philosophical Society Mathematical Proceedings of the Cambridge Philosophical Society (1978).

  • B. P. Chisala, M.-M. Mawanda, Counting Measure for Kuratowski Finite Parts and Decidability , Cah.Top.Géom.Diff.Cat. XXXII 4 (1991) pp.345-353. (pdf)

  • S. J. Henry, Classifying Topoi and Preservation of Higher Order Logic by Geometric Morphisms , PhD University of Michigan (2013). (arxiv)

  • C. Kuratowski, Sur la notion d’ensemble fini , Fund. Math. 1 (1920) pp.129-131. (pdf)

  • Ieke Moerdijk, J. Vermeulen, Relative compactness conditions for toposes (pdf) and Proper maps of toposes , American Mathematical Society (2000)

  • L. N. Stout, Dedekind finiteness in topoi , JPAA 49 (1987) pp.219-225.

  • T. Streicher, P. Freyd, F. Linton, P.Johnstone, W. Lawvere, catlist discussion ‘finiteness in toposes’, January 1997. (link)

  • A. Tarski, Sur les ensembles finis , Fund. Math. 3 (1924) pp.45-95. (pdf)

  • H. Volger, Ultrafilters, ultrapowers and finiteness in a topos , JPAA 6 (1975) pp.345-356.

Last revised on January 22, 2024 at 12:50:10. See the history of this page for a list of all contributions to it.