Freiling's axiom of symmetry

Freiling's axiom of symmetry (AX) is a set-theoretic axiom proposed by Chris Freiling. It is based on intuition of Stuart Davidson but the mathematics behind it goes back to Wacław Sierpiński.

Let A be the set of functions mapping numbers in the unit interval [0,1] to countable subsets of the same interval. The axiom AX states:

For every f in A, there exist x and y such that x is not in f(y) and y is not in f(x).

A theorem of Sierpiński says that under the assumptions of ZFC set theory, AX is equivalent to the negation of the continuum hypothesis (CH). Although Sierpiński did not formally promote this as evidence against CH, it is likely that he understood the paradoxical implications in a similar manner as Freiling. Sierpiński's theorem answered a question of Hugo Steinhaus and was proved long before the independence of CH had been established by Kurt Gödel and Paul Cohen. It was Stewart Davidson who first suggested to Freiling that Sierpiński's theorem should be considered as evidence against CH.

Freiling claims that probabilistic intuition strongly supports this proposition while others disagree. There are several versions of the axiom, some of which are discussed below.

Freiling's argument

Fix a function f in A. We will consider a thought experiment that involves throwing two darts at the unit interval. We probably aren't able to physically determine with infinite accuracy the actual values of the numbers x and y that are hit. Likewise, the question of whether "y is in f(x)" cannot actually be physically computed. Nevertheless, if f really is a function, then this question is a meaningful one and will have a definite "yes" or "no" answer.

Now wait until after the first dart, x, is thrown and then assess the chances that the second dart y will be in f(x). Since x is now fixed, f(x) is a fixed countable set and has Lebesgue measure zero. Therefore this event, with x fixed, has probability zero. Freiling now makes two generalizations:

• Since we can predict with virtual certainty that "y is not in f(x)" after the first dart is thrown, and since this prediction is valid no matter what the first dart does, we should be able to make this prediction before the first dart is thrown. This is not to say that we still have a measurable event, rather it is an intuition about the nature of being predictable.

• Since "y is not in f(x)" is predictably true, by the symmetry of the order in which the darts were thrown (hence the name "axiom of symmetry") we should also be able to predict with virtual certainty that "x is not in f(y)".

The axiom AX is now justified based on the principle that what will predictably happen every time this experiment is performed, should at the very least be possible. Hence there should exist two real numbers x, y such that x is not in f(y) and y is not in f(x).

Relation to the (Generalised) Continuum Hypothesis

Fix $\kappa\,$ an infinite cardinal (e.g. $\aleph_{0}\,$). Let $\texttt{AX}_{\kappa}.\,$ be the statement: there is no map $f:\mathcal{P}(\kappa)\to\mathcal{P}\mathcal{P}(\kappa)\,$ from sets to sets of size $\leq\kappa$ for which $(\forall{x,y\in\mathcal{P}(\kappa)})\,$ either $x\in f(y)\,$ or $y\in f(x)\,$.

Claim: $\texttt{ZFC}\vdash 2^{\kappa}=\kappa^{+}\leftrightarrow\neg\texttt{AX}_{\kappa}.\,$.

Proof: Part I ($\Rightarrow\,$):

Suppose $2^{\kappa}=\kappa^{+}\,$. Then letting $\sigma:\kappa^{+}\to\mathcal{P}(\kappa)\,$ a bijection, we have $f:\mathcal{P}(\kappa)\to\mathcal{P}\mathcal{P}(\kappa)\,$ $:\sigma(\alpha)\mapsto \{\sigma(\beta):\beta\preceq\alpha\}\,$ clearly demonstrates the failure of Freiling's axiom.

Part II ($\Leftarrow\,$):

