Maximum cardinality of a filtered limit of finite sets

Let $(I,<)$ be a directed, partially ordered set. Consider an inverse system $(S_i)_{i \in I}$ of finite sets, i. e. a functor $S:I^{op}\to \mathbf{FinSet}$. What is the maximum possible cardinality of the inverse limit $A=\varprojlim S$ of this system? It is obvious that $|A|=2^{\aleph_0}$ can be achieved (for example by taking $I=\Bbb N$ and $S_i=\mathbb Z/p^i\mathbb Z$ yielding $A=\Bbb Z_p$), but I don't see how to do any better.

• Every set is the directed union of its finite subsets. – Andrej Bauer Jun 26 '14 at 14:49

You can get arbitrarily large cardinalities. For instance, let $X$ be any set and consider the poset $I$ of finite partitions of $X$, ordered by refinement. There is a "tautological" filtered system of finite sets indexed by $I$, and $X$ naturally maps to it. Clearly the map from $X$ to the limit of this system is injective (in fact, the limit can naturally be identified with the set of ultrafilters on $X$, with the natural map being the inclusion of principal ultrafilters).

More generally, you can do a similar construction with the poset of (finite) partitions of any Boolean algebra, and the limit will be the Stone space. Conversely, any inverse limit of finite sets acquires a natural profinite topology. If all the maps in the original inverse system were proper (i.e., non-bijective) surjections, then it can be considered as a cofinal subsystem of the system of all clopen partitions of the limit. That is, every inverse system of proper surjections of finite sets is cofinal in a system of this form. Furthermore, any inverse system of finite sets can be canonically transformed into one in which the maps are proper surjections without changing the limit: first remove all elements of $S_i$ that are not in the image of every map $S_j\to S_i$, and then impose an equivalence relation on $I$ that identifies $i$ and $j$ whenever $S_j\to S_i$ is a bijection.

For example, in Joel's construction, the profinite topology is the topology that sees $X$ as the one-point compactification of the discrete topology on $X\setminus\{0\}$. The Boolean algebra of clopen subsets can be identified with the finite-cofinite Boolean algebra on $X\setminus\{0\}$, and the inverse system is isomorphic to a (cofinal) system of partitions of this algebra: given a finite subset $\{0,x_1,\dots,x_n\}\subseteq X$, identify it with the partition $\{x_1\},\{x_2\},\dots,\{x_n\},X\setminus \{0,x_1,\dots,x_n\}$.

Such an inverse limit can have any size at all, by choosing the $S_i$ and $I$ properly. Specifically, every set is the inverse limit of a system constructed from its finite subsets. Let $X$ be any nonempty set (the result is clear for the empty set), with element $0\in X$, and let $I$ be the set of finite subsets of $X$ containing $0$, ordered under reverse inclusion, so that $i<j\leftrightarrow i\supset j$. For each $i\in I$, let $S_i=i$, and map $S_i$ to $S_j$ by fixing the elements of $S_j$ and mapping the extra points to $0$. So we've got an inverse system $\langle S_i\mid i\in I\rangle$, but the inverse limit is $X$ itself, since every thread in the system stabilizes on an element of $x$ as one moves out in the system.

In general, if $I$ is infinite and the system are fixed, then the size of the inverse system is bounded by $2^{|I|}$, since every element of the inverse system is determined by its image in the system. One can improve this bound in certain cases using cofinality and the fact that the sets are finite, and so cannot increase on a thread more than countably many times.

Given a directed set $I$, let's investigate the least cardinal $\lambda$ with $|\varprojlim_{i\in I}A_{i}|<\lambda$ whenever each $A_{i}$ is finite.

$\mathbf{Lemma}$ Every inverse limit $\varprojlim_{i\in I}A_{i}$ of finite sets is finite if and only if each countable subset of $I$ has an upper bound.

$\mathbf{Proof}$ $\leftarrow$ Suppose without loss of generality that the transitional mappings in $\varprojlim_{i\in I}A_{i}$ are surjective. Suppose for the sake of contradiction that the sets $A_{i}$ are arbitrarily large finite sets. Then there is an increasing sequence $(i_{n})_{n\in\omega}$ such that $|A_{i_{n}}|>n$ for all $n$. If $i$ is an upper bound for all $A_{i_{n}}$, then $|A_{i}|>|A_{i_{n}}|>n$ for all $n$ which is a contradiciton. Therefore, there is some $n$ where $|A_{i}|\leq n$ for all $n$. We may now conclude that $\varprojlim_{i\in I}A_{i}$ is finite.

