UNIT 1

SET THEORY: Introduction, Size of sets and cardinals, Venn diagrams, Combination of sets, Ordered pairs and Set identities. Relation & Functions: Relations- Definition, Operations on relations, Composite relations, Properties of relations, Function- Definition, Classification of functions.


SET THEORY

INTRODUCTION


The concept of a set appears in all mathematics. This chapter introduces the notation and terminology of set theory which is basic and used throughout the text. The chapter closes with the formal definition of mathematical induction, with examples.

SIZE OF SETS AND CARDINALS


Set:Unorderd collection of objects is known as set.
Set Representation:Set can be represented in three forms:
1.Listing/Roaster Form

Ex:A={a,u,o,i,e}
Is a set that contains vowel of english alphabet and here order does not matters.

2.Set Builder Form(Quality of set's element)

Ex:
A={x|x is a month of year}

3.Diagram

In This Type of sets we use diagrams to represent it.


Membership in a set is denoted as follows:
a ? S denotes that a belongs to a set S
a, b ? S denotes that a and b belong to a set
Here ? is the symbol meaning “is an element of.”We use ? to mean “is not an element of.”

Specifying Sets
There are essentially two ways to specify a particular set. One way, if possible, is to list its members separated by commas and contained in braces { }.A second way is to state those properties which characterized the elements in the set. Examples illustrating these two ways are:
A = {1, 3, 5, 7, 9} and B = {x | x is an even integer, x > 0}
That is, A consists of the numbers 1, 3, 5, 7, 9. The second set, which reads:
B is the set of x such that x is an even integer and x is greater than 0,
denotes the set B whose elements are the positive integers. Note that a letter, usually x, is used to denote a typical member of the set; and the vertical line | is read as “such that” and the comma as “and.”

EXAMPLE

(a) The set A above can also be written as A = {x | x is an odd positive integer, x < 10}.
(b) We cannot list all the elements of the above set B although frequently we specify the set by B = {2, 4, 6, . . .}
where we assume that everyone knows what we mean. Observe that 8 ? B, but 3 / ? B.
(c) Let E = {x | x2 - 3x + 2 = 0}, F = {2, 1} and G = {1, 2, 2, 1}. Then E = F = G.
We emphasize that a set does not depend on the way in which its elements are displayed. A set remains the same if its elements are repeated or rearranged.
Even if we can list the elements of a set, it may not be practical to do so. That is, we describe a set by listing its elements only if the set contains a few elements; otherwise we describe a set by the property which characterizes its elements.

Subsets

Suppose every element in a set A is also an element of a set B, that is, suppose a ? A implies a ? B. Then A is called a subset of B.We also say that A is contained in B or that B contains A. This relationship is written A ? B or B ? A
Two sets are equal if they both have the same elements or, equivalently, if each is contained in the other. That is:
A = B if and only if A ? B and B ? A
If A is not a subset of B, that is, if at least one element of A does not belong to B.

EXAMPLE

Consider the sets:
A = {1, 3, 4, 7, 8, 9}, B= {1, 2, 3, 4, 5}, C= {1, 3}.
Then C ? A and C ? B since 1 and 3, the elements of C, are also members of A and B. But B does not belong to A since some of the elements of B, e.g., 2 and 5, do not belong to A. Similarly, A does not belong to B.

Property 1: It is common practice in mathematics to put a vertical line “|” or slanted line “/” through a symbol to indicate the opposite or negative meaning of a symbol.
Property 2: The statement A ? B does not exclude the possibility that A = B. In fact, for every set A we have A ? A since, trivially, every element in A belongs to A. However, if A ? B and A not equal to B, then we say A is a proper subset of B (sometimes written A ? B).
Property 3: Suppose every element of a set A belongs to a set B and every element of B belongs to a set C. Then clearly every element of A also belongs to C. In other words, if A ? B and B ? C, then A ? C. The above remarks yield the following theorem.

Theorem:

Let A, B, C be any sets. Then:
(i) A ? A
(ii) If A ? B and B ? A, then A = B
(iii) If A ? B and B ? C, then A ? C

Special symbols
Some sets will occur very often in the text, and so we use special symbols for them. Some such symbols are:
N = the set of natural numbers or positive integers: 1, 2, 3, . . .
Z = the set of all integers: . . . ,-2,-1, 0, 1, 2, . . .
Q = the set of rational numbers
R = the set of real numbers
C = the set of complex numbers
Observe that N ? Z ? Q ? R ? C.

Universal Set, Empty Set

All sets under investigation in any application of set theory are assumed to belong to some fixed large set called the universal set which we denote by "U" unless otherwise stated or implied.
Given a universal set U and a property P, there may not be any elements of U which have property P. For example, the following set has no elements:
S = {x | x is a positive integer, x2 = 3}
Such a set with no elements is called the empty set or null set and is denoted by
Ø
There is only one empty set. That is, if S and T are both empty, then S = T , since they have exactly the same elements, namely, none.
The empty set Ø is also regarded as a subset of every other set. Thus we have the following simple result which we state formally.

Theorem 1.2: For any set A, we have Ø ? A ? U.

Disjoint Sets

Two sets A and B are said to be disjoint if they have no elements in common. For example, suppose
A = {1, 2}, B= {4, 5, 6}, and C = {5, 6, 7, 8}
Then A and B are disjoint, and A and C are disjoint. But B and C are not disjoint since B and C have elements in common, e.g., 5 and 6.We note that if A and B are disjoint, then neither is a subset of the other (unless one is the empty set).

VENN DIAGRAMS

A Venn diagram is a pictorial representation of sets in which sets are represented by enclosed areas in the plane. The universal set U is represented by the interior of a rectangle, and the other sets are represented by disks lying within the rectangle. If A ? B, then the disk representing A will be entirely within the disk representing B as in Fig.(a). If A and B are disjoint, then the disk representing A will be separated from the disk representing B as in Fig.(b).

However, if A and B are two arbitrary sets, it is possible that some objects are in A but not in B, some are in B but not in A, some are in both A and B, and some are in neither A nor B; hence in general we represent A and B as in Fig.(c).

Arguments and Venn Diagrams

Many verbal statements are essentially statements about sets and can therefore be described by Venn diagrams. Hence Venn diagrams can sometimes be used to determine whether or not an argument is valid.

EXAMPLE

Show that the following argument (adapted from a book on logic by Lewis Carroll, the author of Alice in Wonderland) is valid:
S1: All my tin objects are saucepans.
S2: I find all your presents very useful.
S3: None of my saucepans is of the slightest use.
S : Your presents to me are not made of tin.
The statements S1, S2, and S3 above the horizontal line denote the assumptions, and the statement S below the line denotes the conclusion. The argument is valid if the conclusion S follows logically from the assumptions S1, S2, and S3.
By S1 the tin objects are contained in the set of saucepans, and by S3 the set of saucepans and the set of useful things are disjoint. Furthermore, by S2 the set of “your presents” is a subset of the set of useful things.
Accordingly, we can draw the Venn diagram in Fig.
The conclusion is clearly valid by the Venn diagram because the set of “your presents” is disjoint from the set of tin objects.

COMBINATIONS OF SETS

We sometimes make a selection from a set without regard of order.Such a selection is called a combination.

EXAMPLE

Find all the combinations of 3 letters taken from the set of 5 letters {A,B,C,D,E}

The combinations are: {A,B,C}  ,  {A,B,D},
{A,B,E}  ,  {A,C,D},
{A,C,E}  ,  {A,D,E},
{B,C,D}  ,  {B,C,E},
{B,D,E}  ,  {C,D,E},
There are 10 combinations of the 5 letters tken 3 at a time.

SET OPERATIONS

This section introduces a number of set operations, including the basic operations of union, intersection, and complement.

Union and Intersection

The union of two sets A and B, denoted by A ? B, is the set of all elements which belong to A or to B; that is,
A ? B = {x | x ? A or x ? B}
Here “or” is used in the sense of and/or. Figure(a) is a Venn diagram in which A ? B is shaded. The intersection of two sets A and B, denoted by A n B, is the set of elements which belong to both A and B; that is,
A n B = {x | x ? A and x ? B}
Figure(b) is a Venn diagram in which A n B is shaded.

Recall that sets A and B are said to be disjoint or nonintersecting if they have no elements in common or, using the definition of intersection, if A n B = Ø, the empty set. Suppose
S = A ? B and A n B = Ø
Then S is called the disjoint union of A and B.

EXAMPLE

(a) Let A = {1, 2, 3, 4}, B = {3, 4, 5, 6, 7}, C = {2, 3, 8, 9}. Then
A ? B = {1, 2, 3, 4, 5, 6, 7}, A? C = {1, 2, 3, 4, 8, 9}, B? C = {2, 3, 4, 5, 6, 7, 8, 9},
A n B = {3, 4}, An C = {2, 3}, Bn C = {3}.
(b) Let U be the set of students at a university, and let M denote the set of male students and let F denote the set of female students. The U is the disjoint union of M of F; that is,
U = M ? F and M n F = Ø
This comes from the fact that every student in U is either in M or in F, and clearly no student belongs to both M and F, that is, M and F are disjoint.

The following properties of union and intersection should be noted.

Property 1: Every element x in AnB belongs to both A and B; hence x belongs to A and x belongs to B. Thus A n B is a subset of A and of B; namely
A n B ? A and A n B ? B

Property 2: An element x belongs to the union A? B if x belongs to A or x belongs to B; hence every element in A belongs to A ? B, and every element in B belongs to A ? B. That is,
A ? A ? B and B ? A ? B
We state the above results formally:

Theorem:

For any sets A and B, we have:
(i) A n B ? A ? A ? B and (ii) A n B ? B ? A ? B.
The operation of set inclusion is closely related to the operations of union and intersection, as shown by the following theorem.

Theorem :

The following are equivalent: A ? B, A n B = A, A ? B = B.

Complements, Differences, Symmetric Differences

Recall that all sets under consideration at a particular time are subsets of a fixed universal set U. The absolute complement or, simply, complement of a set A, denoted by AC, is the set of elements which belong to U but which do not belong to A. That is,
AC = {x | x ? U, x does not belong to A}
Some texts denote the complement of A by A'. Fig.(a) is a Venn diagram in which AC is shaded.
The relative complement of a set B with respect to a set A or, simply, the difference of A and B, denoted by
A\B, is the set of elements which belong to A but which do not belong to B; that is
A\B = {x | x ? A, x does not belong to B}
The set A\B is read “A minus B.” Many texts denote A\B by A - B or A ~ B. Fig.(b) is a Venn diagram in which A\B is shaded.
The symmetric difference of sets A and B, denoted by A ? B, consists of those elements which belong to A or B but not to both. That is,
A ? B = (A ? B)\(A n B) or A ? B = (A\B) ? (B\A)
Figure(c) is a Venn diagram in which A ? B is shaded.

EXAMPLE

Suppose U = N = {1, 2, 3, . . .} is the universal set. Let
A = {1, 2, 3, 4}, B= {3, 4, 5, 6, 7}, C= {2, 3, 8, 9}, E= {2, 4, 6, . . .}
(Here E is the set of even integers.) Then:
AC = {5, 6, 7, . . .}, BC = {1, 2, 8, 9, 10, . . .}, EC = {1, 3, 5, 7, . . .}
That is, EC is the set of odd positive integers. Also:
A\B = {1, 2}, A\C = {1, 4}, B\C = {4, 5, 6, 7}, A\E = {1, 3},
B\A = {5, 6, 7}, C\A = {8, 9}, C\B = {2, 8, 9}, E\A = {6, 8, 10, 12, . . .}.

Furthermore:
A ? B = (A\B) ? (B\A) = {1, 2, 5, 6, 7}, B? C = {2, 4, 5, 6, 7, 8, 9},
A ? C = (A\C) ? (B\C) = {1, 4, 8, 9}, A? E = {1, 3, 6, 8, 10, . . .}.

EXAMPLE

Figure(a) is the Venn diagram of three sets A, B, C. The following lists the m = 23 = 8 fundamental products of the sets A, B, C:
P1 = A n B n C,   P3 = A n BC n C,   P5 = AC n B n C,   P7 = AC n BC n C,
P2 = A n B n CC,   P4 = A n BC n CC,   P6 = AC n B n CC,   P8 = AC n BC n CC.
The eight products correspond precisely to the eight disjoint regions in the Venn diagram of sets A, B, C as indicated by the labeling of the regions in Fig(b).

FINITE SETS

Sets can be finite or infinite.A set S is said to be finite if S is empty or if S contains exactly m elements where m is a positive integer; otherwise S is infinite.

EXAMPLE

(a) The set A of the letters of the English alphabet and the setD of the days of the week are finite sets. Specifically, A has 26 elements and D has 7 elements.
(b) Let E be the set of even positive integers, and let I be the unit interval, that is,
E = {2, 4, 6, . . .} and I = [0, 1] = {x | 0 = x = 1}
Then both E and I are infinite.

A set S is countable if S is finite or if the elements of S can be arranged as a sequence, in which case S is said to be countably infinite; otherwise S is said to be uncountable. The above set E of even integers is countably infinite, whereas one can prove that the unit interval I = [0, 1] is uncountable.

Inclusion–Exclusion Principle

There is a formula for n(A ? B) even when they are not disjoint, called the Inclusion–Exclusion Principle.
Namely:

Theorem (Inclusion–Exclusion Principle):

Suppose A and B are finite sets. Then A ? B and A n B are finite and
n(A ? B) = n(A) + n(B) - n(A n B)
That is, we find the number of elements in A or B (or both) by first adding n(A) and n(B) (inclusion) and then subtracting n(A n B) (exclusion) since its elements were counted twice.
We can apply this result to obtain a similar formula for three sets:

Corollary: Suppose A, B, C are finite sets. Then A ? B ? C is finite and

n(A ? B ? C) = n(A) + n(B) + n(C) - n(A n B) - n(A n C) - n(B n C) + n(A n B n C)

Mathematical induction may be used to further generalize this result to any number of finite sets.

EXAMPLE

Suppose a list A contains the 30 students in a mathematics class, and a list B contains the 35 students in an English class, and suppose there are 20 names on both lists. Find the number of students:
(a) only on list A, (b) only on list B, (c) on list A or B (or both), (d) on exactly one list.

(a) List A has 30 names and 20 are on list B; hence 30 - 20 = 10 names are only on list A.
(b) Similarly, 35 - 20 = 15 are only on list B.
(c) We seek n(A ? B).
By inclusion–exclusion,
n(A ? B) = n(A) + n(B) - n(A n B) = 30 + 35 - 20 = 45.
In other words, we combine the two lists and then cross out the 20 names which appear twice.
(d) By (a) and (b), 10 + 15 = 25 names are only on one list; that is, n(A ? B) = 25.

CLASSES OF SETS, POWER SETS, PARTITIONS

Given a set S, we might wish to talk about some of its subsets. Thus we would be considering a set of sets.
Whenever such a situation occurs, to avoid confusion, we will speak of a class of sets or collection of sets rather than a set of sets. If we wish to consider some of the sets in a given class of sets, then we speak of subclass or subcollection.

EXAMPLE

Suppose S = {1, 2, 3, 4}.

(a) Let A be the class of subsets of S which contain exactly three elements of S. Then
A = [{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}]
That is, the elements of A are the sets {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}.

(b) Let B be the class of subsets of S, each which contains 2 and two other elements of S. Then
B = [{1, 2, 3}, {1, 2, 4}, {2, 3, 4}]
The elements of B are the sets {1, 2, 3}, {1, 2, 4}, and {2, 3, 4}. Thus B is a subclass of A, since every element of B is also an element of A. (To avoid confusion, we will sometimes enclose the sets of a class in brackets instead of braces.)

Power Sets

For a given set S , we may speak of the class of all subsets of S. This class is called the power set of S , and will be denoted by P(S). If S is finite, then so is P(S). In fact, the number of elements in P(S) is 2 raised to the power n(S). That is,
n(P (S)) = 2n(S)

EXAMPLE

Suppose S = {1, 2, 3}. Then
P(S) = [Ø, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, S]
Note that the empty set Ø belongs to P(S) since Ø is a subset of S. Similarly, S belongs to P(S). As expected from the above remark, P(S) has 23 = 8 elements.

Partitions

Let S be a nonempty set. A partition of S is a subdivision of S into nonoverlapping, nonempty subsets.
Precisely, a partition of S is a collection {Ai } of nonempty subsets of S such that:

(i) Each a in S belongs to one of the Ai .
(ii) The sets of {Ai } are mutually disjoint; that is, if

Aj not= Ak then Aj n Ak = Ø
The subsets in a partition are called cells. Figure is a Venn diagram of a partition of the rectangular set S of points into five cells, A1, A2,A3,A4,A5.


EXAMPLE

Consider the following collections of subsets of S = {1, 2, . . ., 8, 9}:
(i) [{1, 3, 5}, {2, 6}, {4, 8, 9}]
(ii) [{1, 3, 5}, {2, 4, 6, 8}, {5, 7, 9}]
(iii) [{1, 3, 5}, {2, 4, 6, 8}, {7, 9}]

Then (i) is not a partition of S since 7 in S does not belong to any of the subsets. Furthermore, (ii) is not a partition of S since {1, 3, 5} and {5, 7, 9} are not disjoint. On the other hand, (iii) is a partition of S.

SET IDENTITIES, DUALITY

Sets under the operations of union, intersection, and complement satisfy various laws (identities) which are
listed in Table. In fact, we formally state this as:

Theorem:

Sets satisfy the laws in Table .



Remark: Each law in Table 1-1 follows from an equivalent logical law. Consider, for example, the proof of DeMorgan’s Law 10(a):
(A ? B)C = {x |x /? (A or B)} = {x |x /? A and x /? B} = AC n BC
Here we use the equivalent (DeMorgan’s) logical law:
¬(p ? q) = ¬p ?¬q
where ¬ means “not,” ? means “or,” and ? means “and.” (Sometimes Venn diagrams are used to illustrate the laws in Table 1-1)

Duality

The identities in Table 1-1 are arranged in pairs, as, for example, (2a) and (2b).We now consider the principle behind this arrangement. Suppose E is an equation of set algebra. The dual E * of E is the equation obtained by replacing each occurrence of ?, n, U and Ø in E by n, ?, Ø, and U, respectively. For example, the dual of (U n A) ? (B n A) = A is (Ø ? A) n (B ? A) = A
Observe that the pairs of laws in Table 1-1 are duals of each other. It is a fact of set algebra, called the principle of duality, that if any equation E is an identity then its dual E* is also an identity.

RELATIONS AND FUNCTIONS

INTRODUCTION

The reader is familiar with many relations such as “less than,” “is parallel to,” “is a subset of,” and so on.
In a certain sense, these relations consider the existence or nonexistence of a certain connection between pairs of objects taken in a definite order. Formally, we define a relation in terms of these “ordered pairs.”
An ordered pair of elements a and b, where a is designated as the first element and b as the second element, is denoted by (a, b). In particular,
(a, b) = (c, d)
if and only if a = c and b = d. Thus (a, b) not= (b, a) unless a = b. This contrasts with sets where the order of elements is irrelevant; for example, {3, 5} = {5, 3}.

PRODUCT SETS

Consider two arbitrary sets A and B. The set of all ordered pairs (a, b) where a ? A and b ? B is called the product, or Cartesian product, of A and B. A short designation of this product is A × B, which is read “A cross B.” By definition,
A × B = {(a, b) | a ? A and b ? B}
One frequently writes A2 instead of A × A.

EXAMPLE

Let A = {1, 2} and B = {a, b, c}. Then
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
B × A = {(a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2)}
Also, A × A = {(1, 1), (1, 2), (2, 1), (2, 2)}

RELATIONS

We begin with a definition.
Definition : Let A and B be sets. A binary relation or, simply, relation from A to B is a subset of A × B.
Suppose R is a relation from A to B. Then R is a set of ordered pairs where each first element comes from A and each second element comes from B. That is, for each pair a ? A and b ? B, exactly one of the following is true:
(i) (a, b) ? R; we then say “a is R-related to b”, written aRb.
(ii) (a, b) does not belong to R; we then say “a is not R-related to b”.
If R is a relation from a set A to itself, that is, if R is a subset of A2 = A×A, then we say that R is a relation on A.
The domain of a relation R is the set of all first elements of the ordered pairs which belong to R, and the range is the set of second elements.

OPERATIONS ON RELATIONS

Inverse Relation

Let R be any relation from a set A to a set B. The inverse of R, denoted by R-1, is the relation from B to A which consists of those ordered pairs which, when reversed, belong to R; that is,
R-1 = {(b, a) | (a, b) ? R}

For example, let A = {1, 2, 3} and B = {x, y, z}. Then the inverse of
R = {(1, y), (1, z), (3, y)} is R-1 = {(y, 1), (z, 1), (y, 3)} Clearly, if R is any relation, then (R-1)-1 = R. Also, the domain and range of R-1 are equal, respectively, to the range and domain of R. Moreover, if R is a relation on A, then R-1 is also a relation on A.

Composition of Relation

Let A, B and C be sets, and let R be a relation from A to B and let S be a relation from B to C. That is, R is a subset of A × B and S is a subset of B × C. Then R and S give rise to a relation from A to C denoted by R?S and defined by:
a(R?S)c if for some b ? B we have aRb and bSc.
That is ,
R ? S = {(a, c) | there exists b ? B for which (a, b) ? R and (b, c) ? S}
The relation R?S is called the composition of R and S; it is sometimes denoted simply by RS.
Suppose R is a relation on a set A, that is, R is a relation from a set A to itself. Then R?R, the composition of R with itself, is always defined. Also, R?R is sometimes denoted by R2. Similarly, R3 = R2?R = R?R?R, and so on. Thus Rn is defined for all positive n.

EXAMPLE

Let A = {1, 2, 3, 4}, B = {a, b, c, d}, C = {x, y, z} and let
R = {(1, a), (2, d), (3, a), (3, b), (3, d)} and S = {(b, x), (b, z), (c, y), (d, z)}
Consider the arrow diagrams of R and S as in Fig. Observe that there is an arrow from 2 to d which is followed by an arrow from d to z. We can view these two arrows as a “path” which “connects” the element 2 ? A to the element z ? C. Thus:
  2(R ? S)z since 2Rd and dSz

Similarly there is a path from 3 to x and a path from 3 to z. Hence
  3(R?S)x and 3(R?S)z

No other element of A is connected to an element of C. Accordingly,
  R ? S = {(2, z), (3, x), (3, z)}
Our first theorem tells us that composition of relations is associative.

Theorem:

Let A, B, C and D be sets. Suppose R is a relation from A to B, S is a relation from B to C, and T is a relation from C to D. Then
(R ? S) ? T = R ? (S ? T )

Composition of Relations and Matrices

There is another way of finding R?S. Let MR and MS denote respectively the matrix representations of the relations R and S. Then

The nonzero entries in this matrix tell us which elements are related by R?S. Thus M = MRMS and MR?S have the same nonzero entries.

PROPERTIES OF RELATIONS

This section discusses a number of important types of relations defined on a set A.

Reflexive Relations
A relation R on a set A is reflexive if aRa for every a ? A, that is, if (a, a) ? R for every a ? A. Thus R is not reflexive if there exists a ? A such that (a, a) does not belong to R.

EXAMPLE

Consider the following five relations on the set A = {1, 2, 3, 4}:
    R1 = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}
    R2 = {(1, 1)(1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
    R3 = {(1, 3), (2, 1)}
    R4 = Ø, the empty relation
    R5 = A × A, the universal relation
Determine which of the relations are reflexive.
Since A contains the four elements 1, 2, 3, and 4, a relation R on A is reflexive if it contains the four pairs (1, 1), (2, 2), (3, 3), and (4, 4). Thus only R2 and the universal relation R5 = A × A are reflexive. Note that R1,R3, and R4 are not reflexive since, for example, (2, 2) does not belong to any of them.

EXAMPLE

Consider the following five relations:
(1) Relation = (less than or equal) on the set Z of integers.
(2) Set inclusion ? on a collection C of sets.
(3) Relation ? (perpendicular) on the set L of lines in the plane.
(4) Relation (parallel) on the set L of lines in the plane.
(5) Relation | of divisibility on the set N of positive integers.
Determine which of the relations are reflexive.

The relation (3) is not reflexive since no line is perpendicular to itself. Also (4) is not reflexive since no line is parallel to itself. The other relations are reflexive; that is, x = x for every x ? Z, A ? A for any set A ? C, and n | n for every positive integer n ? N.

Symmetric and Antisymmetric Relations

A relation R on a set A is symmetric if whenever aRb then bRa, that is, if whenever (a, b) ? R then (b, a) ? R.
Thus R is not symmetric if there exists a, b ? A such that (a, b) ? R but (b, a) does not belong to R.

Transitive Relations

A relation R on a set A is transitive if whenever aRb and bRc then aRc, that is, if whenever (a, b), (b, c) ? R
then (a, c) ? R. Thus R is not transitive if there exist a, b, c ? R such that (a, b), (b, c) ? R but (a, c) / ? R.

CLOSURE PROPERTIES

Consider a given set A and the collection of all relations on A. Let P be a property of such relations, such as being symmetric or being transitive. A relation with property P will be called a P-relation. The P-closure of an arbitrary relation R on A, written P(R), is a P-relation such that
                    R ? P(R) ? S
for every P-relation S containing R.We will write
reflexive(R),         symmetric(R),             and transitive(R)
for the reflexive, symmetric, and transitive closures of R.

Reflexive and Symmetric Closures

The next theorem tells us how to obtain easily the reflexive and symmetric closures of a relation. Here = {(a, a) | a ? A} is the diagonal or equality relation on A.

Theorem :

Let R be a relation on a set A. Then:
(i) R ? is the reflexive closure of R.
(ii) R ? R-1 is the symmetric closure of R.
In other words, reflexive(R) is obtained by simply adding to R those elements (a, a) in the diagonal which do not already belong to R, and symmetric(R) is obtained by adding to R all pairs (b, a) whenever (a, b) belongs to R.

EXAMPLE

Consider the relationR = {(1, 1), (1, 3), (2, 4), (3, 1), (3, 3), (4, 3)} on the setA = {1, 2, 3, 4}. Then
reflexive(R) = R ? {(2, 2), (4, 4)} and symmetric(R) = R ? {(4, 2), (3, 4)}

Transitive Closure

Let R be a relation on a set A. Recall that R2 = R?R and Rn = Rn-1?R.We define

This gives us the following theorem:

Theorem:

Let R be a relation on a set A with n elements. Then
transitive (R) = R ? R2 ? . . . ? Rn

EXAMPLE

Consider the relation R = {(1, 2), (2, 3), (3, 3)} on A = {1, 2, 3}. Then:
R2 = R?R = {(1, 3), (2, 3), (3, 3)} and R3 = R2?R = {(1, 3), (2, 3), (3, 3)}
Accordingly,
transitive (R) = {(1, 2), (2, 3), (3, 3), (1, 3)}

EQUIVALENCE RELATIONS

Consider a nonempty set S. A relation R on S is an equivalence relation if R is reflexive, symmetric, and transitive. That is, R is an equivalence relation on S if it has the following three properties:

(1) For every a ? S, aRa. (2) If aRb, then bRa. (3) If aRb and bRc, then aRc.

The general idea behind an equivalence relation is that it is a classification of objects which are in some way “alike.” In fact, the relation “=” of equality on any set S is an equivalence relation; that is:

(1) a = a for every a ? S. (2) If a = b, then b = a. (3) If a = b, b = c, then a = c.
Other equivalence relations follow.

EXAMPLE

(a) Let L be the set of lines and let T be the set of triangles in the Euclidean plane.
  (i) The relation “is parallel to or identical to” is an equivalence relation on L.
  (ii) The relations of congruence and similarity are equivalence relations on T.
(b) The relation ? of set inclusion is not an equivalence relation. It is reflexive and transitive, but it is not symmetric since A ? B does not imply B ? A.
(c) Let m be a fixed positive integer. Two integers a and b are said to be congruent modulo m, written a = b (mod m)
if m divides a - b. For example, for the modulus m = 4, we have
11 = 3 (mod 4) and 22 = 6 (mod 4)
since 4 divides 11-3 = 8 and 4 divides 22-6 = 16. This relation of congruence modulo m is an important equivalence relation.

Equivalence Relations and Partitions

This subsection explores the relationship between equivalence relations and partitions on a non-empty set S.
Recall first that a partition P of S is a collection {Ai} of nonempty subsets of S with the following two properties:
(1) Each a ? S belongs to some Ai .
(2) If Ai not= Aj then Ai n Aj = Ø.
In other words, a partition P of S is a subdivision of S into disjoint nonempty sets.
Suppose R is an equivalence relation on a set S. For each a ? S, let [a] denote the set of elements of S to which a is related under R; that is:
[a] = {x | (a, x) ? R}
We call [a] the equivalence class of a in S; any b ? [a] is called a representative of the equivalence class. The collection of all equivalence classes of elements of S under an equivalence relation R is denoted by S/R, that is,
S/R = {[a] | a ? S}
It is called the quotient set of S by R. The fundamental property of a quotient set is contained in the following theorem.

Theorem :

Let R be an equivalence relation on a set S. Then S/R is a partition of S. Specifically:
(i) For each a in S, we have a ? [a].
(ii) [a] = [b] if and only if (a, b) ? R.
(iii) If [a] not= [b], then [a] and [b] are disjoint.
Conversely, given a partition {Ai } of the set S, there is an equivalence relation R on S such that the sets Ai are the equivalence classes.

EXAMPLE

(a) Consider the relation R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)} on S = {1, 2, 3}.
One can show that R is reflexive, symmetric, and transitive, that is, that R is an equivalence relation. Also:
[1] = {1, 2}, [2] = {1, 2}, [3] = {3}
Observe that [1] = [2] and that S/R = {[1], [3]} is a partition of S. One can choose either {1, 3} or {2, 3} as a set of representatives of the equivalence classes.
(b) Let R5 be the relation of congruence modulo 5 on the set Z of integers denoted by
x = y (mod 5)
This means that the difference x -y is divisible by 5. Then R5 is an equivalence relation on Z. The quotient set Z/R5 contains the following five equivalence classes:

