Basic Structures: Sets, Functions, Sequences, Sums, and Matrices Flashcards
1
Q
Set: ( Intuitive Definition)
A
A set is an unordered collection of distinct objects, called elements or members of the set. A
set is said to contain its elements. We write a ∈ A to denote that a is an element of the set A.
The notation a ∉ A denotes that a is not an element of the set A.
2
Q
Notations to represent Set:
A
- Roaster Method.
2. Set builder
3
Q
Roaster Method:
A
Members of the set are listed between braces
The set V of all vowels in the English alphabet can be written as V = {a, e, i, o, u}.
OR
The set of positive integers less than 100 can be denoted by {1, 2, 3, … , 99}.
ellipses (…) are used when the general pattern of the
elements is obvious so as to be able to represent wout listing all its members.
4
Q
Set Builder:
A
The general form of this notation is {x ∣ x has property P} and is read “the set of all x such that x has
property P.”
5
Q
what are
N , Z, Q , R , C ?
A
N = {1, 2, 3, …}, the set of all natural numbers
Z = {… ,−2,−1, 0, 1, 2, …}, the set of all integers
Z+ = {1, 2, 3, …}, the set of all positive integers
Q = {p∕q ∣ p ∈ Z, q ∈ Z, and q ≠ 0}, the set of all rational numbers
R, the set of all real numbers
R+, the set of all positive real numbers
C, the set of all complex numbers
6
Q
Intervals:
A
Sets of all the real
numbers between two numbers a and b, with or without a and b. If a and b are real numbers
with a ≤ b, we denote these intervals by
[a, b] = {x | a ≤ x ≤ b} –Closed Interval
[a, b) = {x | a ≤ x < b}
(a, b] = {x | a < x ≤ b}
(a, b) = {x | a < x < b}. – Open Interval
Remark: Some books use the notations [a, b[, ]a, b], and ]a, b[ for [a, b), (a, b], and (a, b), respectively.
7
Q
What is a datatype or type?
A
A datatype or type is the name of a set, together with a set of operations that can be performed on objects from that set.
8
Q
2 Sets are equal if:
A
Two sets are equal (A = B) if and only if they have the same elements. Therefore, if A and B are sets,
then A and B are equal if and only if ∀x(x ∈ A ↔ x ∈ B).
The order of elements does not matter.
The number of times an element occurs in set also does not matter as long as it is a member.
9
Q
Empty Set:
A
Set with no elements aka Null Set.
Denoted by: ∅ or { }
10
Q
Singleton Set:
A
A set with one element.
{∅} : Single element of this singleton is empty set itself.
11
Q
Naive Set theory:
A
Set: Collection of objects. This is based on intuitive notion of objects.
The theory that results from this intuitive definition of the set, and the use of the intuitive notion that for any property whatever, there is a set consisting of exactly the objects of this property, leads to paradoxes.
To avoid this there is “Axiomatic Set Theory” : by building set theory beginning
with axioms.
This book uses Naive Set theory.
12
Q
Venn Diagram:
and why are they used?
A
In Venn diagrams the universal set U, which
contains all the objects under consideration, is represented by a rectangle.
Inside this rectangle, circles or other
geometrical figures are used to represent sets. Sometimes points are used to represent the particular elements of the set.
Venn diagrams are often used to indicate the relationships between
sets.
13
Q
SubSet and SuperSet:
A
The set A is a subset of B, and B is a superset of A, if and only if every element of A is also an
element of B. We use the notation A ⊆ B
[ ∀x(x ∈ A → x ∈ B) should be true]
to indicate that A is a subset of the set B. If, instead,
we want to stress that B is a superset of A, we use the equivalent notation B ⊇ A.
(So, A ⊆ B and B ⊇ A are equivalent statements.)
14
Q
Determine If A is or not a subset of B:
A
Showing that A is a Subset of B:
To show that A ⊆ B, show that if x belongs to A then x also
belongs to B.
Showing that A is Not a Subset of B :
To show that A ⊈ B, find a single x ∈ A such that x ∉ B.
15
Q
Theorem 1 , every non-empty set S has at least how many sets and who?
A
at least two subsets, the empty set and the set S itself. THEOREM 1 For every set S, i. ∅ ⊆ S ii. S ⊆ S.
16
Q
Proper Subset:
A
A ⊂ B
A is a proper subset of B
if and only if
∀x(x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x ∉ A)
Venn Diagram:
in Rect, a circle B and in it a circle A. show a point in B n, not A.
17
Q
Show that two sets are equal:
A
To show that two sets A and B are equal, show that
A⊆ B and B ⊆ A.
A = B if and only if ∀x(x ∈ A → x ∈ B) & ∀x(x ∈ B → x ∈ A) or equivalently if and only if
∀x(x ∈ A ↔ x ∈ B),
18
Q
A = {∅, {a}, {b}, {a, b}}
B = {x ∣ x is a subset of the set {a, b}}.
is A = B? or A ⊂ B?
A
Sets may have other sets as members. For instance, we have the sets
Note that these two sets are equal, that is, A = B.
Also note that {a} ∈ A, but a ∉ A
19
Q
Cardinality of set S?
A
If there are exactly n distinct elements in S where n is a nonnegative integer,
we say that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted
by |S|.
|∅| = 0.
20
Q
When Is a set infinite:
A
A set is said to be infinite if it is not finite.
21
Q
Power Set:
A
Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is
denoted by P(S).
Careful:
Power set will have ∅ as its element and not {∅}.
Rest elements will all be sets as well.
22
Q
How many elements will a power set have?
A
If a set has n elements, then its power set has 2^n elements.
BUT HOW!!?
I guess cuz every element has a choice of being present or being absent. so 2 multiplied n times.
23
Q
Ordered n-tuples:
A
The ordered n-tuple (a1, a2, … , an) is the ordered collection that has a1 as its first element,
a2 as its second element, … , and an as its nth element
Remember sets are unordered, that’s why we need a different structure.
24
Q
When are two ordered n tuples equal?
A
If and only if each corresponding pair of their
elements is equal. In other words, (a1, a2, … , an) = (b1, b2, … , bn) if and only if ai = bi
i = 1, 2, … , n.
25
Ordered Pairs:
Ordered 2-tuples
26
Cartesian product: of 2 sets
```
Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is the set of all
ordered pairs (a, b), where a ∈ A and b ∈ B. Hence,
A × B = {(a, b) ∣ a ∈ A ∧ b ∈ B}.
```
Note that the Cartesian products A × B and B × A are not equal unless A = ∅ or B = ∅ (so
that A × B = ∅) or A = B (see Exercises 33 and 40). This is illustrated in Example 18.
27
Cartesian product of more than 2 sets:
The Cartesian product of the sets A1, A2, … , An, denoted by A1 × A2 × ⋯ × An, is the set of
ordered n-tuples (a1, a2, … , an), where ai belongs to Ai for i = 1, 2, … , n. In other words,
A1 × A2 × ⋯ × An = {(a1, a2, … , an) ∣ ai ∈ Ai for i = 1, 2, … , n}.
Note that when A, B, and C are sets, (A × B) × C is not the same as A × B × C
28
What is A^n ?
A^n = {(a1, a2, … , an) ∣ ai ∈ A for i = 1, 2, … , n}.
A^2 = A * A
29
What is a relation?
A subset R of the Cartesian product A × B is called a relation from the set A to the set B. The
elements of R are ordered pairs.
A relation from
a set A to itself is called a relation on A.
30
Recall the use of Set notations with Quantifiers:
Sometimes we restrict the domain of a quantified statement explicitly by making use of a particular notation.
For example, ∀x ∈ S(P(x)) denotes the universal quantification of P(x) over all
elements in the set S.
In other words, ∀x ∈ S(P(x)) is shorthand for
∀x(x ∈ S → P(x)).
Similarly, ∃x ∈ S(P(x)) denotes the existential quantification of P(x) over all elements in S.
That is,
∃x ∈ S(P(x)) is shorthand for ∃x(x ∈ S ∧ P(x)).
31
Truth Set:
```
predicate :P
domain : D
Truth set of P : set of elements x in D for which P(x)
is true.
{x ∈ D ∣ P(x)}.
```
32
Relate the truth values over domain U
| when considering Truth set of P(x) and both the quatifiers:
∀xP(x) is true over the domain U if and only if the truth set of P is the set U.
Likewise, ∃xP(x) is true over the domain U if and only if the truth set of P is nonempty.
33
50. This exercise presents Russell’s paradox. Let S be the
set that contains a set x if the set x does not belong to
itself, so that S = {x ∣ x ∉ x}.
a) Show the assumption that S is a member of S leads to Links a contradiction.
b) Show the assumption that S is not a member of S leads
to a contradiction.
```
By parts (a) and (b) it follows that the set S cannot be defined as it was. This paradox can be avoided by restricting
the types of elements that sets can have.
```
34
What is the union of sets?
Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set that contains
those elements that are either in A or in B, or in both.
A ∪ B = {x ∣ x ∈ A ∨ x ∈ B}.
In Venn diag, circle A and B will be both shaded.
35
What is the Intersection of sets?
Let A and B be sets. The intersection of the sets A and B, denoted by A ∩ B, is the set containing those elements in both A and B.
A ∩ B = {x ∣ x ∈ A ∧ x ∈ B}.
Venn diagram: Shade the part belonging to A and B both, overlapped area.
36
Disjoint Sets:
Two sets are called disjoint if their intersection is the empty set.
37
Principle
| of inclusion-exclusion :
A ∪ B| = |A| + |B| − |A ∩ B|.
38
Enumeration
An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set.
39
difference of sets A and B
| A∖B :
Let A and B be sets. The difference of A and B, denoted by A − B, is the set containing those
elements that are in A but not in B. The difference of A and B is also called the complement
of B with respect to A.
A − B = {x ∣ x ∈ A ∧ x ∉ B}.
Venn Diag: Shade the circle A but which does not include B.
40
Complement of Set:
Let U be the universal set. The complement of the set A, denoted by A(bar), is the complement of
A with respect to U. Therefore, the complement of the set A is U − A.
A = {x ∈ U ∣ x ∉ A}.
U is a superset of A..
Venn Diag: Shade everything but A.
41
Identity laws
A ∩ U = A
| A ∪∅= A
42
Domination laws
A ∪ U = U
| A ∩∅=∅
43
Idempotent laws
Complementation law
Commutative laws
A ∪ A = A
A ∩ A = A
(Abar)bar = A
A ∪ B = B ∪ A
A ∩ B = B ∩ A
44
Associative laws
A ∪ (B ∪ C) = (A ∪ B) ∪ C
| A ∩ (B ∩ C) = (A ∩ B) ∩ C
45
Distributive laws
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
| A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
46
De Morgan’s laws
Absorption laws
~(A ∩ B) = ~A ∪ ~B
~(A ∪ B) = ~A ∩ ~B
Absorption laws
A ∪ (A ∩ B) = A
A ∩ (A ∪ B) = A
47
Complement laws
A ∪ A = U
| A ∩ A = ∅
48
Membership Tables:
A table with columns for each set. Just like truth tables in propositions.
1: to show element belongs to set.
0: to show it doesn't.
49
To prove Identities
Or
LHS = RHS
1. Membership tables:
For each possible combination of the atomic sets, show that an element
in exactly these atomic sets must either belong to both sides or belong to
neither side
2. Subset method:
Show that each side of the identity is a subset of the other side.
Using Set Builder Notation it can done more succinctly, as u directly prove LHS = RHS.
3. Apply existing identities Start with one side, transform it into the other side using a sequence of
steps by applying an established identity
50
Generalized Unions and Intersections
The union of a collection of sets is the set that contains those elements that are members of
at least one set in the collection.
A1 ∪ A2 ∪ ⋯ ∪ An = [ ⋃^n v (i=1) ] Ai
The intersection of a collection of sets is the set that contains those elements that are members
of all the sets in the collection.
A1 ∩ A2 ∩ ⋯ ∩ An = [ ⋂ ^ n v (i=1) ] Ai
51
⋂ [i∈L] Ai ?
⋃ [i∈L] Ai ?
L is a set
⋂ [i∈L] Ai ={x ∣ ∀i ∈ L (x ∈ Ai)}
| ⋃ [i∈L] Ai = {x ∣ ∃i ∈ L (x ∈ Ai)}
52
Computer Representations of sets:
1. Having unordered sets is time-consuming when operations done, cuz time needed to find elements would be large.
2. So first represent Universal set in arbitrary order of elements like a1, a2 ,... , an.
3. Then represent A as a subset of U, by a bit string of length n. If ith element belongs to A then ith bit = 1 or else 0.
53
Using bit strings for set representation makes operations on sets easy.
How to find a complement?
Replace all 0s by 1 and all 1s by zero and there u have the complement.
because x ∈ A if and only if x ∉ A.
(negation..)
54
How to obtain a bitstring for the union and intersection :
We use bitwise boolean operations.
⋃ : bitwise Or [ u get ith bit 0 in resulting bitstring if both bitstrings have ith bit 0 or 1 ]
⋂ : bitwise And [ u get ith bit 1 in resulting bitstring if both bitstrings have ith bit 1 or 0]
55
What do u mean by Multisets?
short for multiple-membership set
Is an unordered collection of elements where an
element can occur as a member more than once.
56
Multiset Notation:
| what are multiplicities?
{m1 ⋅ a1, m2 ⋅ a2, … , mr ⋅ ar}
mi is multiplicity of ai (i = 1,2,...r)
Element ai occurs mi times in set.
57
The multiplicity of the element which does not belong to set?
0
58
Cardinality of multiset?
Summation of mi. i from 1 to r.
| sum of the multiplicities of its elements.
59
Union of Multiset:
The union of the multisets P and Q is the multiset in which the
multiplicity of an element is the maximum of its multiplicities in P and Q
60
Intersection of multiset:
The intersection of P
and Q is the multiset in which the multiplicity of an element is the minimum of its multiplicities
in P and Q.
61
P − Q
The difference of P and Q is the multiset in which the multiplicity of an element is
the multiplicity of the element in P less its multiplicity in Q unless this difference is negative,
in which case the multiplicity is 0.
62
P + Q
The sum of P and Q is the multiset in which the multiplicity of an element is the sum of multiplicities in P and Q
63
A ⊆ B if and only if B ⊆ A ??
Set-theoretic version of the contrapositive law for logic
64
A − B =
A ∩ Bbar
65
symmetric difference of A and B?
The symmetric difference of A and B, denoted by A ⊕ B, is
the set containing those elements in either A or B, but not in
both A and B.
66
XOR and difference property?
A ⊕ B = (A − B) ∪ (B − A).
67
XOR in terms of U and intex?
A ⊕ B = (A ∪ B) − (A ∩ B)
68
XOR properties
| 4 :
a) A ⊕ A = ∅. b) A ⊕ ∅ = A.
| c) A ⊕ U = A. d) A ⊕ Abar = U.
69
The successor of the set A?
The successor of the set A is the set A ∪ {A}
70
Jaccard similarity
The Jaccard similarity J(A, B) of the finite sets A and
| B is J(A, B) = |A ∩ B|∕|A ∪ B|, with J(∅, ∅) = 1.
71
Jaccard distance
The Jaccard distance dj (A, B) between A and B equals dj (A, B) = 1 − J(A, B).
72
Triangle inequality:
Prove that each of the properties in parts (a)–(d) holds
whenever A and B are finite sets.
a) J(A, A) = 1 and dJ (A, A) = 0
b) J(A, B) = J(B, A) and dJ (A, B) = dJ (B, A)
c) J(A, B) = 1 and dJ (A, B) = 0 if and only if A = B
d) 0 ≤ J(A, B) ≤ 1 and 0 ≤ dJ (A, B) ≤ 1 ∗∗e) Show that if A, B, and C are sets, then dJ (A, C) ≤
dJ (A, B) + dJ (B, C). (This inequality is known as the
triangle inequality and together with parts (a), (b),
and (c) implies that dJ is a metric.)
73
Fuzzy Sets:
Fuzzy sets are used in artificial intelligence. Each element
in the universal set U has a degree of membership, which
is a real number between 0 and 1 (including 0 and 1), in a
fuzzy set S. The fuzzy set S is denoted by listing the elements
Links with their degrees of membership (elements with 0 degree of
membership are not listed). For instance, we write {0.6 Alice,
0.9 Brian, 0.4 Fred, 0.1 Oscar, 0.5 Rita} for the set F (of famous people) to indicate that Alice has a 0.6 degree of membership in F..etc
74
Complement in fuzzy set:
The complement of a fuzzy set S is the set Sbar, with the
degree of the membership of an element in Sbar equal to
1 minus the degree of membership of this element in S.
75
Union and Intersection in fuzzy sets:
The union of two fuzzy sets S and T is the fuzzy set S ∪ T,
where the degree of membership of an element in S ∪ T
is the maximum of the degrees of membership of this element in S and in T
The intersection of two fuzzy sets S and T is the fuzzy
set S ∩ T, where the degree of membership of an element
in S ∩ T is the minimum of the degrees of membership
of this element in S and in T
76
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.
Functions aka mappings or transformations.
DOubt : unique!!?? even closure had this confusion.!
77
Function and relation:
A function f : A → B can also be defined in terms of a relation from A to B. A relation from A to B is just a subset of A × B. A relation from A to B that
contains one, and only one, ordered pair (a, b) for every element a ∈ A, defines a function f
from A to B. This function is defined by the assignment f(a) = b, where (a, b) is the unique
ordered pair in the relation that has a as its first element.
78
Functions terminology:
| range and domain and codomain and image and pre image :
```
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.
```
79
Relation of Co Domain and Range:
```
Note that the codomain of a function from A to B is the set of all possible values of
such a function (that is, all elements of B), and the range is the set of all values of f(a) for a ∈ A,
and is always a subset of the codomain. That is, the codomain is the set of possible values of the
function and the range is the set of all elements of the codomain that are achieved as the value
of f for at least one element of the domain.
```
80
Equality of functions:
When we define a function we specify its domain, its codomain, and the mapping of elements of the domain to elements in the codomain. 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. Note that if we change either the domain or
the codomain of a function, then we obtain a different function. If we change the mapping of
elements, then we also obtain a different function.
81
The domain and codomain of functions are often specified in programming languages:
Illustrate:
int func( float a) {....}
tell us that the domain of the func is the set of real numbers (represented by
floating point numbers) and its codomain is the set of integers.
82
Real Valued function
| Integer-valued function
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.
83
Operations allowed for same valued functions:
Let f1 and f2 be functions from A to R. Then f1 + f2 and f1 f2 are also functions from A to R
defined for all x ∈ A by
( f1 + f2)(x) = f1(x) + f2(x),
( f1f2)(x) = f1(x)f2(x).
84
When f is a function from A to B, the image of a subset of A can also be defined.
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. We denote the image of
S by f(S), so
f(S) = {t ∣ ∃s∈S (t = f(s))}.
We also use the shorthand {f(s) ∣ s ∈ S} to denote this set.
Remark: The notation f(S) for the image of the set S under the function f is potentially ambiguous. Here, f(S) denotes a set, and not the value of the function f for the set S
85
One to One function:
A function f is said to be one-to-one, or an injection, if and only if f(a) = f(b) implies that
a = b for all a and b in the domain of f.
A function is said to be injective if it is one-to-one.
∀a∀b( f(a) = f(b) → a = b)
or equivalently ∀a∀b(a ≠ b → f(a) ≠ f(b)), where the universe of discourse = domain of function.
86
Increasing Function/ Decreasing function:
```
A function f whose domain and codomain are subsets of the set of real numbers is called
increasing if f(x) ≤ f(y), and strictly increasing if f(x) < f(y), whenever x < y and x and y
are in the domain of f. Similarly, f is called decreasing if f(x) ≥ f(y), and strictly decreasing
if f(x) > f(y), whenever x < y and x and y are in the domain of f. (The word strictly in this
definition indicates a strict inequality.)
```
Remark: A function f is increasing if ∀x∀y(x < y → f(x) ≤ f(y)), strictly increasing if ∀x∀y(x <
y → f(x) < f(y)), decreasing if ∀x∀y(x < y → f(x) ≥ f(y)), and strictly decreasing if ∀x∀y(x <
y → f(x) > f(y)), where the
universe of discourse = domain of f.
87
Strictly Increasing functions or strictly decreasing functions feature:
They are one to one.
88
Surjection:
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. A function f is called surjective if it is onto.
```
A function f is onto if ∀y∃x( f(x) = y), where the domain for x is the domain of the
function and the domain for y is the codomain of the function.
```
89
Bijective:
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.
90
Suppose that f is a function from a set A to itself. If A is finite, then f is one-to-one when?
Suppose that f is a function from a set A to itself. If A is finite, then f is one-to-one if and
only if it is onto. (This follows from the result in Exercise 74.) This is not necessarily the case
if A is infinite (as will be shown in Section 2.5).
91
Identity function:
Let A be a set. The identity function on A is the function 𝜄
𝜄a : A → A, where
𝜄a(x) = x
for all x ∈ A. In other words, the identity function 𝜄A is the function that assigns each element
to itself. The function 𝜄A is one-to-one and onto, so it is a bijection. (Note that 𝜄 is the Greek
letter iota.)
92
Summary of injective, surjective:
Suppose that f : A → B.
To show that f is injective Show that if f(x) = f(y) for arbitrary x, y ∈ A, 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 find 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.
93
Inverse of function:
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^(-1).
Hence, f^(−1)(b) = a when f(a) = b
```
Be sure not to confuse the function f −1 with the function 1∕f , which is the function
that assigns to each x in the domain the value 1∕f(x). Notice that the latter makes sense only
when f(x) is a nonzero real number
```
Only one to one correspondence are invertible functions.
94
Composition of function:
| its domain and range, when can it be defined:
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 the function
from A to C defined by
( f ◦g)(a) = f(g(a)).
The domain of f ◦g is the domain of g. The range of f ◦g is the image of the range
of g with respect to the function f .
n f ◦g cannot be defined unless the range of g is a subset of the domain
of f
95
Commutative law and composition of function:
fog is not equal to gof.
Not commutative.
96
When the composition of a function and its inverse is formed, in either order, what is the result?
an identity function is obtained.
f^(−1)of = 𝜄A
f of^(−1) = 𝜄B,
where 𝜄A and 𝜄B are the identity functions on the sets
A and B, respectively. That is, ( f^(−1) )^(−1) = f .
97
Graph of function:
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}.
the graph of a function f from A to B is the subset of
A × B containing the
ordered pairs with the
second entry = element of B assigned by f to the first entry.
Also, note that the graph of a function f from A to B is the same as the relation from A to B
determined by the function f
98
Floor function
or
Ceiling function:
```
The floor function assigns to the real number x the largest integer that is less than or equal to
x. The value of the floor 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⌉
```
99
Graph of floor and ceiling function:
| and applications
Floor s function has the same value throughout the
interval [n, n + 1), namely n, and then it jumps up to n + 1 when x = n + 1.
Ceiling function has the same value throughout the interval (n, n + 1], namely n + 1, and then jumps to n + 2 when x is a little larger
than n + 1.
applications:
involving data storage and data transmission.
100
ATM:
Asynchronous Transfer Mode.
| a communications protocol used on backbone networks
101
Useful Properties of the
Floor and Ceiling Functions.
( 9 )
(n is an integer, x is a real number)
(1a) ⌊x⌋ = n if and only if n ≤ x < n + 1
(1b) ⌈x⌉ = n if and only if n − 1 < x ≤ n
(1c) ⌊x⌋ = n if and only if x − 1 < n ≤ x
(1d) ⌈x⌉ = n if and only if x ≤ n < x + 1
(2) x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1
(3a) ⌊−x⌋ = −⌈x⌉
(3b) ⌈−x⌉ = −⌊x⌋
(4a) ⌊x + n⌋ = ⌊x⌋ + n
(4b) ⌈x + n⌉ = ⌈x⌉ + n
102
A useful approach for considering statements about floor and ceiling functions:
```
A useful approach for considering statements about the floor function is to let x = n + 𝜖,
where n = ⌊x⌋ is an integer, and 𝜖, the fractional part of x, satisfies the inequality 0 ≤ 𝜖 < 1.
Similarly, when considering statements about the ceiling function, it is useful to write x = n − 𝜖,
where n = ⌈x⌉ is an integer and 0 ≤ 𝜖 < 1.
```
103
factorial function :
factorial function f : N → Z+,
denoted by f(n) = n!. The value of f(n) = n! is the product of the first n positive integers, so
f(n) = 1 ⋅ 2 ⋯ (n − 1) ⋅ n [and f(0) = 0! = 1].
104
~ sybol stands for:
The symbol ∼ is read “is asymptotic to.
105
notation f(n) ∼ g(n) :
```
notation f(n) ∼ g(n), which means that the ratio f(n)∕g(n) approaches 1 as n grows without bound (that
is, lim n→∞ f(n)∕g(n) = 1).
```
106
Stirling’s formula :
named
after James Stirling, a Scottish mathematician of the eighteenth century.
The rapid growth of the factorial function is made clearer by Stirling’s formula, a result
from higher mathematics that tells us that
n! ∼ √(2𝜋n)(n∕e)^n.
107
log x:
logb x:
ln x:
In this book:
In this book the notation log x will be used
to denote the logarithm to the base 2 of x, because 2 is the base that we will usually use for
logarithms. We will denote logarithms to the base b, where b is any real number greater than 1,
by logb x, and the natural logarithm by ln x.
108
Partial and total function:
A partial function f from a set A to a set B is an assignment to each element a in a subset
of A, called the domain of definition of f , of a unique element b in B. The sets A and B are
called the domain and codomain of f , respectively. We say that f is undefined for elements
in A that are not in the domain of definition of f . When the domain of definition of f equals
A, we say that f is a total function.
Remark: We write f : A → B to denote that f is a partial function from A to B. Note that this is
the same notation as is used for functions. The context in which the notation is used determines
whether f is a partial function or a total function.
109
What if fog is
1. Onto
2. ONe to one
3. bijective
Comment on f,g's injection and surjection.
a) If f ◦g is onto, then f must also be onto.
b) If f ◦g is one-to-one, then g must also be one-to-one.
c) If f ◦g is a bijection, then g is onto if and only if f is
one-to-one.
110
Inverse Image:
Let f be a function from the set A to the set B. Let S be a
subset of B. We define the inverse image of S to be the subset of A whose elements are precisely all preimages of all
elements of S. We denote the inverse image of S by f −1(S),
so f −1(S) = {a ∈ A ∣ f(a) ∈ S}. [Beware: The notation f −1 is
used in two different ways. Do not confuse the notation introduced here with the notation f −1(y) for the value at y of the
inverse of the invertible function f . Notice also that f −1(S),
the inverse image of the set S, makes sense for all functions f ,
not just invertible functions.]
111
Ceiling and floor properties:
a) x < n if and only if ⌊x⌋ < n.
b) n < x if and only if n < ⌈x⌉.
a) x ≤ n if and only if ⌈x⌉ ≤ n.
b) n ≤ x if and only if n ≤ ⌊x⌋
112
Charachteristic function:
Let S be a subset of a universal set U. The characteristic function fS of S is the function from U to the set
{0, 1} such that fS(x) = 1 if x belongs to S and fS(x) = 0
if x does not belong to S.
