Conditions equivalent to finiteness

Question

We've all probably come across some conditions that naturally imply finiteness, or are equivalent to it. For ZFC examples:

1. A set $X$ can be ordered in such a way that the ordering is well-founded and reverse well-founded iff $X$ is finite.
2. The discrete topology on $X$ is compact iff $X$ is finite (this can probably be strengthened topologists).
3. A set $X$ is finite iff it has no countably infinite subsets.
4. A set $X$ is finite iff every self-injection is a surjection.

(The last two 'Dedekind finiteness' conditions fail if we remove choice, I believe)

What other conditions are equivalent to being finite in various background theories?

More ZFC examples are definitely welcome, but I'm also interested if working in weaker/stronger background theories can make fewer/more conditions equivalent to finiteness, or perhaps break an iff in one direction.

Answer 1

A set is infinite iff it admits a structure of non-commutative skew-field.

(One direction is Wedderburn's theorem. The other: If $\alpha$ is an infinite cardinal, choose a nonsplit quaternion algebra over $\mathbf{Q}(X_i:i\in\alpha)$.)

Answer 2

A set $X$ is infinite iff it admits two distinct elements, and admits a bijection $X^2\to X$.

(A set $X$ endowed with a binary law $X^2\to X$ that is bijective is called a Jónsson-Tarski algebra, see Wikipedia. Free Jónsson-Tarski algebras have interesting combinatorics and automorphism groups.)

Answer 3

1. $X$ is finite if and only if every linear order on $X$ is a well-order.

2. $X$ is finite if and only if every partial order has a maximal element.

3. $X$ is finite if and only if $\mathcal P(X)$ is well-founded under $\subseteq$, and this is provable in ZF.

4. $X$ is finite if and only if every $T_1$ topology on $X$ is $T_2$ or $T_{2.5}$ or $T_3$ or $T_4$ or discrete or compact.

5. $X$ is finite if and only if every two linear/well orders are isomorphic.

Answer 4

Here are examples of finiteness that is classically equivalent, but different in constructive mathematics.

• A set is finite if it is equipotent with an element of $\omega$.
• A set is subfinite if it is a subjective image of a subset of an element of $\omega$.
• A set is finitely enumerable if there is a surjection from an element of $\omega$ to the given set.

(The previous definition of subfiniteness was wrong. Thank you for Andreas Blass for pointing it out.)

It is known that every finite set is finitely enumerable, and finitely enumerable sets are subfinite. However, the converse does not hold unless we have the law of excluded middle. Brouwerian counterexamples for separating these notions are the following: let $P$ be a statement whose validity is not known.

1. Consider the set $A=\{0\mid P\}$. Then $A_0$ is subfinite. However, it is not finitely enumerable. If there is a surjection from $0$ to $A$, then $\lnot P$ holds. If there is a surjection from a non-zero natural number to $A$, then $P$ holds. Hence the finite enumerability of $A$ implies $P\lor\lnot P$.
2. Now consider the set $B=\{0,A,1\}$. It is finitely enumerable. Assume that it is finite, and there is a bijection from $n$ to $B$. If $n=2$, then either $A=0$ or $A=1$, which is equivalent to $\lnot P$ and $P$ respectively. If $n=3$, then neither $A=0$ nor $A=1$, which implies $\lnot P\land \lnot\lnot P$, which is impossible. Thus $n=2$, but $n=2$ implies $P\lor\lnot P$.

Answer 5

Here are two fun ones off the top of my head. I don't know if you want these to be in separate answers:

1. A set $X$ is finite iff the free vector space $k[X]$ is finite-dimensional, for any field $k$. Finite-dimensionality in turn has several characterizations which don't require explicitly mentioning bases: a vector space $V$ is finite-dimensional iff

   1. $\text{Hom}(V, -) : \text{Vect} \to \text{Vect}$ preserves colimits ($V$ is compact projective, or tiny) iff
   2. $V \otimes (-) : \text{Vect} \to \text{Vect}$ preserves limits iff
   3. the double dual map $V \to (V^{\ast})^{\ast}$ is an isomorphism iff
   4. $V$ is dualizable in the monoidal sense.

2. A set $X$ is finite iff every ultrafilter on $X$ is principal. I guess this requires the ultrafilter lemma. Stated in terms of the Stone-Cech compactification $X \to \beta X$, this turns out to be equivalent to "the discrete topology on $X$ is compact."

Answer 6

Here are some notions of "finiteness" which make sense in lots of categories, and which characterize the finite sets when the category is $Set$. I view this as an addendum to the notions discussed in Hanul Jeon's answer. A salient point is that notions of finiteness which agree in $Set$ may diverge when considering more general categories, even when those more general categories are things like toposes, i.e. "generalized categories of sets".

1. A set $X$ is finite if and only if it is Noetherian, i.e. it satisfies the ascending chain condition for subobjects.

2. A set $X$ is finite if and only if it is Artinian, i.e. it satisfies the descending chain condition for subobjects.

3. A set $X$ is finite if and only if it is Hopfian, i.e. every surjection $X \to X$ is a bijection.

4. A set $X$ is finite if and only if it is co-Hopfian, i.e. every injection $X \to X$ is a bijection.

In the 1-topos literature, the term "Dedekind-finite" is used to mean co-Hopfian.

5. A set $X$ is finite if and only if it is finitely-presentable, i.e. for every chain $Y_0 \to Y_1 \to \dots$ and every function $f: X \to \varinjlim Y_n$, there is some $m$ such that $f$ factors through $Y_m \to \varinjlim Y_n$.

Variants of (5) include: considering all diagrams of $Y_n$'s indexed by any directed poset, or by any filtered category. In the $\infty$-categorical literature, the term "compact" is used instead of "finitely-presentable".

If we require the transition maps between the $Y_n$'s to be injections, we get the notion of a

6. finitely-generated object.

7. A set is finite if and only it is quasicompact in the sense that the top element of its powerset lattice is finitely-presentable (equivalently, finitely-generated) as an element of that lattice.

The nlab says "compact" instead of "quasicompact" here, but I think in the original literature "quasicompact" is used -- if I recall correctly, the nlab has a general convention to never use the term "quasicompact", insisting instead that "compact" never implies "Hausdorff".

8. A set $X$ is finite if and only if its coherent, i.e. it is "stably quasicompact" in the sense defined at the link.

(7) and (8) come from topos theory. There are corresponding notions in $\infty$-topos theory.

9. A set is finite if and only if it lies in the closure of $\{ \{\emptyset\}\}$ under pushouts and intial objects.

---

Here are some other fun ones:

10. A set $X$ is finite if and only if all linear orders on $X$ are isomorphic.

11. A set $X$ is finite if and only if there exists a first-order theory $T$ such that $T$ has a unique model $M$ up to isomorphism, and moreover $M$ may be taken to have underlying set $X$.