Cardinality

The size of a set is called its cardinality. It's clear when two finite sets have the same cardinality, they have the same number of elements. What do we mean when we say to infinite sets have the same cardinality?

For example, is the set of even integers {..., -4, -2, 0, 2, 4, ...} smaller than the set of all integers {...,-4,-3,-2,-1,0,1,2,3,4,....} ?

Our intuition says that removing an element from a set makes the set smaller, so removing an infinite number of elements should make it a lot smaller. That intuition is wrong though.

We say that two sets have the same cardinality if we can make a 1-to-1 correspondence between them. A 1-to-1 correspondance between A and B is a pairing of elements of A and B where every element of A is in exactly one pair, and every element B is in exactly one pair.

Here's a 1-to-1 correspondence between the integers and the even integers: k pairs with 2k. Every integer is on the left side (the k's) and every even integer is on the right side (the 2k's).