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

the problem is the following:

For all $x \in \mathbb{R}$, we assign a finite set $\Phi(x) \subset \mathbb{R} - \{ x \}$. We say that a set $S \subset \mathbb{R}$ is independent if for any $x,y \in S$, $x \notin \Phi(y)$ and $y \notin \Phi(x)$, that is, if $S \cap \Phi(S) = \emptyset$. Prove that there is an independent set $S$ with the cardinality of the continuum.

Any ideas? Thanks in advance.

share|cite|improve this question
Firstly, the notation $S\cap\Phi(S)$ is problematic, since $\Phi(S)$ is a set of sets, you mean $S\cap\bigcup\Phi(S)$, I believe. Secondly, have you tried assuming by contradiction that every such set has cardinality less than continuum? In this situation, what can you say about |$\bigcup\Phi(S)$|? – Asaf Karagila Dec 27 '10 at 12:55
Thank you, yu're right with the notation. I still don't see how it is done, we can say that |$\bigcup \Phi(S)$| is less than c for any independent set S (in fact it has the same cardinality as S if S is infinite), but I don't know how to continue. – Charlie Dec 27 '10 at 20:55
I don't think that having $|\bigcup \Phi(S)| < c$ gets you there. There is a famous example, assuming AC+CH, that if $\Phi(x)$ is allowed to be countably infinite, the maximum independent S has size 1, yet the first relation still holds for S countable. – Ross Millikan Dec 27 '10 at 23:19
Where can i see this example? I'm very interested in it. – Charlie Dec 27 '10 at 23:53
@Charlie: I saw it on the web somewhere. If you well-order the reals, each one has at most countably many predecessors. So let $\Phi(x)$ be the predecessors of $x$ in this order. Then for any $x, y$ with $x\neq y$, either $x\in \Phi (y)$ or $y\in \Phi(x)$. Some use this as an argument against CH: it seems if $\Phi(x)$ is countable, you should be able to pick "random" x and y and have neither $x\in \Phi (y)$ nor $y\in \Phi(x)$ – Ross Millikan Dec 28 '10 at 1:42
up vote 3 down vote accepted

Charlie, this is a result of Sierpiński. It appears in " Sur un problème de la théorie des relations", Fundamenta Mathematicae, vol 28, (1937), 71-74. You can download the paper here.

The general result of which this is a particular case is due to Hajnal (rather than "independent", one usually talks of "free"). It appears in "Proof of a conjecture of B. Ruziewicz", Fundamenta Mathematicae, vol 50, (1961), 123-128. It can be downloaded here.

Let me know if you have difficulty understanding the arguments there, and I'll sketch the proof.

share|cite|improve this answer

Here is a sketch of a proof (it uses axiom of choice).

Let's introduce a equivalence relation on real numbers.

We say that two numbers $x$ and $y$ are "equal" of there exists a finite set of reals $a_0 = x$, $a_1$, $a_2$, $\cdots$, $a_{n-1}$, $a_n = y$ such that for any $i$ we have $a_i \in \Phi(a_{i+1})$ or $a_{i+1} \in \Phi(a_i)$. Note that $n$ could be zero, so $x$ and $x$ are also considered equal.

It's clear that this equivalence relation is symmetric, reflexive and transitive. Hence we can consider equivalence classes under this relation.

Now, every equivalence classes is countable (because $\Phi(x)$ is finite for all $x$). Hence we have splitted reals into a set of disjoint countable sets.

This implies that number of such sets is a continuum. Now we can just take any element from each set to form $S$.

share|cite|improve this answer
It's not necessarily true that every equivalence class is countable. Consider $\Phi(x)=\{ a \}$ for $x \neq a$, and $\Phi(a)=\{ b \}$ with $b \neq a$. Then there is only one equivalence class, since for every x, x is related to a. – Charlie Dec 27 '10 at 20:52

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.