Let

**f**be a one-to-one correspondence from the set**A**to the set**B**.The inverse function of

**f**is the function that assigns to an element**b**belonging to B the unique element**a**in A such that**f(a) = b**.The inverse function of

**f**is denoted by**f**(b) = a when f(a) = b.^{−1}If a function

**f**is not a one-to-one correspondence, we cannot deﬁne an inverse function of**f**.When

**f**is not a one-to-one correspondence, either it is not one-to-one or it is not onto. If**f**is not one-to-one, some element**b**in the codomain is the image of more than one element in the**domain**.If

**f**is not onto, for some element**b**in the codomain, no element**a**in the domain exists for which**f(a) = b**.Consequently, if

**f**is not a one-to-one correspondence, we cannot assign to each element**b**in the codomain a unique element**a**in the domain such that**f(a) = b**(because for some**b**there is either more than one such**a**or no such**a**).A one-to-one correspondence is called

**invertible**because we can deﬁne an inverse of this function.A function is

**not invertible**if it is not a one-to-one correspondence, because the inverse of such a function**does not exist**.

**Q. Let f be the function from {a, b, c} to {1, 2, 3} such that f(a) = 2, f(b) = 3, and f(c) = 1.
Is f invertible, and if it is, what is its inverse?**

The function

**f**is invertible because it is a one-to-one correspondence. The inverse function**f**reverses the correspondence given by f ,so^{−1}**f**,^{−1}(1) = c**f**, and^{−1}(2) = a**f**.^{−1}(3) = b

**Q. Let f : Z → Z be such that f(x) = x + 1. Is f invertible, and if it is, what is its inverse?**

The function

**f**has an inverse because it is a one-to-one correspondenceTo reverse the correspondence, suppose that

**y**is the image of**x**, so that**y = x + 1**. Then**x = y − 1**. This means that**y − 1**is the unique element of Z that is sent to y by f . Consequently,**f**.^{−1}(y) = y − 1

**Composition of the functions 'f' and 'g'**

Let

**g**be a function from the set**A**to the set**B**and let**f**be a function from the set**B**to the set**C**. The composition of the functions**f and g**, denoted for all**a ∈ A by f ◦ g**, is deﬁned by(f ◦ g)(a) = f (g(a)).

To ﬁnd

**(f ◦ g)(a)**we ﬁrst apply the function**g**to**a**to obtain**g(a)**and then we apply the function**f**to the result**g(a)**to obtain**(f ◦ g)(a) = f(g(a))**.Note that even though

**f ◦ g and g ◦ f**are deﬁned for the functions f and g, f ◦ g and g ◦ f are not equal. In other words, the**commutative law**does not hold for the composition of functions.

**Q. Let g be the function from the set {a, b, c} to itself such that g(a) = b, g(b) = c, and g(c) = a.
Let f be the function from the set {a, b, c} to the set {1, 2, 3} such that f(a) = 3, f(b) = 2, and
f(c) = 1. What is the composition of f and g, and what is the composition of g and f ?**

The composition

**f ◦ g**is deﬁned by**(f ◦ g)(a) = f(g(a)) = f(b) = 2**,**(f ◦ g) (b) = f(g(b)) = f(c) = 1**, and**(f ◦ g)(c) = f(g(c)) = f(a) = 3**

**Q. Let f and g be the functions from the set of integers to the set of integers deﬁned by
f(x) = 2x + 3 and g(x) = 3x + 2. What is the composition of f and g? What is the composition
of g and f ?**

Both the compositions f ◦ g and g ◦ f are deﬁned. Moreover,

(f ◦ g)(x) = f(g(x)) = f(3x + 2) = 2(3x + 2) + 3 = 6x + 7

and

