Chqpter 2 :

Basic Structures :
Sets, Functions, Sequences, Sums, and Matrices

2,1 sets

DEFINITION 1
A set is an unordered collection of 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 not∈ A denotes that a is not an element of
the set A.

examples
N = {0, 1, 2, 3, . . .}, the set of natural numbers
Z = {. . . , −2, −1, 0, 1, 2, . . .}, the set of integers
Z+ = {1, 2, 3, . . .}, the set of positive integers
Q = {p/q | p ∈ Z, q ∈ Z, and q = 0}, the set of rational numbers
R, the set of real numbers
+R , the set of positive real numbers
C, the set of complex numbers.

[a, b] = {x | a ≤ x ≤ b}
[a, b) = {x | a ≤ x < b}
(a, b] = {x | a < x ≤ b}
(a, b) = {x | a < x < b}
empty set

DEFINITION 2 subset
The set A is a subset of B if and only if every element of A is also an element of
B. We use the notation A ⊆ B to indicate that A is a subset of the set B.

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 not ⊆ B, find a single x ∈
A such that x not ∈ B.

Showing Two Sets are Equal To show that two sets A and B are equal, show that
A ⊆ B and B ⊆ A.
DEFINITION 3
Let S be a set. 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|.

DEFINITION 4
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).

What is the power set of the set {0, 1, 2}?

Solution: The power set P ({0, 1, 2}) is the set of all subsets of {0, 1, 2}. Hence,
P ({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.

DEFINITION 5 The Cartesian product

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

example ….

……………………………………………………………………………………
……………………………………………………………………………………

What do the statements ∀x∈ R (x 2 ≥ 0) and ∃x∈ Z (x 2 = 1) mean?

Solution: The statement ∀x∈ R(x 2 ≥ 0) states that for every real number x, x 2
≥ 0. This statement can be expressed as “The square of every real number is
nonnegative.” This is a true statement.
The statement ∃x∈ Z(x 2 = 1) states that there exists an integer x such that x 2 =
1. This statement can be expressed as “There is an integer whose square is 1.”
This is also a true statement
because x = 1 is such an integer (as is −1).
▲
exercise find the values of the differents statements

p for all x , x² >=0

q there exist x in Z suche that x^2= 1

v for all x in Z we have x² = -3
p= true
q= true
v = false

Truth Sets and Quantifiers

We will now tie together concepts from set theory and from predicate logic.
Given a predicate P , and a domain D, we define the truth set of P to be the set
of elements x in D for which P (x) is true.

The truth set of P (x) is denoted by {x ∈ D | P (x)}.

exercise :
What are the truth sets of the predicates P (x), Q(x), and R(x), where the domain
is the set of integers and
P (x) is “|x| = 1,”
Q(x) is “x^2 = 2,” and
R(x) is “|x| = x.”

Solution: The truth set of P , {x ∈ Z | |x| = 1}, is the set of integers for which |x|
= 1. Because
|x| = 1 when x = 1 or x = −1, and for no other integers x, we see that the truth
set of P is the set {−1, 1}.

The truth set of Q, {x ∈ Z | x^2 = 2}, is the set of integers for which x^ 2 = 2.
This is the empty set because there are no integers x for which x^2 = 2.

The truth set of R, {x ∈ Z | |x| = x}, is the set of integers for which |x| = x.
Because
|x| = x if and only if x ≥ 0, it follows that the truth set of R is N, the set of
nonnegative integers.
▲

2.2
Set Operations/

DEFINITION 6
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.
An element x belongs to the union of the sets A and B if and only if x belongs
to A or x belongs to B. This tells us that
A ∪ B = {x | x ∈ A ∨ x ∈ B}.

DEFINITION 7
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.
An element x belongs to the intersection of the sets A and B if and only if x
belongs to A and x belongs to B. This tells us that
A ∩ B = {x | x ∈ A ∧ x ∈ B}.

DEFINITION 8
Two sets are called disjoint if their intersection is the empty set.

|A ∪ B| = |A| + |B| − |A ∩ B|.

There are other important ways to combine sets.

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

DEFINITION 9
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.

exercise1 :
Prove that A ∩ B = A ∪ B and also A ∪ B = A ∩ B by resp. the first and the
second De Morgan Law econd

exercise2 :
exercise 3
exercise4

Let A = {0, 2, 4, 6, 8}, B = {0, 1, 2, 3, 4}, and C = {0, 3, 6, 9}. What are A ∪ B
∪ C and A ∩ B ∩ C?
Solution: The set A ∪ B ∪ C contains those elements in at least one of A, B,
and C. Hence,
A ∪ B ∪ C = {0, 1, 2, 3, 4, 6, 8, 9}.
The set A ∩ B ∩ C contains those elements in all three of A, B, and C. Thus,
A ∩ B ∩ C = {0}.
▲

Computer Representation of Sets :

Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the

elements in increasing order; that is, ai = i. What bit strings represent the subset
of all odd integers in U, the subset of all even integers in U, and the subset of
integers not exceeding 5 in U ?

Solution: The bit string that represents the set of odd integers in U, namely, {1,
3, 5, 7, 9}, has a one bit in the first, third, fifth, seventh, and ninth positions, and
a zero elsewhere. It is 10 1010 1010.
(We have split this bit string of length ten into blocks of length four for easy
reading.) Similarly,
we represent the subset of all even integers in U, namely, {2, 4, 6, 8, 10}, by the
string 01 0101 0101.
The set of all integers in U that do not exceed 5, namely, {1, 2, 3, 4, 5}, is
represented by the string 11 1110 0000.

Using bit strings to represent sets, it is easy to find complements of sets and
unions, inter-sections, and differences of sets. To find the bit string for the
complement of a set from the bit string for that set, we simply change each 1 to
a 0 and each 0 to 1, because x ∈ A if and only if x ∈ / A. Note that this
operation corresponds to taking the negation of each bit when we associate a bit
with a truth value—with 1 representing true and 0 representing false.
Exercise 1 : We have seen that the bit string for the set {1, 3, 5, 7, 9} (with
universal set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}) is 10 1010 1010.
What is the bit string for the complement of this set?

Exercise 2 : The bit strings for the sets {1, 2, 3, 4, 5} and {1, 3, 5, 7, 9} are
11 1110 0000 and 10 1010 1010, respectively. Use bit strings to find the union
and intersection of these sets.
Solution: The bit string for the union of these sets is
11 1110 0000 ∨ 10 1010 1010 = 11 1110 1010,
which corresponds to the set {1, 2, 3, 4, 5, 7, 9}. The bit string for the
intersection of these sets is
11 1110 0000 ∧ 10 1010 1010 = 10 1010 0000,
which corresponds to the set {1, 3, 5}.
▲

exercise 3: Using the same universal set as in the last problem, find
the set specified by each of these bit strings.
a) 11 1100 1111
b) 01 0111 1000
c) 10 0000 0001
54. What subsets of a finite universal set do these bit strings
represent?
a) the string with all zeros
b) the string with all ones
2.3 Functions

