Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have some exam questions that were left unanswered for me:

  1. Suppose that for every $\alpha<\kappa$ there is a subset $A_\alpha$ of $\kappa$ of cardinality $\kappa$. Show that there is a subset X of $\kappa$ so that for every $\alpha<\kappa$ : |$A_\alpha\cap$ X|=|$A_\alpha$ \ X|=$\kappa$.
  2. {$A_\alpha | \alpha<\aleph_1$} a collection of non-stationary disjoint sets. Suppose that their union is a stationary set. Prove that the set {$minA_\alpha | \alpha<\aleph_1$} is stationary.
  3. For every couple of sets A,B $\in P(\omega)$ we will denote A $\subseteq^*$ B if $|A\setminus B|<\aleph_0$. Prove that there exist a sequence of length $\aleph_1$ in relation to $\subseteq^*$ .

I'll appreciate any help regarding those questions. Thanks in advance, Pavel

share|cite|improve this question
I edited your question 3, as it was not displaying properly. What have you tried so far for these questions? How did you run into them? (I.e., these are doubts from reading a specific topic, a homework assignment, or what? This information may help to know what results you are familiar with or can assume.) – Andrés E. Caicedo Feb 6 '11 at 16:54
In question 2 I indeed forgot to to mention that $A_\alpha$ are disjoint (sorry about that). In question 1 such information is not given. The questions are taken from various exams of a course I took on set theory. I'm familiar with the basic results of AC, Zorn's Lemma e.t.c, most of the basic axiomatic theory theorems such as Ulam, Konig, Fodor, Closed and unbounded sets, stationary sets... – Pavel Feb 6 '11 at 18:47
up vote 4 down vote accepted

Question 3 admits an easy answer, once you check two facts:

$A\subseteq^* B\subseteq^* C$ implies $A\subseteq^* C$.

This is completely straightforward: If $A\setminus B\subseteq m$ and $B\setminus C\subseteq n$, then $A\setminus C\subseteq \max\{m,n\}$.

The second is:

Given a (strictly) $\subseteq^*$-increasing sequence $(A_n\mid n\in\omega)$ (so $A_n\setminus A_{n+1}$ is finite but $A_{n+1}\setminus A_n$ is infinite), there is a $B$ with $A_n\subseteq^* B$ for all $n$ (so, in particular, $B\setminus A_n$ is infinite), and such that $\omega\setminus B$ is infinite as well.

For this: Define two strictly increasing sequences of numbers $m_0<m_1<\dots$ and $$t_{00}<t_{01}<t_{10}<t_{11}<t_{20}<t_{21}<\dots$$ so that $A_n\setminus A_{n+1}\subseteq m_n$ for all $n$, $[t_{n0},t_{n1})\cap (\omega\setminus A_{n+1})\ne\emptyset$, and $m_n<t_{n0}<t_{n1}<m_{n+1}$ for all $n$. (Check that this is possible.)

Let $$ B=\bigcup_n [m_n,m_{n+1})\cap A_{n+1}. $$ Check that $A_n\setminus B\subseteq m_n$ for any $n$: If $s\in A_n\setminus B$ and $s\ge m_n$ then $s\in A_{n+1}$ (by definition of $m_n$), so $s\ge m_{n+1}$ (or else $s\in B$); inductively, this gives us that $s\ge m_k$ for all $k$, which of course is absurd.

Moreover, by construction, $\omega\setminus B$ contains at least one element of each interval $[t_{n0},t_{n1})$, so it is infinite.

Using these two facts, a straightforward transfinite construction of length $\omega_1$ gives us the desired $\subseteq^*$ increasing sequence $(A_\alpha\mid\alpha<\omega_1)$:

Start with any $A_0\subseteq\omega$ infinite and coinfinite. Given $A_\alpha$ infinite and coinfinite, let $A_{\alpha+1}$ consist of $A_\alpha$ and an infinite-coinfinite subset of $\omega\setminus A_\alpha$.

At limit stages $\alpha<\omega_1$, given $(A_\beta\mid \beta<\alpha)$, fix $(\beta_n\mid n<\omega)$ increasing and cofinal in $\alpha$ and use the second fact to find $A_\alpha$ with $A_{\beta_n}\subseteq^* A_\alpha$ for all $n$ and $\omega\setminus A_\alpha$ infinite. That $A_\beta\subseteq A_\alpha$ for all $\beta<\alpha$ now follows from the first fact.