Suppose that Freiling's axiom fails. Then fix some $f\,$ to verify this fact. Define an order relation on $\mathcal{P}(\kappa)\,$ by $A\leq_{f} B$ iff $A\in f(B)$. This relation is total and every point has $\leq\kappa$ many predecessors. Define now a strictly increasing chain $(A_{\alpha}\in\mathcal{P}(\kappa))_{\alpha<\kappa^{+}}$ as follows: at each stage choose $A_{\alpha}\in\mathcal{P}(\kappa)\setminus\bigcup_{\xi<\alpha}f(A_{\xi})$. This process can be carried out since for every ordinal $\alpha<\kappa^{+}\,$, $\bigcup_{\xi<\alpha}f(A_{\xi})\,$ is a union of $\leq\kappa\,$ many sets of size $\leq\kappa\,$; thus is of size $\leq\kappa<2^{\kappa}\,$ and so is a strict subset of $\mathcal{P}(\kappa)\,$. We also have that this sequence is cofinal in the order defined, i.e. every member of $\mathcal{P}(\kappa)\,$ is $\leq_{f}\,$ some $A_{\alpha}\,$. (For otherwise if $B\in\mathcal{P}(\kappa)\,$ is not $\leq_{f}\,$ some A_α, then since the order is total $(\forall{\alpha<\kappa^{+}})A_{\alpha}\leq_{f} B\,$; implying $B\,$ has $\geq\kappa^{+}>\kappa\,$ many predecessors; a contradiction.) Thus we may well-define a map $g:\mathcal{P}(\kappa)\to\kappa^{+}\,$ by $B\mapsto\operatorname{min}\{\alpha<\kappa^{+}:B\in f(A_{\alpha})\}$. So $\mathcal{P}(\kappa)=\bigcup_{\alpha<\kappa^{+}}g^{-1}\{\alpha\}=\bigcup_{\alpha<\kappa^{+}}f(A_{\alpha})\,$ which is union of $\kappa^{+}\,$ many sets each of size $\leq\kappa\,$. Hence $2^{\kappa}\leq\kappa^{+}\cdot\kappa=\kappa^{+}\,$ and we are done.

$\blacksquare$ (Claim)

Note that $|[0,1]|=|\mathcal{P}(\aleph_{0})|\,$ so we can easily rearrange things to obtain that $\neg\texttt{CH}\Leftrightarrow\,$ the above mentioned form of Freiling's axiom.

The above can be made more precise: $\texttt{ZF}\vdash(\texttt{AC}_{\mathcal{P}(\kappa)}+\neg\texttt{AX}_{\kappa})\leftrightarrow \texttt{CH}_{\kappa}\,$. This shows (together the fact that the continuum hypothesis is independent of choice) a precise way in which the (generalised) continuum hypothesis is an extension of the axiom of choice.

Objections to Freiling's argument

Freiling's argument is not widely accepted because of the following two problems with it (which Freiling was well aware of and discussed in his paper).