A0 = {. . . ,-10,-5, 0, 5, 10, . . .}
A1 = {. . . ,-9,-4, 1, 6, 11, . . .}
A2 = {. . . ,-8,-3, 2, 7, 12, . . .}
A3 = {. . . ,-7,-2, 3, 8, 13, . . .}
A4 = {. . . ,-6,-1, 4, 9, 14, . . .}
Any integer x, uniquely expressed in the form x = 5q +r where r lies in [0,5), is a member of the equivalence class Ar , where r is the remainder.As expected, Z is the disjoint union of equivalence classes A1,A2,A3,A4.
Usually one chooses {0, 1, 2, 3, 4} or {-2,-1, 0, 1, 2} as a set of representatives of the equivalence classes.

PARTIAL ORDERING RELATIONS

Arelation R on a set S is called a partial ordering or a partial order of S if R is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is called a partially ordered set or poset.

EXAMPLE

(a) The relation ? of set inclusion is a partial ordering on any collection of sets since set inclusion has the three desired properties. That is,
(1) A ? A for any set A.
(2) If A ? B and B ? A, then A = B.
(3) If A ? B and B ? C, then A ? C.
(b) The relation = on the set R of real numbers is reflexive, antisymmetric, and transitive. Thus = is a partial ordering on R.
(c) The relation “a divides b,” written a | b, is a partial ordering on the set N of positive integers. However, “a divides b” is not a partial ordering on the set Z of integers since a | b and b | a need not imply a = b. For example, 3|-3 and -3 | 3 but 3 = -3.

