Math 2.0

Combinatorics Theorem

Bijection principle

Builds on Cardinality of a finite set

Statement

Let AA and BB be finite sets. If there is a bijection f:A→Bf : A \to B, then ∣A∣=∣B∣|A| = |B|. Conversely, if ∣A∣=∣B∣|A| = |B|, then there is a bijection from AA to BB.

Remarks

A bijective proof shows that two sets have the same size by a bijection between them. The proof of the symmetry of binomial coefficients is a standard example. It uses the map S↦X∖SS \mapsto X \setminus S on the subsets of a finite set XX. Dyck words and binary trees are both counted by Catalan numbers, and a bijection explains this.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Cardinality of a finite set, definition, no evidence levelCardinality of a fini…definitionBijection principle, statement, no evidence levelBijection principlestatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Cardinality of a finite set definition
  2. Bijection principle statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Bijective_proof, lead section
About this page
Tag0GV2573FP4
URIm2://0GV2573FP4
Kindstatement, theorem
WritingW0 stub
MSC05A19
StatusThis copy of the site has no build data. Run m2 status 0GV2573FP4.
UsesCardinality of a finite set

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.