nLab finite object

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

---

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 $N$. Write $N_{\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] \in \mathcal{C}$ which is the pullback of $N_{\lt}\to N$ along some global element $n: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 $X$ such that “$X$ is a finite cardinal” is true in the internal logic. This is equivalent to the following

Definition

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

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

An “internally finitely indexed” object is generally called a Kuratowski-finite object or $K$-finite object for short, and an “internally subfinitely indexed” one is called a $\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 $K$-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=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 $\mathcal{T}_{dKf} \hookrightarrow \mathcal{T}$ of decidable $K$-finite objects in a topos $\mathcal{T}$ is a Boolean topos whose subobject classifier is $2$.

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

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

Remark

The full subcategory $\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 \in \mathcal{T}$ is K-finite precisely if the étale geometric morphism

$$\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]$, the finite cardinals are the finite-set-valued functors which are constant on each connected component. In particular, if $C$ is a group, then the topos of finite cardinals is equivalent to FinSet.

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

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

• By contrast, the $K$-finite objects in $[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 $C$ is a groupoid, the topos of decidable $K$-finite objects is equivalent to $[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) $K$-finite objects (“internally finite objects”) fail to coincide.

• In the category of sheaves $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 $X$ such that over each open in the cover, the sheaf is a locally constant function to $N$. These are essentially the same as covering spaces of $X$ with finite fibres.

Related concepts

• finite set, hereditarily finite set

• finite category, finite limit

• finite graph

• decidable object, theory of objects

• finite type

• finite homotopy type, finite CW-complex, finite spectrum

• π-finite homotopy type

• finite (infinity,1)-category, finite (infinity,1)-limit

finite objects:

geometry	monoidal category theory	category theory
perfect module	(fully-)dualizable object	compact object

References

In

• Peter Johnstone, Sketches of an elephant

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.