FUNCTIONS

INTRODUCTION

Suppose that to each element of a set A we assign a unique element of a set B; the collection of such assignments is called a function from A into B. The set A is called the domain of the function, and the set B is called the target set or codomain.
Functions are ordinarily denoted by symbols. For example, let f denote a function from A into B. Then we write
f: A ? B
which is read: “f is a function from A into B,” or “f takes (or maps) A into B.” If a ? A, then f (a) (read: “f of a”) denotes the unique element of B which f assigns to a; it is called the image of a under f, or the value of f at a.

The set of all image values is called the range or image of f. The image of f : A ? B is denoted by Ran(f ),
Im(f ) or f (A).
Frequently, a function can be expressed by means of a mathematical formula. For example, consider the function which sends each real number into its square.We may describe this function by writing
f (x) = x2

In the first notation, x is called a variable and the letter f denotes the function. In the second notation, the barred arrow ?is read “goes into.” In the last notation, x is called the independent variable and y is called the dependent variable since the value of y will depend on the value of x.

Remark: Whenever a function is given by a formula in terms of a variable x, we assume, unless it is otherwise stated, that the domain of the function is R (or the largest subset of R for which the formula has meaning) and the codomain is R.

EXAMPLE

(a) Consider the function f (x) = x3, i.e., f assigns to each real number its cube. Then the image of 2 is 8, and so we may write f (2) = 8.
(b) Figure defines a function f from A = {a, b, c, d} into B = {r, s, t , u} in the obvious way. Here f (a) = s, f (b) = u, f (c) = r, f (d) = s
The image of f is the set of image values, {r, s, u}. Note that t does not belong to the image of f because t is not the image of any element under f.
(c) Let A be any set. The function from A into A which assigns to each element in A the element itself is called the identity function on A and it is usually denoted by 1A, or simply 1. In other words, for every a ? A, 1A(a) = a.
(d) Suppose S is a subset of A, that is, suppose S ? A. The inclusion map or embedding of S into A, denoted by i: S ? A is the function such that, for every x ? S, i(x) = x
The restriction of any function f: A ? B, denoted by f |S is the function from S into B such that, for any x ? S, f |S(x) = f (x)

