101.110
Introduction to the Mathematics of Sets

Learning Outcomes

By the end of this lesson, you should be able to:

• Understand and use basic set theory notation and terminology.
• Perform common set operations and understand their properties.
• Apply set theory concepts to solve mathematical and real-world problems.
• Appreciate the role of functions and relations in set theory.
• Be able to explain the concept of cardinality and its implications in mathematics.

Introduction

This lesson introduces sets in the context of discrete mathematics. It is an introduction only. We will start by defining what a set is. “Discrete Mathematics” is a branch of mathematics that deals with discrete elements, meaning it involves structures that are countable or otherwise distinctly separable. This is in contrast to continuous mathematics, which deals with objects that can vary smoothly and have no gaps or interruptions.

Learning about sets and set theory (i.e., set mathematics) is important for several reasons, particularly in the fields of discrete mathematics, computer science, relational theory, and a number of other disciplines. Here are some key reasons why sets and set theory are useful to learn:

1. Foundation of Modern Mathematics: Set theory provides the foundational language and framework for nearly all areas of modern mathematics. It offers a unifying structure for understanding and exploring mathematical concepts, allowing various branches of mathematics to be expressed in a common language.

2. Critical in Computer Science: In computer science, set theory is fundamental for understanding data structures, relational databases, relational algebra and calculus, algorithms, and network theory. It helps in modeling complex relationships and structures, which are essential for algorithm design, problem-solving, reasoning, and programming.

3. Logical Reasoning and Proof: Sets are essential for developing skills in logical reasoning and mathematical proof. Understanding set operations, relations, and functions is crucial in formulating and proving mathematical arguments rigorously.

4. Understanding Functions and Relations: Since functions and relations are defined in terms of sets, a strong grasp of set theory is essential for understanding these key mathematical concepts. This understanding is critical in advanced mathematics, including calculus and abstract algebra.

5. Applications in Various Fields: Set theory is not limited to mathematics and computer science; it finds applications in fields like economics, statistics, linguistics, and philosophy. It helps in structuring and analyzing complex systems and theories in these disciplines.

6. Problem Solving and Analysis: Learning about sets enhances problem-solving and analytical skills. It provides tools for abstract thinking and simplifying complex problems by breaking them down into manageable sets of elements.

7. Foundation for Further Mathematical Study: For students and researchers, a thorough understanding of set theory is often a prerequisite for studying more advanced topics in mathematics and related fields.

8. Real-world Modeling: Sets are used to model real-world situations and problems, such as grouping different objects, organizing data, and understanding relationships between different entities.

9. Abstract Thinking and Generalization: Set theory encourages abstract thinking and generalization, which are important skills in scientific inquiry and research.

10. Basis for Further Theoretical Developments: In mathematics, set theory has been the basis for further theoretical developments, including topology, measure theory, and more abstract fields like category theory.

In short, sets and set mathematics form the foundation of modern mathematics and computer science, providing essential tools and frameworks for understanding, modeling, and solving a wide range of theoretical and practical problems. Besides their practical value, their study also cultivates abstract thinking, logical reasoning, and a deeper understanding of the structures underlying various scientific and mathematical disciplines.

Key Concepts

Set

Sets are one of the most fundamental concepts in mathematics.

A set is a collection of distinct objects, considered as an object in its own right.

The objects in a set are called the elements, or members, of the set. Sets do not allow duplicates;although in some areas of computer science, we prefer the concept of a multiset or a bag which does allow duplicates.

A set can be defined by simply listing its members inside curly braces, although there are other ways to define sets, as we will see soon. For example, the set of natural numbers less than 4 can be written as {1, 2, 3}.

Sets can contain other sets making them a recursive structure. For example, a set containing sets is {{23,7},{12,14},{1,4},{30,8,67},{2}}.

The Cardinality of a set refers to the number of elements in a set. For example, the cardinality of the set {1, 2, 3} is 3.

Set Operations

2. Subsets: A set A is a subset of a set B if all elements of A are also elements of B. For instance, {1, 2} is a subset of {1, 2, 3}.

3. Union: The union of two sets A and B, written as A ∪ B, is the set of elements which are in A, in B, or in both A and B. For example, if A = {1, 2} and B = {2, 3}, then A ∪ B = {1, 2, 3}.

4. Intersection: The intersection of two sets A and B, written as A ∩ B, is the set of all objects that are members of both A and B. For example, if A = {1, 2} and B = {2, 3}, then A ∩ B = {2}.

