2 of 2

34.2 Cardinality = Size

Every set has a size. The size is just the number of elements in the set.

Cardinality: the number of elements in a set.

Cardinality is another word for the size of a set.

To figure out the cardinality of a set, just count up the elements.

|a| means the cardinality of set a.

A common notation for cardinality is vertical bars around a set, like this: |{0,1,2}|.

This is a set: {0,1,2}
This is a number: |{0,1,2}|

Namely, it is the number of elements in the set, which is 3.

Same Size

Since every set has a size, any two sets will either have the same size or not.

The easiest way to compare sizes of sets is just to count up the elements of each and compare the numbers.

1-to-1 Correspondence

We can compare the sizes of sets without even counting them.

But there’s another way to compare the sizes of two sets, without even counting them.

Here are two large sets, called “prime” and “fib”, which both contain a bunch of numbers.

prime = {2, 3, 5, 7, 11, 13, 17, 19, 23}

fib = {0, 1, 2, 3, 5, 8, 13, 21, 34}

Try to resist the urge to count the elements of prime and fib!

Instead, let’s say we paired off the elements of the sets, so that exactly one element of prime is paired with exactly one element of fib.

We will connect the numbers with a line that are paired together.

2—0
3—1
5—2
7—3
11—5
13—8
17—13
19—21
23—34

Two sets cannot possibly have different sizes, if they can be paired off like this.

If we can pair them off like this, then we can know that prime and fib have the same size, even if we don’t know exactly what their cardinality is.

Notice that we go in numerical order, so that we can keep track. Don’t necessarily pair 2 with 2, even though 2 appears in both sets.

1-to-1 correspondence: pairing exactly one element of one set with exactly one element of another set.

Pairing sets like this is called a 1-to-1 correspondence. (In math, another name for a 1-to-1 correspondence is a bijection, but you don’t need to memorize that word.)

To create a 1-to-1 correspondence, we can use two columns. In the first column goes the elements of one set, and in the second column goes the elements of the other set. Each row is a pairing.

Remember, the requirement to use numerical order is just for keeping our heads straight.

From a logical point of view, any pairing off would count as a 1-to-1 correspondence, as long as exactly one element of each set is paired together.