Composition Function

Consider functions f: A ? B and g: B ? C; that is, where the codomain of f is the domain of g. Then we may define a new function from A to C, called the composition of f and g and written g?f , as follows:
(g?f )(a) = g(f (a))
That is, we find the image of a under f and then find the image of f (a) under g. This definition is not really new. If we view f and g as relations, then this function is the same as the composition of f and g as relations except that here we use the functional notation g?f for the composition of f and g instead of the notation f ?g which was used for relations.
Consider any function f: A ? B. Then
f ?1A = f and 1B?f = f
where 1A and 1B are the identity functions on A and B, respectively.

CLASSIFICATION OF FUNCTIONS

ONE-TO-ONE, ONTO, AND INVERTIBLE FUNCTIONS

A function f : A ? B is said to be one-to-one (written 1-1) if different elements in the domain A have distinct images.
. A function f: A ? B is said to be an onto function if each element of B is the image of some element of A.
In other words, f : A ? B is onto if the image of f is the entire codomain, i.e., if f (A) = B. In such a case we say that f is a function from A onto B or that f maps A onto B.
A function f: A ? B is invertible if its inverse relation f-1 is a function from B to A. In general, the inverse relation f-1 may not be a function. The following theorem gives simple criteria which tells us when it is.

Theorem :

