Course contentsShow
← Mathematics
Lesson 2566 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

Cardinality and Bijections

Use bijections to determine when two sets have the same cardinality or size.

Cardinality and Bijections

What You'll Learn

You'll learn how to use bijections to rigorously determine when two sets have exactly the same "size" or cardinality.

The Core Idea

Cardinality refers to the "size" of a set—how many elements it contains. For finite sets, this is straightforward: {1, 2, 3} has cardinality 3. But how do we compare the sizes of two sets, especially when they look completely different?

The answer: two sets have the same cardinality if and only if there exists a bijection between them.

Remember that a bijection is a function that is both injective (one-to-one) and surjective (onto). If you can construct a bijection f: A → B, you've proven that every element in A pairs with exactly one unique element in B, and every element in B is accounted for. This perfect pairing means A and B must have the same size.

Why Bijections Matter

Think of it like a dance: if every person from group A has exactly one partner from group B, and no one in either group is left out, the groups must be equal in size.

Examples:

  • The sets {1, 2, 3} and {a, b, c} have the same cardinality because we can define f(1) = a, f(2) = b, f(3) = c—a bijection.
  • The sets {positive integers} and {even positive integers} have the same cardinality via f(n) = 2n. Surprising, but the bijection proves they're equally "large"!
  • If no bijection exists between sets A and B, they have different cardinalities.

This notion extends beautifully to infinite sets, allowing mathematicians to compare "sizes of infinity."

Key Takeaway: Two sets A and B have the same cardinality (|A| = |B|) if and only if there exists a bijection between them—establishing a perfect one-to-one correspondence between all elements.