Hoofdstuk 8:
We can define a finite set by enumerating all its elements: People = {Alice, Bob, Carroll } We can
define a function on such a finite set by listing all possible cases: age(Alice) = 23 age(Bob) = 21
age(Carroll) = 19 We can define a relation by listing all the relevant pairs: Likes = { (Alice, IceCream),
(Alice, Toffee), (Carroll, Toffee) }
But for infinite set we can define for example the natural numbers as: N = {0, 1, 2, …}. We (as
humans) can understand this definition perfectly well - but it relies on ‘guessing’ how to fill in the
dots. Because we as human scan guess that after the 2, probably stands a 3, but we do not know this
for sure. Criticism on these notations:
− How could we expect a computer to understand such a definition?
− How can we be sure that the reader ‘guesses’ the right definition? Maybe I meant to define
the set of solutions to the equation x × (x − 1) × (x − 2) = 0.
− The order of elements in a set is not important. Yet this definition implies that the elements
should be listed in some particular order.
− How can we determine whether a particular number is in the set or not? The definition
doesn’t give us an effective check.
− What about sets where the ‘next’ element is difficult to describe, like the set of all real
numbers or the set of all valid C# programs.
Many infinite sets are described using induction, the idea behind induction is to easily describe
infinite sets. Each inductive definition consists of three parts:
− The base case that establishes some objects are in the set. Says these are some elements of
the set
− The inductive case that determines the ways in which elements of the set can be assembled
to create new elements that are also in the set. Describe how to build up bigger elements
from existing elements.
− The extremal clause that asserts that no other elements are in the set unless its
membership can be established from the first two clauses. This is all there is, there are no
other things living in the set.
We can give an inductive definition of the natural numbers (N) as follows:
− 0∈N
− for any n ∈ N, the number (n + 1) ∈ N.
− there are no other elements of N.
Using these clauses, we can show that 3 ∈ N but 4.5 ∈/ N. This inductive definition lets give a finite
description of an infinite set.
, Example of a power set:
Given a set A we can define the powerset of A, written P(A) as follows:
− ∅ ∈ P(A)
− if a ∈ A and X ∈ P(A) then {a} ∪ X ∈ P(A)
− there are no other elements of P(A)
Let B = {1, 2, 3} then from these rules we can conclude that:
− ∅ ∈ P(B)
− {1} ∪ ∅ ∈ P(B) – or more simply {1} ∈ P(B). Similarly, {2} ∈ P(B), {3} ∈ P(B)
− Repeating the second rule also gives us that, {1, 2} ∈ P(B), {1, 3} ∈ P(B), {2, 3} ∈ P(B)
− Finally, {1, 2, 3} ∈ P(B).
− 0∈N
− for any n ∈ N, the number (s(n)) ∈ N. Here we thing of s as being a unary function symbol
that stands for ‘successor’.
− there are no other elements of N.
We consider the digit 4 to be a shorthand for s(s(s(s(0)))). The Arabic numerals are simply a
shorthand for repeatedly adding one using the successor operation.
Example of a string instead of int:
Induction definition:
− the empty string, which we’ll denote using the symbol ε, is a string;
− if c is one of the 256 ASCII characters and s is a string, we can construct a longer string by
writing cs (that is, the character c followed by the string s).
There is very little that is specific to ASCII in this definition! Given any set A, we can construct the
words of characters over some set A, often written A ⋆ as follows:
− ε∈A⋆
− for all a ∈ A an w ∈ A ⋆ , aw ∈ A ⋆
A⋆ To denote the set of all words over A
A+ To denote the set of non-empty words over A.
That is, the only word of length 0.
Let’s try to construct some example inhabitants of the set {0, 1} ⋆:
− ε ∈ {0, 1} ⋆
− 0 ∈ {0, 1} ⋆ and 1 ∈ {0, 1} ⋆
− 00, 01, 10, 11 are all also in {0, 1} ⋆ .
− As are 000, 001, 010, 100, …
We can define a finite set by enumerating all its elements: People = {Alice, Bob, Carroll } We can
define a function on such a finite set by listing all possible cases: age(Alice) = 23 age(Bob) = 21
age(Carroll) = 19 We can define a relation by listing all the relevant pairs: Likes = { (Alice, IceCream),
(Alice, Toffee), (Carroll, Toffee) }
But for infinite set we can define for example the natural numbers as: N = {0, 1, 2, …}. We (as
humans) can understand this definition perfectly well - but it relies on ‘guessing’ how to fill in the
dots. Because we as human scan guess that after the 2, probably stands a 3, but we do not know this
for sure. Criticism on these notations:
− How could we expect a computer to understand such a definition?
− How can we be sure that the reader ‘guesses’ the right definition? Maybe I meant to define
the set of solutions to the equation x × (x − 1) × (x − 2) = 0.
− The order of elements in a set is not important. Yet this definition implies that the elements
should be listed in some particular order.
− How can we determine whether a particular number is in the set or not? The definition
doesn’t give us an effective check.
− What about sets where the ‘next’ element is difficult to describe, like the set of all real
numbers or the set of all valid C# programs.
Many infinite sets are described using induction, the idea behind induction is to easily describe
infinite sets. Each inductive definition consists of three parts:
− The base case that establishes some objects are in the set. Says these are some elements of
the set
− The inductive case that determines the ways in which elements of the set can be assembled
to create new elements that are also in the set. Describe how to build up bigger elements
from existing elements.
− The extremal clause that asserts that no other elements are in the set unless its
membership can be established from the first two clauses. This is all there is, there are no
other things living in the set.
We can give an inductive definition of the natural numbers (N) as follows:
− 0∈N
− for any n ∈ N, the number (n + 1) ∈ N.
− there are no other elements of N.
Using these clauses, we can show that 3 ∈ N but 4.5 ∈/ N. This inductive definition lets give a finite
description of an infinite set.
, Example of a power set:
Given a set A we can define the powerset of A, written P(A) as follows:
− ∅ ∈ P(A)
− if a ∈ A and X ∈ P(A) then {a} ∪ X ∈ P(A)
− there are no other elements of P(A)
Let B = {1, 2, 3} then from these rules we can conclude that:
− ∅ ∈ P(B)
− {1} ∪ ∅ ∈ P(B) – or more simply {1} ∈ P(B). Similarly, {2} ∈ P(B), {3} ∈ P(B)
− Repeating the second rule also gives us that, {1, 2} ∈ P(B), {1, 3} ∈ P(B), {2, 3} ∈ P(B)
− Finally, {1, 2, 3} ∈ P(B).
− 0∈N
− for any n ∈ N, the number (s(n)) ∈ N. Here we thing of s as being a unary function symbol
that stands for ‘successor’.
− there are no other elements of N.
We consider the digit 4 to be a shorthand for s(s(s(s(0)))). The Arabic numerals are simply a
shorthand for repeatedly adding one using the successor operation.
Example of a string instead of int:
Induction definition:
− the empty string, which we’ll denote using the symbol ε, is a string;
− if c is one of the 256 ASCII characters and s is a string, we can construct a longer string by
writing cs (that is, the character c followed by the string s).
There is very little that is specific to ASCII in this definition! Given any set A, we can construct the
words of characters over some set A, often written A ⋆ as follows:
− ε∈A⋆
− for all a ∈ A an w ∈ A ⋆ , aw ∈ A ⋆
A⋆ To denote the set of all words over A
A+ To denote the set of non-empty words over A.
That is, the only word of length 0.
Let’s try to construct some example inhabitants of the set {0, 1} ⋆:
− ε ∈ {0, 1} ⋆
− 0 ∈ {0, 1} ⋆ and 1 ∈ {0, 1} ⋆
− 00, 01, 10, 11 are all also in {0, 1} ⋆ .
− As are 000, 001, 010, 100, …
