Subsets and Intersections

Here is a problem (Kvant, n 5, 1970, M25):

In an n-element set X, 2n-1 subsets have been selected with the property that every three of them have a nonempty intersection. Prove that all 2n-1 of them have a nonempty intersection.

Solution

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

In an n-element set X, 2n-1 subsets have been selected with the property that every three of them have a nonempty intersection. Prove that all 2n-1 of them have a nonempty intersection.

Solution 1

First, let's denote the given set of subsets U and its complement in 2X: V = 2X - U. We combine several useful facts in the following

Lemma

A, B, ... will denote generic subsets of X.

  1. A ∈ U iff Ac ∈ V and vice versa, Ac being the complement of A.

  2. If a ∈ X and {a} ∈ U, then a ∈ A, for every A ∈ U.

  3. If A, B ∈ U then A∩B ∈ U.

Proof

The first claim follows from the observation that A∩Ac = Ø, while no two members of U may have an empty intersection. The second claim follows from the fact that the intersection of any set with {a} is either empty or {a}.

For the third statement, assume A, B ∈ U, while A∩B ∈ V. Then, by 1., (A∩B)c ∈ U, implying

A ∩ B ∩ (A∩B)c = (A∩B) ∩ (A∩B)c = Ø,

contrary to the premises of the problem.

According to 2., if there is a ∈ X such that {a} ∈ U, then a is common to all members of U such that their intersection includes {a} ≠ Ø. In this case the problem is solved.

Assume then that all 1-element subsets of X are in V. By 2., all subsets of X that lack just 1 element are in V. We shall prove that then all nonempty (proper) subsets of X are in U which is impossible, because, in particular, then there will be subsets and their complements contained in U.

Pairwise intersections of distinct subsets that lack a single element lack 2 elements. According to 3., all such subsets are in U.

If A = X - {a} and B = X - {b}, a ≠ b, then A∩B = X - {a, b}. Thus subsets that lack 2 elements also belong to U. Clearly we may continue in this manner until 1-element subsets come up. But these cannot belong simultaneously to U and to V!

Solution 2

This solution is by induction based on property 3. The intersection of any two subsets from U is nonempty and belongs to U. Order anyhow all members of U: A1, A2, ..., A2n-1. Now,

A1∩A2∩...∩Ak∩Ak+1 = (A1∩A2∩...∩Ak)∩Ak+1

Thus if we assume A1∩A2∩...∩Ak nonempty and belonging to U the same will hold for A1∩A2∩...∩Ak+1 and thus for the intersection of all members of U.


Related material
Read more...

Set Theory

  • Addition of Sets
  • Cantor-Bernstein-Schroeder theorem.
  • de Morgan's Laws
  • Equivalence Relations
  • Mutiplication of Sets
  • Nested Subsets
  • Russell's Paradox
  • The set of all subsets of a given set is bigger than the set itself
  • |Contact| |Front page| |Contents| |Algebra| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     62036516

    Search by google: