Foundations 2 Lecture Notes 1 PDF

1 / 19 Foundations 2 Lecture Notes 1 Lecturers: Fairouz Kamareddine and Joe Wells (Edinburgh), Hind Zantout (Dubai), Thomas Basuki (Malaysia) All material is taken from the forthcoming book: Lam...

1 / 19 Foundations 2 Lecture Notes 1 Lecturers: Fairouz Kamareddine and Joe Wells (Edinburgh), Hind Zantout (Dubai), Thomas Basuki (Malaysia) All material is taken from the forthcoming book: Lambda Calculus, Turing Machines and Computability: A First Course by Fairouz Kamareddine and Joe Wells 2024-01-17 Section 1: Overview 2 / 19 Section 1: Overview The main aims of the course include: ▶ Basic mathematical concepts: sets, functions, sequences, etc. ▶ Some sets are infinite. There are different infinite sizes! ▶ What does it mean for something (a function?) to be computable? ▶ What mathematical functions can be calculated by a computer program? There are many more functions than programs, so the vast majority are uncomputable. ▶ Are some computational problems harder than others? Section 2: Examples of computable functions 3 / 19 Section 2: Examples of computable functions ▶ Consider the function Add which takes two natural numbers p and q and returns their sum. ▶ You may write an algorithm which when translated into a programming language, say Java, can give you the result of Add for any two natural numbers. ▶ Here is a possible Java algorithm: public static int Add(int p, int q) { int i = 0; int r = p; while (i < q) { r += 1; i += 1; } return r; } Section 2: Examples of computable functions 4 / 19 Some observations about this algorithm ▶ Given any two natural numbers, it can calculate their sum. ▶ Of course, it uses addition to do this, but it only uses addition of 1, which is simpler than addition of arbitrary numbers. ▶ Given a way of implementing adding 1, comparing two numbers, storing in a variable either zero or the contents of another variable, and doing while loops, this Java Add algorithm shows how to implement adding arbitrary natural numbers. ▶ Of course there might be the limitation of memory size. The numbers might be too big and the machine we are using does not allow such big numbers. This is not a problem however. We can always move to a bigger machine. Section 2: Examples of computable functions 5 / 19 Effectively computable ▶ What we should know however is that the function Add is actually EFFECTIVELY COMPUTABLE (a term we will define throughout our course). ▶ The same thing applies for many many functions. The product, exponentiation and factorial functions are all effectively computable. In fact every function you have ever programmed is effectively computable which makes us wonder if there are any functions which are not effectively computable. ▶ Exercise: Write an algorithm to multiply two natural numbers. The Add function may be used. Try to use only the same kind of basic operations used by Add. Will your algorithm always return an answer for any two natural numbers, provided there are no limitations on time and memory? Section 3: Some functions unknown to be computable 6 / 19 Section 3: Some functions unknown to be computable ▶ The Java Add algorithm given earlier will always after some time stop and then return an answer. The time might depend on how slow or efficient the machine is. ▶ However, there are functions which are not known to be either effectively computable or not effectively computable. That is, it is not known if there exists an algorithm which when given an input to the function will always stop and return the function’s answer. Section 3: Some functions unknown to be computable 7 / 19 Patterns in the digits of π ▶ Remember π, the ratio of the circumference of a circle to its diameter. Its decimal expansion looks like 3.141 · · ·. ▶ Let g ∈ N −tot → {0, 1} be the function such that for every k ∈ N it holds that:   1 if there exist k consecutive occurrences of k g (k) = in the decimal expansion of π, 0 otherwise  ▶ g (1) = 1 because the first digit after the decimal point in the decimal expansion of π is 1. ▶ g (8) = 1 because the sequence 88888888 occurs at position 46663520 counting from the first digit after the decimal point. Section 3: Some functions unknown to be computable 8 / 19 Is g computable? ▶ I do not know if g (14) is 1 or 0 because the sequence 1414141414141414141414141414 (which is 14 consecutive 14’s) does not occur in the first 100 000 000 digits of π, and I was not able to check further. ▶ The first 30 000 000 000 000 digits of π have been calculated somewhere, and perhaps 1414141414141414141414141414 occurs in them. ▶ But even if it does not, we do not currently have any way of knowing if we will find it by searching further. ▶ At the moment it is not known whether there exists an algorithm to compute g. The function g might actually be the constant function which always returns 1, which is easy to implement, but we do not know whether g is this function. Section 3: Some functions unknown to be computable 9 / 19 Attempting to implement g Exercise: Consider this “algorithm” to compute g : 1. Let k be a natural number. 2. Using any of the known algorithms for generating the decimal expansion of π one digit at a time, generate digits and watch for consecutive occurrences of the digits of k. 3. If at some stage a run of k consecutive occurrences of the digits of k has appeared, then stop and return the result 1. 4. If no such sequence appears, then stop and return 0. What do you think of this algorithm? As an implementation of g , how does it compare with the Java Add algorithm as an implementation of addition? What would happen if you used this algorithm to program g ? Section 4: Functions that are certainly non-computable 10 / 19 Section 4: Functions that are certainly non-computable ▶ The function Add is effectively computable. ▶ It is not known whether the function g is effectively computable or non-computable. ▶ The function T given below is definitely uncomputable. Section 4: Functions that are certainly non-computable 11 / 19 Classical first-order predicate logic ▶ This course will make heavy use of classical first-order predicate logic. Here we consider the restriction to no function symbols. ▶ Let P and Q range over predicate symbols. Let x and y range over variables. Formulas are formed by this rule: Φ, Ψ ∈ FOR ::= P(x1 ,... , xn ) | x = y | ¬Φ | Φ → Ψ | ∀x. Φ Operator precedence from highest to lowest is: ¬, →, ∀. ▶ An example formula is ∀x. P(x) → Q(x), which is true if the unary meanings of P and Q are such that for every x, if P(x) is true then Q(x) is true. ▶ More examples include ∀x. P(x) → P(x), which is always true (regardless of what P means), and ∀x. ¬(P(x) → P(x)), which is never true (regardless of what P means). Section 4: Functions that are certainly non-computable 12 / 19 Can we decide tautologies? ▶ The set FOR is the collection containing every formula Φ of our restriction of first-order predicate logic. ▶ Remember that a formula Φ is a tautology iff it is always true regardless of the predicate symbol and variable meanings. ▶ Let T ∈ FOR −tot → {0, 1} be the function such that for every Φ ∈ FOR it holds that:  1 if Φ is a tautology, T (Φ) = 0 otherwise ▶ Question: Given any formula Φ of the predicate calculus, is there a method that will let you tell if T (Φ) is 0 or 1? That is, can you tell whether the formula is a tautology (always true)? Section 4: Functions that are certainly non-computable 13 / 19 T is not computable ▶ Answer: No, it is not possible to do so. One can answer this question for many formulas, but not all. Unfortunately, the examples of the formulas which we can not show to either be or not be a tautology are very complicated. We may mention one or two during the course. ▶ The question above was an open question for 36 years. At the beginning of the last century, in 1900, the respected mathematician Hilbert put a list of open questions in front of the mathematical community. The above question was number 23 on the list of these questions. ▶ It was only in the 1930’s that solutions to these questions started to appear. These solutions mostly turned out to be negative. The solutions had the effect of collapsing the program of Hilbert which wanted to automate all forms of reasoning. This was a turning point in the history of Computer Science, even though electronic computers were only beginning to be invented. Section 4: Functions that are certainly non-computable 14 / 19 But can we decide contradictions? Exercise: For the moment, trust me that there is no method to decide whether a a formula is a tautology (whether it is always true regardless of the predicate symbol and variable meanings). Can there be a method to decide whether a formula is a contradiction (always false)? Section 5: A brief history of logic and computability 15 / 19 Section 5: A brief history of logic and computability Logics and computation have existed in various forms since the times of the ancient Babylonians and the Greeks. Aristotle (384 to 322 B.C.) first systematized deductive logic. Aristotle wanted a set of rules that would be powerful enough for most intuitively valid proofs. Aristotle correctly stated that proof search is harder then proof checking: ▶ Given a proof of statement, one can check that it is a correct proof. ▶ Given a statement, one may not be able to find the proof. Section 5: A brief history of logic and computability 16 / 19 The late 1800’s saw the beginnings of serious formalization. Cantor (1845/1918) began formalizing set theory and made contributions to number theory. He proved by diagonalization that there are more real numbers than natural numbers. We will see that this proof method is used in the proof that some important functions are not computable. Peano (1858/1932) began formalizing arithmetic. His methods inspired later work. Section 5: A brief history of logic and computability 17 / 19 Frege (1845/1925) wrote the Begriffsschrift (1879), the first formalization of logic which presented logical concepts via symbols rather than natural language. Frege also wrote the Grundgesetze der Arithmetik, called later by others Naive Set Theory (NST), which could handle elementary arithmetic, set theory, logic, and quantification. However, Russell discovered a paradox. Hilbert (1862/1943) in his Grundlagen der Mathematik (1934, 1939) aimed to have computational methods to decide various logical and mathematical problems. However, Gödel showed this impossible. Russell (1872/1970) discovered a serious flaw in Frege’s logic (also in Cantor’s earlier set theory). Quite simply, one could make statements about “the set of all sets which do not contain themselves”. This is similar to the barber’s paradox (discussed later). Section 5: A brief history of logic and computability 18 / 19 Gödel (1906/1978) proved the Incompleteness Theorem (1931), which drove the nail in the coffin of Hilbert’s ambitions. His theorem is the first proof that a particular function is not computable, although there was no general notion of computability yet. Church (1903/1995) developed the λ-calculus, an important model of computability. (λ is the Greek letter “lambda”.) Church also formulated what is now known as Church’s Thesis, the belief that any new model of computability which is discovered will be no more powerful than the λ-calculus or Turing machines. Turing (1912/1954) developed what are now known as Turing machines, an important model of computability. We will study computability via Turing machines this term. Section 6: Some puzzles and the limits of intuition 19 / 19 Section 6: Some puzzles and the limits of intuition ▶ Somewhere nearby (maybe somewhere near the Borders or in the Highlands) there is said to be a town where there lives a male barber who shaves every man living in town who does not shave himself and does not shave anyone else. Perhaps you do not believe this. Can you give a convincing argument why this can not really be the case? ▶ Consider this description: The smallest number whose shortest description requires more than eleven words. What number can this possibly be?  1 / 19 Foundations 2 Lecture Notes 2 Lecturers: Fairouz Kamareddine and Joe Wells (Edinburgh), Hind Zantout (Dubai), Thomas Basuki (Malaysia) All material is taken from the forthcoming book: Lambda Calculus, Turing Machines and Computability: A First Course by Fairouz Kamareddine and Joe Wells 2024-01-08 Section 1: Key points from Lecture Notes 1 2 / 19 Section 1: Key points from Lecture Notes 1 ▶ Recall that our interest is in finding out what are the computable or non-computable functions. One major motivation is the desire to answer difficult questions like Hilbert’s problems which were put in 1900 and especially his Entscheidung problem which was put in the late 1920s: ▶ Hilbert’s Entscheidung Problem: Develop a method to establish the truth/falsity of any formula in logic. ▶ 36 Years Later: ▶ Turing discovered the answer to Hilbert’s problem. ▶ Hilbert’s problem was impossible to solve. ▶ This has had profound effects on Mathematics, Philosophy, and Computer Science. Section 1: Key points from Lecture Notes 1 3 / 19 ▶ Also during the 1930s we had: ▶ Gödel’s results on incompleteness which states that there are limitations to what a machine can do. ▶ Church’s and Kleene’s work on the lambda calculus and undefinability results which attempted to give a syntactic definition of the computable functions. ▶ In this course we will discuss computability in terms of Turing machines. ▶ This choice is supported by Church’s Thesis: A function f is effectively computable if and only if f is Turing computable. ▶ Both terms of computability will be defined later. Section 2: Sets 4 / 19 Section 2: Sets ▶ The symbol ∅ stands for the empty set which has no members. The empty set may also be written {}. ▶ Set membership is written as x ∈ S. ▶ S is a subset of T , written S ⊆ T , exactly when for every x ∈ S it also holds that x ∈ T. ▶ Set union is written as S ∪ T , set intersection is written as S ∩ T , and set difference is written as S \ T. ▶ Example: Given the sets R = {1, 2, 3}, S = {3, 4, 5}, and T = {6, 7}, the results below are true: 2∈R 2 ̸∈ S {3} ⊆ R R ∩ S = {3} R ∩T =∅ R ∪ S = {1, 2, 3, 4, 5} R \ S = {1, 2} R⊆R R ∩S ⊆R ∪S Section 2: Sets 5 / 19 Ordered pairs, tuples, and set products ▶ Given two sets S and T , the set product notation S × T stands for the set of all ordered pairs (x, y ) such that x ∈ S and y ∈ T. ▶ Example: The product {A, B} × {2, △, ◦} is: {(A, 2), (A, △), (A, ◦), (B, 2), (B, △), (B, ◦)} ▶ This notation generalizes: S1 × S2 × · · · × Sk is the set of all k-tuples (x1 , x2 ,... , xk ) such that x1 ∈ S1 , x2 ∈ S2 , and so on through xk ∈ Sk. ▶ Given a set S and a positive integer k, the notation S k means S × S × · · · × S where there are k repetitions of S. ▶ Example: N2 is the set of all pairs of natural numbers Section 2: Sets 6 / 19 Set comprehensions ▶ Given a logical formula Φ that might mention the variable x, the set comprehension { x Φ } stands for the set containing exactly every mathematical thing t such that Φ is true when the value of x is t, if there is such a set. ▶ The notation { x ∈ S Φ } abbreviates { x x ∈ S ∧ Φ } and will be a set if S is a set. ▶ The notation { (x, y ) Φ } abbreviates { p ∃x. ∃y. p = (x, y ) ∧ Φ }. ▶ Example: The set of all even natural numbers: E = { y ∈ N ∃z ∈ N. y = 2 × z } The set of all odd natural numbers: O = { y ∈ N ∃z ∈ E. y = z + 1 } Section 3: Numbers and arithmetic 7 / 19 Section 3: Numbers and arithmetic ▶ N is the set of all natural numbers: 0, 1, 2, 3, and so on. ▶ Z is the set of all integers:... , −3, −2, −1, 0, 1, 2, 3,.... ▶ Q is the set of all rational numbers, each of which is the result of dividing an integer x by a positive integer y , written x/y. ▶ R is the set of all real numbers, each of which can be viewed as the sum of an infinite sequence of rational numbers. ▶ Example: ▶ π = 3.1415 · · · = 3/100 + 1/101 + 4/102 + 1/103 + 5/104 +... ▶ 5.75 = 5/100 + 7/101 + 5/102 + 0/103 + 0/104 +... ▶ Numeric multiplication can be written i × j, division can be written i/j, and exponentiation is written i j. Section 3: Numbers and arithmetic 8 / 19 Operations on integers and real numbers ▶ The sign of x ∈ R is:   1 if x > 0 sgn(x) = 0 if x = 0 −1 if x < 0  ▶ The distance between x ∈ R and y ∈ R is d(x, y ) = (x − y ) × sgn(x − y). ▶ The absolute value of x ∈ R is |x| = d(x, 0). ▶ The floor of x ∈ R, written ⌊x⌋, is the greatest integer y ∈ Z such that y ≤ x. ▶ The ceiling of x ∈ R, written ⌈x⌉, is the least integer y ∈ Z such that x ≤ y. Section 3: Numbers and arithmetic 9 / 19 ▶ The truncation of x ∈ R, written trunc(x), is the integer y ∈ Z with the same sign as x and the greatest absolute value such that |y | ≤ |x|, or equivalently, trunc(x) = sgn(x) × ⌊ |x| ⌋. ▶ The rounding of x ∈ R, written round(x) is the integer y ∈ Z with least distance from x, choosing the even integer if there are two integers with least distance. ▶ Example: x sgn(x) |x| trunc(x) ⌊x⌋ ⌈x⌉ round(x) −3.5 −1 3.5 −3 −4 −3 −4 −2.5 −1 2.5 −2 −3 −2 −2 2.5 1 2.5 2 2 3 2 3.5 1 3.5 3 3 4 4 Section 3: Numbers and arithmetic 10 / 19 Integer division and modulo ▶ Integer division is written i div j in this course. (Others sometimes write it as i \ j, or sometimes i/j, although the latter form risks confusion with ordinary division.) ▶ In i div j, the number i is the dividend and j is the divisor. The division result is the quotient. ▶ The closely related modulo operation is written i mod j (or in some programming languages: i % j). The result of i mod j is called the remainder. ▶ The connection between integer division and the modulo operation is this: i = ((i div j) × j) + (i mod j) Section 3: Numbers and arithmetic 11 / 19 Variants of integer division ▶ At least 5 different definitions of integer division and modulo are actually used. Each converts non-integer division results to integers in its own way. ▶ F-division uses flooring (going down to the next integer) so the remainder has the same sign as the divisor. ▶ T-division uses truncation (going towards zero to the next integer) so the remainder has the same sign as the dividend. ▶ Euclidean division chooses the remainder to be non-negative. ▶ Sometimes also rounding or the ceiling operation are used (e.g., both are available in Common Lisp). ▶ For positive inputs, T-division, F-division, and E-division all yield identical results. The various definitions of integer division and modulo can yield different results when one or both of the inputs is negative. Fortunately, the relationship between i div j and i mod j is preserved in all of the common definitions. (Warning: Pascal uses incompatible definitions of integer division and modulo.) Section 3: Numbers and arithmetic 12 / 19 This course uses F-division ▶ This course uses F-division, which is defined so that: i div j = ⌊i/j⌋ ▶ Example: ▶ 7 div 3 = 2 ▶ 7 mod 3 = 1 ▶ 7 = (7 div 3) × 3 + (7 mod 3) ▶ For more details on integer division and modulo, consult the paper Division and Modulus for Computer Scientists by Daan Leijen. Section 4: Binary relations and functions 13 / 19 Section 4: Binary relations and functions ▶ A binary relation is a set of ordered pairs. A function f is a binary relation obeying the condition that if (x, y ) ∈ f and (x, z) ∈ f , then y = z. ▶ Example: Let f and g be defined like this: f = {(0, 2), (1, 3), (2, 4), (3, 5), (4, 6)} g = {(0, 3), (1, 4), (2, 0), (3, 1), (4, 2), (5, 3),...} = { p ∃x ∈ N. p = (x, (x + 3) mod 5) } ▶ The functions f and g are the least (comparing with ⊆) functions that satisfy these formulas: f (x) = x + 2 if x ∈ N and x ≤ 4 g (x) = (x + 3) mod 5 if x ∈ N Section 4: Binary relations and functions 14 / 19 Application, domain, and range ▶ Given a binary relation R, the application R(x) denotes y such that (x, y ) ∈ R, if there is exactly one such y , and is otherwise undefined. ▶ Example: With f from before, f (4) = 6 and f (5) is undefined. ▶ The domain of a binary relation R is the set dom(R) = { x ∃y. (x, y ) ∈ R }. ▶ Example: Using our earlier examples, dom(f ) = {0, 1, 2, 3, 4} and dom(g ) = N. ▶ The range of a binary relation R is the set ran(R) = { y ∃x. (x, y ) ∈ R }. ▶ Example: Using our earlier examples, ran(f ) = {2, 3, 4, 5, 6} and ran(g ) = {0, 1, 2, 3, 4}. Section 4: Binary relations and functions 15 / 19 Function spaces ▶ The function space from set S to set T , written S → 7 T , is the set of every function f such that dom(f ) ⊆ S and ran(f ) ⊆ T. If f ∈ S →7 T , it is said that f is a function from S to T. ▶ Example: Using our earlier examples: ▶ f ∈N→ 7 N, i.e., f is a function from N to N. ▶ Also, f ∈ {0, 1, 2, 3, 4} →7 N, and f ∈ N → 7 {2, 3, 4, 5, 6}, and f ∈ {0, 1, 2, 3, 4} → 7 {2, 3, 4, 5, 6}. ▶ g ∈N→ 7 N, and g ∈ N → 7 {0, 1, 2, 3, 4}. ▶ Every function belongs to many function spaces. Section 4: Binary relations and functions 16 / 19 Total function spaces ▶ A function f is total on S if and only if dom(f ) = S. The tot total function space from S to T , written S −→ T , is the set of every function f ∈ S →7 T such that dom(f ) = S. ▶ Example: Using earlier examples, f ∈ {0, 1, 2, 3, 4} − tot → N and tot g ∈ N −→ N (f is total on {0, 1, 2, 3, 4} and g is total on N). ▶ Example: Function spaces are generally huge sets, but it is possible to write down completely some very small function spaces like this space that contains only 4 functions:     {(0, 2), (1, 2)},  {(0, 2), (1, 3)},   tot {0, 1} −→ {2, 3} =   {(0, 3), (1, 2)},  {(0, 3), (1, 3)}   Section 4: Binary relations and functions 17 / 19 Inverses and injections ▶ The inverse of a binary relation R is R −1 = { p ∃x. ∃y. p = (y , x) and (x, y ) ∈ R }. ▶ Example: Using our earlier example, f −1 = {(2, 0), (3, 1), (4, 2), (5, 3), (6, 4)}. ▶ A binary relation R is one-to-one (injective) exactly when both R and its inverse R −1 are functions. ▶ Example: Using our earlier examples f and g : ▶ The function f is one-to-one. ▶ The function g is not, because g (0) = 3 = g (5). Section 4: Binary relations and functions 18 / 19 Surjections and bijections ▶ A function f is onto S (surjective to S) if and only if ran(f ) = S. ▶ A bijection from S to T is a function that is total on S, one-to-one (injective), and onto T (surjective). ▶ Example: ▶ Our earlier example f is onto {2, 3, 4, 5, 6} and is a bijection from {0, 1, 2, 3, 4} to {2, 3, 4, 5, 6}. ▶ Our earlier example g is onto {0, 1, 2, 3, 4}, but is not a bijection. Section 5: Logical reasoning by contradiction 19 / 19 Section 5: Logical reasoning by contradiction ▶ We now review a kind of logical reasoning that confuses many. ▶ Suppose several formulas together imply a contradiction: (P ∧ Q) ⇒ (R ∧ ¬R) ▶ This is equivalent to one of the formulas being false: ((P ∧ Q) ⇒ (R ∧ ¬R)) ⇔ ((¬P) ∨ ¬Q) ▶ You can observe that the two rightmost columns in this truth table have the same truth values: P Q P ∧Q R ∧ ¬R (P ∧ Q) ⇒ (R ∧ ¬R) (¬P) ∨ ¬Q true true true false false false true false false false true true false true false false true true false false false false true true ▶ If we derive a contradiction, then one of our assumptions must be false. If there is only one assumption, then it is false.  1 / 17 Foundations 2 Lecture Notes 3 Lecturers: Fairouz Kamareddine and Joe Wells (Edinburgh), Hind Zantout (Dubai), Thomas Basuki (Malaysia) All material is taken from the forthcoming book: Lambda Calculus, Turing Machines and Computability: A First Course by Fairouz Kamareddine and Joe Wells 2024-01-08 Section 1: Enumerability 2 / 17 Section 1: Enumerability ▶ To enumerate a set is to arrange its members in a single list with a first entry, a second entry, etc., so that: ▶ every member of the set appears sooner or later in the list and ▶ every entry in the list belongs to the set. ▶ In an enumerated set, every member of the set must be listed after at most a finite number of other members. ▶ Example: ▶ The set Z+ of positive integers can be enumerated by: 1, 2, 3, 4,... (an infinite list) ▶ The set E5 of even numbers strictly less than 5 can be enumerated by: 0, 2, 4 (a finite list) Section 1: Enumerability 3 / 17 Lists that are NOT enumerations ▶ CAREFUL: We said that Z+ can be enumerated by the list 1, 2, 3,... but the following list is not an enumeration of Z+ : 1, 3, 5,... , 2, 4, 6,... ▶ Here all the odd positive integers are listed and then all the even ones. ▶ This is not acceptable because we said that every member of Z+ must appear sooner or later in the list, after only a finite number of other members. ▶ In 1, 3, 5,..., 2, 4, 6,... none of the even numbers will appear until after an infinite number of odd numbers. Section 1: Enumerability 4 / 17 Thinking about enumerations as functions ▶ To avoid invalid enumerations, we can limit ourselves to enumerating a set S by using a function f from N (the set of natural numbers) to S. ▶ Example: Our earlier enumeration of Z+ (that is, the set {1, 2, 3,...}) can be given by a function f such that: f (0) = 1, f (1) = 2, f (2) = 3,... This can be depicted like this: N: 0 1 2 3 · · · f : ↓ ↓ ↓ ↓ ··· Z+ : 1 2 3 4 · · · ▶ Example: Similarly, our earlier enumeration of E5 can be given by the function f ′ from the set of natural numbers N to E5 such that f ′ (0) = 0, f ′ (1) = 2, and f ′ (2) = 4. (What about f ′ (n) for n different from 0, 1, and 2?) Section 1: Enumerability 5 / 17 Enumerations are not unique ▶ Fact: Any nonempty set that can be enumerated, can be enumerated by an infinite number of distinct functions. ▶ Example: We saw that the set Z+ can be enumerated by N: 0 1 2 3 · · · f : ↓ ↓ ↓ ↓ ··· Z+ : 1 2 3 4 · · · But Z+ can also be enumerated by a function g such that: g (0) = 2, g (1) = 1, g (2) = 4, g (3) = 3, g (4) = 6, g (5) = 5,... This can be depicted like this: N: 0 1 2 3 4 5 · · · g: ↙ ↘ ↙ ↘ ↙ ··· ↘ Z+ : 1 2 3 4 5 6 · · · Section 1: Enumerability 6 / 17 Enumerations are not unique (continued) ▶ Reminder: Here is f again: N: 0 1 2 3 · · · f : ↓ ↓ ↓ ↓ ··· Z+ : 1 2 3 4 · · · Here is g depicted differently: N: 0 1 2 3 4 5 ··· g: ↓ ↓ ↓ ↓ ↓ ↓ ··· Z+ : 2 1 4 3 6 5 · · · ▶ The function g is not as neat as f but it enumerates Z+. ▶ For each member m ∈ Z+ , there is a natural number n ∈ N for which we have g (n) = m. ▶ Also, g (n) ∈ Z+ for every natural number n ∈ N. Section 1: Enumerability 7 / 17 Enumerations are not unique (continued) ▶ Example: Here is an even more complicated function enumerating Z+ : h(0) = 1 h(1) is undefined h(2) = 2 h(3) is undefined h(4) = 3 h(5) is undefined...... ▶ The function h can be drawn as: N: 0 1 2 3 4 5 ··· h: ↓ ↓ ↓ ↓ ↓ ↓ ··· Z+ : 1 ⊥ 2 ⊥ 3 ⊥ · · · ▶ The function h from N to Z+ is not total on N, but it enumerates Z+. ▶ For each member m ∈ Z+ , there is a natural number n ∈ N for which it holds that h(n) = m. ▶ For every natural number n ∈ N either h(n) ∈ Z+ or h(n) is undefined (and thus not outside of Z+ ). Section 1: Enumerability 8 / 17 Enumerations are not unique (continued) ▶ It may seem to be unnecessarily complicating things to choose h instead of f to enumerate Z+ , but there are sets other than Z+ which are more easily enumerated by functions that are not total on N. ▶ Example: The set E of even natural numbers is enumerated by j ∈ N →7 E such that:  n if n is even and n ∈ N, j(n) = undefined otherwise. ▶ j can be drawn as: N: 0 1 2 3 4 5 · · · j: ↓ ↓ ↓ ↓ ↓ ↓ · · · E: 0 ⊥ 2 ⊥ 4 ⊥ · · · ▶ The set E is also enumerated by k ∈ N − tot → E such that k(n) = 2 × n if n ∈ N. Section 1: Enumerability 9 / 17 What is an enumerable set? ▶ Definition: We say that a set A is enumerable if and only if there exists a function f from N to A (possibly not total on N) such that the range of f is exactly A, i.e., ran(f ) = A, and in this case we say that f enumerates A. (Note that we do not require f to be one-to-one.) ▶ Example: Take the set A = {Z+ , E , ∅}, a set of 3 sets. The set A is enumerated by the function e ∈ N → 7 A such that: e(0) = Z+ e(1) = E e(2) = ∅ e(n) is undefined otherwise ▶ Just for fun: Consider the set of all numbers that have not been considered before... oops, they’re all gone now. Section 2: Cardinality and countability 10 / 17 Section 2: Cardinality and countability ▶ Sets can be finite or infinite. The notation |A| stands for the cardinality of A, i.e., the number of members in the set A. ▶ If the set A is finite, then |A| ∈ N. If A is infinite, then |A| is a special kind of number known as an infinite cardinal number. ▶ The smallest infinite cardinal number is named a and the next larger one is named c ▶ Although there are an infinite number of infinite cardinal numbers, we will only discuss a, c, and 2a. ▶ When thinking more about a set’s size rather than about listing the set, we say an enumerable set is countable. ▶ lf a set is enumerable and infinite, we say it is countably infinite (or enumerably infinite). ▶ The size of a countably infinite set is a. ▶ The set N is countably infinite. Section 2: Cardinality and countability 11 / 17 Facts about cardinality ▶ |A1 × A2 × · · · × An | = |A1 | × |A2 | × · · · × |An |. ▶ |A| ≤ |B| (i.e., B is at least as large as A) if and only if ▶ there exists an injective (one-to-one) function f from A to B that is total on A, which holds if and only if ▶ there exists a function g from B to A that is onto A. ▶ |A| = |B| (i.e., A and B are of the same size) if and only if there exists a bijection f from A to B. ▶ If |A| ≤ |B| and B is countable then A is countable. ▶ If A1 , A2 ,..., An are countable then both A1 ∪ A2 ∪ · · · ∪ An and A1 × A2 × · · · × An are countable. (Lecture Notes 5 shows how to enumerate both A1 ∪ A2 and A1 × A2.) ▶ If p ∈ Z+ , then ▶ a = a + p = a + a = a × p = a × a, and ▶ c = c + p = c + c = a + c = c × p = c × a = c × c. Section 3: Uncountability of the real numbers 12 / 17 Section 3: Uncountability of the real numbers ▶ Given two real numbers x and y , the notation [x, y [ stands for the set { z ∈ R x ≤ z and z < y } , i.e., the set of all real numbers at least as large as x and strictly smaller than y. ▶ Not every set is countable. ▶ Consider [0, 1[, the set of all real numbers whose decimal representation has just “0” to the left of the decimal point. ▶ This section shows [0, 1[ is not countable. Section 3: Uncountability of the real numbers 13 / 17 Uncountability of the real numbers (continued) ▶ Suppose for the sake of argument that [0, 1[ is a countable set. Then there must exist an enumeration function f ∈ N → 7 [0, 1[. ▶ This function f must enumerate [0, 1[ roughly like this, where each number ai,j is a single digit: f (0) = 0. a0,0 a0,1 a0,2 a0,3 ··· f (1) = 0. a1,0 a1,1 a1,2 a1,3 ··· f (2) = 0. a2,0 a2,1 a2,2 a2,3 ··· f (3) = 0. a3,0 a3,1 a3,2 a3,3 ···.................. ▶ Now we will construct a new real number b which clearly belongs to [0, 1[ but which can not appear in the enumeration. Section 3: Uncountability of the real numbers 14 / 17 Uncountability of the real numbers (continued) ▶ For each i ∈ N, let bi = (ai,i mod 8) + 1. ▶ The point is merely that we are choosing bi to be a digit different from ai,i , and 0, and 9. ▶ Now choose b to be the real number whose decimal representation looks like this: b = 0.b0 b1 b2 b3 · · · ▶ It is easy to see that b ∈ [0, 1[. Therefore, by our (questionable) assumption that we have a function f enumerating [0, 1[, it must be the case that b = f (k) for some k ∈ N. ▶ Therefore, it must be true that: b = f (k) = 0.ak,0 ak,1 ak,2 ak,3 · · · ▶ In particular, it must be the case for the kth digit after the decimal point that bk = ak,k. However, bk was carefully defined so that bk ̸= ak,k ! Section 3: Uncountability of the real numbers 15 / 17 Uncountability of the real numbers (continued) ▶ The situation looks like this, where ak,i = bi ̸= ai,i for every i ∈ N: f (0) = 0. a0,0 a0,1 a0,2 a0,3 ··· a0,k... f (1) = 0. a1,0 a1,1 a1,2 a1,3 ··· a1,k... f (2) = 0. a2,0 a2,1 a2,2 a2,3 ··· a2,k... f (3) = 0. a3,0 a3,1 a3,2 a3,3 ··· a3,k........................ f (k) = 0. ak,0 ak,1 ak,2 ak,3 · · · ???..................... ▶ This is a contradiction, which means one of our assumptions must be false. ▶ The only assumption we have made (other than all the standard rules of mathematics) is that [0, 1[ is countable, so this must be false. Section 3: Uncountability of the real numbers 16 / 17 Uncountability of the real numbers (continued) ▶ Theorem: [0, 1[ is uncountable. ▶ This method that we used to show that [0, 1[ is uncountable is called diagonalisation and is due to Cantor. ▶ What we did here was to put the members of [0, 1[ into a list and then to find a member b ∈ [0, 1[ which does not belong to the list. ▶ The problem can not be repaired by adding b to the list somewhere, because you can apply diagonalisation again to the new list and there will still be a contradiction. ▶ As a result of this argument, we know that the size of R (which contains [0, 1[ ) is bigger than a. In fact, it turns out to be 2a = c = |R|. Section 4: Exercises 17 / 17 Section 4: Exercises ▶ Exercise 1: Without using “... ”, define the enumeration functions f , g , and h (of Z+ ) that were depicted earlier. ▶ Exercise 2: Here is a list enumerating the set N: 1, 0, 3, 2, 5, 4,... Without using “... ”, define the enumeration function corresponding to this list. ▶ Exercise 3: Here is a list that does not enumerate N: 1, 3, 5,... , 0, 2, 4,... In this listing, each even number is preceded by an infinite number of odd numbers. Use the technical definition of “enumerable” to explain why this list can not be an enumeration of N? Why can’t there be an enumeration function corresponding to this list?