5. Difference: The difference of two sets A and B, written as A - B, is the set of elements that are in A but not in B. For example, if A = {1, 2, 3} and B = {2, 3, 4}, then A - B = {1}.

6. Complement: The complement of a set A refers to elements not in A. If we’re considering sets within a universal set U, the complement of A is the set of elements in U that are not in A.

Types of Sets and Subsets

Empty Set

This is a set with no elements, denoted by ∅ or {}.

Power Set

The “power set” of a given set is a fundamental concept in set theory. It refers to the set of all possible subsets of that set, including both the empty set and the set itself. The power set is denoted as \(\mathcal{P}(S)\) for a set \(S\).

Key Characteristics of the Power Set:

1. Inclusion of All Subsets: The power set of \(S\) contains every subset of \(S\), including the subsets that have fewer elements than \(S\), as well as the empty set (∅) and \(S\) itself.

2. Cardinality: If a set \(S\) has \(n\) elements, then the power set of \(S\) will have \(2^n\) elements. This is because each element of \(S\) can either be included or not included in each subset, leading to \(2^n\) combinations.

3. Higher Order Set: The power set is a set of sets. Each of its elements is a set itself.

Example:

Consider a set \(A = \{1, 2\}\). The power set of \(A\) would include all the subsets of \(A\), which are:

• The empty set: \(\{\}\) or \(\emptyset\)
• The set containing only 1: \(\{1\}\)
• The set containing only 2: \(\{2\}\)
• The set containing both 1 and 2: \(\{1, 2\}\)

So, the power set of \(A\), denoted as \(\mathcal{P}(A)\), is \(\{ \emptyset, \{1\}, \{2\}, \{1, 2\} \}\).

Notation:

• The power set is denoted by \(\mathcal{P}(S)\), where \(S\) is the original set.
• Some texts may also use the notation \(2^S\) to denote the power set.

Importance in Mathematics:

• Theory: The concept of the power set is important in various areas of mathematics, including combinatorics, algebra, and topology.
• Applications: In computer science, the power set concept is used in algorithms, data structures, and database theory. It helps to understand computational complexity and algorithmic solutions that involve all possible combinations of a given set of elements.
• Logical and Theoretical Foundations: Power sets are also crucial in the foundations of mathematics, particularly in set theory and logic.

Understanding power sets is vital for grasping the nature of set operations and the relationships between sets. It provides a more profound insight into the structure and properties of sets, which is essential in advanced mathematical studies and various applications in computer science.

Proper Subset

A “proper subset” is a concept in set theory that describes a specific relationship between two sets. Given two sets, A and B, we say that A is a proper subset of B if every element of A is also in B, and there is at least one element in B that is not in A, i.e.,

\(A \subset B \iff \exists x | x \in B \land x \notin A\).

This relationship is denoted by A ⊂ B. The above says that A is a proper subset of B if and only if there exists at least on element x in B that is not an element in A.

Key Characteristics of a Proper Subset:

1. Inclusion of All Elements: For A to be a proper subset of B, every element in A must also be a member of B. This is similar to the condition for a subset.

2. At Least One Exclusive Element in the Superset: The set B must contain at least one element that is not in A. This is what differentiates a proper subset from a subset.

3. A is not Equal to B: If A were equal to B, then A would be a subset but not a proper subset of B. For A to be a proper subset, there must be an element in B that is not in A.

Examples:

1. Consider two sets A = {1, 2} and B = {1, 2, 3}. Here, A is a proper subset of B because every element of A is in B, and B has an additional element, 3, that is not in A.

2. If A = {1, 2, 3} and B = {1, 2, 3}, then A is not a proper subset of B. A is a subset of B, but since there are no extra elements in B that are not in A, it’s not a proper subset.

Notation:

The notation A ⊂ B is used to indicate that A is a proper subset of B. It’s important to note that some texts use this symbol to mean subset (including the possibility of A being equal to B), but the most common use is to denote a proper subset.

Comparison with Subset:

The term “subset” includes the possibility that the two sets are equal (i.e., A can be equal to B). In contrast, “proper subset” explicitly excludes the possibility of the sets being equal. So, every proper subset is a subset, but not every subset is a proper subset.

Understanding the concept of proper subsets is important for analyzing set relations and is a fundamental part of set theory, with applications in various areas of mathematics, logic, and computer science.

Finite vs Infinite Sets

The difference between finite and infinite sets is a fundamental concept in set theory, distinguishing between sets based on the number of elements they contain.

Finite Sets

