# What's wrong with this proof of Sperners theorem?

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?

-
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

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 http://mathoverflow.net/questions/10679/sperners-theorem-and-pushing-shadows-around/10689#10689 for example.)