Problem in set theory 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.
 A: 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$.
A: 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.
