SafekipediaCardinality
Adapted from Wikipedia · Adventurer 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. This idea even works for sets with 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. Today, cardinality is an 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 key idea in understanding set sizes is that this one-to-one pairing creates an equivalence relation. This relation has three important 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 some models can seem to have many objects, but they can also be made with just a few. This is because what looks like a lot can change depending on how you see it.
Skolem showed this in 1922 by proving that counting objects can change based on the model you use. This idea was new and surprising, but it helped mathematicians learn more about how models work.
History
Ancient history
In ancient times, around the 6th century BCE, Greek thinkers like Anaximander talked about groups with endless objects, but found it confusing. Aristotle separated two types of infinity, and Greek mathematicians used the word “number” only for exact, limited amounts of things. This idea appeared later in Euclid’s work Elements, which states “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 noticed a puzzle about endless numbers. He saw 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 odd. 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 organize ideas about infinity. He talked about matching points between different sizes of ranges, like from 0 to 5 and from 0 to 12, but still didn’t say these ranges were the same size.
Early set theory
Georg Cantor
Georg Cantor began the real study of the sizes of endless sets in the 1870s and 1880s. He showed that the group of real numbers is larger than the group 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 remained unanswered.
Other contributors
Richard Dedekind also worked on set theory and supported Cantor’s ideas. Giuseppe Peano showed that certain shapes can fill space completely, which helped show that some endless sets can be 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.