12
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 4 should say "countably infinite subsets" - trivially, a set is finite iff it has no infinite subsets. $\endgroup$ – Noah Schweber Jan 18 at 8:41
  • $\begingroup$ @NoahSchweber Thank you for the correction. $\endgroup$ – Alec Rhea Jan 18 at 8:41
  • 2
    $\begingroup$ If we have the same definition for the characteristic of a field, 2. is definititely false. $\endgroup$ – abx Jan 18 at 9:43
  • $\begingroup$ @abx Total brain fart, thanks for the catch. $\endgroup$ – Alec Rhea Jan 18 at 10:16
  • $\begingroup$ I think you're talking about finiteness of sets. Are you also interested in finiteness in other categories? $\endgroup$ – Tim Campion Feb 13 at 12:58
5
$\begingroup$

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)$.)

$\endgroup$
5
$\begingroup$

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.)

$\endgroup$
1
  • 3
    $\begingroup$ Remark: Under ZF, AC holds iff this property holds for every infinite set (proved by Tarski, Sur quelques th\'eor`emes qui `equivalent a l’axiome choix). $\endgroup$ – Farmer S Jan 18 at 21:04
5
$\begingroup$
  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.

$\endgroup$
3
  • $\begingroup$ I think that $X$ is finite if and only if in every $T_0$ topology every singleton is either open or closed. But I'm too lazy to find the mistake in the proof I have in mind. $\endgroup$ – Asaf Karagila Jan 18 at 20:35
  • 1
    $\begingroup$ Any set with at least $3$ elements can be endowed with a partial order such that some element $x$ is neither minimal nor maximal. Then in the corresponding $T_0$ upset topology, $\{x\}$ is neither open nor closed. $\endgroup$ – Emil Jeřábek Jan 18 at 20:43
  • $\begingroup$ @Emil: Thanks for saving me the time and effort! :-) $\endgroup$ – Asaf Karagila Jan 18 at 20:44
4
$\begingroup$

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$.
$\endgroup$
5
  • $\begingroup$ I don't see the "finitely enumerable sets are subfinite" part of your answer. It seems to me that, in a subfinite set, equality of elements must be decidable, but this decidability can fail in a finitely enumerable set. $\endgroup$ – Andreas Blass Jan 19 at 17:23
  • $\begingroup$ @AndreasBlass It follows from Proposition 8.1.9 of Aczel and Rathjen, which states a set is subfinite if and only if the set is a subset of a finitely enumerable set. I have no idea how to refute your argument directly, though. (I will think about it after sleeping.) $\endgroup$ – Hanul Jeon Jan 19 at 17:34
  • 1
    $\begingroup$ The definition of "subfinite" in Aczel+Rathjen (8.1.8) isn't the same as in your answer. They have "surjective image" where you have "equipotent". $\endgroup$ – Andreas Blass Jan 19 at 17:46
  • $\begingroup$ @AndreasBlass You are right, thank you for pointing it out. $\endgroup$ – Hanul Jeon Jan 19 at 17:51
  • 1
    $\begingroup$ The nlab contains an overview of such notions. Note that the term "Kuratowski-finite" is used to mean "subquotient of a finite ordinal". $\endgroup$ – Tim Campion Feb 13 at 14:23
4
$\begingroup$

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."

$\endgroup$
2
  • 1
    $\begingroup$ (2) is much weaker than BPI. It is consistent that BPI fails, but every infinite set admits a free ultrafilter. $\endgroup$ – Asaf Karagila Jan 18 at 19:15
  • 1
    $\begingroup$ If we're quibbling about the axiom of choice, then (1) also requires some form of choice, as the free real vector space on the natural numbers satisfies (1.3) in any model of ZF + DC + all subsets of any Polish space have the Baire property. See Andreas Blass's answer here: mathoverflow.net/a/67557 $\endgroup$ – Robert Furber Jan 27 at 5:42
3
$\begingroup$

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.

  1. 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

  1. finitely-generated object.

  2. 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".

  1. 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.

  1. 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:

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

  2. 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.