∞Intro to the Theory of Sets Unit 7 – Countable vs Uncountable Sets

Key Concepts and Definitions

• Set a well-defined collection of distinct objects considered as a whole
• Element an object that belongs to a set, also known as a member
• Cardinality the size or number of elements in a set, denoted as $|A|$ for set $A$
• Finite set a set with a specific number of elements that can be counted
• Infinite set a set with an endless number of elements that cannot be counted
• Countable set a set with the same cardinality as the set of natural numbers $\mathbb{N}$
  • Can be either finite or infinite
• Uncountable set a set with a cardinality greater than the set of natural numbers $\mathbb{N}$
  • Always infinite and cannot be put into a one-to-one correspondence with $\mathbb{N}$

Finite vs Infinite Sets

• Finite sets have a specific number of elements that can be counted (set of days in a week)
• Infinite sets have an endless number of elements that cannot be counted (set of all integers)
• Finite sets can be represented by listing all their elements, while infinite sets cannot
• The set of natural numbers $\mathbb{N}$ is an example of an infinite set
• Infinite sets can be further classified as countable or uncountable
• The union of two finite sets is always finite, while the union of an infinite set with any other set is always infinite
• The power set of a finite set is finite, while the power set of an infinite set is always uncountable

Countable Sets Explained

• A set is countable if it has the same cardinality as the set of natural numbers $\mathbb{N}$
• Countable sets can be either finite or infinite
• Examples of countable sets include the set of integers $\mathbb{Z}$, the set of rational numbers $\mathbb{Q}$, and the set of algebraic numbers
• A set is countable if there exists a bijective function (one-to-one correspondence) between the set and $\mathbb{N}$
  • This means each element in the set can be paired with a unique natural number
• The union of two countable sets is always countable
• The Cartesian product of two countable sets is also countable
• A subset of a countable set is either finite or countable

Uncountable Sets and Their Properties

• An uncountable set has a cardinality greater than the set of natural numbers $\mathbb{N}$
• Uncountable sets are always infinite and cannot be put into a one-to-one correspondence with $\mathbb{N}$
• The set of real numbers $\mathbb{R}$ is an example of an uncountable set
• Other examples include the set of irrational numbers, the power set of $\mathbb{N}$, and the set of all functions from $\mathbb{R}$ to $\mathbb{R}$
• The union of a countable set and an uncountable set is always uncountable
• The Cartesian product of an uncountable set with any non-empty set is always uncountable
• The power set of an uncountable set is always uncountable
• Uncountable sets cannot be listed or enumerated, as there will always be elements left out

Comparing Set Sizes

• Two sets have the same cardinality if there exists a bijective function between them
• For finite sets, the cardinality is simply the number of elements in the set
• Infinite sets can have different cardinalities, such as countable and uncountable
• Cantor's theorem states that the power set of any set has a greater cardinality than the original set
  • This implies that there are infinitely many different sizes of infinite sets
• The continuum hypothesis states that there is no set with a cardinality between that of $\mathbb{N}$ and $\mathbb{R}$
  • This hypothesis is independent of the standard axioms of set theory (ZFC)
• The cardinality of the set of all subsets of a countable set is equal to the cardinality of $\mathbb{R}$

Cantor's Diagonal Argument

• Cantor's diagonal argument is a proof technique used to show that the set of real numbers $\mathbb{R}$ is uncountable
• The argument assumes that $\mathbb{R}$ is countable and then derives a contradiction
• It starts by assuming that all real numbers in the interval $[0, 1]$ can be listed in a sequence
• A new real number is constructed by changing the digit on the diagonal of the list
  • This new number differs from each number in the list by at least one digit
• The constructed number is a real number in $[0, 1]$ but is not in the original list
• This contradicts the assumption that all real numbers were listed, proving that $\mathbb{R}$ is uncountable
• The diagonal argument can be adapted to prove the uncountability of other sets, such as the power set of $\mathbb{N}$

Real-World Applications

• Countable and uncountable sets have applications in various fields, such as mathematics, computer science, and physics
• In probability theory, the concept of countability is used to define discrete and continuous probability spaces
• In computer science, the notion of computability is closely related to countable sets
  • Turing machines can only compute functions with countable domains and ranges
• The study of uncountable sets is crucial in understanding the foundations of mathematics and the limitations of formal systems
• In physics, the concept of uncountability arises in the study of quantum mechanics and the continuum of space-time
• Countable and uncountable sets are essential for understanding the nature of infinity and its role in various branches of mathematics

Common Misconceptions and FAQs

• Misconception all infinite sets have the same cardinality
  • In reality, there are different sizes of infinite sets, such as countable and uncountable
• Misconception the set of rational numbers $\mathbb{Q}$ is uncountable because it is dense in $\mathbb{R}$
  • Despite being dense, $\mathbb{Q}$ is countable, as it can be put into a one-to-one correspondence with $\mathbb{N}$
• FAQ Is the set of irrational numbers countable?
  • No, the set of irrational numbers is uncountable, as it has the same cardinality as $\mathbb{R}$
• FAQ Can an uncountable set contain a countable subset?
  • Yes, an uncountable set can contain countable subsets (the set of integers is a countable subset of $\mathbb{R}$)
• Misconception the union of countable sets is always countable
  • This is true for the union of finitely many countable sets, but the union of infinitely many countable sets can be uncountable
• FAQ Is the power set of a countable set always uncountable?
  • Yes, by Cantor's theorem, the power set of any set has a greater cardinality than the original set, so the power set of a countable set is uncountable