In combinatorics, bijective proof is a proof technique that finds a bijective function f : A → B between two finite sets A and B, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of counting its elements. Then establishing a bijection from A to some B solves the problem in the case when B is more easily countable. Another useful feature of the technique is that the nature of the bijection itself often provides powerful insights into each or both of the sets.
Read more about Bijective Proof: Other Examples
Famous quotes containing the word proof:
“A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
—Samuel Johnson (1709–1784)