Given two sets $S, T$ and a relation defined by a set of pairs $R \subset S \times T$, such that: $$ \exists \, s_1, s_2 \in S : s_1 \neq s_2 \\ \exists \, t_1, t_2 \in T : t_1 \neq t_2 \\ \forall s \in S \, \exists \, t \in T : (s,t) \in R \\ \forall t \in T \, \exists \, s \in S : (s,t) \not \in R $$ Show that $$ \exists \, s, s' \in S : \exists\, t, t' \in T : \left[ (s,t) \in R \right] \wedge \left[ (s', t') \in R \right] \wedge \left[ (s,t') \not \in R \right] \wedge \left[ (s',t) \not \in R \right] $$ For $S$ and $T$ finite, I can prove this by induction on the numbers of elements in $S$ and $T$. This is a statement of an old Putnam problem saying that if at a party every boy dances with at least one girl and no girl dances with every boy, then there exists a pair of couples such that $b$ danced with $g$ and $b'$ danced with $g'$ but $b$ did not dance with $g'$ nor $b'$ with $g$.
Equivalent to the proof by induction, I think, is a proof by considering a minimal example of $S$ and $T$ which violates the proposition, and removing one member of $S$ or $T$, and looking at the properties of the remaining set, to show that then purported minimal violating set actually obeys the proposition. (For example, a step in this proof would be to say that the reduced sets cannot have a "qualified" duo of pairs since that would be qualified in the full sets; so either there is a universal $T$ or a no-relation $S$, and in either case adding back the removed element yields a qualified duo of pairs.)
My question concerns proving the proposition when $S$ and $T$ may be infinite, and in particular, may be uncountably infinite. It looks to me as if the same sort of proof requires at least the axiom of choice, but maybe it can be done with just transfinite induction.
I'm shaky as to when a step in my proof implicitly assumes AC, so any help would be appreciated.
As I commented, this is false for infinite sets. To understand why, I think it is simplest to forget about elements of $T$ that are not in the range of $R$ and then to forget about the distinction between different elements of $S$ that have the same image under $R$ in $T$. When you have done that, you can also forget about induction. In more detail:
The given assumptions on $S$, $T$ and $R$ imply that the range of $R$ has at least two elements. In fact, instead of the first two assumptions, you just need that $S \not= \emptyset$: given $s_1 \in S$, there is $t_1 \in T$ with $(s_1, t_1) \in R$, then $s_2 \in S$ with $(s_2, t_1) \not\in R$ and then $t_2 \in T$ with $(s_2, t_2) \in R$, but then $t_1$ and $t_2$ are both in the range of $R$ and $t_1 \not= t_2$. So we can assume $T$ is the range of $R$ (because that preserves the assumptions on $S$, $T$ and $R$ and results in an equivalent conclusion).
Now let $U$ comprise all subsets $A$ of $T$ such that $A = A_s = \{t \mathrel {|} (s, t) \in R\}$ for some $s \in S$. We need to find $A, A' \in U$ such that $A \mathop{\backslash} A' \not= \emptyset \not= A' \mathop{\backslash} A$. But $U$ is a family of non-empty subsets of $T$ with $\bigcup U = T$, so if no such pair $A$ and $A'$ exists, then $U$ must be a chain. But if $U$ is a chain of subsets of $T$ whose union is $T$ and $T$ is finite, then $T \in U$, but no $A_s = T$, a contradiction. If $T$ is infinite, it certainly can be written as the union of a chain of proper subsets and you get a counter-example, e.g., by taking $S= \mathbb{N}$ and $A_n = \{ i \mathrel{|} i \le n\}$.