For question 2, use Fodor's lemma: Suppose, towards a contradiction that the $A_\alpha$ are pairwise disjoint non-stationary subsets of $\omega_1$ such that $\bigcup_\alpha A_\alpha$ is stationary, and yet $$B=\{{\rm min}(A_\alpha)\mid\alpha<\omega_1\}$$ is non-stationary. Let $A=\bigcup_\alpha A_\alpha\setminus B$. Then $A$ is stationary. Define a regressive $f:A\to\omega_1$ as follows: Given $\beta\in A$, there is a unique $\alpha$ such that $\beta\in A_\alpha$. Then set $f(\beta)=\min(A_\alpha)$.

By Fodor, $f$ is constant on a stationary set. This is, by construction, a subset of a fixed $A_\alpha$ (since the $A_\alpha$ are pairwise disjoint), contradicting that no $A_\alpha$ is stationary.

As a side remark, note that you need something like the assumption that the $A_\alpha$ are disjoint. An easy counterexample otherwise is obtained by setting $A_\alpha=\alpha+1$. Then $\bigcup_\alpha A_\alpha=\omega_1$, yet $B=\{0\}$.

share|cite|improve this answer
Thank you for the explanation. I especially liked the proof of question 2, very elegant. – Pavel Feb 8 '11 at 19:11
Thanks. It is a nice problem, I hadn't seen it before. I'll probably use it next time I teach this material. – Andrés E. Caicedo Feb 8 '11 at 19:27

Here is a solution for the first problem:

We already know that for every cardinal $\kappa$ we have $\kappa=\kappa\cdot\kappa$. So separate every $A_\alpha$ into $\kappa$ partitions of size $\kappa$ and let's call them $A_{\alpha,\beta}$. Now let $\{B_\alpha : \alpha<\kappa\}$ be an enumeration of all the $A_{\alpha,\beta}$. Observe now that we need to find sets $X,Y$ such that for every $\alpha<\kappa$ we have $B_\alpha\cap X\neq\varnothing\neq B_\alpha\cap Y$ and $X\cap Y=\varnothing$.

Each of these sets will satisfy the property we want since in every $A_{\alpha,\beta}$ there will exist an element in $X$ and one in $Y$ and therefore $\kappa$ elements of $A_\alpha$ in $X$ and $\kappa$ in $Y$ and furthermore $X\cap Y=\varnothing$ will give $Y\subset\kappa\setminus X$ and $X\subset\kappa\setminus Y$. I will construct two such sets $\mathcal{C}$, $\mathcal{D}$ inductively:

Let $\gamma_0$ be the least element of $B_0$ and make $\mathcal{C}_0=\{\gamma_0\}$. Now let $\delta_0$ be the least element of $B_0\setminus\mathcal{C}_0$ and let $\mathcal{D}_0=\{\delta_0\}$. Assume now that for every $\xi<\alpha$ we have defined $\mathcal{C}_\xi$ and $\mathcal{D}_\xi$ such that each of them have at most $|\xi+1|$ elements.

If $(\bigcup_{\xi<\alpha}\mathcal{C}_\xi)\cap B_\alpha$ is non-empty let $\mathcal{C}_\alpha=\bigcup_{\xi<\alpha}\mathcal{C}_\xi$ Otherwise let $\gamma_\alpha$ be the least element of $B_\alpha\setminus(\bigcup_{\xi<\alpha}\mathcal{D}_\xi)$ (this element has to exist since the union has at most $|\alpha|$ elements while $B_\alpha$ has $\kappa$) and let $\mathcal{C}_\alpha=(\bigcup_{\xi<\alpha}\mathcal{C}_\xi)\cup\{\gamma_\alpha\}$ (observe that this has at most $|\alpha+1|$ elements). Now if $(\bigcup_{\xi<\alpha}\mathcal{D}_\xi)\cap B_\alpha$ is non-empty let $\mathcal{D}_\alpha=\bigcup_{\xi<\alpha}\mathcal{D}_\xi$. Otherwise if $\delta_\alpha$ is the least element of $B_\alpha\setminus\mathcal{C}_\alpha$ (again this exists) let $\mathcal{D}_\alpha=(\bigcup_{\xi<\alpha}\mathcal{D}_\xi)\cup\{\delta_\alpha\}$. Finally let $\mathcal{C}=\bigcup_{\alpha<\kappa}\mathcal{C}_\alpha$ and $\mathcal{D}=\bigcup_{\alpha<\kappa}\mathcal{D}_\alpha$.

Finally, notice that $\mathcal{C}\cap\mathcal{D}=\varnothing$ because of the above construction and for every $\alpha<\kappa$ we have $B_\alpha\cap\mathcal{C}\neq\varnothing$ and $B_\alpha\cap\mathcal{D}\neq\varnothing$.

share|cite|improve this answer
Seems like the right answer. Thank you. – Pavel Feb 8 '11 at 19:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.