applying Martin's axiom

Question

I am struggling with the following problem:

Let $A_n$ for $n \in \omega$ be sets of respective cardinality $n + 1$, and let $X = \prod A_n$. Show that Martin's axiom for $\kappa$ proves that for every $B \subseteq X$ of cardinality $\kappa$, there exists $x \in X$ which is eventually different from every function in $B$ (two functions $f,g \in X$ are eventually different if for some $m \in \omega$ we have $f(n) \neq g(n)$ for $n > m$).

My idea:

I need to come up with a certain ccc partial order (along with some dense subsets) that will allow me to apply Martin's axiom and get in return a filter which is the key to find the element $x \in X$ that I am looking for. I tried a few cases to see if that would suggest the partial order I need. The finite case (i.e., $\kappa$ is finite) is easy but not very suggestive. Now according to the following post, the truly suggestive case is $\kappa = \aleph_0$ and if I can find a simple diagonalization argument for this case, then I will have an idea about which partial order I need but I am stuck here.

Can you please provide hints?

Answer 1

For $\kappa=\aleph_0$, you can list your set $B$ as $f_0,f_1,f_2,\ldots$. The diagonalization will mean coming up with a $g$ which is eventually different from all the $f_i$. But where the diagonal part of diagonalization comes in is that $g$ will be eventually different from the $f_i$ but the point past which $g$ is eventually different will depend on $i$. You can do this by successively defining more and more of $g$, but as you define more of $g$ you'll have to make sure that you keep $g$ being eventually different from more and more of the $f_i$.

So, you need to think of how to make a $g$ that once you've defined $g$ up to $n$, you can ensure that $g$ is eventually different from the first $n$ of the functions. (You won't have $g$ completely defined yet, but you will know how to proceed in a way that $g$ will be different from the first $n$ functions.)

Then there remains to find the forcing that mimics this diagonalization, but understanding this diagonalization is a place to start.

Answer 2

We assume WLOG that $\kappa \geq \aleph_0$, since for smaller $\kappa$, we can simply add functions to $B$ until we have $\aleph_0$ of them. And of course we know that $MA(\aleph_0)$ holds.

We need to come up with some partial order where a maximal filter on the partial order represents some $x \in X$.

A "condition" consists of a finite set $S \subseteq B$, together with some $j \in \mathbb{N}$ and some $f \in \prod\limits_{i = 0}^{j - 1} A_j$, such that $|S| \leq j$.

We say that $(S_1, j_1, f_1) \leq (S_2, j_2, f_2)$ if and only if (1) $j_2 \leq j_1$, (2) for all $n < j_2$, $f_2(n) = f_1(n)$, (3) $S_2 \subseteq S_1$, and (4) for all $s \in S$, for all $n$ such that $j_2 \leq n < j_1$, $f_1(n) \neq s(n)$.

Let $U$ be the set of conditions. Then $(U, \leq)$ forms a partial order.

To show $U$ is ccc: Suppose given $j \in \mathbb{N}$ and $f \in \prod\limits_{i = 0}^{j - 1} A_i$. Given some $S \subseteq B$, consider the function $g_S \in \prod\limits_{k = j}^{2j - 1} P(A_j)$ defined by $g_S(n) = \{s(n) \mid s \in S\}$. If we had $S_1, S_2$ such that $g_{S_1} = g_{S_2}$, then it's easy to see that $(S_1, j, f)$ and $(S_2, j, f)$ are comparable, since we can extend $f$ to some $h \in \prod\limits_{i = 0}^{2j - 1}A_i$ by picking, for each $i$ such that $j \leq i < 2j - 1$, some $h(i) \in A_i \setminus g_{S_1}(i)$. Then $(S_1 \cup S_2, 2j, h)$ is a common extension of $(S_1, j, f)$ and $(S_2, j, f)$.

So given an antichain $A$, we see that for all $j \in \mathbb{N}$, $f \in \prod\limits_{i = 0}^{j - 1} A_i$, we see that the set $\{S \subseteq B \mid (S, j, f) \in A\}$ must be finite. This proves that $A$ is countable.

Let $F \subseteq U$ be a filter. The "corresponding condition" to $F$ consists of the set $S_F = \bigcup\limits_{(S, j, f) \in F} S \subseteq B$, together with some initial segment $I_F = \bigcup\limits_{(S, j, f) \in F} \{n \in \mathbb{N} \mid n < j\} \subseteq \mathbb{N}$ and some partial function $f_F = \bigcup\limits_{(S, j, f) \in F} f \in \prod\limits_{i \in I} A_i$. The "corresponding condition" of $F$ satisfies $\forall s \in S_F \exists n \in \mathbb{N} \forall m \in I$, if $m > n$ then $f_F(m) \neq s(m)$.

We want to get a filter with corresponding condition satisfying $I = \mathbb{N}$ and $S = B$. This will give us the $f_F \in X$ we need.

To make $I_F = \mathbb{N}$, we consider the indexed family $\{D_n\}_{n \in \mathbb{N}}$ defined by $D_n = \{(S, j, f) \mid j \geq n\}$. Note that $D_n$ is dense in $U$, since by design, we can always extend $(S, j, f)$ to $(S, j + 1, f')$ for some $f'$. A filter which gets under all $D_n$ will have $I_F = \mathbb{N}$.

To make $S = B$, we consider the indexed family $\{K_b\}_{b \in B}$ defined by $K_b = \{(S, j, f) \mid b \in S\}$. Each $K_b$ is dense, since given $(S, j, f)$, we can extend this to $(S, j + 1, f')$ for some $f'$ and then extend that to $(S \cup \{b\}, j + 1, f')$. A filter which gets under all the $K_b$ will have $S_F = B$.

So simply consider the collection $\{K_b \mid b \in B\} \cup \{D_n \mid n \in \mathbb{N}\}$, which is a collection of $\kappa$-many dense sets. Then we can take a filter $F$ which gets under all of them and therefore has $I_F = \mathbb{N}$ and $S_F = B$; then $f_B$ is eventually away from all elements of $B$.