S and T and finite sets. U is a collection of ordered pairs (s, t) with s ∈ S and t ∈ T. There is no element s ∈ S such that all possible pairs (s, t) ∈ U. Every element t ∈ T appears in at least one element of U. Prove that we can find distinct s1, s2 ∈ S and distinct t1, t2 ∈ T such that (s1, t1), (s2, t2) ∈ U, but (s1, t2), (s2, t1) ∉ U.
Solution
Suppose that we cannot find such si, ti. We will establish a contradiction.
Take t in T. Suppose that there are n distinct s in S such that (s, t) is in U. Suppose n > 0. Then take a specific s' such that (s', t) is in U. There must be some t' such that (s', t') is not in U. Now consider whether we have (s, t') in U. If (s, t) is not in U, then (s, t') cannot be in U (or we would have found si, ti). But there are at most n-1 distinct s such that (s, t') is in U (the only candidates are the cases for which (s, t) is in U, and one of those, namely s', does not work).
Iterating, we must eventually get some x in T for which there is no s in S with (s, x) in U. Contradiction.
© John Scholes
jscholes@kalva.demon.co.uk
25 Jan 2002