**Complement :**Let U be the universal set. The complement of the set A, denoted by A, is the complement of A with respect to U. Therefore, the complement of the set A is U − A.A ={x ∈ U | x ∉ A}.

Let A = {a, e, i, o, u} (where the universal set is the set of letters of the English alphabet). Then

**A**= {b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w,x,y,z}.Let A be the set of positive integers greater than 10 (with universal set the set of all positive integers). Then

**A**= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.**Note :**A − B = A ∩ B.

Identity | Name |
---|---|

A ∩ U = A | Identity laws |

A ∪ ∅ = A | Identity laws |

A ∪ U = U | Domination laws |

A ∩ ∅ = ∅ | Domination laws |

A ∪ A = A | Idempotent laws |

A ∩ A = A | Idempotent laws |

(A) = A | Complementation law |

A ∪ B = B ∪ A | Commutative laws |

A ∩ B = B ∩ A | Commutative laws |

A ∪ (B ∪ C) = (A ∪ B) ∪ C | Associative laws |

A ∩ (B ∩ C) = (A ∩ B) ∩ C | Associative laws |

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) | Distributive laws |

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) | Distributive laws |

(A ∩ B) = (A) ∪ (B) | De Morgan’s laws |

(A ∪ B) = (A) ∩ (B) | De Morgan’s laws |

A ∪ (A ∩ B) = A | Absorption laws |

A ∩ (A ∪ B) = A | Absorption laws |

A ∪ A = U | Complement laws |

A ∩ A = ∅ | Complement laws |

Let "A" and "B" be nonempty sets. A

*function f*from "A" to "B" is an assignment of exactly one element of "B" to each element of "A". We write*f(a) = b*if "b" is the unique element of "B" assigned by the function 'f' to the element**a**of A. If**f**is a function from**A to B**, we write f : A → B.**Remark :**Functions are sometimes also called mappings or transformations

**Domain and Codomain of a function**

If

**f**is a function from**A to B**, we say that "A" is the domain of "f" and "B" is the codomain of**f**.If

**f(a) = b**, we say that "b" is the image of "a" and "a" is a preimage of "b".The range, or image, of

**f**is the set of all images of elements of**A**. Also, if**f**is a function from**A to B**, we say that**f**maps**A to B**.Two functions are

**equal**when they have the same**domain**, have the same**codomain**, and map each element of their common domain to the same element in their common codomain

**Q. What are the domain, codomain, and range of the function that assigns grades to students
described in the ﬁrst paragraph of the introduction of this section?**

Let

**G**be the function that assigns a grade to a student in our discrete mathematics class. Note that**G(Adams) = A**, for instance.The domain of

**G**is the set {Adams, Chou, Goodfriend, Rodriguez, Stevens}, and the codomain is the set {A, B, C, D, F}.The range of

**G**is the set {A, B, C, F}, because each grade except**D**is assigned to some student.

**Q. Let R be the relation with ordered pairs (Abdul, 22), (Brenda, 24), (Carla, 21), (Desire, 22),
(Eddie, 24), and (Felicia, 22). Here each pair consists of a graduate student and this student’s
age. Specify a function determined by this relation**

If

**f**is a function speciﬁed by**R**, then f(Abdul ) = 22, f(Brenda) = 24, f(Carla) = 21, f(Desire) = 22, f(Eddie) = 24, and f(Felicia) = 22.For the

**domain**, we take the set {Abdul, Brenda, Carla, Desire, Eddie, Felicia}.A

**co-domain**needs to contain all possible ages of students. Because it is highly likely that all students are less than 100 years old, we can take the set of positive integers less than 100 as the codomainThe

**range**of the function we have speciﬁed is the set of different ages of these students, which is the set**{21, 22, 24}**.

**Q. Let f be the function that assigns the last two bits of a bit string of length 2 or greater to that
string. For example, f(11010) = 10. Then, the domain of f is the set of all bit strings of length
2 or greater, and both the codomain and range are the set {00, 01, 10, 11}.**

Let

**f : Z → Z**assign the square of an integer to this integer. Then,**f(x) = x**.^{2}Here the domain of

**f**is the set of all integers, the**codomain of f**is the set of all integers, and the**range of f**is the set of all integers that are perfect squares, namely, {0, 1, 4, 9,...}.

**Q. The domain and codomain of functions are often speciﬁed in programming languages. For
instance, the Java statement
int ﬂoor(ﬂoat real){...}
and the C++ function statement
int function (ﬂoat x){...}
**

The

**domain**of the ﬂoor function is the set of real numbers (represented by ﬂoating point numbers) and its**codomain**is the set of integers.A function is called real-valued if its

**codomain**is the set of real numbers, and it is called integer-valued if its codomain is the set of integers.Two

**real-valued functions**or two integer valued functions with the**same domain**can be added, as well as multiplied.

