Infinite Sets

An infinite set is a collection of elements whose counting process never ends. Unlike finite sets, where every element can be enumerated up to a final term, an infinite set always has more elements to consider, regardless of how many have already been counted.

From a formal perspective, a set A is infinite if there is no natural number n such that its elements can be placed in a one-to-one correspondence with the reference set {1, 2, 3, ..., n}. Consequently, the size or cardinality of an infinite set cannot be represented by an integer, which is why specific set-theoretic symbols are used to describe its size.

Another defining characteristic of infinite sets is that they can be placed in a one-to-one correspondence with a proper subset of themselves. While any proper subset of a finite set strictly contains fewer elements than the whole, an infinite set allows every element of the entire set to be paired with the elements of one of its subsets, with nothing left over and none omitted.

Examples

Below, we examine several examples of infinite collections:

1. The set of natural numbers N = {1, 2, 3, 4, ...} is the foundational example of an infinite set, since for any number chosen, there is always a successor obtained by adding one.
2. The set of integers Z = {..., −3, −2, −1, 0, 1, 2, 3, ...} extends in two opposite directions, encompassing positive integers, negative integers, and zero.
3. The set of even numbers P = {x ∈ Z | x = 2k, k ∈ Z} = {..., −4, −2, 0, 2, 4, ...} contains an unbounded number of elements. Although it is a subset of the integers, it has just as many elements as the entire set because it can be paired one-to-one with it.
4. The set of prime numbers Pr = {2, 3, 5, 7, 11, 13, 17, ...} has no final element. By Euclid's theorem, the list of integers greater than 1 that are divisible only by 1 and themselves continues indefinitely.
5. The set of rational numbers Q = {a/b | a, b ∈ Z ∧ b ≠ 0} contains all possible fractions. Between any two distinct fractions, another fraction can always be found, generating an infinite number of values across any segment of the number line.
6. The closed interval I = [0, 1] = {x ∈ R | 0 ≤ x ≤ 1} represents a continuous segment of the real line. Despite being bounded between 0 and 1, it contains an infinity of real numbers due to the property of continuity.
7. The Cartesian plane R² = {(x, y) | x ∈ R ∧ y ∈ R} represents the set of all points in two dimensions. Each point is defined by an ordered pair of real coordinates, forming a surface with infinitely many points along each axis and throughout the space they define.

Properties of Infinite Sets

1) Correspondence with a proper subset: Every infinite set can be placed in a one-to-one correspondence with at least one of its proper subsets. This condition distinguishes infinite sets from finite ones, where no proper subset can match the cardinality of the whole set.

2) Subsets of an infinite set: A subset taken from an infinite set is not necessarily infinite. Depending on the elements chosen, a subset can be either finite or infinite.

3) Union with finite sets: Taking the union of an infinite set with any finite set leaves the total number of elements infinite, preserving the same transfinite cardinality.

A is infinite ∧ B is finite → |A ∪ B| = |A|

4) Union of infinite sets: The union of two infinite sets always yields another infinite set. The resulting size matches the cardinality of the larger set involved.

|A ∪ B| = max(|A|, |B|)

5) Intersection with other sets: The intersection between an infinite set and a finite set always produces a finite set. If two infinite sets intersect, the result may be the empty set, a finite set, or a new infinite set.

6) Difference of infinite sets: Subtracting a finite set from an infinite set leaves the resulting collection infinite without altering its cardinality. If two infinite sets are subtracted, the result may be empty, finite, or infinite, depending on the shared elements.

A is infinite ∧ B is finite → |A − B| = |A|

7) Infinite Cartesian product: The Cartesian product of two infinite sets produces a new infinite set of ordered pairs. In particular, the Cartesian product of two countably infinite sets retains the same cardinality as each individual set.

8) Growth via power set: Cantor's theorem states that the power set P(A) of any infinite set has a strictly greater cardinality than the original set. This relationship proves that there is no maximum infinity, as a set with more elements can always be constructed using this operation.

|P(A)| > |A|

Countable and Uncountable Sets

Not all infinite sets contain the same number of elements. In set theory, the size of an infinite collection is classified based on whether its members can be listed in an ordered sequence using the natural numbers as an index.

Countably Infinite Sets

An infinite set is countably infinite (or countable) when a one-to-one correspondence can be established between its elements and the set of natural numbers N. This means each element can be assigned a fixed position (first, second, third) without omitting any member along an endless list.

The cardinality of these sets is denoted by the symbol ℵ₀ (aleph-null), which represents the smallest level of infinity:

• Natural numbers (N): They serve as the direct benchmark for infinite counting, meaning their cardinality is |N| = ℵ₀.
• Integers (Z): Even though they include the natural numbers along with their negative counterparts and zero, they have the exact same size. They can be listed by alternating signs: 0, 1, −1, 2, −2, 3, −3, ..., proving that |Z| = ℵ₀.
• Rational numbers (Q): Despite the density of fractions on the number line, Georg Cantor proved that all positive and negative rational numbers can be arranged in a diagonal traversal without skipping any, showing that |Q| = ℵ₀.
• Infinite subsets of N: Collections such as even numbers, odd numbers, or prime numbers also have cardinality ℵ₀, as they can be mapped one-to-one onto the set of natural numbers.

