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.

  • 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