About compactness theorem application

Question

A transversal function is a one-to-one function f with domain F such that for every $X ∈ F, f(X) ∈ X$. Then I have to prove that if $E$ is a family of finite sets such that for every finite $E' \in E$ $E'$ has a transversal, then $E$ has a transversal. Is true if $E$ contains infinite sets?.

First I think I have to build a model for this proposition to prove the existence on the final set.

My problem is how to build the set of propositional variables. Should I do $P_i$ if the set $P$ has a transversal?.

How can I continue with that?

Thanks you!

Answer 1

Like any other context, it's good to see some examples first. So: can we find an $E$ which does not have a transversal?

This may seem hard, but it's actually just an application of the pigeonhole principle! Consider e.g. $$E=\{\{1\}, \{2\}, \{1, 2\}\}.$$ Basically, what's going on here is that $E$ is a family of subsets of some set $U$, and $E$ has more elements than $U$ does. Whenever that happens, $E$ won't have a transversal. Do you see why?

Now what you're being asked to prove is a compactness property for transversals:

For $\mathcal{E}$ a class of sets, say $\mathcal{E}$ is compact for transversals if for all $E\in E$, if every finite $E'\subseteq E$ has a transversal then $E$ has a transversal.

You're being asked to prove that the class $\mathcal{E}_0$ of sets each of whose elements are finite is compact for transversals.

Again, an example is useful: when can a class not be compact for transversals? That is - is there any set $E$ such that every finite $E'\subseteq E$ has a transversal, but $E$ does not?

HINT: Consider the family $J=\{\{n\}: n\in\mathbb{N}\}$. If $E$ contains $J$, then any transversal $f$ for $E$ must have $f(\{n\})=n$ (why?); so if we add a set of naturals to $J$, we'll get a set with no transversal (why?). Now, we want to get a set with no transversal but all of whose finite subsets have transversals; do you see what sort of set we should add to $J$ to accomplish this? (rot13'd to avoid spoilers: Jung unccraf vs lbh gnxr R gb or W gbtrgure jvgu gur frg bs nyy anghenyf - be, zber trarenyyl, nal vasvavgr frg bs anghenyf?)

---

Hopefully, the examples above show that

• Having a transversal is not automatic, and

• compactness for transversals fails if we allow infinite sets.

So, how can we approach the problem at hand?

Well, remember what the compactness theorem does: given a family of sentences (which is finitely satisfiable), it gives you a valuation making them all true. We don't want a valuation, though - we want a transversal! So starting with some $E$ consisting only of finite sets, such that every finite $E'\subseteq E$ has a transversal, you want

a family of sentences $\Gamma$ such that, from any valuation making $\Gamma$ true, you can get a transversal for $E$.

That is, we're going to have to juggle a bit - between sentences and facts about the function we're trying to build. This can be weird at first, so let me outline the idea.

We want to first write down a list of sentences which are satisfied by any transversal $f$ of $E$. Suppose $E=\{A_i: i\in I\}$, and $A_i=\{a_j^i: j\in \{1, 2, . . . , k_i\}\}$ (remember, each $A_i$ is finite by assumption). Then for any transversal $f$, we have:

$f(i)\in A_i$, and $f(i)=f(i')\iff i=i'$.

Here are some related propositional sentences

$\bigvee_{1\le j\le k_i} f(i)=a^i_j$ (for each $i\in I$, this is one sentence since $A_i$ is finite) and $f(i)\not=f(i')$ (this is one sentence for each pair of distinct $i, i'\in I$).

If we're allowed to use the compactness theorem for first-order logic, we're basically done here. If we really have to make due with compactness for propositional logic, then things are a bit messy:

• For each $a\in \bigcup E$ (that is, each element of an element of $E$ - each $a$ in some $A_i$) and each $i\in I$ (or equivalently, each $A_i\in E$) we have a propositional variable $p_{i, a}$.

• Intuitively, we want $p_{i, a}$ to be true iff $f(i)=a$.

• Do you see how to express "$\bigvee_{1\le j\le k_i} f(i)=a^i_j$" for each $i$ as a single propositional sentence in these variables?

• Do you see how to express "$f(i)\not=f(i')$" for each $i\not=i'$ as a single propositional sentence in these variables?