Problem 50 - Discrete Mathematics with Applications

Question

Prove. The cartesian product of two countable sets is countable.

Step-by-Step Solution

Answer

Since the given sets A and B are countable, we can establish a one-to-one correspondence between them and the natural numbers. We can label the elements in A as \(a_1, a_2, a_3, ...\), and the elements in B as \(b_1, b_2, b_3, ...\), where each element in A and B corresponds to a different natural number. We compute the cartesian product A x B and organize the elements in a matrix form. By creating a sequence for A x B that covers all the elements in the matrix following a diagonal pattern, this creates a one-to-one correspondence between the cartesian product A x B and the natural numbers. Hence, we conclude that the cartesian product of two countable sets is countable.

Step 1: Establish a one-to-one correspondence between the countable sets and the natural numbers

Since the given sets A and B are countable, we can establish a one-to-one correspondence between them and the natural numbers. We can label the elements in A as \(a_1, a_2, a_3, ...\), and the elements in B as \(b_1, b_2, b_3, ...\), where each element in A and B corresponds to a different natural number.

Step 2: Create the cartesian product A x B

Next, compute the cartesian product A x B by forming the set of all ordered pairs (a, b) such that a ∈ A and b ∈ B. Since we have the sequences \(a_1, a_2, a_3, ...\) and \(b_1, b_2, b_3, ...\), the resulting cartesian product will have elements like (a1, b1), (a1, b2), (a2, b1), (a2, b2), (a3, b1), and so on.

Step 3: Organize the elements of A x B in a matrix

To make it easier to see the pattern, organize the elements of A x B in a matrix form. Each row of the matrix represents one element from A paired with all elements of B, and each column represents one element from B paired with all elements of A: \( \begin{matrix} (a_1,b_1) & (a_1,b_2) & (a_1,b_3) & \cdots \\ (a_2,b_1) & (a_2,b_2) & (a_2,b_3) & \cdots \\ (a_3,b_1) & (a_3,b_2) & (a_3,b_3) & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{matrix}\)

Step 4: Create a sequence for A x B

Now, create a sequence for A x B that covers all the elements in the matrix. One simple way to do this is by following a diagonal pattern. Start with the element in the first row and first column, (a1, b1), then move to the element in the first row and second column, (a1, b2), down to the second row and first column, (a2, b1), across to the second row and third column, (a2, b2), and so on. This creates a one-to-one correspondence between the cartesian product A x B and the natural numbers. The resultant sequence would look like this: \((a_1, b_1), (a_1, b_2), (a_2, b_1), (a_2, b_2), (a_1, b_3), (a_3, b_1), (a_3, b_2), (a_2, b_3), (a_3, b_3), ...\)

Step 5: Conclude that A x B is countable

Since there exists a one-to-one correspondence between the elements of A x B and the natural numbers, we have demonstrated that the cartesian product of two countable sets is also countable.<|disc_score|>7

Key Concepts

Countable Sets

When we talk about countable sets, we're discussing a concept in mathematics that pertains to the size of a set. A set is considered countable if its elements can be matched one-to-one with the set of natural numbers. In simpler terms, you can 'count' the elements, even if there are infinitely many of them, by aligning each one with a natural number.

Two classic examples of countable sets are the set of all natural numbers itself, and the set of all even numbers. At first glance, one might think that there are more natural numbers than even numbers since the even numbers are a subset of the natural numbers. However, because we can match each even number with a natural number (e.g., 2 with 1, 4 with 2, 6 with 3, and so forth), both sets are actually the same size in terms of their 'countability'. This fascinating property underlies some astounding results in set theory, like the fact that two countable sets can be combined to form another countable set.

One-to-One Correspondence

The heart of understanding countable sets lies in the idea of one-to-one correspondence. This is a way to pair each element of one set with exactly one element of a second set, such that there's no overlap and no element is left out of either set. Imagine two rows of boxes where each box in one row is connected by a line to a box in the other row — that's one-to-one correspondence in a nutshell.

For instance, let's say you have a set of chairs and a set of people. If you can seat every person in a chair without any empty chairs and without any person standing, you've achieved a one-to-one correspondence between people and chairs. This concept extends to infinite sets as well, and it's what allows mathematicians to determine whether an infinite set is countable or not. It's the technique used in establishing a one-to-one correspondence between the cartesian product of two countable sets and the natural numbers, which helps in proving the countability of the combined set.

Natural Numbers

The natural numbers are the simplest numbers we use: 1, 2, 3, etc. They're what we use to count objects and are fundamental to arithmetic. In set theory, they hold a special place because they form a 'simplest' infinity, known as 'countable infinity'.

Every natural number has a successor (just add 1!), and this goes on endlessly. This property gives the natural numbers their countability, as they can be put into a sequence where each number is followed by its unique successor. They provide an essential baseline against which the 'size' of infinite countable sets is measured. If a set can be put in one-to-one correspondence with the natural numbers, it's said to be countably infinite. This ties back to the exercise problem where the cartesian product of two countable sets is mapped out to show it's countably infinite as well.