Math 2.0

statement theorem

Infinite pigeonhole principle

Statement

Let AA be an infinite set, let BB be a finite set, and let f:A→Bf : A \to B be a function. Then there is an element b∈Bb \in B such that the fibre f−1(b)f^{-1}(b) is infinite.

Remarks

The proof is short. If each of the finitely many fibres were finite, then AA, their union, would be finite. Example: in any infinite sequence of integers, infinitely many terms have the same remainder modulo 1010. The statement is the starting point of the infinite form of Ramsey's theorem.

Explanations

L1 human

If you put infinitely many objects into finitely many boxes, at least one box gets infinitely many of them. For example, colour each natural number red or blue. Then one of the two colours is used infinitely often.

What this node 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 node is. They do not measure its truth.

What this needs

To read this node, read these 3 nodes in this order. The foundations come first, and the list ends with this node.

Cardinality of a finite set, definition, no evidence levelCardinality of a fini…definitionPigeonhole principle, statement, no evidence levelPigeonhole principlestatementInfinite pigeonhole principle, statement, no evidence levelInfinite pigeonhole p…statement
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Cardinality of a finite set definition
  2. Pigeonhole principle statement
  3. Infinite pigeonhole principle statement

Sources

  1. Web https://en.wikipedia.org/wiki/Pigeonhole_principle, Infinite sets

What links here

No node links to this node yet.