A set is considered finite if it contains a countable number of elements, and it’s possible to list all elements in the set. The key characteristic of a finite set is that there is a specific, finite number of elements in the set.

• Example: The set of all fingers on a human hand, \(\{ thumb, index, middle, ring, little \}\), is a finite set because we can count and list each element, and there are exactly five elements in this set.

Infinite Sets

An infinite set, on the other hand, is a set that has an unlimited, or infinite, number of elements. It’s not possible to list all the elements of an infinite set, as there is no “last” element.

• Example: The set of all natural numbers \(\mathbb{N} = \{1, 2, 3, 4, 5, \ldots\}\) is an infinite set. No matter how high you count, there is always another number that follows, making the set endless.

Key Differences

1. Number of Elements:
   • Finite sets have a specific number of elements (which can be zero in the case of the empty set).
   • Infinite sets do not have a specific number of elements, and their size is not countable in a practical sense.
2. Listability:
   • In a finite set, it is possible to list all the elements.
   • In an infinite set, you cannot list all elements, as they continue indefinitely.
3. End Element:
   • Finite sets have a definite, last element when listed.
   • Infinite sets do not have an end element.
4. Cardinality:
   • The cardinality (or size) of a finite set is a non-negative integer.
   • Infinite sets have a cardinality that is not representable by a standard integer. In mathematics, different sizes of infinity, such as countable and uncountable infinity, are studied.
5. Examples in Mathematics:
   • Common examples of finite sets include the set of students in a classroom, the set of letters in a word, etc.
   • Examples of infinite sets include the set of natural numbers, the set of real numbers, and the set of points on a line.

Understanding the distinction between finite and infinite sets is crucial in many areas of mathematics and computer science, especially in the study of algorithms, number theory, and combinatorics. Infinite sets introduce the concept of infinity, which is a fundamental and intriguing aspect of higher mathematics.

Set Definition Methods

Sets can be defined in several ways, each catering to different contexts and requirements in mathematics. Here are some common methods of defining sets:

1. Roster or Tabular Form: In this method, all the members (elements) of the set are listed, usually enclosed in curly braces. The order of elements does not matter, and each element is listed only once. For example, the set of vowels in the English alphabet can be defined as \(A = \{ a, e, i, o, u \}\).

2. Set Builder Notation: This is a more concise way of defining sets, especially useful when the set is too large to list all elements or when the set is defined by a property shared by its members. It typically involves a variable, a condition, and curly braces. For example, the set of all positive even numbers can be defined as \(B = \{ x \mid x \text{ is a positive even number} \}\), where \(x\) is an element of the set, and the condition is that \(x\) must be a positive even number.

3. Intervals: This method is used for sets of numbers and is especially useful for continuous sets. Intervals can be closed (including the endpoints) or open (excluding the endpoints). For example, the set of all real numbers between 1 and 3 can be defined as \((1, 3)\) for an open interval, or \([1, 3]\) for a closed interval.

4. Description or Rule Method: Here, a set is defined by a clear description or a rule. This method is used when listing elements or using set-builder notation is not efficient. For example, the set of all planets in the solar system can be defined as “the set of all celestial bodies orbiting the sun that are recognized as planets by the International Astronomical Union.”

5. Using Venn Diagrams: While this is more of a visual representation than a definition per se, Venn diagrams are often used to depict sets, especially to show relationships among different sets like intersections, unions, and differences.

6. Predicate Notation: In more advanced contexts, sets can be defined using predicates, which are logical statements that return true or false. For example, \(C = \{ x \in \mathbb{Z}^{+} \mid P(x) \}\), where \(\mathbb{Z}^{+}\) is the set of positive integers, and \(P(x)\) is a predicate or property that elements of the set must satisfy.

7. Recursive Definition: Some sets, particularly in computer science, are defined recursively. This means that the definition of the set refers back to itself. This is common in defining sequences, trees, and other structures in theoretical computer science.

Each of these methods has its own place and utility depending on the nature of the elements of the set and the context in which the set is being used.

Predicates

In the context of set theory and discrete mathematics, a predicate is a logical expression that describes a property or condition and can be evaluated as true or false for each element in a set. Essentially, predicates are functions that return a Boolean value (true or false) and are used to test whether a given condition holds for elements of a set.

Here are some key points about predicates in this context:

1. Formulation: A predicate is often formulated as a statement or formula involving variables. For example, the predicate \(P(x)\) might represent the statement “x is an even number.” When we substitute a specific value for \(x\), the predicate becomes a statement that can be judged as true or false.

