Cardinality of sets¶

Level: 101 → 201 · for anyone who has counted the rows in a table

One line: |A| is the size of a set, defined by matching rather than counting — which changes nothing for a finite set, lets ℕ be the same size as its even numbers, proves that some functions have no program, and is the one word behind index size, foreign-key ranges, UML multiplicities and "high-cardinality" telemetry.

The bars¶

|C| = 4 does not mean an absolute value. Inside the bars is a set, and the bars ask how many members it has: its cardinality. The notation is reused because both are a kind of size, and the thing inside tells you which. |−4| is 4; |{−4}| is 1; |{1, 1, 1}| is 1, because a set does not count repeats. Section 2 of the program prints all four.

For a finite set that is the whole story, and "cardinality" is a long word for "how many elements". The word earns its keep the moment counting stops working.

What the program prints¶

Verified output of cardinality.py — regenerated by tools/run_examples.py, never hand-typed.

1. COUNTING AND MATCHING AGREE ON FINITE SETS
   C = ['bishop', 'knight', 'pawn', 'rook']
   D = ['east', 'north', 'south', 'west']
   |C| = 4, |D| = 4
     bishop  <-> east
     knight  <-> north
     pawn    <-> south
     rook    <-> west
   one-to-one, nothing left over:  True
   can C match ['east', 'north', 'south']?  every pairing leaves one of C over,
   because |C| = 4 and |E| = 3.

2. THE BARS MEAN SIZE, AND SIZE DEPENDS ON THE KIND OF THING
   |-4|          = 4           absolute value of a number
   |{-4}|        = 1           cardinality of a one-member set
   |{-4, 4}|     = 2           cardinality of a two-member set
   |{1, 1, 1}|   = 1           a set does not count repeats

3. THE PRODUCT RULE  |A x B| = |A| . |B|,  READ AS TYPES
   |A| = 4, |B| = 7, |A x B| = 28 = 4 x 7
   A type is a set of values, so it has a cardinality, and the type
   constructors follow the set rules. Build each one and count it:
     type             built as                     count   rule
     void             no values                        0   0
     unit / None      one value                        1   1
     bool             {False, True}                    2   2
     u2               {0, 1, 2, 3}                     4   2^2
     (bool, u2)       every pair                       8   2 x 4    product type
     bool | u2        tagged L or R                    6   2 + 4    sum type
     Optional[u2]     u2 or None                       5   4 + 1    sum with unit
     u2 -> bool       every truth table               16   2^4      function type
   Sizes a programmer already knows come from the same rules:
     uint8                         256   2^8
     (uint8, uint8)             65,536   256 x 256, the same count as uint16 = 65,536
     (bool, uint8)                 512   2 x 256
     bool | uint8                  258   2 + 256
     Optional[uint8]               257   1 + 256: one more than uint8, and a
                                        uint8 cannot hold it, which is why -1
                                        as 'no value' is a bug waiting to happen
     uint8 -> bool           1.158e+77   2^256
   The algebra of sets is the algebra of types. Distributivity, checked:
     |(bool | u2) x bool| = 12 = |bool x bool| + |u2 x bool| = 4 + 8 = 12
   And it is why an exhaustive match on (bool, u2) needs 8 arms, a
   match on bool | u2 needs 6, and a fuzzer that tries every
   (uint8, uint8) input has exactly 65,536 cases to run.

4. CARDINALITY OF A COLUMN
   a table of 12 rows:   name   country   role
     COUNT(DISTINCT name)     = 12   = |{ann, bob, cy, dee, eli, fay, ...}|
     COUNT(DISTINCT country)  =  4   = |{DE, FR, PL, US}|
     COUNT(DISTINCT role)     =  2   = |{admin, user}|
   A query planner keeps these numbers. An index on `name` narrows
   a lookup to 1 row; an index on `role` narrows it to 10. The
   cardinality of the column is what decides whether the index is
   worth reading.
   an index on (country, role) can hold at most |country| x |role|
   = 4 x 2 = 8 distinct keys; this table uses 5 of them.
   The product rule again: the key space of a compound index is a
   Cartesian product, and its cardinality is the product of the parts.

