Combinatorics question with infinite sets I have made a claim that I now am trying to prove. The claim is:
if $f: S \times S \to P(S) $ is an injective function mapping pairs to subsets then there exists a pair $(a,b)$ with the property that $f(a,b) = s$ and $c \in s$ with $c \neq a$ and $c \neq b$.
I'm quite sure this claim is true. My idea is to prove it using the pigeon hole principle. Count the domain, $D = |S|^2$ and the range of sets that only are made up of pairs, $R = {|S| \choose 1} + {|S| \choose 2} = |S|+{|S| \choose 2}$. Then for $|S|>1$ it is true that $D > R$. 
But this proof only works for finite $S$ because for infinite $S$, $|S|^2 = |S|$ and $R > D$. How to prove the case $S$ infinite?
 A: If $S$ is infinite it simply need not be true. For example, let $S=\Bbb Z^+$, and let
$$f\big(\langle m,n\rangle\big)=\{m,2^m3^n\}$$
for all $\langle m,n\rangle\in\Bbb Z^+\times\Bbb Z^+$. The map $\langle m,n\rangle\mapsto 2^m3^n$ is injective, so $f$ is injective, but $m\in f\big(\langle m,n\rangle\big)$ for all $\langle m,n\rangle\in\Bbb Z^+\times\Bbb Z^+$.
Added: It occurs to me that I may have misunderstood: I took the requirement to be that there is a pair $\langle a,b\rangle$ such that no $c\in f\big(\langle a,b\rangle\big)$ is either $a$ or $b$. If, however, you simply meant that there is some pair $\langle a,b\rangle$ such that $f\big(\langle a,b\rangle\big)$ contains at least one element other than $a$ and $b$, the conjecture is true for infinite as well as for finite sets. 
To see this, suppose that $f\big(\langle a,b\rangle\big)\subseteq\{a,b\}$ for each $\langle a,b\rangle\in S\times S$. Fix distinct $a,b,c,d\in S$. The map $f$ must take the four ordered pairs $\langle a,a\rangle,\langle a,b\rangle,\langle b,a\rangle$, and $\langle b,b\rangle$ to subsets of $\{a,b\}$, and there are exactly four such subsets, $\varnothing,\{a\},\{b\}$, and $\{a,b\}$. Similarly, $f$ must take the four ordered pairs $\langle c,c\rangle,\langle c,d\rangle,\langle d,c\rangle$, and $\langle d,d\rangle$ to subsets of $\{c,d\}$, and there are exactly four such subsets, $\varnothing,\{c\},\{d\}$, and $\{c,d\}$. But that means that eight different ordered pairs must be sent to seven different sets, since $\varnothing$ is a subset of both $\{a,b\}$ and $\{c,d\}$. Thus, $f$ cannot be injective.
A: It's true if $S$ has at lest 3 elements $a_1,a_2$ and $a_3$.
You know that for a function $f$ not respecting you property: $f(a_i,a_i)\in \{\emptyset,\{a_i\}\}$.
Suppose that $f(a_i,a_i)=\{a_i\}$. Then $f(a_1,a_2)\in\{\emptyset,\{a_1,a_2\}\}$ and $f(a_2,a_1)\in\{\emptyset,\{a_1,a_2\}\}$
Suppose, without loss of generality, that $f(a_1,a_2)=\emptyset$ and $f(a_2,a_1)=\{a_1,a_2\}$.
Then $f(a_1,a_3)\in\{\{a_1,a_3\}\}$ and $f(a_1,a_3)\in\{\{a_1,a_3\}\}$ contradiction with $f$ injective.
Hence one of the $f(a_i,a_i)$ has to be equal to $\emptyset$. Suppose, without loss of generality, that it's $a_3$.
Then $f(a_1,a_2)\in\{\{a_1,a_2\}\}$ and $f(a_2,a_1)\in\{\{a_1,a_2\}\}$ contradiction with $f$ injective.
Hence for$|S|\geq 3$, every injective function respect your property.
A: One can use a local pigeonhole argument to prove your result.
Consider the contrapositive: suppose that $f(a,b) \subseteq \{a,b\}$ for every $a,b\in S$.
Now suppose that there are distinct elements $a,b,z \in S$.  Consider $\{f(x,y)\mid x,y \in \{a,b,z\}\}$.  Injectivity of $f$ requires this set to contain 9 elements; yet, due to the subset requirement, only 7 possible subsets of $S$ can be used: $\{a\},\{b\},\{z\},\{a,b\},\{a,z\},\{b,z\},\emptyset$.
This shows that $|S| \le 2$.  For a two element set $S$, one can indeed construct such a function, so this is tight.
Hence your result holds for all sets with at least three elements (whether finite or not).
A: Given the interpretation in my comment, you just need to look at pairs. You must add the hypothesis that $|S|>2$ (as your claim fails for the empty set and for any singleton set $S$, and as we shall see also for doubletons). Then is $\{a,b\}$ is any two-element subset of $S$, the $4$-element set $\{a,b\}\times\{a,b\}$ cannot be mapped injectively to the $3$-element set $\{\{a\},\{b\},\{a,b\}$}, so the pigeonhole principle gives you an element $x\in\{a,b\}^2$ with a different image. Any element$~c\notin\{a,b\}$ of its image $f(x)$ immediately gives you your claim, so the claim can only fail if there are no such elements, which means $f(x)\subseteq\{a,b\}$. But as we excluded the non-empty sbsets of $\{a,b\}$, this can only mean that $f(x)=\emptyset$ (and indeed for $S=\{a,b\}$ the mapping $(a,a)\mapsto\{a\}, (a,b)\mapsto\{a,b\}, (b,b)\mapsto\{b\}, (b,a)\mapsto\emptyset$ defies your claim). But there is only one empty set, so choosing a different two-element subset $D\neq\{a,b\}$ of $S$, which is possible when $|S|>2$, will provide you with $x'\in D\times D$ with $f(x')\not\subseteq D$, and now taking $c\in f(x')\setminus D$ will prove your claim.