(g ◦ f )(x) = g(f(x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11.

**(f**= f^{−1}◦ f )(a)^{−1}(f (a)) = f^{−1}(b) = a**(f ◦ f**= f(f^{−1})(b)^{−1}(b)) = f(a) = b

Let

**f**be a function from the**set A to the set B**. The graph of the function**f**is the set of ordered pairs**{(a, b) | a ∈ A and f(a) = b}**.

**Q. Display the graph of the function f (n) = 2n + 1 from the set of integers to the set of integers.**

The graph of

**f**is the set of ordered pairs of the form**(n, 2n + 1)**, where**n**is an integer.

**Q. Display the graph of the function f(x) = x ^{2}
from the set of integers to the set of integers.**

The graph of f is the set of ordered pairs of the form (x, f (x)) =

**(x, x**, where x is an integer.^{2})

**Ceiling and Floor functions :**

The ﬂoor function (greatest integer function) assigns to the real number

**x**the largest integer that is less than or equal to**x**.The value of the ﬂoor function at x is denoted by

**⌊x⌋**.The ceiling function assigns to the real number

**x**the smallest integer that is greater than or equal to**x**.The value of the ceiling function at x is denoted by

**⌈x⌉**.**Example :**⌊1/2⌋ = 0; ⌈1/2⌉ = 1

Property of ceil | Property of floor |
---|---|

⌈x⌉ = n if and only if n − 1 < x ≤ n | ⌊x⌋ = n if and only if n ≤ x < n+ 1 |

⌈x⌉ = n if and only if x ≤ n < x + 1 | ⌊x⌋ = n if and only if x − 1 < n ≤ x |

x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x+ 1 | |

⌈-x⌉ = −⌈x⌉ | ⌊-x⌋ = − ⌊x⌋ |

⌈x + n⌉ = ⌈x⌉ + n | ⌊x + n⌋ = ⌊-x⌋ + n |

A

**sequence**is a discrete structure used to represent an ordered list. For example, 1, 2, 3, 5, 8 is a sequence with ﬁve terms and 1, 3, 9, 27, 81 ,... ,3^{n}, ... is an**inﬁnite sequence**.A

**geometric progression**is a sequence of the form a, ar^{2}, ar^{3},..., ar^{n}where the initial term**"a"**and the**common ratio "r"**are real numbers.An

**arithmetic progression**is a sequence of the form a, a + d,a + 2d,...,a + nd where the initial term**"a"**and the common difference**"d"**are real numbers.Sequences of the form a

^{1}, a^{2}... a^{n}are often used in computer science. These ﬁnite sequences are also called**strings**. This string is also denoted by a a^{1}, a^{2}... a^{n}.The length of a string is the number of terms in this string. The

**empty string**, denoted by**λ**, is the string that has**no terms**. The empty string has length zero.

**The sequences {s _{n}} with s_{n} = −1 + 4n and {ts_{n}} with ts_{n} = 7 − 3n are both arithmetic progressions
with initial terms and common differences equal to −1 and 4, and 7 and −3, respectively,
if we start at n = 0. The list of terms s_{1}, s_{2}, s_{3} ... s_{n}**

List "s" begins with −1, 3, 7, 11,...

List "t" begins with 7, 4, 1, −2,....

**Recurrence Relations**

A recurrence relation for the sequence {a

_{n}} is an equation that expresses a_{n}in terms of one or more of the previous terms of the sequence, namely, a_{0}, a_{1},...,a_{n-1}, for all integers n with n ≥ n_{0}, where n_{0}is a nonnegative integer.A

**sequence**is called a solution of a recurrence relation if its terms satisfy the recurrence relation.

**Q. Let {a _{n}} be a sequence that satisﬁes the recurrence relation a_{n} = a_{n-1} + 3 for n = 1, 2, 3,...,
and suppose that a_{0} = 2. What are a_{1}, a_{2}, and a_{3}?**

We see from the recurrence relation that a

_{1}= a_{0}+ 3 = 2 + 3 = 5It then follows that a

_{2}= 5 + 3 = 8 and a_{3}= 8 + 3 = 11.

**Q. The Fibonacci sequence, f _{0} = 0, f_{1} = 1
and the recurrence relation f_{n} = f_{n-1} + f_{n-2} for n = 2,3...
**

The recurrence relation for the Fibonacci sequence tells us that we ﬁnd successive terms by adding the previous two terms. Because the initial conditions tell us that f

_{0}= 0 and f_{1}= 1, using the recurrence relation in the deﬁnition we ﬁnd thatf

_{2}= f_{1}+ f_{0}f

_{3}= f_{2}+ f_{1}f

_{4}= f_{3}+ f_{2}

**Important Summations**

**Cardinality**of a ﬁnite set as the number of elements in the set.The sets A and B have the same

**cardinality**if and only if there is a**one-to-one**correspondence from A to B. When A and B have the same cardinality, we write**|A| = |B|**.If there is a

**one-to-one**function from A to B, the cardinality of A is less than or the same as the cardinality of B and we write**|A| ≤ |B|**. Moreover, when |A| ≤ |B| and A and B have different cardinality, we say that the cardinality of A is less than the cardinality of B and we write**|A| < |B|**.

**Countable Sets**

A set that is either ﬁnite or has the same cardinality as the set of positive integers is called

**countable.**A set that is not countable is called

**uncountable**. When an inﬁnite set S is countable, we denote the cardinality of S by**ℵ**_{0}(where ℵ is aleph).We write

**|S| = ℵ**and say that S has cardinality_{0}**“aleph null.”**

**Q. Show that the set of odd positive integers is a countable set.**

To show that the set of odd positive integers is countable, we will exhibit a one-to-one correspondence between this set and the set of positive integers. Consider the function

**f (n) = 2n − 1**from Z^{+}to the set of odd positive integers.We show that

**f**is a one-to-one correspondence by showing that it is both one-to-one and onto. To see that it is one-to-one, suppose that**f (n) = f (m). Then 2n − 1 = 2m − 1, so n = m**. To see that it is**onto**, suppose that**t**is an odd positive integer. Then t is 1 less than an even integer 2k, where k is a natural number. Hence**t = 2k − 1 = f(k)**.

**Q. Show that the set of all integers is countable.**

We can list all integers in a sequence by starting with 0 and alternating between positive and negative integers: 0, 1, −1, 2, −2,.... Alternatively, we could ﬁnd a

**one-to-one**correspondence between the set of positive integers and the set of all integers.The function

**f(n) = n/2**when n is even and**f(n) =−(n−1)/2**when n is odd is such a function. Consequently, the set of all integers is**countable**.

**Useful Theorems**

If A and B are countable sets, then A ∪ B is also countable.

If A and B are sets with

**|A| ≤ |B| and |B| ≤ |A|**, then**|A| = |B|**. In other words, if there are one-to-one functions**f from A to B and g from B to A**, then there is a**one-to-one**correspondence between A and B.A function is

**computable**if there is a computer program in some programming language that ﬁnds the values of this function. If a function is not computable we say it is**uncomputable**.

A

**matrix**is a rectangular array of numbers. A matrix with m rows and n columns is called an**m × n**matrix. The plural of matrix is matrices. A matrix with the same number of rows as columns is called**square**.**Two**matrices are equal if they have the same number of rows and the same number of columns and the corresponding entries in every position are**equal**.Let A =[a

_{ij}] and B =[b_{ij}] be m × n matrices. The sum of A and B, denoted by A + B, is the m × n matrix that has [a_{ij}+ b_{ij}] as its (i, j)th element. In other words,**A + B =[a**._{ij}+ b_{ij}]Let A be an m × k matrix and B be a k × n matrix. The product of A and B, denoted by

**AB = [c**then_{ij}]**c**_{ij}= a_{i1}b_{1j}+ a_{i2}b_{2j}+ ... + a_{ik}b_{kj}In general, suppose that A is an m × n matrix and B is an r × s matrix. Then AB is deﬁned only when

**n = r**and BA is deﬁned only when**s = m**; AB and BA are not necessarily equalThe identity matrix of order n is the n × n matrix I

_{n}=[δ_{ij}], where**δ**if i = j and_{ij}= 1**δ**if i ≠ j._{ij}= 0The

**transpose of A**, denoted by A' , is the n × m matrix obtained by interchanging the rows and columns of A.A square matrix

**A**is called symmetric if A = A'. Thus A =[a_{ij}] is symmetric if a_{ij}= a_{ji}for all i and j with**1 ≤ i ≤ n and 1 ≤ j ≤ n**.A matrix all of whose entries are either 0 or 1 is called a

**zero–one matrix.**Let A =[a

_{ij}] and B =[b_{ij}] be m × n zero–one matrices. Then the**join**of A and B is the zero–one matrix with (i, j)th entry a . The**join**of A and B is denoted by**A**. The meet of A and B is the zero–one matrix with (i, j)th entry a_{ij}∨ B_{ij}_{ij}∨ b_{ij}. The**meet**of A and B is denoted by**A**._{ij}∧ B_{ij}Let A =[a

_{ij}] be an**m × k**zero–one matrix and B =[b_{ij}] be a**k × n**zero–one matrix. Then the Boolean product of A and B, denoted by A &exnor; B, is the m × n matrix with (i, j)th entry c_{ij}where**c**_{ij}= (a_{i1}∧ b_{1j}) ∨ (a_{i2}∧ b_{2j}) ∨ ... ∨ (a_{ik}∧ b_{kj})Let A be a

**square zero–one matrix**and let**r**be a positive integer. The r^{th}Boolean power of A is the Boolean product of r factors of A. The r^{th}Boolean product of A is denoted by**A**.^{[r]}

Previous | Next |