• The naive probabilistic intuition used by Freiling tacitly assumes that there is a well-behaved measure on the reals such that all subsets are measurable, and hence often leads to contradictions when used together with the axiom of choice, since an invocation of the axiom of choice typically generates non-measurable sets. Some examples of such contradictions are the Banach–Tarski paradox and the existence of Vitali sets.
• A minor variation of his argument gives a contradiction with the axiom of choice whether or not one accepts the continuum hypothesis, if one replaces countable additivity of probability by additivity for cardinals less than the continuum. (Freiling used a similar argument to claim that Martin's axiom is false.) It is not clear why Freiling's intuition should be any less applicable in this instance, if it applies at all. (Maddy 1988, p. 500) So Freiling's argument seems to be more an argument against the possibility of well ordering the reals than against the continuum hypothesis.

Connection with Solovay's forcing

Freiling's argument appeals to the intuitive idea of throwing darts at the real line. In order to consistently throw darts at the real line, every subset of the real line must be measurable. The reason is that given a set S, if you throw a dart, it becomes a "fixed" and "definite" real number, and you can check if it is in the set S or not. Throw the dart again and again, and define the measure of any set as the limit of the ratio: (# that land in S) / (# thrown).

Since every throw is statistically independent, this converges to a unique value. The value defines a countably additive, translation invariant measure which coincides with Lebesgue measure for intervals, a thing which cannot exist according to the axiom of choice. This is why Freiling's argument is really about the axiom of choice, not so much about the continuum hypothesis.

The existence of a model of ZF set theory (without the axiom of choice) in which the reals support a translation-invariant measure over all sets (in fact, it may be taken to be Lebesgue measure itself) is consistent assuming that it is consistent to have an inaccessible cardinal. This was proven by Robert Solovay who, following earlier work of Paul Cohen, introduced the notion of a random real number. The definition of measure of a set as a ratio is closely related to Solovay's definition of measure.

Connection to graph theory

Using the fact that in $\texttt{ZFC}\,$ we have $2^{\kappa}=\kappa^{+}\Leftrightarrow\neg\texttt{AX}_{\kappa}\,$ (see above), it is not hard to see that the failure of the axiom of symmetry — and thus the success of $2^{\kappa}=\kappa^{+}\,$ — is equivalent to the following combinatorial principle for graphs:

• The complete graph on $\mathcal{P}(\kappa)\,$ can be so directed, that every node leads to at most $\kappa\,$-many nodes.
• In the case of $\kappa=\aleph_{0}\,$, this translates to: The complete graph on the unit circle can be so directed, that every node leads to at most countably-many nodes.

Thus in the context of $\texttt{ZFC}$, the failure of a Freiling axiom is equivalent to the existence of a specific kind of choice function.

Extensions and alternate versions

There are several variations to consider. Suppose first that A was the set of functions mapping [0,1] to finite subsets of [0,1]. Suppose that we made the corresponding assertion:

For every f in A, there exist x and y such that x is not in f(y) and y is not in f(x).

This statement is not just intuitively true, it can be proved. However, let's now make a minor adjustment to accommodate three darts. Let A be the set of functions that map pairs of numbers from [0,1] to finite subsets of [0,1]. After two darts x, y are thrown, we can predict that the third dart, z, will not be in the set assigned to the pair {x,y}. As before, since this prediction is always the same, it should be equally valid before the first two darts are thrown. Then by symmetry, we also expect that x is not in the set assigned to {y,z} and that y is not in the set assigned to {x,z}. Hence we should at least believe that:

For every f:{{x,y} :x,yє[0,1], y ≠ x}→P([0,1]), in A, there exist distinct x, y,z, such that x is not in f({y,z}), y is not in f({x,z}) and z is not in f({x,y}).

Like the original version given above, this is equivalent in ZFC to the negation of the continuum hypothesis. The advantage of this version is that it requires only intuition about finite sets having probability zero.

One can throw more and more darts this way, and with each successive dart, the lower bound on the continuum grows. If one allows versions for infinitely many darts then the continuum is bounded below by a Jónsson cardinal, which is a type of large cardinal. But if one tries this with ω+1 darts then another contradiction is reached with the Axiom of Choice.

References

• Freiling, Chris (1986), "Axioms of symmetry: throwing darts at the real number line", The Journal of Symbolic Logic 51 (1): 190–200, doi:10.2307/2273955, ISSN 0022-4812, MR830085 
• Maddy, Penelope (1988). "Believing the Axioms, I". Journal of Symbolic Logic 53 (2): 481–511. doi:10.2307/2274520. 
• David Mumford, "The dawning of the age of stochasticity", in Mathematics: Frontiers and Perspectives 2000, American Mathematical Society, 1999, 197–218.

• Sierpiński, Wacław (1956) [1934], Hypothèse du continu, Chelsea Publishing Company, New York, N. Y., MR0090558 

• John Simms, "Traditional Cavalieri principles applied to the modern notion of area", J. Philosophical Logic 18 (1989), 275–314.