Axiom of Symmetry, aka Freiling's argument against CH
Asked 12 years, 1 month ago
Modified 1 month ago
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.
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.
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$.
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.
Matteo Mio
Martin Sleziak
IamMeeohIamMeeoh
$\begingroup$ Great question! $\endgroup$
– Cam McLeman
$\begingroup$ I think Dr. Freiling should be given a Field Medal, except he is over 40. $\endgroup$
$\begingroup$ If I instead wanted to believe that the cardinality of $[0,1]$ was aleph_17, could you not then propose that it is "obvious" that for all functions from [0,1] to the set of subsets of size at most aleph_16, by "probability", there will exist $x$ and $y$ with $x$ not in $f(y)$ and $y$ not in $f(x)$, and hence refute my belief? Doesn't this observation then give evidence that the axiom of symmetry is "wrong"? $\endgroup$
$\begingroup$ The assertion that $2^\omega$ is at least $\aleph_{17}$ is equivalent to the assertion that for any function $f$ mapping 16-tuples of reals to countable sets of reals, there are 17 reals such that none of them is an element of $f$ of the other 16. This is proved in Freiling's original paper. $\endgroup$
$\begingroup$ That is, in order to make the continuum at least $\aleph_n$, you need only throw $n$ darts randomly at the real line. $\endgroup$
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 relation, 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.
Joel David HamkinsJoel David Hamkins
$\begingroup$ 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. $\endgroup$
$\begingroup$ 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. $\endgroup$
– IamMeeoh
$\begingroup$ 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. $\endgroup$
$\begingroup$ 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). $\endgroup$
$\begingroup$ "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. $\endgroup$
– Theo Johnson-Freyd
Actually, in regards to your question B), there is a large cardinal axiom that implies $AS$. Your link to the wikipedia article regarding Freiling's axiom of symmetry states the following, in the section "Objections to Freiling's Argument":
"The naive probabilistic intuition used by Freiling tacitly assumes that there is a well-behaved way to associate a probability to any subset of the reals."
This is important, because the truth or falsity of $CH$ is intimately connected with the ability to assign to each subset of the reals, a probability measure.
Consider the following definition, from the Wikipedia article on measurable cardinals:
"A cardinal $\kappa$ is real-valued measurable iff there is a $\kappa$-additive probability measure on the power set of $\kappa$ which vanishes on singletons" (i.e. singletons have probabiity measure zero).
Axiom. Let $\mathfrak c$ be the cardinality of the continuum. $\mathfrak c$ is real-valued measurable.
Consider also the following equivalences from the same wikipedia article:
"A real-valued measurable cardinal ='$\mathfrak c$' exists iff there is a countably additive extension of the Lebesgue measure to all sets of reals iff there is an atomless probability measure on $\mathscr P$($\mathfrak c$).
Note also that the wikipedia article on Freiling's axiom of symmetry linked to your question states that $AS$ is equivalent to $\lnot$$CH$ by a theorem of Sierpinski, and also states that back in 1929, Banach and Kuratowski proved that $CH$ implies that $\mathfrak c$ is not real-valued measurable.
So consider the contrapositive of that statement, that if $\mathfrak c$ is real-valued measurable, then $\lnot$$CH$. Since $AS$ is equivalent to $\lnot$$CH$, then "$\mathfrak c$ is real-valued measurable" immediately implies $AS$. By the definition of real-valued measurable and the aforementioned equivalences found in the wikipedia article on measurable cardinals, Freiling's prereflective probabilistic argument seems to be essentially correct.
This is further confirmed by Noa Goldring in his paper "Measures, Back and Forth Between point Sets and Large Sets", (The Bulletin of Symbolic Logic, Vol. 1, Number 2, June 1995, pp. 182-183 footnotes 17 and 18--also ibid, pp. 171-188.
answered Sep 7, 2015 at 1:19
Independence result where probabilistic intuition predicts the wrong answer?
Limiting set theory using symmetry
Omega_{1} unions of null sets: Martin's Axiom
Can we put a probability measure on every $\sigma$-algebra?
Freiling's Axiom of Symmetry Concretized
A question regarding the relation between Freiling's Axiom of Symmetry and real-valued measurable cardnals
A question regarding a common critique of Freiling's Axiom of Symmetry
A variant of Freiling's Axiom of Symmetry and a weak form of the Continuum Hypothesis in models where all sets of reals are Lebesgue measurable
Does the existence of a non-principal measure on ω imply that of a non Lebesgue measurable set?
Can random variables that almost surely solve equations be repaired to surely solve these equations?
Is "There exists an unbounded non-measurable set but no bounded non-measurable set" consistent with $\mathsf{ZF}$?