Question

Does there exist a set $M \subset \mathbb{R}^2$ which has the following two properties:

• Forall $x \in \mathbb{R}$ the set $\{y \in \mathbb{R} \mid (x,y) \in M\}$ is countable.
• Forall $y \in \mathbb{R}$ the set $\{x \in \mathbb{R} \mid (x,y) \notin M\}$ is countable.

Answer 1

It is a theorem of Sierpinski (Sur un theoreme equivalent a l'hypothese du continu) that the existence of such a set is equivalent to the continuum hypothesis.

Answer 2

Here's an easy proof of the equivalence of the statement to CH (I think). One direction is just what Emil said. For the other direction:

Suppose continuum is $\geq \aleph_2$. Restrict attention to an $\aleph_2$-sized subset of $\mathbb{R}$, and suppose we had a relation with the properties you want on that subset. (Note: if there is a relation with those properties on $\mathbb{R}^2$ then it will retain those properties when we restrict to a smaller set.) Take $\aleph_1$ many $x$-coordinates from this set; each of them only has countably many $y$'s that it gets paired with in the relation, so in total there are at most $\aleph_1$ many $y$'s that get paired with any of these $x$'s. So, take some $y$ which doesn't get paired with any of these $x$'s. (There will be such a $y$ because we have $\aleph_2$ many $y$'s in total.) This $y$ has at least $\aleph_1$ many $x$'s that it does not get paired with; and this contradicts the properties of the relation.

Ramiro, I'm guessing this is the same argument Sierpinski gave?