TOC by Kamala Krithivasan

1.1. Sets, Relations, and Functions

Sets

A set is a collection of well-defined objects. Usually the elements of a set have common properties. For example, all the students who enroll for a course ‘Computability’ make up a set. Formally,

Definition 1.1 A set is an unordered collection of objects.

Note that the definition of a set is intuitive in nature and was stated by the German mathematician Cantor in 1895. The objects in a set are called the elements or members of the set.

Example 1.1.

The set E of even positive integers less than 20 can be expressed by: E = {2, 4, 6, 8, 10, 12, 14, 16, 18} or E = {x|x is even and 0 < x < 20} A set is finite if it contains a finite number of elements and is infinite otherwise. The empty set has no elements and is denoted by φ. Cardinality of a set A is the number of elements in A and is denoted by #A or |A|. For example, if A = {2, 4, 6, 8}, then #A = 4. Note that #φ = 0. If a set is infinite, one can not list all its elements. This set can be specified by providing a property that all members of the set must satisfy. For example, A = {x|x is a positive integer divisible by 3}. The general format of such specification is A = {x|P(x) is a property that x must satisfy}. Sets can be represented by either set builder form or by explicitly listing its elements. Sets can be defined using an inductive definition also. An inductive definition of a set has three components. They are: The basis or basis clause that lists some elements in the set (which are basic building blocks). The induction or inductive clause which states how to produce new elements from the existing elements of the set. The extremal clause which asserts that no object is a member of the set unless its being so follows from a finite number of applications of the basis and inductive clauses.

Example 1.2.

Let W denote the set of well-formed parentheses. It can be defined inductively as follows: Basis clause: [ ] ∊W Inductive clause: if x, y ∊W, xy ∊ W and [x] ∊W Extrenal clause: No object is a member of W unless its being so follows from a finite number of applications of the basis and the inductive clauses. A set A is a subset of a set B if each element of A is also an element of B and is denoted by A ⊆ B. We also say that A is included in B. If A is a subset of B and A is not same as B, then we say that A is a proper subset B and is denoted by A ⊂ B. φ is a subset of every set. Two sets A and B are equal if every element of A is also an element of B and vice versa. We denote equal sets by A = B. Two sets can be combined to form a third set by various set operations. They are union, intersection, and difference. The union of two sets has as elements, the elements of one of the two sets and possibly both. Union is denoted by the symbol ∪ so that A ∪ B = {x|x ∊ A or x ∊ B}. The intersection of two sets is the collection of all elements of the two sets which are common and is denoted by ∩. For two sets A, B, A ∩ B = {x|x ∊ A and x ∊ B}. The difference of two sets A and B denoted by A − B is the set of all elements that are in the set A but not in the set B. For the sets A and B, A − B = {x|x ∊ A and x ∉ B}. Let U be the universal set and A ⊆ U. The complement of A with respect to U is defined as Ā = U − A. The power set of set S is the set of all subsets of S and is denoted by . If S = { a, b, c} then, = {φ, {a}, {b}, {c},{a, b},{b, c}, {a, c}, {a, b, c}}.

Sequences and Tuples

A sequence of objects is a list of objects in some order. For example, the sequence 7, 14, 21 would be written as (7, 14, 21). In a set, the order does not matter but in a sequence it does. Also, repetition is not permitted in a set but is allowed in a sequence. For example, (7, 7, 14, 21, 21) is a sequence whereas {7, 14, 21} is a set. Like sets, sequences may be finite or infinite. Finite sequences are called tuples. A sequence of k elements is called a k-tuple. For example, (2, 4) is a 2-tuple, (7, 14, 21) is a 3-tuple.

If A and B are two sets, the Cartesian product or cross product of A and B written as A × B is the set of all pairs where the first component is a member of the set A and second component is a member of the set B. For example, if

A = {0, 1}, B = {x, y, z}, A × B = {(0, x), (0, y), (0, z), (1, x), (1, y), (1, z) }

One can also write the Cartesian product of k-sets A₁, A₂,..., A_k in a similar fashion.

Relations and Functions

A binary relation on two sets A and B is a subset of A × B. For example, if A = {1, 3, 9}, B = {x, y}, then {(1, x), (3, y), (9, x)} is a binary relation on 2-sets. Binary relations on k–sets A₁, A₂,..., A_k can similarly be defined.

Another basic concept on sets is function. A function is an object that sets up an input-output relationship. That is, a function takes an input and produces the required output. For a function f, with input x, the output y, we write f(x) = y. We also say that f maps x to y. For example, addition is a function which produces the sum of the numbers that are input. The set of possible inputs to a function is called its “domain.” The output of a function comes from a set called its “range.” Let D be the domain and R be the range of a function f. We denote this description of a function as “f: D → R”. For example, f is a function with domain Z and range Z, we write it as f: Z → Z. A function that uses all the elements of the range is said to be onto (surjective). A function “f: D → R” is said to be one-to-one or 1–1 (injective) if for any two distinct elements a, b ∊ D, f(a)≠f(b). A function which is both one-to-one and onto is called a bijective function.

