Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello! I would like to open a discussion about the Axiom of Symmetry of Freiling, since I didn't find in MO a dedicated question. I'll first try to summarize it, and the ask a couple of questions.

DESCRIPTION

The Axiom of Symmetry, was proposed in 1986 by Freiling and it states that

$AS$: for all $f:I\rightarrow I_{\omega}$ the following holds: $\exists x \exists y. ( x \not\in f(y) \wedge y\not\in f(x) )$

where $I$ is the real interval $[0,1]$, and $I_{\omega}$ is the set of countable subsets of $I$.

It is known that $AS = \neg CH$. What makes this axiom interesting is that it is explained and justified using an apparently clear probabilistic argument, which I'll try to formulate as follow:

Let us fix $f\in I\rightarrow I_{\omega}$. We throw two darts at the real interval $I=[0,1]$ which will reach some points $x$ and $y$ randomly. Suppose that when the first dart hits $I$, in some point $x$, the second dart is still flying. Now since $x$ is fixed, and $f(x)$ is countable (and therefore null) the probability that the second dart will hit a point $y\in f(x)$ is $0$. Now Freiling says (quote),

Now, by the symmetry of the situation (the real number line does not really know which dart was thrown first or second), we could also say that the first dart will not be in the set $f(y)$ assigned to the second one.

This is deliberately an informal statement which you might find intuitive or not. However, Freiling concludes basically saying that, since picking two reals $x$ and $y$ at random, we have almost surely a pair $(x,y)$ such that, $x \not\in f(y) \wedge y\not\in f(x) )$, then, at the very least, there exists such a pair, and so $AS$ holds.

DISCUSSION

If you try to formalize the scenario, you'd probably model the "throwing two darts" as choosing a point $(x,y) \in [0,1]^{2}$. Fixed an arbitrary $f\in I\rightarrow I_{\omega}$, Freiling's argument would be good, if the set

$BAD = ${$(x,y) | x\in f(y) \vee y \in f(x) $}

has probability $0$. $BAD$ is the set of points which do not satisfy the constraints of $AS$. If $BAD$ had measure zero, than finding a good pair would be simple, just randomly choose one! In my opinion the argument would be equally good, if $BAD$ had "measure" strictly less than $1$. In this case we might need a lot of attempts, but almost surely we would find a good pair after a while.

However $BAD$ needs not to be measurable. We might hope that $BAD$ had outermeasure $<1$, this would still be good enough, I believe.

However, if $CH$ holds there exists a function $f_{CH}:I\rightarrow I_{\omega}$ such that $BAD$ is actually the whole set $[0,1]^{2}$!! This $f_{CH}$ is defined using a well-order of $[0,1]$ and defining $f_{CH}(x) = ${$y | y \leq x $}. Under $CH$ the set $f(x)$ is countable for every $x\in[0,1]$. Therefore

$BAD = ${$ (x,y) | x\in f_{CH}(y) \vee y \in f_{CH}(x) $}$ = ${$ (x,y) | x\leq y \vee y \leq x $}$ =[0,1]^{2}$

So it looks like that under this formulation of the problem, if $CH$ then $\neg AS$, which is not surprisingly at all since $ZFC\vdash AS = \neg CH$. Also I don't see any problem related with the "measurability" of $BAD$.

QUESTIONS

Clearly it is not possible to formalize and prove $AS$. However the discussion above seems very clear to me, and it just follows that if $CH$ than $BAD$ is the whole set $[0,1]^{2}$. without the need of any non-measurable sets or strange things. And since picking at random a point in $[0,1]^{2}$ is like throwing two darts, I don't really think $AS$ should be true, or at least I don't find the probabilistic explanation very convincing.

On the other hand there is something intuitively true on Freiling's argument.

My questions, (quite vague though, I would just like to know what you think about $AS$), are the following.

A) Clearly Freiling's makes his point, on the basis that the axioms of probability theory are too restrictive, and do not capture all our intuitions. This might be true if the problem was with some weird non-measurable sets, but in the discussion above, non of these weird things are used. Did I miss something?

B) After $AS$ was introduced, somebody tried to tailor some "probability-theory" to capture Freling's intuitions? More in general, is there any follow up, you are aware of?

C) Where do you see that Freiling's argument deviates (even philosophically) from my discussion using $[0,1]^{2}$. I suspect the crucial, conceptual difference, is in seeing the choice of two random reals as, necessarily, a random choice of one after the other, but with the property that this arbitrary non-deterministic choice, has no consequences at all.

Thank you in advance,

Matteo Mio

share|improve this question
1  
Two minor typos: In your displayed equation $BAD = ... [0,1]^2$, you've got $x\le y$ twice, whereas you wanted one $x\le y$ and one $y\le x$. And in the sentence just after the heading QUESTIONS, you want $[0,1]^2$, not $[0,1]$. –  Steven Landsburg Dec 17 '10 at 11:58
    