A function f: A ? B is invertible if and only if f is both one-to-one and onto.
If f : A ? B is one-to-one and onto, then f is called a one-to-one correspondence between A and B. This terminology comes from the fact that each element of A will then correspond to a unique element of B and vice versa.

Some texts use the terms injective for a one-to-one function, surjective for an onto function, and bijective for a one-to-one correspondence.

EXAMPLE

Consider the functions f1: A ? B, f2: B ? C, f3: C ? D and f4: D ? E defined by the diagram of Fig. Now f1 is one-to-one since no element of B is the image of more than one element of A.
Similarly, f2 is one-to-one. However, neither f3 nor f4 is one-to-one since f3(r) = f3(u) and f4(v) = f4(w)

As far as being onto is concerned, f2 and f3 are both onto functions since every element of C is the image under f2 of some element of B and every element of D is the image under f3 of some element of C, f2(B) = C and f3(C) = D. On the other hand, f1 is not onto since 3 ? B is not the image under f4 of any element of A. and f4 is not onto since x ? E is not the image under f4 of any element of D.
Thus f1 is one-to-one but not onto, f3 is onto but not one-to-one and f4 is neither one-to-one nor onto. However, f2 is both one-to-one and onto, i.e., is a one-to-one correspondence between A and B. Hence f2 is invertible and f-12 is a function from C to B.