A binary relation K ⊆ A × B has an inverse, say K⁻¹ ⊆ B × A defined as (b, a) ∊ K⁻¹ if and only if (a, b) ∊ K. For example,

K={(x, y)|x ∊ S, y ∊ T, x is the student of y}

K⁻¹={(y, x)|x ∊ S, y ∊ T, y is the teacher of x}

Note that the inverse of a function need not be a function. A function f: A → B may not have an inverse if there is some element b ∊ B such that f(a)=b for no a ∊ A. But every bijective ‘f’ possesses an inverse f⁻¹ (say), and f⁻¹(f(a)) = a for each a ∊ A.

A binary relation R is an equivalence relation if R satisfies the following conditions:

• R is reflexive i.e., for every x, (x, x) ∊ R.
• R is symmetric i.e., for every x and y, (x, y) ∊ R implies (y, x) ∊ R.
• R is transitive i.e., for every x,y and z, (x, y) ∊ R and (y, z) ∊ R implies (x, z) ∊ R.

Equivalence relation on a set A partitions A into equivalence classes. The number of equivalence classes is called the index or rank of an equivalence relation. Index can be finite or infinite.

Example 1.3.

Let N be the set of non-negative integers. The relation ≡ is defined as follows: a ≡ b if and only if a and b leave the same remainder when divided by 3. This can be easily seen to be an equivalence relation of index 3. An equivalence relation induces a partition on the underlying set. In the above example, the set of non-negative integers is partitioned into three equivalence classes: E11={0, 3, 6, ...}, E12={1, 4, 7, ...}, E13={2, 5, 8, ...}, An equivalence relation E2 is a refinement of an equivalence relation E1 if every equivalence class of E2 is contained in an equivalence class of E1. For example, let E1 denote the mod 3 equivalence relation defined in Example 1.3. Let E2 be an equivalence relation on the set of non-negative integers such that aE2b if a and b leave the same remainder when divided by 6. In this case there are 6 equivalence classes. E21={0, 6, 12, ...} E22={1, 7, 13, ...} E23={2, 8, 14, ...} E24={3, 9, 15, ...} E25={4, 10, 16, ...} E26={5, 11, 17, ...} It can be seen that every E2j is completely included in an E1k, 1≤ j ≤ 6, 1 ≤ k ≤ 3. Hence, E2 is a refinement of E1.

Ordered Pairs

Ordered pairs of natural numbers can be represented by a single natural number. That is we are not only interested in encoding ordered pairs into natural numbers, but also in decoding the natural numbers into ordered pairs. That is, we are interested to get a 1–1 mapping from N² to N. One of the simplest form of bijection from N² to N is as below:

Cantor-numbering scheme: Let π² : N² → N be such that

π²(x, y) is called the Cantor number of the ordered pair (x, y). For example, the Cantor number of (2, 4) is 23. The following table lists some Cantor numbers for some pairs.

x|y	0	1	2	3	4	5
0	0	1	3	6	10	15
1	2	4	7	11	16	22
2	5	8	12	17	23	30
3	9	13	18	–	–	–
4	14	19	–	–	–	–
5	20	26	–	–	–	–

This bijection is required in some computer science applications. This method can be used to enumerate ordered triples, as π³(x₁, x₂, x₃) can be looked as π²(π²(x₁, x₂), x₃) and also to enumerate higher-order tuples.

Closures

Closure is an important relationship among sets and is a general tool for dealing with sets and relations of many kinds.

Let R be a binary relation on a set A. Then the reflexive (symmetric, transitive) closure of R is a relation R′ such that:

1. R′ is reflexive (symmetric, transitive)
2. R′ ⊇ R
3. If R″ is a reflexive (symmetric, transitive) relation containing R, then R″ ⊇ R′.

The reflexive, transitive closure of R is denoted by R*. Reflexive, transitive closure of a binary relation R is only one of the several possible closures. R⁺ is a transitive closure of R which need not be reflexive, unless R itself happens to be reflexive.

Finite and Infinite Sets

A finite set contains finite number of elements. The size of the set is its basic property. The set which is not finite is said to be infinite. Two sets A and B have equal number of elements, or is said to be equinumerous if there is a one-to-one, onto function f: A → B. In general, a set is finite if it is equinumerous with the set {1, 2, 3, ..., n} for some natural number n. A set is said to be countably infinite if it is equinumerous with N, the set of natural numbers. A set which is not countable is said to be uncountable.