thanks Steven! fixed. –  Matteo Mio Dec 17 '10 at 13:06
    
Great question! –  Cam McLeman Dec 17 '10 at 15:16
add comment

1 Answer

up vote 15 down vote accepted

The point is that violations of the Axiom of Symmetry are fundamentally connected with non-measurable sets, and counterexample functions $f$ to AS cannot be nice measurable functions.

You have proved the one direction $CH\to \neg AS$, that if there is a well-order of the reals in order type $\omega_1$, then the function $f$ that maps each real to its predecessors violates AS. Observe in this case that the set of pairs $\{(x,y) \mid y\in f(x)\}$ has all vertical sections countable, and all horizonatal sections co-countable, which would violate Fubini's theorem if it were measurable. So it is not measurable.

Conversely, for the direction $\neg AS\to CH$, all violations of AS have essentially this form. To see this, suppose that $f$ is a function without the symmetry property, so that for any two reals $x$ and $y$, either $x\in f(y)$ or $y\in f(x)$. For any real $x$, let $A_x$ be the closure of $x$ under $f$, obtained by iteratively applying $f$ to $x$ and to any real in $f(x)$, and so on to all those reals iteratively. Thus, $A_x$ is a countable set of reals and closed under $f$. Define a relation $y\leq x$ if $y\in A_x$. This is a reflexive transitive relation. The symmetry assumption on $f$ exactly ensures that this relation is a linear relations, so that either $x\leq y$ or $y\leq x$ for any two reals. So it is a linear pre-order. Furthermore, all proper initial segments of the pre-order are countable, since any such initial segment is contained in some $A_y$. In other words, the relation $\leq$ is an $\omega_1$-like linear pre-order of the reals. This implies CH, since the cofinality of this order can be at most $\omega_1$, for otherwise there would be an uncountable initial segment, and so $\mathbb{R}$ would be an $\omega_1$-union of countable sets. That is, the argument shows that every counterexample to AS arises essentially the same way as in your CH argument, but using a pre-order instead of a well-order.

Note that the set $A=\{(x,y)\mid y\in A_x\}$ is non-measurable by the same Fubini argument: all the vertical slices are countable, and all horizontal slices co-countable.

My view is that any philosophical, pre-reflection or intuitive concept of probability will have a very fundamental problem in dealing with subsets of the plane for which all vertical sections are countable and all horizontal sections are co-countable. For such a set, from one direction it looks very big, and from another direction it looks very small, but our intuitive concept is surely that rotating a set shouldn't affect our judgement of its size.

share|improve this answer
2  
Let me emphasize the connection (or contrast) between Joel's answer and the quote "if CH than BAD is the whole set [0,1]^2 without the need of any non-measurable sets or strange things" from the question. Even though BAD is not "strange" in this situation, Freiling's symmetry argument depends on looking at the two pieces $\{(x,y):x\leq y\}$ and $\{(x,y):x\geq y\}$ of BAD; as Joel explained, these pieces will be non-measurable. –  Andreas Blass Dec 17 '10 at 15:48
    
Thank you very much Joel and Andreas for the excellent answers! I wrote a follow up, since I'd like to try to understand a bit more the matter. –  Matteo Mio Dec 17 '10 at 17:06
1  
Let me comment first about "intuition suggests that $B_1$ and $B_2$ have "size" 1/2." Perhaps intuition does suggest that, but first it must have suggested that "size" makes sense for these sets. What the non-measurability of the two sets shows is, in my opinion, that any such intuition needs to be corrected. Our intuition that sets have sizes (in the sense used here --- generalized area in the plane) is based on far tamer sets than these and simply does not apply to sets as wild as these well-order relations. –  Andreas Blass Dec 17 '10 at 17:53
1  
Now about the dart argument: For each fixed $x$, almost all $y$ satisfy $x<y$ (where $<$ is well-ordering of length $\omega_1$), and it is tempting to conclude that therefore almost all pairs $(x,y)$ satisfy $x<y$. Unfortunately, this mode of argument, going from "for each $x$, for almost all $y$,..." to "for almost all $(x,y)$,...", plausible though it may sound, is in fact valid only under the extra hypothesis that the "..." part defines a measurable set (in which case it's a consequence of Fubini's theorem). –  Andreas Blass Dec 17 '10 at 18:00
2  
"rotating a set shouldn't affect our judgement of its size." Then again, it is known that some vision neurons are particularly good at seeing horizontal lines, and others at vertical lines, and it's a little harder for us (mammals, at least --- I think the experiments were done by putting probes into cat brains) to see diagonals. It is also known that we're not very good at telling whether a vertical line and a horizontal line have the same length: I can't remember which direction the effect is, but I think there's a standard error. –  Theo Johnson-Freyd Jul 13 '11 at 13:03
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.