Question

Prove that if \(A\) is countable but \(B\) is not, then \(B-A\) is uncountable.

Short answer

If \(A\) is countable and \(B\) is uncountable, then \(B - A\) is uncountable.

Step-by-step solution

Define the Concept of Countable and Uncountable Sets

A set is countable if it is finite or has the same cardinality as the set of natural numbers, \( \mathbb{N}\). Examples of countable sets include \( \mathbb{N}\) itself, the set of integers, and the set of rational numbers. A set is uncountable if it is not countable, meaning its cardinality is greater than that of \( \mathbb{N}\). The most familiar example of an uncountable set is the set of real numbers, \( \mathbb{R}\).

Explore the Sets Involved

We need to explore two sets: \(A\), which is countable, and \(B\), which is uncountable. We are interested in the set \(B - A\), which consists of all elements that are in \(B\) but not in \(A\). Since \(B\) is uncountable, its cardinality is greater than any countable set including \(A\).

Understand the Relationship Between A and B

Given \(A\) is countable and \(B\) is uncountable, this means \(B\) must contain some elements that are not in \(A\) (otherwise \(B\) would also be at most countable). This implies \(B - A\) is not empty.

Prove the Uncountability of B - A

Assume towards contradiction that \(B - A\) is countable. Then, \(B\) would be a countable union of two countable sets: \(A\) and \(B - A\). However, a union of two countable sets is also countable. This contradicts the given condition that \(B\) is uncountable. Hence, \(B - A\) must be uncountable.

Key concepts

Countable Sets

In set theory, a set is considered countable if its elements can be put into a one-to-one correspondence with the natural numbers, \( \mathbb{N} \). This means that the elements of the set can be listed in a sequence: the first element, the second, the third, and so on. If you can imagine "counting" the elements, either because the set is finite or infinitely countable like the natural numbers themselves, then it is countable.

Some common examples of countable sets include:

• The set of natural numbers, \( \mathbb{N} = \{0, 1, 2, 3, \ldots\} \)
• The set of integers, \( \mathbb{Z} = \{0, 1, -1, 2, -2, \ldots\} \)
• The set of rational numbers, which can be represented by fractions like \( \frac{1}{2}, \frac{3}{4} \)

Even though the rationals can be quite dense on the number line, there's still a clever way to "list" all rational numbers. Thus, making them countable.

Countable sets are crucial in mathematics because they often represent the most straightforward forms of infinity, supporting intuition in exploring larger concepts.

Uncountable Sets

An uncountable set is a collection of elements that cannot be put into a one-to-one correspondence with the natural numbers. This means you cannot "list" the elements in such a way where you can assign a distinct natural number to each element. The set of real numbers, \( \mathbb{R} \), is the classic example of an uncountable set.

Uncountability was famously proven by Cantor using his diagonal argument. This argument shows that even if you attempted to list all real numbers between 0 and 1, you could always construct a new number not on your list, thus demonstrating that the real numbers cannot be counted in the same way as the natural numbers. The implication is that the cardinality of \( \mathbb{R} \) is strictly greater than that of \( \mathbb{N} \).

Being uncountable makes a set infinitely larger, in a sense, than countable sets. Thus, understanding the nature of uncountable sets helps in grasping the scope of different types of infinities present in mathematics.

Cardinality

Cardinality is a measure of the "number of elements" in a set. It extends our familiar notion of size for finite sets into the realm of infinite sets. For finite sets, cardinality is simply the number of elements. For infinite sets, it's not as straightforward.

To compare the cardinality of two sets, we often use the concept of a bijection— a one-to-one correspondence between the sets. If such a bijection exists, we say the sets have the same cardinality. For instance, the sets of natural numbers and even numbers have the same cardinality because you can match each natural number \( n \) with \( 2n \), covering all elements of both sets.

Different sizes of infinity exist in mathematics.

• Countable infinities, such as \( \mathbb{N} \), \( \mathbb{Z} \), and \( \mathbb{Q} \)
• Uncountable infinities, like \( \mathbb{R} \)

Cardinality helps formalize the idea of differentiating these sizes of infinity. The cardinality of countable sets is denoted as \( \aleph_0 \) (aleph-null). For uncountable sets, like the reals, cardinality is referred to using the continuum, represented by \( c \). This exploration of cardinalities enriches our understanding of potential "sizes" of different sets in mathematics.