Talk:Freiling's axiom of symmetry

The page says:

Given a function f in A, and some arbitrary real numbers x and y, it is generally held that x is in f(y) with probability 0, i.e. x is not in f(y) with probability 1.

How is this probability counted? My intuity would be that x is in f(y) with chance 0.5, since my method of getting a random subset of real numbers would be by giving each real number chance 0.5 to be in the set. Apparently there is another way of defining 'random' set of real numbers being used here, but which is it? Andre Engels 14:11, 27 Jan 2004 (UTC)

f(y) is not a "random" set of real numbers at all (the article says nothing about f being random). However, it is countable; this means that f(y) covers a very small fraction of all possible real numbers and that a "random" real number will be in f(y) (or any other countable set) with probability 0. Cwitty 22:15, 27 Jan 2004 (UTC)

Oops... I missed that 'countable' in the definition. Thanks. Andre Engels 00:50, 29 Jan 2004 (UTC)

Reference?

I seem to recall that this appeared in the Journal of Symbolic Logic in about 1985. I'll add the reference if I find it, unless someone beats me to it. Michael Hardy 23:34, 23 Jan 2005 (UTC)

Stewart Davidson

The article claims the argument is based on "Stewart Davidson"'s intuition. Who is he? --Aleph4 18:04, 28 May 2006 (UTC)

Never mind. Stuart Davidson is mentioned in the abstract of Freiling's article. --Aleph4 19:13, 28 May 2006 (UTC)

smallest non-zero set

Define κ as the largest cardinal such that

• For all sets C of cardinality less than κ it is virtually certain that a random x is not in C. Equivalently, κ is the smallest cardinal such that there is a set D for which the statement

a randomly selected x will be outside D

will not be almost surely true.

(In traditional mathematical language this is read as "κ is the smallest size of a set which is not of measure zero". This cardinal is usually called the "uniformity of the Lebesgue null ideal", unif(null) or non(null)).

Let B be the set of all functions mapping numbers in the unit interval [0,1] to subsets of the same interval of cardinality smaller than κ. Let A'X be the axiom stating:

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

Replacing "countable" in Freiling's argument by "of cardinality less than κ" now justifies the axiom A'X. From axiom A'X one can derive (using the function that assigns to each element of D the set of its predecessors, and to all other reals the empty set) that after throwing two arrows at the unit interval, it is virtually certain that not both arrows are in the set D. But as the two arrows are independent, we must be certain that both arrows land outside D. This contradicts the definition of D. -- June 10, 2006. Aleph4

It is well known that such κ = continuum. You seem to think that a proper subset of a set of given cardinality must have smaller cardinality - it is not so for infinite sets, so your argument fails. Leocat 17:44, 22 October 2006 (UTC)

No. He thinks (correctly) that any set can be well-ordered in such a way that the set of predecessors of any element has cardinal less than the whole set. Mind, I don't follow the proof; I don't see how to go from "there exist x and y such that x is not in f(y) and y is not in f(x)" to "almost every x and y are such that x is not in f(y) and y is not in f(x)" as his argument seems to require. The latter statement does of course follow from Freiling's "natural intuition". Ben Standeven 05:49, 8 April 2007 (UTC)

The argument seems to be: Choose D to be cofinite, so that landing in D is certain. So the first arrow hits $x\in D$. Then f(x) = {a: a < x} which has cardinality smaller than D. (If $c=\aleph _{2}$ then f(x) has cardinality $\aleph _{1}$, for example). So the second arrow hits y which must be in D but not in f(x); i.e., y > x. Yet this implies that the first arrow landed in f(y), an event with probability 0.

But are the sets f(x) and f(y), which are virtually certain not to be countable (if CH is false), even measurable? If they are nonmeasurable sets, can a meaningful probability be assigned to an arrow landing in f(x) or f(y)? That may be where Aleph4's argument fails. Throw out AC and the argument fails because there is no well-ordering of the reals; keep AC and the argument fails because the images under f are (almost entirely) nonmeasurable sets. Rsmoore (talk) 07:38, 28 August 2008 (UTC)