5. CARDINALITY OF A RELATIONSHIP: HOW MANY ROWS ON EACH SIDE
   KNA1 (customers)  = C001, C002, C003, C004
   VBRK (invoices)   = INV1->C001, INV2->C001, INV3->C002, INV4->C001, INV5->C004
   customers per invoice:  [1]   every invoice names exactly one customer
   invoices per customer:  [0, 1, 3]   a customer has 0, 1 or many
   SE11 notation, check table first:        1:CN
   DDL notation, foreign key table first:   [0..*,1]
   Same relationship, the two sides written in opposite orders. The
   numbers are cardinalities of sets: |{customers of INV1}| = 1 and
   |{invoices of C001}| = 3, and the notation records the range.

6. MATCHING WORKS WHERE COUNTING STOPS: N AND THE EVEN NUMBERS
   Pair n with 2n. The first few pairs, and the rule for all of them:
     0<->0  1<->2  2<->4  3<->6  4<->8  5<->10  6<->12  7<->14  8<->16  9<->18  ...   n <-> 2n
   in the first 100,000 pairs, every even number below 200,000 is hit
   exactly once:  True
   The rule never runs out on either side, so by the matching
   definition |N| = |even numbers|, though one is a proper part of
   the other. Counting has no opinion here; it never finishes.

7. AND MATCHING CAN FAIL: THE DIAGONAL
   Suppose someone claims to have listed EVERY infinite 0/1 sequence,
   row 0, row 1, row 2, ... Here are 8 rows of such a list:
     row 0:  [0]  1   0   1   0   1   0   1
     row 1:   1  [1]  1   1   1   1   1   1
     row 2:   0   1  [0]  1   0   1   0   1
     row 3:   1   1   0  [0]  1   1   0   0
     row 4:   0   1   0   1  [0]  1   0   1
     row 5:   1   1   1   1   1  [1]  1   1
     row 6:   0   1   1   0   1   0  [0]  1
     row 7:   1   1   1   1   1   1   1  [1]
     diagonal:         0   1   0   0   0   1   0   1
     flipped:          1   0   1   1   1   0   1   0
   the flipped diagonal differs from row r in column r, for every r:
   [True, True, True, True, True, True, True, True]
   So it is a 0/1 sequence that is on no row of the list. Whatever
   list is offered, this builds a sequence it missed. No matching of
   N onto the set of 0/1 sequences exists: that set is UNCOUNTABLE.

8. WHY A PROGRAMMER SHOULD CARE: MORE FUNCTIONS THAN PROGRAMS
   A program is a finite string over a finite alphabet. Those can be
   listed, shortest first, alphabetically within a length:
     a  b  aa  ab  ba  bb  aaa  aab  aba  abb  baa  bab  bba  bbb  ...
   over a 2-letter alphabet there are 2^L strings of length L, so
   every string has a finite position in the list, and |programs| = |N|.
   (A real alphabet has 128 or 256 letters, which changes the count
   per length and nothing else.)

   A function from N to {0, 1} is an infinite 0/1 sequence, and section
   7 showed those cannot be listed. The same diagonal works for N -> N:
   given any list of functions g_0, g_1, g_2, ..., define
     d(n) = g_n(n) + 1
     g_0..g_5 at their own index:  [0, 2, 4, 7, 1, 95]
     d at those points:            [1, 3, 5, 8, 2, 96]
     d differs from every g_n at n: True
   d is a perfectly good function from N to N and it is on no list,
   so |N -> N| > |N| = |programs|. Some functions have no program.

   How many is 'some'? Every program computes at most one function,
   so the computable functions are at most countable. The functions
   N -> {0, 1} match the subsets of N, and Cantor's theorem says
   |P(N)| > |N|. Almost every function, in the cardinality sense, is
   uncomputable; the ones we can compute are the rare exceptions.
   This argument names no specific function. The halting problem is
   the famous named example, but counting gets there first.

