3.1 Introduction
TLDR: This chapter introduces set theory, starting with an intuitive understanding of sets as collections of objects. However, it immediately highlights the limitations of a naive approach to set theory by presenting Russell’s paradox, which demonstrates the need for a more rigorous axiomatic foundation.
3.1.1 An Intuitive Understanding of Sets
Definition (Informal):
A set is a well-defined collection of distinct objects. These objects are called the elements or members of the set. We use curly braces {}
to denote sets.
Examples:
-
Example 3.1: The set of all even numbers: . Note: This is an infinite set, represented using an ellipsis to suggest continuation of the pattern.
-
Example 3.1: The set of vowels in the English alphabet: . This is a finite set.
-
Example 3.1: The set of prime numbers less than 10: . This is also a finite set.
-
Notation: means that is an element of set . means that is not an element of .
Set Cardinality (Informal):
The cardinality of a finite set is the number of elements it contains. We denote it as .
Examples:
- Example 3.1:
- Example 3.1:
3.1.2 Russell’s Paradox
Russell’s paradox demonstrates the inconsistency of naive set theory, where any definable collection of objects is considered a set. This paradox highlights the need for a more rigorous axiomatic approach.
The Paradox:
Consider the set defined as:
.
This attempts to define R as the set of all sets that do not contain themselves as members. Let’s analyze this:
-
Case 1: If R is a member of itself, then by the definition of R, it must not be a member of itself, which is a contradiction.
-
Case 2: If R is not a member of itself, then by the definition of R, it should be a member of itself, which is another contradiction.
Resolution:
This contradiction arises from the unrestricted definition of sets. The naive set theory assumes that any property can be used to define a set. Russell’s paradox shows this assumption is false. It illustrates the need for a formal axiomatic system for set theory (e.g., Zermelo-Fraenkel set theory) that prevents the construction of self-contradictory sets like R. Axiomatic set theory carefully restricts how sets are defined, avoiding such paradoxes.
Additional Examples and Considerations:
-
Example illustrating the need for well-defined sets: The collection of “all large numbers” is not a well-defined set. “Large” is subjective and does not create a definite boundary that determines which numbers are and aren’t included. A precise definition of the property that defines the collection is needed to create a well-defined set.
-
The importance of axioms in set theory: Axiomatic set theories (like Zermelo-Fraenkel set theory or von Neumann-Bernays-Gödel set theory) lay down specific rules for creating sets. These axioms prevent the creation of contradictory sets like Russell’s R and provide a solid foundation for the study of sets.
3.2 Sets and Operations on Sets
TLDR: This chapter introduces sets as unordered collections of unique elements, defines set equality, and explores fundamental set operations (union, intersection, difference, power set, Cartesian product). It also shows how to construct the natural numbers from the empty set and the successor operation.
3.2.1 The Set Concept
A set is an unordered collection of distinct objects. We represent sets using curly braces {}
. The objects within a set are called its elements. Order and repetition of elements are irrelevant.
Example 3.1:
The set of prime numbers less than 10 is . The set represents the same set. The set also represents the same set (repeated elements are ignored).
3.2.2 Set Equality and Constructing Sets From Sets
Set Equality:
Two sets, A and B, are equal () if and only if they contain exactly the same elements. This is the axiom of extensionality. The manner in which the sets are described is irrelevant.
Constructing Sets from Sets:
We can create new sets from existing ones. This is an important process and foundational to set theory.
Examples:
- We can create a singleton set, which is a set containing only one element: .
- We can create sets with multiple elements: .
3.2.3 Subsets
Definition:
A set is a subset of a set () if every element of is also an element of . is a proper subset of () if and .
Example 3.3:
. is a subset of . is also true, but not a proper subset. because every element of is in , and the sets are not identical.
3.2.4 Union and Intersection
Definitions:
-
Union (): The union of sets and , denoted , is the set containing all elements found in either or (or both): .
-
Intersection (): The intersection of sets and , denoted , is the set containing only the elements common to both and : .
Examples:
- Example 3.2: Let and . Then and .
3.2.5 The Empty Set
Definition:
The empty set, denoted or , is the unique set containing no elements. For any element , .
Lemma 3.5:
There is only one empty set.
Proof: (Indirect) Assume there are two distinct empty sets, and . By the definition of an empty set, and contain no elements. Since they have the same elements (none), by the axiom of extensionality. This contradiction shows that only one empty set can exist.
Lemma 3.6:
The empty set is a subset of every set: .
Proof: (Indirect) Suppose there exists a set such that . This implies there is at least one element such that and . However, by the definition of the empty set, there are no such elements . This contradiction proves that the empty set is a subset of every set.
More rigorously:
3.2.6 Constructing Sets from the Empty Set
The empty set is a foundational concept. Using only set-theoretic operations, we can build any set starting with the empty set. This is often demonstrated through the construction of the natural numbers (see below).
3.2.7 A Construction of the Natural Numbers
The natural numbers can be constructed recursively from the empty set using the successor function.
Definitions:
- Zero (0): Defined as the empty set, .
- Successor Function (s): For a set , its successor is .
Construction:
- …and so on.
Each natural number is defined as a set containing all previous numbers in the sequence. The cardinality of each set corresponds to the number it represents.
3.2.8 The Power Set of a Set
Definition:
The power set of a set , denoted or , is the set of all subsets of : .
Example 3.5:
If , then . Note that , where denotes the cardinality of A.
3.2.9 The Cartesian Product of Sets
Definition:
The Cartesian product of sets and , denoted , is the set of all possible ordered pairs where and : .
Example 3.7:
If and , then . Note that the order matters in ordered pairs: unless . Also, .
3.3 Relations
TLDR: This chapter defines relations as sets of ordered pairs and explores various ways to represent and manipulate them. It introduces fundamental operations on relations (union, intersection, inverse, composition) and examines key properties (reflexive, symmetric, transitive), culminating in the concept of transitive closure. Equivalence relations, a special type of relation possessing all three properties are discussed as well.
3.3.1 The Relation Concept
Definition:
A relation from a set (the domain) to a set (the codomain) is a subset of the Cartesian product , i.e., . Each element of is an ordered pair where and . If , is a relation on . We write to denote .
Examples:
-
Example 3.8: Let be a set of students and be a set of courses. The relation “takes” where if student is taking course .
-
Example 3.9: On the set of all people, we can define relations like “parent of,” “child of,” “sibling of,” “married to,” etc. Each such relation is a subset of (People × People).
-
Example 3.10: On the set of integers, we have relations like , , , , , , (divides), (does not divide). Each of these is a subset of (Integers × Integers).
-
Example 3.11: The relation (congruence modulo m) on the integers, where if and have the same remainder when divided by . This relation is defined as .
-
Example 3.12: The relation on the set of real numbers represents the set of points on the unit circle (a subset of ).
-
Example 3.13: For any set , the subset relation is a relation on the power set (the set of all subsets of ).
3.3.2 Representations of Relations
Relations can be represented in several ways:
-
List of Ordered Pairs: Explicitly listing all the ordered pairs in the relation (Example 3.12).
-
Diagram: A visual representation using nodes representing elements from the domain and codomain, with arrows (directed edges) to show the relation. Useful for small sets.
-
Matrix: A Boolean matrix where the rows and columns correspond to elements of the domain and codomain, respectively. A 1 in row and column indicates that the pair (, ) is in the relation, and 0 indicates that it is not. This is especially useful for finite sets.
Examples:
Let and .
- Example 3.15: For the relation , the matrix representation is:
R 1 2 3
a 1 1 0
b 0 0 1
c 1 0 1
3.3.3 Set Operations on Relations
Since relations are sets, we can apply standard set operations:
-
Union (): . The union of two relations contains all pairs from either relation.
-
Intersection (): . The intersection contains only pairs common to both relations.
-
Complement (): . The complement contains all pairs in that are not in .
3.3.4 The Inverse of a Relation
Definition:
The inverse of a relation , denoted or , is obtained by swapping the elements in each ordered pair. Formally, .
Examples:
-
Example 3.19: If is the “owns” relation from the set of people to the set of objects, then is the “is owned by” relation.
-
Example 3.20: If is the “parent of” relation, is the “child of” relation.
-
Example 3.21: The inverse of the relation on integers is the relation .
3.3.5 Composition of Relations
Definition:
Let be a relation from to , and a relation from to . The composition of and , denoted , is the relation from to such that if and only if there exists some such that and . Formally, .
Lemma 3.7 (Associativity of Relation Composition):
. The composition of relations is associative.
Proof:
We need to show that . Let’s consider one direction:
Assume . Then . This means . Thus . But this means . This implies , which means . The opposite direction is shown similarly.
3.3.6 Special Properties of Relations
Relations can have several special properties that define important classes of relations:
1. Reflexive:
A relation on a set is reflexive if every element is related to itself: . This means that the identity relation .
Examples:
- The relation “equals” () is reflexive.
- The relation "" (less than or equal to) is reflexive.
- The relation "" is reflexive.
- The relation “divides” on integers is reflexive.
2. Symmetric:
A relation on is symmetric if whenever is related to , then is also related to : .
Examples:
- The relation “equals” () is symmetric.
- The relation “is a sibling of” is symmetric.
- The relation “is married to” is symmetric.
- The relation "" (congruence modulo m) is symmetric.
3. Transitive:
A relation on is transitive if whenever is related to and is related to , then is related to : .
Examples:
- The relation “equals” () is transitive.
- The relation "" (less than or equal to) is transitive.
- The relation "" is transitive.
- The relation “is an ancestor of” is transitive.
- The relation “divides” on integers is transitive.
- The relation "" (congruence modulo ) is transitive.
4. Antisymmetric:
A relation on is antisymmetric if whenever is related to and is related to , then and are the same element: . Note that this does not mean that the relation is not symmetric.
Examples:
- The relation "" (less than or equal to) is antisymmetric.
- The relation "" is antisymmetric.
- The relation “is a subset of” () is antisymmetric.
- The relation “divides” on positive integers is antisymmetric. (If a divides b and b divides a, then a = b).
5. Asymmetric:
A relation on is asymmetric if whenever is related to , then is not related to : . Note that this is different from “not symmetric”. A relation can be neither symmetric nor asymmetric.
Examples:
- The relation (strictly less than) on integers is asymmetric.
- The relation (strictly greater than) on integers is asymmetric.
- The relation “is a parent of” is asymmetric (generally ; we assume that there are no instances of an individual being their own parent).
3.3.7 Transitive Closure
Definition:
The transitive closure of a relation on a set is the smallest transitive relation containing . It’s essentially all pairs such that there exists a sequence where each consecutive pair is in .
Example:
Consider the relation . The transitive closure is .
3.4 Equivalence Relations
TLDR: This section defines equivalence relations as relations that are reflexive, symmetric, and transitive. It proves that an equivalence relation partitions a set into disjoint equivalence classes, illustrating this with the construction of rational numbers as an example.
3.4.1 Definition of Equivalence Relations
Definition 3.19:
An equivalence relation on a set is a binary relation that satisfies three properties for all elements , , and in :
-
Reflexivity: (Every element is related to itself).
-
Symmetry: If , then (If is related to , then is related to ).
-
Transitivity: If and , then (If is related to , and is related to , then is related to ).
Examples:
-
Example 3.31: The equality relation "" on any set is an equivalence relation. For all , (reflexive), if , then (symmetric), and if and , then (transitive).
-
Example 3.32: The congruence modulo relation () on integers is an equivalence relation. For integers , , and :
- Reflexivity: because .
- Symmetry: If (meaning ), then , so .
- Transitivity: If () and (), then , so .
-
Example 3.33: On the set of points in the plane, define a relation such that two points are related if they lie on the same line parallel to the line . This is an equivalence relation:
- Reflexivity: A point always lies on the same line parallel to y = -x that passes through itself.
- Symmetry: If points and lie on the same line parallel to y = -x, then and lie on the same line parallel to y = -x.
- Transitivity: If points and lie on the same line parallel to y = -x, and points and lie on the same line parallel to y = -x, then points and must lie on the same line parallel to y = -x.
The Intersection of Equivalence Relations
Lemma 3.10: The intersection of two equivalence relations on the same set is also an equivalence relation.
Proof:
Let and be two equivalence relations on a set . We need to show that their intersection, denoted by , is also an equivalence relation. To do this, we need to prove that satisfies reflexivity, symmetry, and transitivity.
-
Reflexivity: For any , since and are equivalence relations, we have and . Therefore, , demonstrating reflexivity for .
-
Symmetry: Let such that . By definition of intersection, this means and . Since and are symmetric, we also have and . Therefore, , demonstrating symmetry for .
-
Transitivity: Let such that and . This implies , , , and . Because and are transitive, we have and . Therefore, , demonstrating transitivity for .
Since satisfies reflexivity, symmetry, and transitivity, it is an equivalence relation. Therefore, Lemma 3.10 is proven.
Example 3.34 (Illustrative):
Consider the equivalence relations (congruence modulo 3) and (congruence modulo 5) on the set of integers . Their intersection, , is the equivalence relation (congruence modulo 15). This demonstrates Lemma 3.10 in a concrete case. Each equivalence class in is a subset of an equivalence class in both and .
3.4.2 Equivalence Classes Form a Partition
Definition 3.21:
A partition of a set is a collection of non-empty, pairwise disjoint subsets (called cells or blocks) of whose union is .
Theorem 3.11:
Given an equivalence relation on a set , the equivalence classes of form a partition of .
Proof:
Let be an equivalence relation on . The equivalence class of an element is defined as . (We can drop the subscript if the relation is clear.)
-
Every element belongs to at least one equivalence class: By reflexivity (), belongs to its own equivalence class . Therefore, .
-
Equivalence classes are disjoint: Suppose for some . This means there exists an element such that and . By definition, and . By symmetry, . By transitivity, . Now, if , then . Since and , we have by transitivity, thus , which means . A similar argument shows . Therefore, . Thus, any two equivalence classes are either identical or disjoint.
-
Therefore, the set of equivalence classes forms a partition of .
3.4.3 Example: Definition of the Rational Numbers
The set of rational numbers, , can be elegantly defined using equivalence classes.
Construction:
-
Universe: Consider the set of ordered pairs of integers . An element intuitively represents the fraction .
-
Equivalence Relation: We define the relation on as follows: .
-
Proof that ~ is an equivalence relation:
- Reflexivity: because .
- Symmetry: If , then . This implies , so .
- Transitivity: If () and (), then . Since , we can divide both sides to obtain , implying . The case where is not possible because implies .
-
Rational Numbers as Equivalence Classes: The rational numbers are defined as the set of equivalence classes of : . Each equivalence class represents a rational number, often denoted as . Note that many different pairs can represent the same rational number (e.g., (1,2), (2,4), (-1,-2) all represent the same rational number).
This construction provides a rigorous and elegant mathematical definition of rational numbers using the concept of equivalence relations and partitions.
3.5 Partial Order Relations
TLDR: This section defines partial order relations, which are reflexive, antisymmetric, and transitive. It introduces Hasse diagrams as a visual representation of partial orders, explores how to combine partial orders (posets) using lexicographical order, and defines special elements within posets (minimal, maximal, least, greatest) and lattice structures (meet, join).
3.5.1 Definition
A partial order is a binary relation, ≤, on a set that satisfies three properties:
-
Reflexivity: For all , . (Every element is related to itself).
-
Antisymmetry: For all , if and , then . (If two elements are related in both directions, they must be the same element).
-
Transitivity: For all , if and , then . (If is related to , and is related to , then is related to ).
A set with a partial order ≤ is called a partially ordered set (poset), denoted . Note that a partial order doesn’t necessarily relate every pair of elements in . Some elements may be incomparable.
3.5.2 Hasse Diagrams
A Hasse diagram provides a visual representation of a finite poset. It simplifies the representation by omitting:
- Reflexive edges: Edges from a node to itself (since reflexivity is implied).
- Transitive edges: If and , the edge between and is implied and omitted.
The diagram uses the vertical positioning of nodes to indicate the ordering: Higher nodes represent larger elements in the partial order.
Example 3.42:
The Hasse diagram for the poset (where ”|” denotes the “divides” relation) is shown in the textbook figure. This shows that , etc., with no explicit transitive relationships (e.g., and , but only is explicitly shown).
Example 3.43:
The Hasse diagram for is shown in the textbook figure. This illustrates a more complex poset with multiple levels of divisibility.
Example 3.44:
The Hasse diagram for (where represents the power set of , and denotes the subset relation) illustrates another type of poset, where subsets are ordered by the subset relationship.
Example 3.45:
This example is an exercise ; you are given two Hasse diagrams and asked to identify integer sets with the divisibility relationship that would produce these diagrams. This requires constructing sets of integers where the divisibility relation creates the same structure as in the diagrams.
The first diagram could be something like and the second could be something like
3.5.3 Combinations of Posets and the Lexicographic Order
We can create new posets by combining existing ones. One method is the lexicographical order:
Definition 3.28: Lexicographical Order
Given two posets and , their lexicographical product is the poset , where:
This definition says that is less than or equal to if either is strictly less than according to , or if and are equal, and is less than or equal to according to . This is analogous to how words are ordered lexicographically in a dictionary.
Theorem 3.12: The Lexicographical Product of Two Posets is a Poset
Statement: Given two posets and , their lexicographical product is also a poset, where the lexicographical order is defined as:
Proof: We need to show that is reflexive, antisymmetric, and transitive.
-
Reflexivity: For any , we have because and (since is reflexive).
-
Antisymmetry: Let . Suppose and . We need to show that .
-
From , we have either or ( and ).
-
From , we have either or ( and ).
-
If , then cannot be less than or equal to (by antisymmetry of ). Thus, we must have and and . Then, by the antisymmetry of , . Therefore .
-
-
Transitivity: Let . Suppose and . We need to show that .
-
Case 1: . Since is transitive, if and , then . If , then by the definition of . If , then , and the only possibility is that and then and , which implies because is transitive. Then .
-
Case 2: and . If , then by the definition of . If (hence ), then and , which means . Therefore .
-
Since satisfies reflexivity, antisymmetry, and transitivity, is a poset.
Theorem 3.13: A Different Combination Yielding a Partial Order
Statement: For given posets and , the relation defined on by:
is a partial order relation.
Proof: This proof is very similar to the previous one and again involves showing reflexivity, antisymmetry, and transitivity.
-
Reflexivity: This follows directly from the reflexivity of and because for all since and .
-
Antisymmetry: If and , then the only way this can be true is if and and . By antisymmetry of , . Therefore .
-
Transitivity: Suppose and . We need to show .
-
If , then since , by transitivity of , we have , so .
-
If and , then if , we again have and . If , then and and , which implies (transitivity of ), and therefore .
-
Therefore, is a partial order.
3.5.4 Special Elements in Posets
Consider a poset . Certain elements have special properties based on the relationship ≤:
Definitions:
-
Minimal Element: An element is minimal if there’s no such that ( and ). There can be multiple minimal elements.
-
Maximal Element: An element is maximal if there’s no such that . There can be multiple maximal elements.
-
Least Element: An element is the least element if for all . There can only be at most one least element.
-
Greatest Element: An element is the greatest element if for all . There can only be at most one greatest element.
Example 3.47:
This example, using the Hasse diagram from Example 3.42, illustrates minimal, maximal, least, and greatest elements within that poset (Note: the example specifies that 2, 3, 5, and 7 are minimal elements, and 5, 6, 7, 8, and 9 are maximal elements in Figure 3.1. There is no least element nor greatest element).
Example 3.48:
This example, using the Hasse diagram from Example 3.43, demonstrates a poset with both a least and a greatest element. This involves finding the greatest lower bound and least upper bound of particular subsets.
Example 3.49:
This example examines the poset , which is shown in the Hasse diagram from Example 3.44. It is shown to have both a least and a greatest element.
Example 3.50:
The example highlights that a poset may have a least element but not a greatest element (or vice-versa). This is shown by analyzing , where are the positive integers and is the “divides” relation. is the least element.
3.5.5 Meet, Join, and Lattices
These concepts describe special relationships between elements in a poset:
Definitions:
-
Meet (): The meet of two elements and in a poset is their greatest lower bound. That is, the largest element such that and .
-
Join (): The join of two elements and in a poset is their least upper bound. That is, the smallest element such that and .
-
Lattice: A poset is a lattice if every pair of elements has both a meet and a join.
Example 3.51:
This example shows that , , and (where is any set) are lattices.
Example 3.52:
The example (from above) is a lattice where the meet is the greatest common divisor and the join is the least common multiple. The example also shows that is not a lattice (because some pairs lack either a meet or join).
3.6 Functions
TLDR: This section defines functions as a specific type of relation where each element in the domain maps to exactly one element in the codomain. It distinguishes between total and partial functions, injective, surjective, and bijective functions, and introduces function composition and the concept of the image and preimage of a set under a function.
Definition of a Function
A function, , from a set (the domain) to a set (the codomain), denoted , is a relation satisfying two properties:
-
Totality: Every element in the domain is mapped to at least one element in the codomain. . We often write this as .
-
Uniqueness: Every element in the domain is mapped to at most one element in the codomain. . We often write this as .
A function maps each input () to a unique output (). The notation indicates that the function maps the element to the element .
Total Function
A total function is a function where every element in the domain is mapped to exactly one element in the codomain. There are no “undefined” values in the domain ; every input has an output.
Example: Let be defined by . This is a total function because every real number has a unique square. The image of this function is (all non-negative real numbers).
Partial Function
A partial function is a relation that satisfies the uniqueness property of functions but not necessarily the totality property. This means that some elements in the domain may not be mapped to any element in the codomain. In other words, there may be some inputs for which the function is undefined.
Example: Let be defined by . This is a partial function because it is undefined at . The function is not defined for every .
Special Types of Functions
Functions can be further categorized:
Injective Function (One-to-One)
A function is injective (or one-to-one) if different elements in the domain map to different elements in the codomain:
(note for injective functions we can restate it as the converse too)
Example:
Let be defined by . This is injective because if , then .
Surjective Function (Onto)
A function is surjective (or onto) if every element in the codomain is the image of at least one element in the domain:
Example:
Let be defined by . This is surjective because every non-negative real number is the square of some real number.
Bijective Function
A function is bijective if it is both injective and surjective. This means there’s a one-to-one correspondence between the elements of the domain and codomain.
Example:
Let be defined by . This is a bijective function.
Function Composition
Given functions and , their composition, denoted or simply , is a function defined by . Function composition is associative, meaning . Not that by convention we don’t use the “relation composition” order but the “function composition” order (which is in reverse).
Example 3.55:
Let and . Then .
Image and Preimage
For a function and a subset , the image of under is . For a subset , the preimage of under is .
Example 3.53:
Consider again . (the image of the interval ). (the preimage of ).
Additional Considerations
-
Set of Functions: The set of all functions from a set to a set is denoted as . If and are finite, .
-
Function as Relations: A function is a special kind of relation. We defined a function in terms of relations (ordered pairs). The notation is a shorthand for .
-
Inverse Function: Only bijective functions have an inverse function, denoted . The inverse function satisfies for all and for all .
These additional points provide a more comprehensive understanding of functions within the context of set theory and relations.
3.7 Countable and Uncountable Sets
TLDR: This section distinguishes between countable and uncountable sets. Countable sets can be put into a one-to-one correspondence with the natural numbers ; uncountable sets cannot. Cantor’s diagonalization argument proves the uncountability of the set of infinite binary sequences, which leads to the important conclusion that uncomputable functions exist.
3.7.1 Countability of Sets
Definition:
A set is countable if there exists a bijection (a one-to-one and onto mapping) , where is the set of natural numbers. This means we can list the elements of as A finite set is also considered countable.
Examples:
-
Example 3.56: The set of integers is countable. A bijection can be defined as:
-
Example 3.57: The set of odd natural numbers is countable. A bijection is .
Lemma 3.15
3.7.2 Between Finite and Countably Infinite
Countably Infinite Sets:
A set is countably infinite if it’s countable but not finite. This means there exists a bijection between the set and the natural numbers, but the listing is infinite.
Example:
The set of natural numbers itself is countably infinite.
Theorem 3.17:
A set A is countable if and only if it is finite or . (There’s no cardinality between finite and countably infinite.)
Proof:
-
() If A is finite, it’s countable by definition. If A is countably infinite, by definition there’s a bijection between A and , so .
-
() If A is finite, it’s countable. If , then A is countably infinite (and hence countable).
3.7.3 Important Countable Sets
-
Example 3.56: The set of natural numbers is countable.
-
Example 3.56: The set of integers is countable.
-
Example 3.21: The set of rational numbers is countable.
This is less obvious and requires a proof. The standard proof involves creating a list of rational numbers by organizing the fractions (where and ) in a specific pattern (such as diagonals). See: Simple Proof
3.7.4 Uncountability of
Definition:
denotes the set of all infinite sequences consisting of 0s and 1s. Each sequence represents a function .
Theorem 3.23:
The set is uncountable.
Proof (by contradiction):
-
Assumption: Assume is countable. Then there exists a bijection . This allows us to list all the infinite sequences:
…
-
Diagonalization Argument: Construct a new sequence where:
-
Contradiction: This sequence differs from every sequence in the original list in at least one position (the -th position). But, if is a bijection, then must be equal to for some . This creates a contradiction.
-
Conclusion: Our initial assumption that is countable must be false. Therefore, is uncountable.
3.7.5 Existence of Uncomputable Functions
Theorem 3.24 (Corollary):
There exist uncomputable functions .
Proof:
-
Every computer program can be represented as a finite binary string (and thus as a natural number).
-
The set of all such programs is therefore countable.
-
The set of all functions is equinumerous with and hence uncountable.
-
Since the number of functions is larger than the number of programs, it follows that there must exist functions that cannot be computed by any program.
Next Chapter: Chapter 4 - Number Theory