D being cofinite does not make landing in D certain. Also, cofinite sets only have the smallest cardinality on non-null sets if that cardinality is the cardinality of the continuum. What I think I can do is simplify Aleph4's work a little by modifying the proof in the article.

Let k be the initial ordinal of the smallest cardinality of non-null sets, and A be any ordinal with the cardinality of the continuum. Then there is a bijection g between [0,1] and A such that D = {x : g(x)<k} is not null. Now for all x, let f(x) = {y : g(y)≤g(x)<k}. This means that if k≤g(x), then f(x) is empty.

Since k was chosen to be the smallest cardinality of non-null sets, if g(x)<k, then f(x) is null, otherwise k≤g(x), so f(x) is empty. This means for all x, f(x) is null. Therefore, for all x, y is almost surely not in f(x), and for all y, x is almost surely not in f(y). On the other hand, for any pair of numbers x and y in D, either f(x) contains y, or f(y) contains x. This would suggest that almost surely x and y are not both in D, but D is not a null set. JumpDiscont (talk) 04:40, 27 September 2009 (UTC)

Where is the contradiction with the axiom of choice?

If we replace "countable" by any other statement which implies "of Lebesgue measure zero" we will still get probability = 1 that x is not in f(y) and that y is not in f(x). I do not see any contradiction with the axiom of choice. Leocat 21:26, 21 October 2006 (UTC)

Fix a well-ordering of the continuum <. Let f map its argument to the set of all smaller elements under <. Now for x and y, either x is in f(y) or y is in f(x). So by AXI it must be that there is some x for which f(x) is not of zero Lebesgue measure, even though its cardinal less than the continuum. Technically, I don't see any contradiction with the axiom of Choice, though. If we assume that f(x) is always a measurable set, we can repeat the above argument on f(x) and thereby set up an infinite descending sequence of ordinals. Ben Standeven 05:37, 8 April 2007 (UTC)

Countable Additivity of a Dart-Throw Measure

Since the discussion in the section "connection with random forcing" is intuitive, like much of Freiling's argument, it isn't possible to establish properties like countable additivity from axioms. The formal way to argue in set theory is to do something equivalent to Solovay forcing. But having said that, an intuitive property implies that the dart throw measure is countably additive.

The important thing to realize is that the dart throws can be used simultaneously to find the measures of a collection of disjoint sets and that of the disjoint union, by throwing the dart at the interval and seeing which of the sets it landed in. Either it landed in one of the sets, or else it landed in the complement, and since the sum of the probability of all the possibilities has to equal one, the measure of the complement of the disjoint union must equal 1 minus the sum of the measures of the disjoint sets. This is countable additivity. The probability of landing in the complement is 1 minus the probability of landing in the set.

Despite that, I just wrote a bogus argument! I believe it is easy, but I made a mistake just now.128.84.241.136 (talk) 00:05, 8 January 2008 (UTC)

The reason that the previous argument was bogus is because the probability axioms must properly deal with cases where there are an infinite number of events, each with nonzero probability. To deal with that, you need to include some version of this: if a sequence of positive events has probabilities whose sum is less than epsilon, the disjoint union of these events are rare.

The reason I am going to lengths here is that the axiom that the sum of the probabilities of infinitely many mutually exclusive events is equal to the probability of the "or" of all of them can be viewed as tantamount to the axiom of countable additivity.

A classical proof of these things assumes the compactness lemma that a countable collection of open intervals that cover [0,1] has a finite subset which covers [0,1].

The proof: assume not, then there is an x_k which is not in any of the I_r for r<k. The x_k have an accumulation point, and this point is in one of the I_s. This is a contradiction, since it implies that I_s includes infinitely many of the points x_k, in particular some with k>s, and the x_k were chosen not to be in any of the I_k.

The accumulation point sublemma can be proved by bisection: given an infinite sequence of points in [0,1], bisect the interval and choose the half which still has infinitely many points. Continue bisecting, choosing the half with infinitely many points. The limit of the bisections is an accumulation point.