9. COMBINATORICS: A SEARCH SPACE IS THE CARDINALITY OF A SET
   subsets of {w, x, y, z}: 16 = 2^4
     {}  {w}  {x}  {y}  {z}  {w,x}  {w,y}  {w,z}  {x,y}  {x,z}  {y,z}  {w,x,y}  {w,x,z}  {w,y,z}  {x,y,z}  {w,x,y,z}
   (each item is in or out: a 4-fold product of {in, out}, so 2 x 2 x 2 x 2)

       n     subsets 2^n   edges n(n-1)/2            orderings n!
       4              16                6               2.400e+01
      10           1,024               45               3.629e+06
      20       1,048,576              190               2.433e+18
      30   1,073,741,824              435               2.653e+32
      60       1.153e+18            1,770               8.321e+81
   The rows n <= 10 were counted by enumeration and matched the formula;
   the rest are the formula alone, because enumerating 2^60 subsets is
   the point: a brute-force search visits every member of a set, and
   the set's cardinality is the running time. 2^n and n! are the
   cardinalities that make a problem 'exponential'. An algorithm that
   beats brute force is one that decides without visiting every member.

   Two more counts that are the same rule:
     edges of the complete graph on 5 nodes:   10 = C(5, 2)
     possible graphs on 5 nodes:            1,024 = 2^10   (each edge in or out)
     length-4 passwords over 10 digits:        10,000 = 10^4   (a 4-fold product)

Matching, not counting¶

How many members does ℕ = {0, 1, 2, …} have? Infinitely many. And ℝ? Also infinitely many. Are those the same answer? Counting cannot say, because it never finishes either set.

Cantor's move was to replace counting with matching. Two sets have the same cardinality when their members can be paired off one to one with nothing left over on either side. Section 1 checks that this agrees with counting on finite sets: four chess pieces match four compass points, and no pairing of the four pieces with three directions closes, because one piece is always left standing.

Section 6 applies the same definition where counting is silent. Pair every natural number n with the even number 2n. The rule never runs out on either side, and the program checks on the first 100,000 that every even number is hit exactly once. So |ℕ| = |even numbers|, although the evens are a proper part of ℕ. Counting intuition says a part must be smaller. For infinite sets it need not be, and matching is the definition that says so precisely. The same kind of pairing lists every fraction, which is the countable sets page; a set that matches ℕ is called countable, and its cardinality is written ℵ₀.

Where matching fails¶

Section 7 is Cantor's diagonal argument on eight rows. Suppose someone hands you a list of infinite 0/1 sequences and claims every sequence is on it. Read down the diagonal, row r column r, and flip every bit. The result differs from row 0 in column 0, from row 1 in column 1, and so on: it differs from every row somewhere, so it is on no row. The list was incomplete, and the argument did not depend on which list was offered. No matching of ℕ onto the 0/1 sequences exists. That set is uncountable, and its cardinality is strictly bigger than ℵ₀.

This is the same fact that makes chapter 2 surprising. ℝ is uncountable, and so is the Cantor set, which still has length zero. Cardinality and length are two different questions about size, and the chapter is about how far apart their answers can be.

The product rule¶

Section 3 checks |A × B| = |A| · |B| on a 4-by-7 grid, the rule from the Cartesian product. It is worth knowing that the rule holds for infinite sets too, with a twist: |ℝ × ℝ| = |ℝ|. The plane has exactly as many points as the line. There is a matching, though not an obvious one.

Where a programmer meets it¶

The word turns up in computing far more often than in a first mathematics course, almost always in the finite sense. Three of these are the set rules read as something else: types, search spaces, and the count of programs.

Types¶

A type is a set of values, so it has a cardinality, and every way of building a new type from old ones is a way of building a new set. Section 3 constructs each one as an actual Python set and counts it.

type	built as	count	rule
void, never	no values	0	0
unit, `None`, `()`	one value	1	1
`bool`	{False, True}	2	2
`u2`	{0, 1, 2, 3}	4	2²
`(bool, u2)`	every pair	8	2 × 4
`bool \\| u2`	tagged left or right	6	2 + 4
`Optional[u2]`	`u2` or `None`	5	4 + 1
`u2 -> bool`	every truth table	16	2⁴

