# 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.

-
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

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.

-

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$.

-
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