8
$\begingroup$

Freiling's Axiom of Symmetry says that for any function $f:[0,1]\to \mathcal{P}([0,1])$ such that for every $x\in [0,1]$ we have $|f(x)|=\aleph_0$, then there exist $y,z\in [0,1]$ such that $z\notin f(y)$ and $y\notin f(z)$. This is equivalent to the negation of the continuum hypothesis (see this wiki page).

My question is whether one can produce an uncountable set $A$, using the axioms in ZFC, so that if we plug $A$ in place of $[0,1]$, it satisfies Freiling's Axiom.

$\endgroup$
  • 1
    $\begingroup$ I just wanted to thank all three people who answered this question! Great answers all. $\endgroup$ – Pace Nielsen Mar 26 '15 at 1:01
6
$\begingroup$

Theorem. The following are equivalent for a set $A$

  1. $A$ has the property of Freiling's axiom. That is, if $a\mapsto X_a$ is any map from $A$ to the countable subsets of $A$, then there are $a$ and $b$ with $a\notin X_b$ and $b\notin X_a$.

  2. $A$ has size at least $\aleph_2$.

Proof. ($1\to 2$) We prove the contrapositive. If $A$ had size less than $\aleph_2$, then we can enumerate the elements of $A$ as $A=\{\ a_\alpha\mid \alpha<\omega_1\ \}$. For any $a\in A$, let $\alpha$ be least with $a=a_\alpha$, and map $a\mapsto X_a=\{a_\beta\mid\beta<\alpha\}$. For any $a\neq b$, one of them appears first before the other, and so either $a\in X_b$ or $b\in X_a$, contrary to statement $1$.

($2\to 1$) If $A$ has size at least $\aleph_2$, then suppose we have any function $a\mapsto X_a$ where $X_a$ is a countable subset of $A$. By applying the function $\omega_1$ many times, we may find a subset $Y\subset A$ of size $\omega_1$, which is closed under the map, in the sense that $a\in Y\to X_a\subset Y$. Now pick any $b\notin Y$. Since $X_b$ is countable, there is some $a\in Y$ with $a\notin X_b$, and since $b\notin Y$, it follows that $b\notin X_a$, and so we have achieved Freiling's property. QED

$\endgroup$
  • 1
    $\begingroup$ I view this theorem as the essential content of Freiling's observation that the axiom of symmetry is equivalent to $\neg\text{CH}$; the argument is essentially the same. $\endgroup$ – Joel David Hamkins Mar 25 '15 at 22:08
4
$\begingroup$

Take any set $A$ with $|A|>\aleph_1$ (e.g. $A=\omega_2$). Then it satisfies Freiling´s Axiom. For this let $f:A \to \mathcal{P}(A)$ with $|f(x)|=\aleph_0$ for $x\in A$. Fix a subset $B \subseteq A$ with $|B|=\aleph_1$. Note that $C:=\bigcup_{x \in B} f(x)$ has size $\aleph_1$ so there must be an $a \in A \setminus C$. Now since $f(a)$ is countable there must be a $b \in B \setminus f(a)$. But then $a \notin f(b)$ and $b \notin f(a)$.

$\endgroup$
  • $\begingroup$ Aha, we had the same idea! $\endgroup$ – Joel David Hamkins Mar 25 '15 at 21:40
  • $\begingroup$ @JoelDavidHamkins, yes! but I didn´t mention anything about the other direction. $\endgroup$ – Ramiro de la Vega Mar 25 '15 at 21:45
4
$\begingroup$

For any function $f:X\to P(X)$, a set $F\subseteq X$ is called free (or $f$-free) if $y\notin f(z)$ and $z\notin f(y)$ for all distinct $y,z$ in $F$.

Hajnal's "free set theorem" says the following: If $f:\lambda \to [\lambda]^{<\mu}$ for some $\mu<\lambda$, then we cannot only find a 2-element free set but even a free set of size $\lambda$. (Chapter 26 in the wonderful book by Komjáth and Totik is called "Set mappings". Hajnal's theorem is problem 8. For regular $\lambda$ this was proved earlier by Sierpiński.)

If you plug in $\lambda\ge\aleph_2$, $\mu=\aleph_1$, then you get: If all values of $f$ are at most countable, then there is free set of size $\lambda$.

$\endgroup$
  • $\begingroup$ Doesn't Hajnal's theorem only hold for set mappings (i.e. functions with $x\notin f(x)$), not arbitrary functions? $\endgroup$ – Pace Nielsen Mar 26 '15 at 2:03
  • 2
    $\begingroup$ If you demand that $x\notin f(x)$ for all $x$, then the free set $F$ will have the property $y\notin f(z)$ for all $y,z\in F$. If you do not demand this, you get $y\notin f(z)$ only for all distinct $y,z\in F$. $\endgroup$ – Goldstern Mar 26 '15 at 6:13
  • $\begingroup$ Is that modified version proven in the book by Komjáth and Totik, or is there another reference for the modified result? $\endgroup$ – Pace Nielsen Mar 26 '15 at 14:12
  • 2
    $\begingroup$ To prove "my" version from "your" version, just apply "your" version to the function $g(x):= f(x) \setminus \{x\}$. $\endgroup$ – Goldstern Mar 26 '15 at 21:36
  • $\begingroup$ Thanks for the nice words... My recollection is that the regular case was done by Sophie Piccard FM 1937 and independently and unpublished by Dezso Lazar as reported in Erdos's "Some remarks in set theory". $\endgroup$ – Péter Komjáth Mar 27 '15 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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