The names languages use for these constructors are the arithmetic. A pair, tuple, struct or record is a product type because it is a Cartesian product and its cardinality is the product of the parts: (bool, uint8) has 2 × 256 = 512 values, and (uint8, uint8) has 256 × 256 = 65,536, exactly the count of uint16, which is why two bytes pack into one and back without loss. A tagged union, enum with payloads, or variant is a sum type because a value is either from the left set or from the right, so the cardinality is the sum: bool | uint8 has 258. Optional[T] is the sum of T with the unit type, one more value than T. That one extra value is the reason a uint8 cannot hold "a uint8 or nothing": 257 values do not fit in 256, and every scheme that uses −1 or 255 as "no value" is stealing a member of T to pay for it. A function type A -> B has |B|^|A| values, one per lookup table, so uint8 -> bool has 2²⁵⁶ of them.

Because the rules are the set rules, the algebra of sets holds for types. Section 3 checks distributivity, |(bool | u2) × bool| = |bool × bool| + |u2 × bool| = 4 + 8 = 12, by building both sides. The practical readings are direct. An exhaustive match on (bool, u2) needs 8 arms and on bool | u2 needs 6, and the compiler that warns about a missing arm is counting. A fuzzer that tries every (uint8, uint8) input has exactly 65,536 cases and can be exhaustive; one that tries every (uint32, uint32) input has 2⁶⁴ and cannot. Two types with the same cardinality can be converted into each other without loss, and two with different cardinalities cannot, whatever the code says.

Databases¶

The cardinality of a column is how many distinct values it holds. Section 4 takes a 12-row table: name has cardinality 12, country 4, role 2. A query planner keeps estimates of exactly these numbers, because an index on a high-cardinality column narrows a lookup to a row or two and an index on a low-cardinality one barely narrows it at all. COUNT(DISTINCT x) computes it; a wrong estimate of it is the classic reason a query picks a bad plan. Relationship cardinality in a schema, one-to-one and one-to-many, is the same word applied to how many rows on each side can match.

A compound index makes the product rule concrete. An index on (country, role) has a key space that is the Cartesian product of the two columns' value sets, so its cardinality is at most |country| · |role|, which section 4 prints as 4 × 2 = 8 possible keys, of which the table uses 6. Two fields with 2 and 3 values give an index of cardinality 6. Every extra column multiplies.

Relationships between tables¶

The second database meaning is the one a schema designer uses: the cardinality of a foreign key says how many rows on each side can match. One-to-one, one-to-many, many-to-many. It is still |set|: for each invoice, the set of customers it names has cardinality exactly 1; for each customer, the set of invoices naming it has cardinality 0, 1 or more. Section 5 computes both on a five-invoice, four-customer table and reads off the answer.

The ABAP Dictionary writes this in two notations, and they run in opposite directions, which is a documented pitfall. In transaction SE11 the check table comes first: 1:CN means each invoice names exactly one customer (1, or C if the field may be empty), and each customer has any number of invoices (CN; 1, C and N are the other options). In the DDL syntax of ABAP Cloud the foreign key table comes first, and the ranges are spelled out: the same relationship is with foreign key [0..*,1], read as 0 or more invoices per customer, exactly 1 customer per invoice. So 1:CN and [0..*,1] describe one relationship, and a reader who applies the SE11 order to a DDL bracket, or the reverse, gets the parent and child swapped. The program prints both forms from the same data. The joins that consume these relationships are the sibling ABAP library's SELECT ↗, and the Dictionary objects that declare them are its DDIC, domains and data elements ↗.

Object models¶

UML draws composition as a line from a diamond on the composite class to the component class, and writes a cardinality at the component end: 1 for exactly one, * for any number, 1..4 or 1..* for a range. That is the foreign-key idea drawn as a picture, and the DDL brackets above use the same 0..* spelling. A GIS relationship class (ArcGIS ↗) offers the same three choices, one-to-one, one-to-many and many-to-many, between an origin and a destination table.

Observability¶

