Finiteness of subsets of arbitrary finite sets

The goal of this blog post is to provide a novel proof of the following result:

Proposition: Let \(A\) be a finite set and let \(B\) be a subset of \(A\). Then \(B\) is finite.

Proof: Suppose otherwise, that \(B\) is an infinite subset of \(A\). This means precisely that the complement of \(B\) is not an element of the Fréchet filter \(\mathcal F\) in \(A\), hence \(\mathcal F\) is a proper filter on \(A\). Since it’s a proper filter, we can apply the ultrafilter lemma to show that it is contained in some ultrafilter \(\mathcal U\). A standard result states that any ultrafilter containing Fréchet filter is nonprincipal. So \(U\) is a nonprincipal ultrafilter on \(A\). This implies that the Stone-Čech compactification \(\beta A\) is a proper superset of \(A\) (under the standard identification of elements of \(A\) as principal ultrafilters in \(A\)). In particular, by pigeonhole principle, \(\beta A\) and \(A\) are not bijective.

Now note that \(\beta A\), as a topological space, is the Stone-Čech compactification of \(A\) considered as a topological space with discrete topology. Since \(A,\beta A\) are not bijective, they are surely not homeomorphic as topological spaces. We will reach a contradiction as soon as we show that \(A\) is homeomorphic to its own Stone-Čech compactification.

To show that, we will use the characterization of Stone-Čech compactification as the unique, up to homeomorphism, compact Hausdorff topological space \(X\) containing \(A\) as a subspace and satisfying the universal property: any continuous function \(f:A\rightarrow Y\), where \(Y\) is some compact Hausdorff space, can be uniquely extended to a continuous function \(\widetilde f:X\rightarrow Y\) such that, for all \(a\in A,f(a)=\widetilde f(a)\). We need to verify all these properties.

Compactness: Let \(\displaystyle A\subseteq \bigcup_{i\in I}U_i\), where \(U_i\) are all open. Then for any \(a\in A\) there is an \(i_a\in I\) such that \(a\in U_{i_a}\). Since \(A\) is finite, this gives us a finite set of indices \(i_a,a\in A\) such that \(\displaystyle A\subseteq\bigcup_{a\in A} U_{i_a}\). This gives us a finite subcover of any open cover of \(A\). This means that \(A\) is compact.

Hausdorffness: Let \(a,b\in A\) be two distinct elements. Then \(\{a\},\{b\}\) are open, because we consider \(A\) with the discrete topology. Moreover, these two sets are disjoint, because every element in their intersection would be both \(a\) and \(b\), and these are different. This means precisely that \(A\) is Hausdorff.

Universal property: Let \(f:A\rightarrow Y\) be any continuous function, where \(Y\) is compact and Hausdorff. We define \(\widetilde f:A\rightarrow Y\) by \(\widetilde f(a)=f(a)\) for every \(a\in A\). Then for every \(a\in A\) we have \(f(a)=\widetilde f(a)\). Moreover, for any open set \(U\subseteq Y\) we have \(\widetilde f^{-1}(U)=f^{-1}(U)\), which is open, since \(f\) is continuous by assumption, so \(\widetilde f\) is continuous. We have shown existence, so we only need to confirm uniqueness. Suppose \(\widetilde{\widetilde f}\) is another such function. In particular, for all \(a\in A, \widetilde{\widetilde f}(a)=f(a)=\widetilde f(a)\). This means that \(\widetilde{\widetilde f}=\widetilde f\), as we wanted.

So we have a contradiction. Hence \(B\) is finite. \(\square\)


Proof sketch of Thue’s theorem


PNT for polynomials using the zeta function


  1. David V Feldman

    Re the first line of your proof:
    As the Frechet filter contains *co-finite* sets, not lying in it equates with having an infinite *complement.*
    (Perhaps some symbol isn’t rendering, but I tried two browsers.)

Leave a Reply

Powered by WordPress & Theme by Anders Norén