Uncountably Infinite Sets

An infinite set is uncountably infinite (or uncountable) when it is impossible to arrange all its elements into a sequential list. Any attempt to enumerate them invariably leaves elements out, indicating that this is an infinity strictly greater than ℵ₀.

The cardinality of these sets is associated with the continuum and is denoted by the letter c or as 2^ℵ₀. This magnitude arises when working with continuous spaces that have no gaps or interruptions:

• Real numbers (R): Using Cantor's diagonal argument, it can be proven that decimal numbers cannot be put into a one-to-one correspondence with the natural numbers. Therefore, |R| = c.
• Real intervals: Any interval of the real line, such as the open interval (0, 1) or the closed interval [a, b] with a < b, contains just as many points as the entire real number line.
• Points in the Cartesian plane (R²): The two-dimensional coordinate plane contains the exact same number of points as a single continuous line, confirming that |R²| = c.

Solved Practice Problems

To determine whether a set is finite or infinite, or to compare the sizes of two infinite collections, analyze the nature of their elements or establish a one-to-one rule between them. Below, we work through four practical problems to apply these principles step by step.

Exercise 1

Consider the sets defined in set-builder notation A = {x ∈ Z | −2 ≤ x ≤ 3} and B = {x ∈ R | −2 ≤ x ≤ 3}. Determine whether each set is finite or infinite, justifying the answer based on its elements.

Solution

First, analyze set A, whose elements belong to the set of integers Z. Because there is only a fixed count of integer values between −2 and 3, write the set in roster form:

A = {−2, −1, 0, 1, 2, 3}

Counting its members terminates at a non-negative integer, so A is a finite set with cardinality |A| = 6.

Next, evaluate set B, defined over the real numbers R. Although the set begins at −2, it is impossible to determine which real number immediately follows it: would it be −1.9, −1.99, or −1.999? Between any two distinct real numbers, intermediate real numbers always exist. Due to this density property and the continuity of the real line, its elements cannot be listed sequentially, confirming that B is an infinite set.

Exercise 2

Prove that the set of positive even integers P = {2, 4, 6, 8, ...} has the same number of elements as the set of natural numbers N = {1, 2, 3, 4, ...} by constructing a one-to-one correspondence between them.

Solution

To prove that two infinite sets have the same cardinality, each element of N must be paired with a unique element of P such that no elements remain unassigned on either side.

Define the assignment function f(n) = 2n, where n ∈ N. Evaluate this rule term by term:

• For n = 1: f(1) = 2(1) = 2
• For n = 2: f(2) = 2(2) = 4
• For n = 3: f(3) = 2(3) = 6
• For n = 4: f(4) = 2(4) = 8

Each natural number corresponds to exactly one positive even integer (twice its value), and every positive even integer maps back to its half in the natural numbers. Because this bijection exists, both sets have the exact same size, meaning |P| = |N| = ℵ₀.

Exercise 3

Prove that the set of positive odd integers I = {1, 3, 5, 7, ...} has the same cardinality as the set of natural numbers N = {1, 2, 3, 4, ...} using a bijective function.

Solution

Find an algebraic rule that connects each natural number to a unique positive odd integer in an ordered way.

Set up the function g(n) = 2n − 1 for all n ∈ N and evaluate the first few terms:

• For n = 1: g(1) = 2(1) − 1 = 1
• For n = 2: g(2) = 2(2) − 1 = 3
• For n = 3: g(3) = 2(3) − 1 = 5
• For n = 4: g(4) = 2(4) − 1 = 7

This relation assigns each element of N to a unique odd integer without leaving empty values or duplicating assignments. Thus, a one-to-one correspondence is established, proving that the set of positive odd integers has the same number of elements as the natural numbers: |I| = |N| = ℵ₀.

Exercise 4

Let A = {x ∈ R | x ≥ 0}, B = {x ∈ R | x ≤ 4}, and C = {1, 2, 3}. Evaluate the operations A ∩ B and A ∩ C, and determine in each case whether the resulting set is finite or infinite.

Solution

For the first operation, find the real numbers that satisfy both inequalities simultaneously: x ≥ 0 and x ≤ 4. Combining both conditions defines the closed interval:

A ∩ B = [0, 4] = {x ∈ R | 0 ≤ x ≤ 4}

Because this is an interval of real numbers, it contains a continuum of points without gaps, making A ∩ B an uncountably infinite set.

For the second operation, determine which elements of the finite set C also belong to set A (real numbers greater than or equal to zero):

• 1 ≥ 0, so 1 ∈ A
• 2 ≥ 0, so 2 ∈ A
• 3 ≥ 0, so 3 ∈ A

Every member of C satisfies the condition given in A, resulting in:

A ∩ C = {1, 2, 3}

With a bounded count of three elements, A ∩ C is a finite set with cardinality |A ∩ C| = 3.