CS103: Sets and Cantor's Theorem

• The text provides course notes for CS103, a preliminary course on the mathematical foundations of computing, taught by Keith Schwarz in Fall 2015.
• The notes cover topics from set theory and proof techniques to mathematical induction, graphs, and computability.

Chapter 0: Introduction

• Computer science is defined as the art of solving problems with computers.

Chapter 1: Sets and Cantor's Theorem

• This chapter covers Set Theory and proof of Cantor's theorem
• A set is an unordered collection of distinct elements.
• Sets are denoted using curly braces, e.g., {1, 2, 3} represents a set with elements 1, 2, and 3.
• The order of listing elements doesn't matter, and duplicates are ignored.
• x ∈ S denotes that x is an element of set S, while x ∉ S denotes that x is not an element of set S.
• The empty set, denoted Ø, contains no elements, and x ∉ Ø is always true.

Sets Containing Other Sets

• It is permissible for sets to contain other sets.
• Set containment is “opaque,” meaning it only checks for direct containment within the set, not indirect containment.

Giving Sets Names

• Assigning names to sets for easier reference is a common practice.

The Empty Set

• The empty set (∅) contains no elements and is a subset of every set.

Set Operations

• The intersection of two sets S and T (S ∩ T) contains elements in both S and T.
• The union of two sets A and B (A ∪ B) contains elements in either A or B.

Set Difference

• Set difference of A and B which can be written as A – B or A \ B, represents elements in A but not in B.
• Set difference is asymmetric.

Symmetric Difference

• The symmetric difference of two sets A and B (A Δ B) contains elements in exactly one of A or B, but not both.

Special Sets and their properties

• ℤ represents the set of all integers.
• ℕ represents the set of all natural numbers; in these notes 0 is included.
• ℝ represents the set of all real numbers.
• Finite set is defined as set containing only a finite amount of numbers.
• Infinite set is defined as set containing an infinite amount of umbers.

Set-Builder Notation

• A tool for defining sets based on common properties is called Set-builder notation.
• The pattern generally follows the form "{variable | conditions on that variable}".

Set-builder Notation

• {n | n ∈ ℕ and n is even} can be read as "the set of all n, where n is a natural number and n is even".

Transforming Sets

• Set-builder notation can transform elements of one set to convert them into a different set.
• {n² | n ∈ ℕ} denotes the set of all n², where n is a natural number.

Relations on Sets

• Under set equality, two sets are equal when they contain the same elements; the definition is called the axiom of extensionality.
• M is a superset of F, if music library M contains everything that the set of favorites F does.
• F is a subset of M.

Subsets and Supersets

• A is a subset of B, written as A ⊆ B, if every element of A is also contained in B.
• B is a superset of A, written as B ⊇ A, if B contains every element of A.
• A is a strict subset of B, written as A ⊂ B, if A ⊆ B and A ≠ B.
• B is a strict superset of A, written as B ⊃ A, if A ⊂ B.

Vacuous Truths

• A statement is vacuously true if its assertion doesn't apply to anything.
• Ø ⊆ S is always true for any set S.

Power Set

• The power set of S, denoted ℘(S), is the set of all subsets of S.
• ℘({1, 2}) = {Ø, {1}, {2}, {1, 2}}.
• ℘(S) = { T | T ⊆ S}.

Cardinality Definition

• Cardinality measures the "size" of a set, denoted as |A|.
• An infinite cardinality are a special class of values to measure the size of infinitely large sets.
• The cardinality of ℕ is ℵ₀ (aleph-nought, or aleph-zero, or aleph-null).

Theorem of Cardinality

• |Even| = |Odd| = |ℕ| = ℵ₀

Cantor's Theorem

• It establishes that there are infinitely many infinite sets with differing cardinalities.
• Problems unsolvable by computers and true statements that are unprovable comes from Cantor's theorem.

Cantor's Diagonal Argument

• It proves that |S| < |℘(S)| by showing you can always find an element of ℘(S) that isn't paired.

Formalizing Diagonal Argument

• It requires a set S and the set of all subsets of S, denoted ℘(S)
• The set S represents any given pairing, with the goal of constructing a diagonal showing how it should be applied to a finite set.

Formal Proof of Cantor's Theorem

• Cantor’s diagonal argument proves that, for any set S, |S| < |℘(S)|.
• The proof is best formulated by contradiction and utilizes the power set.

Significance of Cantor's Theorem

• This theorem suggests a hierarchy of infinities, challenging the notion of a singular "infinity".
• Implications extend to the limits of computing.

Limits of computing

• More problems exist than there are programs to solve them.

Limits of programs

• The numbers of programs is strictly below the numbers of problems to solve, hence programs < problems.

Chapter 1 Summary

• Sets, cardinality, power sets, vacuous truths, and Cantor's diagonal argument are all part of the chapter's summaries

Chapter 2: Mathematical Proof

• A mathematical proof shows logical series of steps which start set of assumptions to conclude that a statement it must be true.
• Math requires proven definitions with proofs to give insight to mathematics that we can be certain of, which cannot be solved by a computer.
• Proof writing is similar to software and consists of an appropriate vocabulary and language which all must be checked.

Transitioning to Proof-Based Mathematics

• High school mathematics often focuses on calculation, while higher-level math is focused on properties of different types of objects.

Defining Assumptions

• To build mathematical foundations, you need definitions that are known through definitions and theorems.

Indirect proofs

• Indirect proofs involve showing that some proposition must be true by arriving at a desired conclusion.
• Proof by contradiction and contrapositive are essential.

Indirect Proof Techniques

• A contradiction shows that proposition must be true by showing it cannot be false
• Contrapositive that P implies Q, that if and only an entirely if there correct connection the two

Chapter 3: Mathematical Induction

• It can be useful for showing statements and facts about all natural numbers when using a "base" number and "recursively" building up
• You begin by showing statement P(0) is true, assuming natural number exists (P meaning) number. After a certain number k is reached it must.

Flipping Glasses Puzzle

• Begins a discussion of induction, and starts through demonstrating puzzles to illustrate how this process functions

Chapter 4: Graph Theory

• It sets up mathematical structure for modelling complex equations and structures.
• A graph can navigate a graph to solve complex computational models

Chapter 5: Relations

• A mathematical structure of relations and well-defined founded sets

Chapter 6: Functions and Cardinality

• It formally analyses functions and relationships in cardinality.
• Focuses on rigorous exploration on properties of infinity.