Now Lebesgue's lemma: given a collection of intervals whose length adds up to less than 1, there is a point which is not contained in any of those intervals.

proof: Fatten up the intervals to open intervals by adding a length to each one which shrinks fast enough so that the sum of the lengths is still less than 1 even after fattening. The union of the open intervals is still the entire interval, the previous lemma guarantees that a finite number cover, contradiction.

From this it is possible to establish:

1. No interval can be covered with any countable collection of intervals whose length adds up to less than the length of the interval.
2. The lebesgue measure of an interval is its length.
3. The lebesgue measure of a set is well defined and unique.

None of this required uncountable choice, so there is no contradiction with a Solovay universe, in which all sets are measurable. So this is still true in a more or less objective way.

These theorems translate to a probability theorem: The probability of the "or" of countably infinitely many events is less than or equal to the sum of their probabilities.

Now given disjoint sets $S_{i}$ with measures (probability for landing) $p_{i}$, finite additivity guarantees that the sum of the p_i is less than or equal to the measure p of the disjoint union.

Choosing N large enough, the sum for i up to N of p_i is almost equal to the limit sum of all the p_i, leaving a small residual error e. The remaining sets S_i for i>N then together are of small measure, and therefore their disjoint union has a small measure. This proves countable additivity.

The thing is, the proof does need to use some nonconstructive assumptions, but they seem to me to be essential to probability. If you don't assume countable additivity, it is hard to see how to prove things as trivial as that a sequence of coin-flips has probability zero of eventually repeating itself in a cycle. This is equivalent to proving that a real number chosen binary digit by binary digit is irrational. Sorry for going on and on.128.84.241.25 (talk) 02:29, 8 January 2008 (UTC)

Well, one other way you can prove that is to define the measure "explicitly", i.e. outer measure rather than Borel measure. Also, (I think) ZF doesn't prove that Lebesgue measure is countably additive, because (I think) it is consistent that the continuum is a countable union of countable subsets.

JumpDiscont (talk) 17:27, 30 September 2009 (UTC)

"Objection to Freiling" section needs more words.

It sure would be nice to have an expanded explanation of why the argument in the second bullet in the section "Objection to Freiling ..." leads to a contradiction. Even one more sentence.

I'm sure the statement that it leads to a contradiction is true, because I trust the Wikipedia math author's, but, I sure don't see it.DeaconJohnFairfax (talk) 21:17, 16 July 2008 (UTC)

How does negation of CH show that AX fails?

The introduction says that AX is equivalent to the negation of CH. There's a section showing one direction of this: AX implies the negation of CH, shown indirectly by the contrapositive: CH implies negation of AX. The article ought to show the other direction, if only for completeness. I'm having trouble seeing this on my own. Perhaps this is because I'm trying to show that the negation of one of the axioms, which amounts to the existence of hypothesized peculiar set or function, implies the other axiom, which says something universal about all sets or functions. In other words, I don't see how to jump from one bad object to an assertion about a huge bunch of objects. I'd be really interested to see this. DRLB (talk) 17:07, 25 June 2009 (UTC)

Here's a hint: First show that not AX implies that there is a total order on the reals where each element has countably many predecessors; then show that this implies the continuum hypothesis. (The former part requires a cardinality argument, the latter part requires the Axiom of Choice.)Ben Standeven (talk) 22:06, 15 July 2009 (UTC)

