3
$\begingroup$

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.

  • 1
    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)$|?2010-12-27
  • 0
    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.2010-12-27
  • 0
    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.2010-12-27
  • 0
    Where can i see this example? I'm very interested in it.2010-12-27
  • 1
    @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)$2010-12-28
  • 0
    Very nice and simple example.2010-12-28
  • 0
    @Charlie: The proof in the Hajnal paper cited by Andres Caicedo requires that $|\Phi(x)|\lt m \lt n$, where $n$ is the cardinality of the universe (for you $\mathbb{R}$) and $m$ is another cardinal (for you $\omega$). This is satisfied for finite sets.2010-12-28

2 Answers 2

3

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.

3

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

  • 0
    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.2010-12-27