DEFINITION 1
Let A and B be none empty 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.

Example domain and codomain

The domain and codomain of functions are often specified in programming

languages. For
instance, the Java statement
int floor(float real){. . .}
and the C++ function statement
int function (float x){. . .}
both tell us that the domain of the floor function is the set of real numbers
(represented by
floating 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.

Example of functions

Let f be the function from {a, b, c, d} to {1, 2, 3} defined by f (a) = 3, f (b) = 2,

f (c) = 1,
and f (d) = 3. Is f an onto function?

Is the function f (x) = x 2 from the set of integers to the set of integers onto?

Determine whether the function f (x) = x 2 from the set of integers to the set of
integers is
one-to-one.

2.4
Sequences and Summations

Sequences
A sequence is a discrete structure used to represent an ordered list. For example,
1, 2, 3, 5, 8 is
a sequence with five terms and 1, 3, 9, 27, 81 , . . . , 3n , . . . is an infinite
sequence.
DEFINITION 1
A sequence is a function from a subset of the set of integers (usually either the
set {0, 1, 2, . . .}
or the set {1, 2, 3, . . .}) to a set S. We use the notation an to denote the image of
the integer n.
We call an a term of the sequence.

EXAMPLE 1

exercise
Compound Interest Suppose that a person deposits $10,000 in a savings account at a bank
yielding 11% per year with interest compounded annually. How much will be in the account
after 30 years?

Summation

Summations
Next, we consider the addition of the terms of a sequence. For this we introduce
summation
notation. We begin by describing the notation used to express the sum of the
terms
am , am+1 , . . . , an

Use summation notation to express the sum of the first 100 terms of the
sequence {aj }, where
aj = 1/j for j = 1, 2, 3, . . . .

calculate with programming

same question for the duble summation

2.5

Cardinality of Sets

DEFINITION 1
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|.

Countable Sets
We will now split infinite sets into two groups, those with the same cardinality
as the set of
natural numbers and those with a different cardinality.

DEFINITION 3
A set that is either finite 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 infinite set
S is countable,
we denote the cardinality of S by 0 ‫( א‬where ‫ א‬is aleph, the first letter of the
Hebrew alphabet).
We write |S| = 0 ‫ א‬and say that S has cardinality “aleph null.”

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

2.6
Matrices