Pigeonhole Principle - Infinite Sets

Infinite Sets

The pigeonhole principle can be extended to infinite sets by phrasing it in terms of cardinal numbers: if the cardinality of set A is greater than the cardinality of set B, then there is no injection from A to B. However in this form the principle is tautological, since the meaning of the statement that the cardinality of set A is greater than the cardinality of set B is exactly that there is no injective map from A to B. What makes the situation of finite sets interesting is that adding at least one element to a set is sufficient to ensure that the cardinality increases.

Read more about this topic:  Pigeonhole Principle

Famous quotes containing the words infinite and/or sets:

    “It has no future but itself—
    Its infinite contain
    Its past—enlightened to perceive
    New periods of pain.”
    —Emily Dickinson (1830–1886)

    “To the extent to which genius can be conjoined with a merely good human being, Haydn possessed genius. He never exceeds the limits that morality sets for the intellect; he only composes music which has “no past.””
    —Friedrich Nietzsche (1844–1900)