$\rightarrow$ Suppose that $(i_{n})_{n\in\omega}$ is a countable increasing sequence without an upper bound. Then let $(B_{n})_{n\in\omega}$ be an arbitary inverse system of finite sets. Then define $A_{i}=B_{n}$ where $n$ is the least natural number such that $i_{n}\not\leq i$. The transitional mappings in $(A_{i})_{i\in I}$ are the same mappings as they are in $(B_{n})_{n\in\omega}$. Then the inverse limit $\varprojlim_{i\in I}A_{i}$ is infinite. $\mathbf{QED}$

$\mathbf{Proposition}$ Suppose that $I$ is a directed set and $\lambda$ is the least cardinal where $|\varprojlim_{i\in I}A_{i}|<\lambda$ whenever each $A_{i}$ is finite. If $\lambda_{n}<\lambda$ for all $n\in\omega$, then $\prod_{n\in\omega}\lambda_{n}<\lambda$ as well whenever $\lambda$ is uncountable. In particular, $cf(\lambda)>\aleph_{0}$.

$\mathbf{Proof}$

Suppose that $\lambda_{n}<\lambda$ for $n\in\omega$. Then for each $n\in\omega$ there is some inverse limit $\varprojlim_{i\in I}A_{i,n}$ of finite sets with $|\varprojlim_{i\in I}A_{i,n}|\geq\lambda_{n}$.

Now let $(i_{n})_{n\in\omega}$ be an increasing sequence in $I$ with no least upper bound. Now let $B_{i,n}=A_{i,n}$ whenever $i\geq i_{n}$ and let $B_{i,n}$ be a one element set whenever $i\not\geq i_{n}$. Then $\varprojlim_{i\in I}A_{i,n}\simeq\varprojlim_{i\in I}B_{i,n}$, so $|\varprojlim_{i\in I}B_{i,n}|\geq\lambda_{n}$ as well.

Now, for each $i\in I$, the set $\prod_{n\in\omega}B_{i,n}$ is a finite set since $|B_{i,n}|=1$ for all but finitely many $n\in\omega$. Therefore, we have inverse limit $|\varprojlim_{i\in I}\prod_{n\in\omega}B_{i,n}|<\lambda$. On the other hand, the mapping $$\psi:\prod_{n\in\omega}\varprojlim_{i\in I}B_{i,n}\rightarrow \varprojlim_{i\in I}\prod_{n\in\omega}B_{i,n}$$ defined by $\psi((x_{i,n})_{i\in I})_{n\in\omega}=((x_{i,n})_{n\in\omega})_{i\in I}$ is an isomorphism. Therefore, $\prod_{n\in\omega}\lambda_{n}\leq\prod_{n\in\omega}|\varprojlim_{i\in I}B_{i,n}|<\lambda$. $\mathbf{QED}$.

In some directed sets $I$, one can say more.

$\mathbf{Proposition}$ Suppose that $I$ is a directed set. Let $\lambda$ be the least cardinal with $|\varprojlim_{i\in I}A_{i}|<\lambda$ whenever each $A_{i}$ is finite. Suppose furthermore that $R\subseteq I$ and whenever $i\in I$ there are only finitely many $r\in R$ with $r\leq i.$ Then $\lambda_{r}<\lambda$ for $r\in R$ implies that $\prod_{r\in R}\lambda_{r}<\lambda$.

$\mathbf{Proof}$: Suppose that $\lambda_{r}<\lambda$ for $r\in R$. Then let $\varprojlim_{i\in I}B_{i,r}$ be an inverse system of finite sets with $\lambda_{r}\leq|\varprojlim_{i\in I}B_{i,r}|$ and where $|B_{i,r}|=1$ whenever $i\not\geq r$. Then $\prod_{r\in R}B_{i,r}$ is finite for each $i\in I$, but $|\varprojlim_{i\in I}\prod_{r\in R}B_{i,r}|\geq\prod_{r\in R}\lambda_{r}$. $\mathbf{QED}$.