Hey DRLB, it's been up there for a while, I'm sure you've seen it by now. It's now been more generalised. Note that it is not uncommon in mathematics that the existence of one thing can open up the gateway to the existence of loads of things (typically the machinery behind this is Zorn's lemma). —drusus null 00:28, 10 January 2011 (UTC)

Notation

"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)."

This is not well-defined IMO. As far as the set A goes, ok. But, even if one is able to figure out that x and y are elements of the unit interval, "x is not in f(y)" is fuzzy. Standard notation implies that that f(y) is one number in the range of the function (otherwise f wouldn't even be a function). I guess we are talking pre-images here, i.e. x is not in {z: f(z) = y}. —Preceding unsigned comment added by YohanN7 (talk • contribs) 23:11, 1 September 2009 (UTC)

Hmm... Apparantly it can't be pre-images either because later it says that f(x) is a set of Lebesque measure zero ruling out f(x) = 0 which seems to fill the bill for membership in the set A. —Preceding unsigned comment added by YohanN7 (talk • contribs) 23:21, 1 September 2009 (UTC)

Aha, now I see it! f(x) is not an element of some countable subset B of [0,1]. It is the countable subset B itself. I blame my blunder on too little sleep the past few days.

Example

How about adding an example to the first section:

Let x = 1/2 and let y = π/4. Let B be the subset of A for which f(x) = {1/2, 1/4, 1/8, ...} and for which f(y) = {1/2 + π/10, 1/4 + π/10, 1/8 + π/10, ...}. Then x is not an element of f(y) because all elements of f(y) are irrational and x is not. Likewise, y is not an element of f(x) because all elements of f(x) are not irrational while y is. Thus for the subset B of A the statement of AX is provably true.

This decidedly would have made it immediately clear to me what AX says. [I was the one complaining about the notation above.]

A second example:

The statement "For every f in A, there exist x and y such that x is not in f(y)" is simply true. This is because f(y) is by definition countable and can't possibly contain the uncountably many real numbers x in [0,1]. The problem arises when we in addition require that y is not in f(x) for the same x and y.

YohanN7 (talk) 01:30, 2 September 2009 (UTC)

Connection with Solovay's forcing

There are a couple of questionable things here. First is that given an arbitrary sequence $x:\omega \to [0,1]\,$, then for any subset $S\subseteq [0,1]\,$, there is no guarantee that ${\frac {|\{i<n:x_{i}\in S\}|}{n}}\,$ will converge (in fact given an $S\,$, one can find continuum many sequences where this won't converge). Second is that, even given a sequence $x:\omega \to [0,1]\,$ for which $\mu _{x}(S):=\operatorname {lim} _{n}|\{i<n:x_{i}\in S\}|/n\,$ exists for all $S\subseteq [0,1]\,$, there is no guarantee that this defines a countably additive measure, let alone translation invariant. I actually agree with the intuition that this should work, but in keeping with what is the case, one can only at best say "it seems likely that this sets up a well-defined, countably additive, rotation-invariant… probability measure". —drusus null 01:02, 10 January 2011 (UTC) — Preceding unsigned comment added by Drusus 0 (talk • contribs)

Text by Hamkins

There is an interesting recent text by Hamkins dealing with this problem. Is it worth including it? Tkuvho (talk) 13:05, 12 January 2014 (UTC)

Simpler proof of Part (ii)

I will edit it in if there are no objections.

Assume that $2^{\kappa }\neq \kappa ^{+}$. Then $2^{\kappa }>\kappa ^{+}$. Let $A$ be a subset of $2^{\kappa }$ such that $|A|=\kappa ^{+}$. There are at most $\kappa ^{+}\cdot \kappa =\kappa ^{+}$ elements $m$ of $2^{\kappa }$ such $\exists y\in A.m\in f(y)$. Let $x$ be an element of $2^{\kappa }$ such that this is not true. Likewise, there are only $\kappa$ elements $n$ of $A$ such that $n\in f(x)$. Let $y$ be an element of $A$ such that this is not true. Therefore $x\notin f(y)$ and $y\notin f(x)$. Therefore Freiling's axiom is true.

(Credit goes to Eric Wofsey (as part of another argument).)

TheKing44 (talk) 21:05, 17 November 2017 (UTC)

Earlier work by Michiel van Lambalgen?

I heard about Freiling's axiom in the PhD thesis of the Dutch logician Michiel van Lambalgen, which was published a year or two before Freijling's paper. Looks like several brilliant people had the same idea about the same time. https://www.illc.uva.nl/Research/Publications/Dissertations/HDS-08-Michiel-van-Lambalgen.preamble.pdf Richard Gill (talk) 01:35, 20 March 2021 (UTC)