EXAMPLE

Consider the following four functions from R into R:
f1(x) = x2, f2(x) = 2x, f3(x) = x3 - 2x2 - 5x + 6, f4(x) = x3
The graphs of these functions appear in Fig. Observe that there are horizontal lines which intersect the graph of f1 twice and there are horizontal lines which do not intersect the graph of f1 at all; hence f1 is neither oneto- one nor onto. Similarly, f2 is one-to-one but not onto, f3 is onto but not one-to-one and f4 is both one-to-one and onto. The inverse of f4 is the cube root function.


RECURSIVELY DEFINED FUNCTIONS

A function is said to be recursively defined if the function definition refers to itself. In order for the definition not to be circular, the function definition must have the following two properties:
(1) There must be certain arguments, called base values, for which the function does not refer to itself.
(2) Each time the function does refer to itself, the argument of the function must be closer to a base value.
A recursive function with these two properties is said to be well-defined.
The following examples should help clarify these ideas.

Factorial Function
The product of the positive integers from 1 to n, inclusive, is called “n factorial” and is usually denoted by n!.
That is,
n! = n(n - 1)(n - 2) · · · 3 · 2 · 1
It is also convenient to define 0! = 1, so that the function is defined for all nonnegative integers. Thus:
0! = 1, 1! = 1, 2! = 2 · 1 = 2, 3! = 3 · 2 · 1 = 6, 4! = 4 · 3 · 2 · 1 = 24
5! = 5 · 4 · 3 · 2 · 1 = 120, 6! = 6 · 5 · 4 · 3 · 2 · 1 = 720
And so on. Observe that
5! = 5 · 4! = 5 · 24 = 120 and 6! = 6 · 5! = 6 · 120 = 720
This is true for every positive integer n; that is,
n! = n · (n - 1)!
Accordingly, the factorial function may also be defined as follows:

Definition (Factorial Function):
(a) If n = 0, then n! = 1.
(b) If n > 0, then n! = n · (n - 1)!
Observe that the above definition of n! is recursive, since it refers to itself when it uses (n - 1)!. However:
(1) The value of n! is explicitly given when n = 0 (thus 0 is a base value).
(2) The value of n! for arbitrary n is defined in terms of a smaller value of n which is closer to the base value 0.
Accordingly, the definition is not circular, or, in other words, the function is well-defined.

EXAMPLE

figure shows the nine steps to calculate 4! using the recursive definition. Specifically:
Step 1. This defines 4! in terms of 3!, so we must postpone evaluating 4! until we evaluate 3. This postponement is indicated by indenting the next step.
Step 2. Here 3! is defined in terms of 2!, so we must postpone evaluating 3! until we evaluate 2!.
Step 3. This defines 2! in terms of 1!.
Step 4. This defines 1! in terms of 0!.
Step 5. This step can explicitly evaluate 0!, since 0 is the base value of the recursive definition.
Steps 6 to 9.We backtrack, using 0! to find 1!, using 1! to find 2!, using 2! to find 3!, and finally using 3! to find 4!. This backtracking is indicated by the “reverse” indention.

Observe that we backtrack in the reverse order of the original postponed evaluations.

