Glossary

8.2 Countable and Uncountable Sets

2 min read•july 25, 2024

Set theory explores the sizes of through . Countable sets match up with , while sets are larger. This distinction forms the foundation for comparing infinities.

Bijections prove countability by mapping sets to natural numbers. For uncountable sets like , Cantor's diagonalization method shows no such mapping exists. These concepts reveal the surprising complexities of infinity.

Set Theory and Cardinality

Countable vs uncountable sets

Top images from around the web for Countable vs uncountable sets

  • Cardinality - Wikipedia View original

    Is this image relevant?

  • Summary: Classes of Real Numbers | Developmental Math Emporium View original

    Is this image relevant?

  • Cardinality - Wikipedia View original

    Is this image relevant?

1 of 3

Top images from around the web for Countable vs uncountable sets

  • Cardinality - Wikipedia View original

    Is this image relevant?

  • Summary: Classes of Real Numbers | Developmental Math Emporium View original

    Is this image relevant?

  • Cardinality - Wikipedia View original

    Is this image relevant?

1 of 3
  • Countable sets correspond one-to-one with natural numbers or subsets includes finite and sets (natural numbers, integers, rational numbers)
  • Uncountable sets cannot correspond one-to-one with natural numbers have cardinality greater than natural numbers (real numbers, of natural numbers)
  • Formal definitions use injective functions ∃f:A→N\exists f: A \to \mathbb{N} for countable and ∄f:A→N\nexists f: A \to \mathbb{N} for uncountable
  • Cardinality notation uses ℵ0\aleph_0 for countably infinite and c\mathfrak{c} for uncountable sets like reals

Bijections for countable sets

  • means one-to-one and onto function establishes countability
  • Proving countability requires:
    1. Construct explicit function from set to natural numbers
    2. Show function is injective (one-to-one)
    3. Show function is surjective (onto)
  • Common techniques employ list method for countably infinite sets use pairing functions for Cartesian products apply diagonal arguments for unions of countable sets
  • Provably countable sets include integers rational numbers algebraic numbers

Advanced Cardinality Concepts

Uncountability of real numbers

  • Cantor's diagonalization method proves uncountability of reals:
    1. Assume reals are countable
    2. List all reals between 0 and 1
    3. Construct new number differing from each listed number
    4. Show new number not in list contradicts assumption
  • Key proof steps use decimal representation alter digits along diagonal ensure new number differs from every listed number
  • Uncountability implies existence of transcendental numbers demonstrates non-enumerability of reals

Cardinality of infinite sets

  • Cardinal numbers represent size of infinite sets establish ordering among infinities
  • Cardinal arithmetic operations for infinite sets:
    • Addition: ∣A∪B∣=max⁡(∣A∣,∣B∣)|A \cup B| = \max(|A|, |B|)
    • Multiplication: ∣A×B∣=max⁡(∣A∣,∣B∣)|A \times B| = \max(|A|, |B|)
    • Exponentiation: ∣AB∣>∣A∣|A^B| > |A|
  • Cantor-Schröder-Bernstein theorem states if ∣A∣≤∣B∣|A| \leq |B| and ∣B∣≤∣A∣|B| \leq |A|, then ∣A∣=∣B∣|A| = |B|
  • Cardinality comparisons show ∣N∣=∣Z∣=∣Q∣=ℵ0|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| = \aleph_0 and ∣R∣=∣P(N)∣=2ℵ0=c|\mathbb{R}| = |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0} = \mathfrak{c}
  • Continuum hypothesis posits no set with cardinality between ℵ0\aleph_0 and c\mathfrak{c}

Key Terms to Review (15)

