Subsets and Intersections

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

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

Solution

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

Copyright © 1996-2018 Alexander Bogomolny

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

Solution 1

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

Lemma

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

Proof

The first claim follows from the observation that A∩A^c = Ø, 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: A₁, A₂, ..., A_2^n-1. Now,

A₁∩A₂∩...∩A_k∩A_k+1 = (A₁∩A₂∩...∩A_k)∩A_k+1

Thus if we assume A₁∩A₂∩...∩A_k nonempty and belonging to U the same will hold for A₁∩A₂∩...∩A_k+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|

Copyright © 1996-2018 Alexander Bogomolny