Level Numbers

Let P be a procedure or recursive formula which is used to evaluate f (X) where f is a recursive function and X is the input.We associate a level number with each execution of P as follows. The original execution of P is assigned level 1; and each time P is executed because of a recursive call, its level is one more than the level of the execution that made the recursive call. The depth of recursion in evaluating f (X) refers to the maximum level number of P during its execution.

Consider, for example, the evaluation of 4!which uses the recursive formula n! = n(n - 1)!.

Step 1 belongs to level 1 since it is the first execution of the formula. Thus:
Step 2 belongs to level 2; Step 3 to level 3, . . . ; Step 5 to level 5.
On the other hand, Step 6 belongs to level 4 since it is the result of a return from level 5. In other words, Step 6 and Step 4 belong to the same level of execution. Similarly,
Step 7 belongs to level 3; Step 8 to level 2; and Step 9 to level 1.
Accordingly, in evaluating 4!, the depth of the recursion is 5.

Fibonacci Sequence

The celebrated Fibonacci sequence (usually denoted by F0, F1, F2, . . .) is as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .
That is, F0 = 0 and F1 = 1 and each succeeding term is the sum of the two preceding terms. For example, the next two terms of the sequence are
34 + 55 = 89 and 55 + 89 = 144
A formal definition of this function follows:
Definition (Fibonacci Sequence): (a) If n = 0, or n = 1, then Fn = n.
(b) If n > 1, then Fn = Fn-2 + Fn-1.
This is another example of a recursive definition, since the definition refers to itself when it uses Fn-2 and Fn-1 However:
(1) The base values are 0 and 1.
(2) The value of Fn is defined in terms of smaller values of n which are closer to the base values.
Accordingly, this function is well-defined.