In telemetry the word is used for a field, and it means how many distinct values that field takes across all events. A species field on human users has cardinality 1. A country field has a couple of hundred. A user_id, request_id or container_id has the highest possible, since nearly every value is unique. Two consequences follow, and both are |set| in disguise. Metrics systems store one time series per distinct combination of tag values, so tagging a metric with a high-cardinality field multiplies the series count by that field's cardinality, which is why metrics stay cheap only with low-cardinality tags and why they cannot answer "which host?" once there are enough hosts. Debugging a novel failure, on the other hand, needs exactly those fields, because the needle is usually one user or one request. That is the argument for wide structured events over pre-aggregated metrics. A high-cardinality value can always be bucketed down to a low-cardinality one, last names by first letter, say; the reverse is impossible, since the information is gone. Dimensionality is the related but different count: not how many values a field has, but how many fields an event has.

Approximate counting¶

Counting distinct visitors across a billion events needs a billion-entry set, unless an estimate will do. HyperLogLog gives one within a few percent using a few kilobytes, and the field is called cardinality estimation. Redis exposes both: SCARD for an exact set cardinality and PFCOUNT for the estimate.

Combinatorics and algorithms¶

Every "how many" in an algorithms course is the cardinality of a set, and most of them are the product rule in disguise. Section 9 counts the subsets of a 4-element set by listing all 16 of them. The reason there are 2ⁿ is that each element is in or out, so a subset is a member of {in, out} × {in, out} × … × {in, out}, an n-fold product with cardinality 2 × 2 × … × 2. The edges of a complete graph on n nodes are the 2-element subsets, n(n−1)/2 of them; the possible graphs on those nodes are the subsets of the edge set, 2^(n(n−1)/2); the orderings of n items are n!; the 4-digit passwords are 10⁴, a 4-fold product. The program checks every formula by enumeration up to n = 10 and then prints the formula alone for n = 20, 30 and 60.

That switch is the point. A brute-force algorithm visits every member of some set, so the set's cardinality is its running time, and 2⁶⁰ subsets or 60! orderings cannot be visited. "Exponential" is a statement about the cardinality of the search space, and an algorithm that beats brute force is one that decides without touching every member. Counting the set is the first thing to do with a new problem, because it says whether enumeration is an option at all.

Computability¶

Section 8 is the one place the infinite version explains something concrete, and it is worth following slowly, because it proves that uncomputable functions exist without ever naming one.

A program is a finite string over a finite alphabet. Finite strings can be listed: all the strings of length 1, then length 2, then 3, alphabetically within each length. Over a 2-letter alphabet there are 2^L strings of length L, so every string appears at some finite position, and a real alphabet of 128 or 256 characters changes only the count per length. So |programs| = |ℕ|, and since each program computes at most one function, the computable functions are at most countable.

Now count the functions. A function from ℕ to {0, 1} is an infinite 0/1 sequence, and section 7 showed those cannot be listed. Section 8 runs the same diagonal on functions from ℕ to ℕ: given any list g₀, g₁, g₂, …, define d(n) = gₙ(n) + 1. Then d differs from g₀ at 0, from g₁ at 1, and from every gₙ at n, so d is on no list. The program builds d from six concrete functions and checks the six disagreements. Whatever list is offered, this produces a function it missed, so |ℕ → ℕ| > |ℕ|.

Put the two counts together. The programs are countable and the functions are not, so there are strictly more functions than programs, and some functions have no program. The functions ℕ → {0, 1} correspond to the subsets of ℕ, and Cantor's theorem, the diagonal argument once more, says |P(ℕ)| > |ℕ|. In the cardinality sense almost every function is uncomputable; the computable ones are the rare exceptions. The halting problem is the famous named example, and the counting argument is why one had to exist. It is pure cardinality, and it is the reason a lesson on the sizes of infinite sets belongs in a library that a programmer reads.

Run it yourself¶

From the root of your clone of this repository:

python3 04_Sets/cardinality/examples/cardinality.py

Auf Deutsch: Stichwörter¶

Zwei Mengen sind gleich groß, wenn eine Bijektion zwischen ihnen besteht; ℕ und ℚ sind abzählbar, ℝ ist es nach Cantors Diagonalargument nicht.

Stichwörter: Mächtigkeit (cardinality), Bijektion, abzählbar unendlich, überabzählbar, Diagonalargument, Kardinalzahl, ℵ₀.