SafekipediaCardinality
Adapted from Wikipedia · Discoverer experience
In mathematics, cardinality is a way to describe the size of groups of things, called sets. It tells us how many individual objects are in a set, and this idea works even for sets that have an infinite number of objects. We can understand cardinality by matching objects from one set to objects in another set, making sure each object pairs with only one other object.
Two sets have the same cardinality if we can pair their objects perfectly, with none left out. Using this idea, we can see that some infinities are bigger than others. For example, the set of even numbers and the set of rational numbers both have the same size, even though they seem different. But the set of all real numbers is larger than the set of counting numbers.
The concept of cardinality was first fully developed by the mathematician Georg Cantor in the late 19th century. His work showed that there are many different sizes of infinity and introduced tools to compare them. Today, cardinality is a basic and important idea in many areas of mathematics.
Basics
Cardinality is a property of sets that tells us their size. It means how many individual things are in a group, even if we don’t know the exact number. We can compare two groups by matching each thing in one group with a thing in the other group, making sure each thing is matched only once. If we can do this perfectly, the groups have the same cardinality.
Sets are collections of objects, like numbers or fruits. For example, a set might contain the numbers 1, 2, and 3. Functions help us match items from one set to another. If every item in the second set is matched exactly once, and no item is left out, the function is a perfect match, showing the sets have the same size.
| not surjective | surjective | |
|---|---|---|
| not injective | general function | surjective only |
| injective | injective only | bijective |
Comparing sets
Two sets have the "same size" if their objects can be paired one-to-one. This means each object in one set can be matched with a unique object in the other set, with no objects left unpaired. This pairing shows that both sets contain the same number of objects.
A fundamental idea in understanding set sizes is that this one-to-one pairing creates an equivalence relation. This relation has three key properties: reflexivity (every set has the same size as itself), symmetry (if set A has the same size as set B, then B has the same size as A), and transitivity (if A and B have the same size, and B and C have the same size, then A and C also have the same size). These properties help organize sets into groups where each group represents a possible size.
| Exponentiation | Inequality and Monotonicity | Identity elements | Absorption laws (for infinite A,B) |
|---|---|---|---|
| ( | A | | B | ) | C | = | A | | B × C | {\displaystyle {\big (}\vert A\vert ^{\vert B\vert }{\big )}^{\vert C\vert }=\vert A\vert ^{\vert B\times C\vert }} | | A | ≤ | B | {\displaystyle \vert A\vert \leq \vert B\vert } implies | A | + | C | ≤ | B | + | C | {\displaystyle \vert A\vert +\vert C\vert \leq \vert B\vert +\vert C\vert } | | A | + 0 = | A | {\displaystyle \vert A\vert +{\mathbf {0}}=\vert A\vert } | | A | + | B | = max ( | A | , | B | ) {\displaystyle \vert A\vert +\vert B\vert =\operatorname {max} (\vert A\vert ,\vert B\vert )} |
| | A | | B | + | C | = | A | | B | ⋅ | A | | C | {\displaystyle \vert A\vert ^{\vert B\vert +\vert C\vert }=\vert A\vert ^{\vert B\vert }\cdot \vert A\vert ^{\vert C\vert }} | | A | ≤ | B | {\displaystyle \vert A\vert \leq \vert B\vert } implies | A | ⋅ | C | ≤ | B | ⋅ | C | {\displaystyle \vert A\vert \cdot \vert C\vert \leq \vert B\vert \cdot \vert C\vert } | | A | ⋅ 1 = | A | {\displaystyle \vert A\vert \cdot {\mathbf {1}}=\vert A\vert } | | A | ⋅ | B | = max ( | A | , | B | ) {\displaystyle \vert A\vert \cdot \vert B\vert =\operatorname {max} (\vert A\vert ,\vert B\vert )} |
| | A × B | | C | = | A | | C | ⋅ | B | | C | {\displaystyle \vert A\times B\vert ^{\vert C\vert }=\vert A\vert ^{\vert C\vert }\cdot \vert B\vert ^{\vert C\vert }} | | A | ≤ | B | {\displaystyle \vert A\vert \leq \vert B\vert } implies | A | | C | ≤ | B | | C | {\displaystyle \vert A\vert ^{\vert C\vert }\leq \vert B\vert ^{\vert C\vert }} | | A | 1 = | A | {\displaystyle \vert A\vert ^{\mathbf {1}}=\vert A\vert } | 0 ⋅ | A | = 0 {\displaystyle {\mathbf {0}}\cdot \vert A\vert ={\mathbf {0}}} (annihilator) |
| | A | 0 = 1 {\displaystyle \vert A\vert ^{\mathbf {0}}={\mathbf {1}}} | | A | ≤ | B | {\displaystyle \vert A\vert \leq \vert B\vert } and 0 implies | C | | A | ≤ | C | | B | {\displaystyle \vert C\vert ^{\vert A\vert }\leq \vert C\vert ^{\vert B\vert }} | 1 | A | = 1 {\displaystyle {\mathbf {1}}^{\vert A\vert }={\mathbf {1}}} |
Skolem's paradox
Main article: Skolem's paradox
In math, a model is a way to understand ideas using objects and rules. Skolem's paradox is a puzzle about how many objects are in a model. It shows that even though some models seem to have a lot of objects, they can also be made with just a few. This happens because what seems like a lot can depend on how you look at it.
Skolem explained this in 1922 by showing that how we count objects can change depending on the model we use. This idea was new and surprising, but it helped mathematicians understand more about how models work.
History
Ancient history
In ancient times, around the 6th century BCE, Greek thinkers like Anaximander talked about sets with infinite objects, though they often saw this as confusing. Aristotle made a difference between two types of infinity, and Greek mathematicians used the word “number” only for definite, finite amounts of things. This idea was later shown in Euclid’s work Elements, where it says “The whole is greater than the part.”
Around the 4th century BCE, mathematicians in Jaina discussed different sizes of infinity. They described three kinds: countable (finite numbers), uncountable, and infinite in various ways.
One early example of matching items one-to-one comes from Aristotle’s work. He described a puzzle with wheels of different sizes moving together, showing how each point on the smaller wheel matches a point on the larger wheel.
Pre-Cantorian set theory
Portrait of Galileo Galilei (left). Portrait of Bernard Bolzano (right).
Galileo Galilei pointed out a puzzle about infinite numbers. He noticed that perfect squares (like 1, 4, 9) have square roots (1, 2, 3), and there are just as many perfect squares as there are square roots. But not every number is a perfect square, which seemed strange. Later, David Hume said that two groups are equal if each item in one group matches an item in the other group.
Bernard Bolzano tried to bring order to ideas about infinity. He talked about matching points between different sizes of intervals, like from 0 to 5 and from 0 to 12, but still didn’t say these intervals were the same size.
Early set theory
Georg Cantor
Georg Cantor started the real study of sizes of infinite sets in the 1870s and 1880s. He showed that the set of real numbers is larger than the set of natural numbers. Later, he used a method called the diagonal argument to prove this. Cantor also introduced ideas about cardinal numbers and ordinal numbers, and he created rules for adding, multiplying, and raising cardinal numbers to powers. He also asked a big question called the Continuum Hypothesis, which was left unanswered.
Other contributors
Richard Dedekind also worked on set theory and helped support Cantor’s ideas. Giuseppe Peano showed that certain shapes can fill space completely, which helped show that some infinite sets can have the same size. Gottlob Frege tried to build numbers using logic, but his work had problems that were later fixed by Bertrand Russell and Alfred Whitehead.
At a big meeting of mathematicians in 1900, David Hilbert made a list of important problems, and he put Cantor’s question about the Continuum Hypothesis as the very first problem. This helped bring more attention to Cantor’s work.
Axiomatic set theory
In 1908, Ernst Zermelo created a system of rules for set theory to avoid problems with earlier ideas. Later, this system was improved by Abraham Fraenkel and Thoralf Skolem. During the early 1900s, mathematicians like Felix Hausdorff studied very large numbers, now called large cardinals.
In 1940, Kurt Gödel showed that a certain big question about numbers could not be answered using Zermelo-Fraenkel set theory. In 1963, Paul Cohen showed that this question could also not be proven using those rules, using a new method called forcing.
Images
Related articles
This article is a child-friendly adaptation of the Wikipedia article on Cardinality, available under CC BY-SA 4.0.
Images from Wikimedia Commons. Tap any image to view credits and license.