Analysis exercise

Consider the following assertion:

For any function $f$ from $\mathbb{R}$ to the countable subsets of $\mathbb{R}$, there are real numbers $a$ and $b$ such that $b\notin f(a)$ and $a\notin f(b)$.

Can you prove it? Can you disprove it? If you can’t prove or disprove it, does your intuition suggest that it’s true or false? Let’s hear in the comments.

Aside | This entry was posted in Logic, Set theory. Bookmark the permalink.

17 Responses to Analysis exercise

1. Jay Cummings says:

“Every math problem can be solved by counting.”

• Jay Cummings says:

But I don’t see how…..

• Z Norwood says:

Who said this?

• Jay Cummings says:

I don’t know.. But it is a “famous” quote.

2. Jay Cummings says:

Maybe: If there were some $f$ such that no such pair $a,b$ exists, then given any pair $x$ and $y$, either $x \in f(y)$, $y \in f(x)$ or both. But this implies that $x$ must be in the image of all but countably many $y$, in particular all the $y$ that are not in $f(x)$.

But because this holds for every $x$, maybe by a counting or diagonalization or measure theoretic argument, one of the $f(x)$ would have to have uncountably many elements, a contradiction?

3. soffer801 says:

Let’s assume the axiom of choice, because, as we all know, it’s true.

Take a well-ordering $\prec$ of $\mathbb R$, and let $f:x\mapsto \{y\mid y\prec x\}$. Then either $x\prec y$ or $y\prec x$, so either $x\in f(y)$ or $y\in f(x)$. But wait, how do I know $f(x)$ is always countable? Okay, so assume the continuum hypothesis too. Then I can pick a well-ordering of $\mathbb R$ such that $f(x)$ is always countable.

Presumably if we assume the negation of the continuum hypothesis, we’ll run into a contradiction, but I can’t seem to make that happen. I’ll get back to you.

4. Jay Cummings says:

Zach, do you remember that similar problem that we talked about last year? Roger had mentioned it during Algebra. The solution involved taking a well ordering of the reals. Although I think it was about a map from subsets of $\mathbb{R}$ to $mathbb{R}$ and projecting onto the least element…..

• Z Norwood says:

In the email I sent Roger about it I provide a link to this math.SE question. Maybe that’s the question he asked. I don’t think it has anything to do with the question I give in this post, though.

• Z Norwood says:

Maybe that wasn’t the question you were thinking of. It doesn’t require considering a wellordering of $\mathbb{R}$.

5. Z Norwood says:

Don’t think _too hard_ about proving it, only hard enough to develop enough intuition to decide whether you think it’s true or false. I’m more interested in what your intuition tells you than whether you can (dis)prove it. And you shouldn’t worry about Choice. That is, feel free to assume AC or ¬AC: whatever suits your boat.

Consider this, if you’re struggling to gain some intuition about the problem: pick your favo(u)rite pair of real numbers $a$ and $b$. Is it likely that $a\in f(b)$?

I’ll wait until we hear from our resident analysts before I say more. Surely Hotovy has an opinion about this?

• Jay Cummings says:

I don’t have a strong intuition about whether it’s true or not. I initially was leaning towards it not being true, but then later started to move away from that. (My first intuition was actually that you were going to tell us that this problem is equivalent to a famous unsolved problem from set theory.)

• Z Norwood says:

Some (namely, those who argue that CH is an ‘unsolved problem’) would argue that your first intuition is correct.

I guess I’ll say a few words about this. There are (at least) two kinds of set theorists: (0) the multiversist argues that CH is settled by our extensive knowledge of how CH behaves under forcing. (1) The universist argues that there is a natural extension of ZF(C) (e.g. Freiling’s Axiom of Symmetry) in which CH is settled. That is, there should be some axiom (like AS) that appeals to our intuition about what a set should be and implies either CH or ¬CH.

• Z Norwood says:

Maybe I should have had e.g. Hotovy author this post, so you wouldn’t all immediately assume that it’s some sort of independence result.

6. Nicki says:

My intuition tells me this is false. Though, I don’t know how I would go about proving this.

• Z Norwood says:

Thanks for commenting, Nicki! This is an interesting perspective. Among the few people I’ve discussed this with, most have claimed that it seems true or that they don’t know. I’d love to hear any sort of further explanation of why you think it seems false!

I think that Andy’s on the right track. Andy believes that if your assertion is true, then the continuum hypothesis is false. So here’s an attempt at a converse. Suppose the continuum hypothesis is false. Let $f$ be such a function and pick a subset of $\mathbb{R}$ of size $\aleph_1$, call it $Z$ (for Zach, not Zahlen).

Note that $f(z)$ is countable for every $z\in Z$ by assumption. So $\mathcal{Z}=\bigcup_{z\in Z} f(z)$ must also be $\aleph_1$, being an $\aleph_1$-union of $\aleph_0$ sets. But $\mathbb{R}$ has cardinality $\mathfrak{c}>\aleph_1$ (by assumption), and so $\mathbb{R}\setminus \mathcal{Z}$ is non-empty. So choose some $a\in \mathbb{R}\setminus \mathcal{Z}$.

Now, since $f(a)$ is countable ($\aleph_0$) and $Z$ is $\aleph_1$, it follows that $Z\setminus f(a)$ is non-empty. So we can choose $b\in Z\setminus f(a)$. So $b\not\in f(a)$ and $a\not\in \mathcal{Z}$ which, since $f(b)\subseteq \mathcal{Z}$, implies that $a\not\in f(b)$. Since $f$ was chosen arbitrarily, this proves the assertion. Andy’s comment above shows the other direction, that if the continuum hypothesis is true, then the assertion is false. (Zach, just spoil it already!)

At first glance I thought this was false. It just seems like an incredibly rare property for a function to have.

8. Z Norwood says:

You all are too clever for your own good. The punchline, as ‘Zam & Andy point out, is that the assertion (hereafter AS’) is equivalent to ¬CH. My intent was not to give you an unsolvable exercise or get you to realise that AS is equivalent to ¬CH; I hoped that some of you would have a(n at least moderately) strong opinion about whether AS should be true. (Apparently CH holds for Nicki’s $\mathbb{R}$!) Then you’d maybe have an opinion about CH (though it’s unclear what it means to have an opinion about CH’ and what the significance of such an opinion might be).

Fwiw, AS is called the Axiom of Symmetry. It was introduced by Chris Freiling, who intended to convince people that CH should be false (again, whatever that means). In the first few pages of his paper Freiling presents his case by throwing darts at the real line’, and those first few pages are recommended reading. I tried to hint at this, but I didn’t want to mention darts’, lest you be tempted to ask Google for the answer!

Anywho, maybe now that the curtain has been torn away, you can forget about the fact that AS is equivalent to ¬CH and see what your intuition says about AS.