Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Sperners theorem is about antichains (subsets of powerset of n elements for which no pair of elements contains the other) for example if we choose from

row 5: {a,b,c,d}
row 4: {a,b,c} {a,b,d} {a,c,d} {b,c,d}
row 3: {a,b} {a,c} {a,d} {b,c} {b,d} {c,d} <-- middle row is biggest
row 2: {a} {b} {c} {d}
row 1: {}

we find {a,b,c} {a,c,d} {b,d} is an antichain of size 3. It looks like the biggest antichain is the middle row {a,b} {a,c} {a,d} {b,c} {b,d} {c,d}.

To prove that is always the case take an antichain and pick all the elements from the lowest row R below the middle (flip the antichain upside down by taking the complement of every element if it's not below the middle). There must be at least |R| gaps in the above row: so push everything in the bottom row up one and it's still an antichain. Repeat until everything is in the middle row.

Any ideas where the mistake in this is?

share|cite|improve this question
You don't specify what "push up" means, so one cannot check whether this preserves the antichain condition – Marc van Leeuwen Oct 9 '12 at 17:33
@MarcvanLeeuwen, write the antichain as a disjoint union U u R in the universe X, then there is an map f : R -> X which takes makes every set one element bigger and the image f(R) is not in U. Then I claim U u f(R) is an antichain. – sperners lemma Oct 9 '12 at 18:30
@spernerslemma: the tricky part is choosing $f$ to be an injection. – Colin McQuillan Oct 9 '12 at 18:42
up vote 1 down vote accepted

If by $R$ you mean the set of element of the lowest row, then this argument can be made to work. But an argument is needed: why can $R$ be pushed around in this way? In other words, why is the "upper shadow" of $R$ least as large as $R$? (Here upper shadows are defined at for example.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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