2. Usage in Set Builder Notation: Predicates are commonly used in set builder notation to define sets. For example, the set of all even integers greater than 10 can be defined as \(\{ x \in \mathbb{Z} \mid x > 10 \text{ and } P(x) \}\), where \(P(x)\) is the predicate “x is an even number,” and \(\mathbb{Z}\) represents the set of all integers.

3. Role in Logic and Mathematics: Predicates play a crucial role in mathematical logic and form the basis of predicate logic. They are used to express more complex logical formulations, such as implications, equivalences, and quantified statements.

4. Quantifiers: In conjunction with predicates, quantifiers like “for all” (denoted by \(\forall\)) and “there exists” (denoted by \(\exists\)) are used. For example, \(\forall x \in \mathbb{N}, P(x)\) means “for all natural numbers \(x\), \(P(x)\) is true,” whereas \(\exists x \in \mathbb{N}\) such that \(P(x)\) means “there exists at least one natural number \(x\) for which \(P(x)\) is true.”

5. Application in Proofs: In mathematical proofs, especially in discrete mathematics, predicates are often used to formalize statements that need to be proved or disproved. They help in structuring arguments logically and precisely.

In short, predicates are fundamental in set theory and discrete mathematics, providing a way to express properties and conditions for set elements, formulating logical statements, and facilitating rigorous mathematical reasoning and proofs.

Special Sets in Mathematics

Natural Numbers

The set of natural numbers, denoted by the symbol \(\mathbb{N}\) is the set of positive integers starting from 1 and continuing indefinitely in an increasing manner. Can alternatively be defined as \(\mathbb{N} = \{1,2,3,4, \ldots\}\).

Natural numbers are the basic counting numbers used in everyday life and are a fundamental part of mathematics. They are the set of positive integers starting from 1 and continuing indefinitely in an increasing manner. The set of natural numbers is usually denoted by the symbol \(\mathbb{N}\).

Key Characteristics of Natural Numbers:

1. Starting Point: Natural numbers start from 1 (1, 2, 3, 4, 5, …). Some mathematical definitions include 0 in the set of natural numbers, but traditionally it starts from 1.

2. Positive Integers: They are all positive and do not include negative numbers, fractions, or decimals.

3. Counting: Natural numbers are used for counting objects. For instance, when you count the number of books on a shelf, you use natural numbers.

4. Infinity: The set of natural numbers is infinite; it has no upper limit.

5. Discreteness: Natural numbers are discrete, meaning there are no fractions or decimals between them.

6. Fundamental in Mathematics: They form the basis for more complex number systems, including integers, rational numbers, and real numbers.

In mathematical notation, the set of natural numbers is often represented as follows:

\[ \mathbb{N} = \{1, 2, 3, 4, 5, \ldots\} \]

Natural numbers are foundational in various branches of mathematics, including arithmetic, number theory, and are widely used in everyday life for counting and ordering objects.

Integers

The set of integers, denoted by (**\(\mathbb{Z}\)), including positive, negative, and zero. The symbol comes from the German word for numbers: Zahlen.

Rational Numbers

Rational numbers are numbers that can be expressed as the quotient or fraction \(\frac{p}{q}\) of two integers, where the numerator \(p\) is an integer and the denominator \(q\) is a non-zero integer. Essentially, a rational number represents a ratio between two integers.

Key Characteristics of Rational Numbers:

1. Fractional Form: They can always be expressed as fractions.

2. Include Integers: All integers are rational numbers since any integer \(z\) can be expressed as \(\frac{z}{1}\).

3. Decimal Representation: Rational numbers can be represented as either terminating decimals or repeating decimals.

4. Density: Between any two rational numbers, there’s another rational number. This property is known as the density of rational numbers.

5. Negative Numbers: The set of rational numbers includes both positive and negative numbers, as well as zero.

Symbol for Rational Numbers:

The set of rational numbers is denoted by the symbol \(\mathbb{Q}\). The letter “Q” stands for “quotient,” reflecting the fact that any rational number represents the quotient of two integers.

Examples:

• \(\frac{1}{2}\), \(\frac{5}{3}\), and \(-\frac{4}{7}\) are rational numbers.
• All integers are rational numbers, for example, 7 (which is the same as \(\frac{7}{1}\)).
• Numbers like 0.75 (which is \(\frac{3}{4}\)) and 0.333… (which is \(\frac{1}{3}\)) are also rational.

In mathematical notation, the set of rational numbers can be represented as:

\[ \mathbb{Q} = \left\{ \frac{p}{q} \mid p, q \in \mathbb{Z}, q \neq 0 \right\} \]

Where \(\mathbb{Z}\) denotes the set of all integers. Rational numbers play a crucial role in mathematics, bridging the gap between integers and the more comprehensive set of real numbers.

Irrational Numbers

Irrational numbers are a type of real number that cannot be expressed as a simple fraction - that is, the ratio of two integers. The defining characteristic of an irrational number is that its decimal representation is non-terminating and non-repeating. This means it goes on forever without repeating a pattern.

Key Characteristics of Irrational Numbers:

1. Non-representable as Fractions: Unlike rational numbers, you cannot express irrational numbers as a fraction of two integers.

2. Non-terminating, Non-repeating Decimals: In decimal form, these numbers never end and do not display a repeating pattern of digits.

3. Cannot be Exactly Calculated: The exact value of an irrational number cannot be precisely calculated or written down in decimal form.

4. Examples: Famous examples include:

   • Pi (π), the ratio of the circumference of a circle to its diameter.
   • Euler’s number (e), the base of natural logarithms.
   • The square root of a non-perfect square number (like √2, √3, etc.).

5. Real Numbers: All irrational numbers are real numbers but they are not rational numbers.

Symbol for Irrational Numbers:

There is no standard symbol universally used to denote the set of all irrational numbers. However, sometimes the set is represented as the set difference of the real numbers and the rational numbers, which can be notated as \(\mathbb{R} \setminus \mathbb{Q}\). This notation reflects that irrational numbers include all real numbers that are not rational.

Inclusion in the Number System:

Irrational numbers, along with rational numbers, make up the real numbers, \(\mathbb{R}\). The discovery of irrational numbers was significant in mathematics as it expanded the understanding of numerical concepts beyond the simple ratios of integers.

Significance:

Irrational numbers are essential in various areas of mathematics and applied sciences. They often appear in formulas, geometric measurements, and calculations where exact precision is required beyond the limitation of rational numbers. They are fundamental in understanding the continuum of real numbers and play a crucial role in advanced mathematics, including calculus and mathematical analysis.

Real Numbers

Real numbers are the set of numbers that include both the rational numbers (such as integers and fractions) and the irrational numbers (such as \(\sqrt{2}\), \(\pi\), and \(e\)). They form a continuum of numbers that can represent any quantity along a continuous line, known as the number line.

Key Characteristics of Real Numbers:

1. Inclusivity: The set of real numbers includes:

   • All rational numbers, which can be expressed as fractions or decimals that either terminate or repeat.
   • All irrational numbers, which cannot be expressed as fractions and have non-terminating, non-repeating decimal representations.

2. Representation on the Number Line: Every point on the number line corresponds to a unique real number. This includes both positive and negative numbers, as well as zero.

3. Complete and Continuous: The real numbers are complete, meaning they contain all the limit points, and are continuous, with no gaps between the numbers.

4. Decimal Expansion: Every real number can be expressed as an infinite decimal expansion.

5. Arithmetic Operations: The set of real numbers is closed under addition, subtraction, multiplication, and division (except division by zero).

Symbol for Real Numbers:

The set of real numbers is denoted by the symbol \(\mathbb{R}\).

Examples:

• Rational numbers like \(-3\), \(\frac{1}{2}\), and \(4.75\) are real numbers.
• Irrational numbers like \(\sqrt{2}\), \(\pi\), and \(e\) are also real numbers.
• All integers and natural numbers are included in the set of real numbers.

Importance:

Real numbers are fundamental in mathematics and are used to measure continuous quantities such as distance, time, and temperature. They form the basis of calculus and analysis and are essential for describing the physical world in sciences and engineering. The concept of real numbers allows for precise and comprehensive descriptions of quantities in a wide range of mathematical, physical, and practical applications.

Tutorial

None yet.

Practice Questions

Question 1

What are the cardinalities of the following sets:

1. {A,F,G,X}
2. {‘Goldwasser’,‘Knuth’,‘Codd’}
3. \(\{ x \in \mathbb{Z}^{+} \mid (x \% 2 = 0) \}\) where % is the modulus operator
4. {{33,2},{334,{p,q,r}}}
5. {}

Question 2

Define the set of all real positive numbers.

Question 3

Define a set that includes four digit whole numbers that are greater than 0.

---

Files & Resources

All Files for Lesson 101.110

---

References

None yet.

Errata

Let us know.