Bijection: A bijection is a special type of function between two sets where every element of the first set is paired with exactly one unique element of the second set, and vice versa. This one-to-one correspondence means that both sets have the same cardinality, which is vital in understanding concepts like countable and uncountable sets. Bijections also play a crucial role in Cantor's Theorem and diagonalization, helping to illustrate the differences in size between different infinities, while also being linked to the study of ordinals and cardinals in set theory.
Cantor's Theorem: Cantor's Theorem states that for any set, the power set (the set of all subsets) of that set has a strictly greater cardinality than the set itself. This theorem shows the existence of different sizes of infinity and is fundamental in understanding the concepts of countable and uncountable sets, as well as ordinal and cardinal arithmetic. It also introduces methods like diagonalization, which are crucial for demonstrating uncountability.
Cardinality: Cardinality refers to the measure of the 'size' or number of elements in a set. It helps differentiate between finite sets, which have a specific count of elements, and infinite sets, which can be countably infinite or uncountably infinite, leading to different levels of infinity. Understanding cardinality is crucial for comparing sets and analyzing their properties, especially when dealing with functions and the structure of numbers.
Countably Infinite: Countably infinite refers to a type of infinity that can be put into a one-to-one correspondence with the natural numbers. This means that although the set is infinite, its elements can be listed in a sequence where each element is assigned a unique natural number. This concept helps distinguish between different sizes of infinity and is crucial for understanding how certain sets relate to each other.
Diagonal Argument: The diagonal argument is a mathematical proof technique used to demonstrate that certain sets are uncountable, meaning they cannot be put into a one-to-one correspondence with the set of natural numbers. This method, famously introduced by Cantor, shows that the real numbers cannot be listed in a sequence, highlighting the existence of sizes of infinity beyond that of countable sets like the integers or natural numbers.
Georg Cantor: Georg Cantor was a German mathematician known for founding set theory and introducing concepts of infinity, particularly distinguishing between countable and uncountable sets. His work laid the groundwork for modern mathematics, emphasizing that not all infinities are equal and leading to significant advancements in understanding the nature of mathematical existence.
Infinite sets: Infinite sets are collections of elements that do not have a finite number of members, meaning they continue indefinitely. This concept is crucial for understanding the differences between countable and uncountable sets, as infinite sets can be either countable, where their elements can be matched with the natural numbers, or uncountable, where they cannot. Recognizing the distinction between these two types of infinite sets helps to grasp the foundational ideas in mathematical logic and set theory.
Intersection: The intersection of two or more sets is the collection of elements that are common to all the sets involved. This concept is central to understanding how different sets relate to each other, providing insight into shared properties and elements. The intersection helps in analyzing relationships between sets, whether they are countable or uncountable, as well as in exploring the foundational axioms that govern set theory and the classification of different types of sets, including recursive ones.
Natural Numbers: Natural numbers are the set of positive integers starting from 1 and extending infinitely, typically represented as {1, 2, 3, ...}. They are fundamental in mathematics for counting and ordering, serving as the building blocks for more complex numerical systems and concepts. Understanding natural numbers is essential for exploring finite and infinite sets, as well as foundational axioms in set theory.
Power Set: A power set is the set of all subsets of a given set, including the empty set and the set itself. This concept is crucial in understanding how sets can be organized and manipulated, as well as exploring the sizes of sets, particularly in distinguishing between countable and uncountable sets. Power sets also play a significant role in Cantor's theorem, which illustrates that the power set of any set has a strictly greater cardinality than the original set, and are foundational for set operations such as Cartesian products.
Real Numbers: Real numbers are the set of all numbers that can be found on the number line, including both rational numbers (like integers and fractions) and irrational numbers (like $\\sqrt{2}$ or $\\pi$). They play a crucial role in various mathematical concepts and are essential for understanding both finite and infinite sets, as well as countability and uncountability within those sets.
The set of all subsets of a set: The set of all subsets of a set, known as the power set, is the collection of every possible subset that can be formed from that set, including the empty set and the set itself. This concept is fundamental in understanding the nature of sets and their cardinality, particularly when distinguishing between countable and uncountable sets.
The set of integers: The set of integers consists of all whole numbers, including positive numbers, negative numbers, and zero. It is denoted by the symbol $$ ext{Z}$$ and is essential in understanding various concepts in mathematics, particularly in number theory and algebra. The integers form a fundamental building block for more complex mathematical structures and are crucial when discussing countability, as they represent a classic example of a countably infinite set.
Uncountable: Uncountable refers to a type of set that cannot be matched one-to-one with the set of natural numbers, meaning its size is larger than any countable set. This concept highlights a distinction between different sizes of infinity, showing that some infinities, like the set of real numbers, are uncountable while others, such as the set of integers, are countable. Understanding uncountable sets leads to deeper insights into the nature of mathematical infinity and the foundational aspects of set theory.
Union: Union is a fundamental operation in set theory that combines all the elements from two or more sets, ensuring that each element appears only once in the resulting set. This operation highlights the relationship between different sets and is crucial for understanding how sets interact with each other. By defining the union of sets, we can analyze complex structures and relationships within mathematics, which leads to insights about countable and uncountable sets, as well as recursive and recursively enumerable sets.
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.
Back
Practice QuizGlossary
Practice QuizGlossary
Next guide