In the Paxos consensus protocol, a fact that follows from its construction is "any two majority sets of acceptors will have at least one acceptor in common". This observation can be extended to any N majority sets of acceptors having either at least one acceptor in common, or acceptors that are distinctly present in each N-1 sets of acceptors.
"Therefore if two proposals are agreed to by a majority, there must be at least one acceptor that agreed to both. This means that when another proposal, for example, is made, a third majority is guaranteed to include either the acceptor that saw both previous proposals or two acceptors that saw one each."
I have an intuitive understanding of why this is so (should be a simple pigeonhole principle application), but I am having difficulty proving this formally. I would like a formal proof.