|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander BogomolnyI'll give two proofs of this fact.

(In the following |X| designates the number of elements in a finite set X, while 2^{X} denotes the set of all subsets of set X.)

Select an arbitrary element x from a set **A** with n elements (*n-set*) and consider two families of subsets. The family **N** consists of all subsets of **A** that do not contain x; the family **Y** comprises the remaining subsets (each one of these contains x.) There are exactly 2^{n-1} subsets in both **N** and **Y**.

We start with a family **B** that contains more than a half of all subsets of **A**. By the Pigeonhole principle, one of the **N** or **Y** families contains at least a half of the subsets from **B**. If it's **N**, we may continue directly. If it's **Y**, we first note that all the subsets involved contain the chosen number x. If we drop it from all the subsets we arrive at exactly the same situation as in the first case. Let's summarize.

We are given a set **A _{new}** (this is the former

**A**with the element x removed), for which set

**N**(or

**Y**with x removed) serves as the set of all subsets. Now, we know that

**B**| > |2

^{A}|/2 = |

**A**|.

_{new}**B**| = |

**N**∩

**B**| + |

**Y**

**B**|.

**N**

**B**| > |

**A**|/2

_{new}**Y**

**B**| > |

**A**|/2.

_{new}Depending on which of the inequalities holds, let **B _{new}** denote either

**N**∩

**B**or

**Y**

**B**with x removed. In either case,

**B**| > |2

_{new}^{Anew}|/2.

**A**now contains 1 element less than before.

We may now proceed either *by induction* (all it takes is to check some minimal set of a few elements) or by just regressing backwards to a set with a small number of elements, which amounts to the same thing. So let's consider a set with a small number of elements. How many should we take? Let's take n = 1. The set of all subsets of {1} consists of two sets - the empty set {} and {1}. To contain more than half of all subsets **B** is bound to contain both of them. In which case, it clearly contains two sets of which one {} is a subset of another {1}.

The following proof is by William A McWorter Jr..

Let again x be an element of the n-set **A** (the result is vacuously true when
n=0). For each of the 2^{n-1} subsets A of **A** not containing x, form
the pair {A, A∪{x}}. These pairs form a partition of the subsets of
**A**. Now, given more than half of its subsets, some two must belong to the same pair,
and so have the property that one is a subset of the other.

## Remark

The result obtained with the help of the Pigeonhole principle can be strengthened considerably: in order to assure that among selected subsets one contains another, one does not need to select more than half the subsets. Fewer will suffice.

There is a very related problem:

Show that if more than half of the subsets of an n-element set are
selected, there exists a pair of them such that one is not a subset of another provided
none of the selected sets is empty.
Combine all subsets into pairs {X,X ## ExampleOne can't dispose of the prohibition to select an empty set. Indeed, the 2-set ## RemarkAlternatively one may preclude selecting |Contact| |Front page| |Contents| |Up| Copyright © 1996-2018 Alexander Bogomolny67831453 |