X

### Set Operations

• 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.

### Set Identities

IdentityName
A ∩ U = A Identity laws
A ∪ ∅ = A Identity laws
A ∪ U = U Domination laws
A ∩ ∅ = ∅ Domination laws
A ∪ A = A Idempotent laws
A ∩ A = AIdempotent laws
(A) = A Complementation law
A ∪ B = B ∪ A Commutative laws
A ∩ B = B ∩ ACommutative laws
A ∪ (B ∪ C) = (A ∪ B) ∪ C Associative laws
A ∩ (B ∩ C) = (A ∩ B) ∩ CAssociative 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) = AAbsorption laws
A ∪ A = U Complement laws
A ∩ A = ∅ Complement laws

### Functions

• 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 codomain

• The 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) = x2.

• 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 f1 and f2 be functions from A to R. Then f1 + f2 and f1 . f2to R deﬁned for all x ∈ A by

1. (f1 + f2)(x) = f1(x) + f2(x)

2. (f1 . f2)(x) = f1(x) . f2(x)

Q. f1 and f2 be functions from R to R such that f1(x) = x2 and f2(x) = x - x2. What are the functions (f1 + f2)(x) and (f1 . f2)(x)

• (f1 + f2)(x) = f1(x) + f2(x)

• = x2 + x - x2

• = x

Step 2:

• (f1 . f2)(x) = f1(x) . f2(x)

• = x2 . ( x - x2)

• = x3 - x4

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}.

### One-to-One and Onto Functions

• 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) = x2 from the set of integers to the set of integers is one-to-one.

• The function f(x) = x2 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) = x2 from the set of integers to the set of integers onto?

• The function f is not onto because there is no integer x with x2 = −1.

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 tA : A → A where tA(x) = x for all x ∈ A.

• So, the identity function tA is the function that assigns each element to itself.

• The function tA 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