3
$\begingroup$

I was reading this paper. In particular the second point. He proves the Hall's marriage Theorem for infinite family using the Tychonoff theorem on topological product of compact $T_2$ spaces and the Hall's marriage Theorem for finite family.

So assume that $Y$ is an infinite family of finite sets such that any $k$ sets in $Y$ have at least $k$ elements in their union ($k$ is a finite number). We want to prove that there is a $1-1$ function $f:Y\longrightarrow \underset{X\in Y}{\cup}X$.

Endow each $X\in Y$ with the discrete topology. Since $X$ is finite it is a compact $T_2$ space. The topological product $\underset{X\in Y}{\prod}X$ is a compact $T_2$ space.

We now take the $F$ to be the family of all sets $S_G$ of all $f\in \underset{X\in Y}{\prod}X$ such that their restriction to $G$ is injective; for all $G$ finite subsets of $Y$.

He claims that $S_G$ is closed and nonempty by the Hall's marriage theorem for finite family. I do not understand why. In particular I ask myself the following things:

As matter the nonemptiness I was thinking of finding an injective function using Hall's marriage theorem for the finite family $G$ and then to extend to all $Y$. But how? How can we say that $\underset{X\in Y}{\prod}X$ is not empty without using the full strenght of the Axiom of Choice?

Where do we make (if we make) us of the fact that the product is a $T_2$ space?

The closeness of $S_G$ just came from the fact that the projection onto the factor is a continuus function and that the antiimages of closed set is a closed set?

$\endgroup$
6
$\begingroup$

The paper shows that the infinite Hall theorem follows from the Tychonoff theorem for compact Hausdorff spaces (or even the Tychonoff theorem for finite discrete spaces). So we are allowed to use that fact.

Now the Tychonoff theorem for non-empty finite discrete spaces implies that the product of finite discrete spaces is non-empty (i.e. collections of finite sets have a choice function). This uses the same argument (essentially) as the fact that full Tychonoff implies full AC.

Proof: let $F_i, i \in I$ be a set of non-empty finite sets. Let $p$ be any point not in $\cup_i F_i$, and define $X_i = F_i \cup \{p\}$ for all $i$, and give this set the discrete topology. We know that $\prod_i X_i$ is compact by assumption. Define $F'_i = (\pi_i)^{-1}[F_i]$, where $\pi_i$ is the projection from $\prod_i X_i$ onto $X_i$. Then the $F'_i$ are closed in $\prod_i X_i$ and they have the finite intersection property: we can pick finitely many points in finitely many $F_j$ and $p$ for all other coordinates. We essentially added $p$ as the default, always present, choice point. The intersection of the $F'_i$ is thus non-empty by compactness, and this is what we needed.

The previous result let's us use that when the finite Hall theorem on a finite $G \subset Y$ gives us a choice function that is 1-1 there, and extend using choice; as said, not full choice, but choice for finite sets, which we are allowed to use, as we are working under the assumption of the Tychonoff theorem for finite discrete spaces. This covers the non-emptyness.

The closedness is just a product property: if $f \notin S_G$, it must be the case that there are $Y_1 \neq Y_2$ both in $G$, that have the same choice under $f$, i.e. $f(S_{Y_1}) = f(S_{Y_2})$. But then we can take the basic open product set $O$ that equals $\{f(S_{Y_1})\}$ at coordinate $Y_1$, and $\{f(S_{Y_2})\}$ at coordinate $Y_2$, and the full set elsewhere. All points in $O$ still have the property that injectiveness fail (at the same $Y_1$ and $Y_2$), so $O$ misses $S_G$. This shows that $S_G$ is closed. Note we use the discreteness here (to see the singletons are open).

And as the paper notes $S_{G_1 \cup G_2} \subset S_{G_1} \cap S_{G_2}$, so the set $S_G$, where $G$ ranges over the finite subsets of $Y$ has the finite intersection property, so has non-empty intersection (second application of the Tychonoff theorem for finite discrete spaces) and this is what we needed: a choice function for all of $Y$. It will clearly be injective, as failing to be injective already happens in a finite subset of $Y$.

So we do not need the full Tychonoff for compact Hausdorff spaces, but "only" the Tychonoff theorem for finite discrete spaces (which might or might not be weaker, I'd have to look it up). Edit: looked it up in "Consequences of the Axiom of Choice", and the Tychonoff theorem for compact Hausdorff, finite and even two point spaces are all equivalent (to the Boolean Prime Ideal theorem, among others). It's form 14 in the book, while Hall's theorem is form 107, so weaker.

$\endgroup$
  • $\begingroup$ That is a really exhausting answer! Thanks! $\endgroup$ – W4cc0 May 11 '14 at 13:31

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.