**Definition 3: Function**

Let f

_{1}and f_{2}be functions from A to R. Then f_{1}+ f_{2}and f_{1}. f_{2}to R deﬁned for all x ∈ A by(f

_{1}+ f_{2})(x) = f_{1}(x) + f_{2}(x)(f

_{1}. f_{2})(x) = f_{1}(x) . f_{2}(x)

**Q. f _{1} and f_{2} be functions from R to R such that f_{1}(x) = x^{2} and f_{2}(x) = x - x^{2}. What are the functions (f_{1} + f_{2})(x) and (f_{1} . f_{2})(x)**

(f

_{1}+ f_{2})(x) = f_{1}(x) + f_{2}(x)= x

^{2}+ x - x^{2}= x

Step 2:

(f

_{1}. f_{2})(x) = f_{1}(x) . f_{2}(x)= x

^{2}. ( x - x^{2})= x

^{3}- x^{4}

**DEFINITION 4 **

Let

**f**be a function from**A to B**and let**S**be a subset of**A**. The image of**S**under the function**f**is the subset of**B**that consists of the images of the elements of**S**.**Example :**Let A = {a, b, c, d, e} and B = {1, 2, 3, 4} with f(a) = 2, f(b) = 1, f(c) = 4, f(d) = 1, and f(e) = 1. The image of the subset S = {b, c, d} is the set f(S) = {1, 4}.

Some functions never assign the same value to two different domain elements. These functions are said to be

**one-to-one or injective**.We can express that f is one-to-one using quantiﬁers as

**∀a∀b(f (a) = f(b) → a = b)**or equivalently**∀a∀b(a ≠ b → f(a) ≠ f(b))**, where the universe of discourse is the domain of the function.

**Q. Determine whether the function f from {a, b, c, d} to {1, 2, 3, 4, 5} with f(a) = 4, f(b) = 5,
f(c) = 1, and f(d) = 3 is one-to-one**

The function

**f**is one-to-one because**f**takes on different values at the four elements of its domain.

**Q. Determine whether the function f(x) = x ^{2}
from the set of integers to the set of integers is
one-to-one.**

The function f(x) = x

^{2}is not one-to-one because, for instance, f(1) = f(−1) = 1, but 1 ≠ −1.

**Increasing and Decreasing functions :**

**Increasing :**∀x∀y(x < y → f(x) ≤ f(y))**Strictly increasing :**∀x∀y(x < y → f (x) < f (y))**Decreasing :**∀x∀y(x < y → f(x) ≥ f(y))**Strictly decreasing :**∀x∀y(x < y → f (x) > f (y))

**Surjective Functions**

A function

**f**from A to B is called**onto, or a surjection**if and only if for every element**b ∈ B**there is an element**a ∈ A**with f(a) = b.

**Q. Let f be the function from {a, b, c, d} to {1, 2, 3} deﬁned by f(a) = 3, f(b) = 2, f(c) = 1,
and f(d) = 3. Is f an onto function?**

Because all three elements of the codomain are images of elements in the domain, we see that

**f**is onto.Note that if the codomain were {1, 2, 3, 4}, then

**f**would not be onto.

**Q. Is the function f(x) = x ^{2}
from the set of integers to the set of integers onto?**

The function

**f**is not onto because there is no integer**x with x**= −1.^{2}

**Q. Is the function f(x) = x + 1 from the set of integers to the set of integers onto?**

This function is

**onto**, because for every integer**y**there is an integer**x**such that**f(x) = y**. To see this, note that**f(x) = y**if and only if**x + 1 = y**, which holds if and only if**x = y − 1**.

**Function : one-to-one correspondence, or a bijection**

The function

**f**is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. We also say that such a function is bijective.

**Q. Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f(a) = 4, f(b) = 2, f(c) = 1, and
f(d) = 3. Is 'f' a bijection?**

The function

**f**is one-to-one and onto. It is**one-to-one**because no two values in the domain are assigned the same function value. It is onto because all four elements of the codomain are images of elements in the domain. Hence,**f**is a bijection

**The identity function on A **

Let A be a set. The identity function on A is the function t

_{A}: A → A where t_{A}(x) = x for all x ∈ A.So, the identity function t

_{A}is the function that assigns each**element to itself**.The function t

_{A}is**one-to-one and onto**, so it is a bijection.

**Suppose that f : A → B.
**

To show that

**f is injective**: Show that if f(x) = f(y) for arbitrary x, y ∈ A with x ≠ y, then x = y.To show that

**f is not injective**Find particular elements x, y ∈ A such that x ≠ y and f(x) = f(y).To show that

**f is surjective**Consider an arbitrary element y ∈ B and ﬁnd an element x ∈ A such that f(x) = y.To show that

**f is not surjective**Find a particular y ∈ B such that f(x) ≠ y for all x ∈ A

Previous | Next |