Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge II: Almost Disjoint Sets, solved by HS-Scientist

  1. Aug 8, 2013 #1
    Written by micromass:

    The newest challenge was the following:

    This was solved by HS-Scientist. Here's his solution:

    This is a very beautiful construction. Here's yet another way of showing it.

    Definition: Let ##X## be a countable set. Let ##A,B\subseteq X##, we say that ##A## and ##B## are almost disjoint if ##|A\cap B|## is finite. An almost disjoint family is a collection of subsets of ##X##, thus ##\mathcal{A}\subseteq \mathcal{P}(X)## such that every ##A\in \mathcal{A}## is infinite and such that any two distinct elements in ##\mathcal{A}## are almost disjoint.

    First we prove a lemma:

    Lemma: Define for a set ##X##, the set ##\mathcal{P}_\text{fin}(X) = \{A\subseteq X~\vert~A~\text{is finite}\}##. If ##X## is countable, then so is ##\mathcal{P}_\text{fin}(X)##.

    So instead of finding an almost disjoint family of ##\mathbb{N}##, we might as well find such a family on ##\mathcal{P}_\text{fin}(X)##.

    To do this, take any infinite subset ##X\subseteq \mathbb{N}##. Define
    [tex] A_X = \{X\cap \{0\},~X\cap \{0,1\},~X\cap \{0,1,2\},...,X\cap \{0,1,2,...,n\},...\}[/tex]
    Then the ##A_X## are clearly an almost disjoint family.
    Furthermore, there is a bijection between ##\{X\subseteq \mathbb{N}~\vert~X~\text{is infinite}\}## and ##\mathbb{R}##, so we have found our almost disjoint family.

    Another solution that I got, was from jgens who did a very beautiful diagonal argument. It comes down to this:

    Definition: A maximal almost disjoint family ##\mathcal{A}## of ##X## is an almost disjoint family that is not properly contained in any other almost disjoint family.

    From Zorn's lemma, we can immediately get the existence of a maximal disjoint family. This almost disjoint family cannot be countable. Indeed, if it were countable, then it wouldn't be maximal. Here is a proof of this that uses a very clever diagonal argument:

    The problem with this solution is of course that we have only found an uncountable almost disjoint family. But we do not necessarily have an almost disjoint family that is in bijection with ##\mathbb{R}##.

    However, both arguments are very useful in generalizations. A natural generalization of this problem is the following:

    Definition: Let ##X## be an infinite set. Let ##A,B\subseteq X##, we say that ##A## and ##B## are almost disjoint if ##|A\cap B|<|X|##. An almost disjoint family is a collection of subsets of ##X##, thus ##\mathcal{A}\subseteq \mathcal{P}(X)## such that every ##|A| = |X|## for every ##A\in \mathcal{A}## and any two distinct elements in ##\mathcal{A}## are almost disjoint.

    Both arguments can be generalized to this situation, but they both use other hypotheses. The argument by Hs-Scientist generalizes nicely if the cardinality of ##\{A\subseteq X~\vert~|A|<|X|\}## is equal to ##|X|##. This is a very restrictive condition. But in this case we can show that there is an almost disjoint family of cardinality ##2^{|X|}##.

    The jgens argument generalizes much better since it doesn't require such a restrictive condition. On the other hand, we do not get an almost disjoint family of cardinality ##2^{|X|}##. We can only infer that there is an almost disjoint family that has cardinality strictly greater than ##|X|##.

    Finally, I would like to mention the following problem: If ##\mathcal{A}## is an almost disjoint family of ##\mathbb{N}##. If ##\mathcal{A}## is not in bijective correspondance with ##\mathbb{R}##, does ##\mathcal{A}## then fail to be maximal?

    We have seen that there is a maximal family of cardinality ##\mathbb{R}##, but that doesn't mean that they're all of this cardinality. With other words, can we extend any almost disjoint family to a maximal disjoint family of cardinality ##\mathbb{R}##?

    The answer is that this is independent of the ZFC axioms. We require a new axiom. Under the Continuum Hypothesis, the answer to this is trivially yes (since if ##\mathcal{A}## does not have size ##|\mathbb{R}|##, then it is countable).

    However, there is another axiom that is sometimes interesting. This is called Martin's axiom. This is an axiom that is studied very deeply in set theory and has many interesting consequences. Under this axiom, the answer is again yes.

    For more information, I refer to "Set Theory, an Introduction to Independence Proofs" by Kunen.

    Congratulations to HS-Scientist and jgens for their nice and elegant solutions!
     
    Last edited: Aug 8, 2013
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted



Similar Discussions: Challenge II: Almost Disjoint Sets, solved by HS-Scientist
Loading...