|
| Sets |
| |
|
|
| |
|
Sets |
Definition
of a set and notation |
|
Set
membership |
|
Set
builder notation |
|
Cardinal
number |
|
Ordinal
number |
|
Equal
sets |
|
Subsets |
|
The
empty set or the null set |
|
Universal
set or universe |
|
Power
set |
|
Operations on sets and Venn diagrams |
|
Union,
intersection and difference |
|
Partition
of a set |
|
The
fundamental laws of the algebra of sets |
|
Sets and logic |
|
The
"and", the conjunction or the logical product |
|
The
"or", the disjunction or the logical sum |
|
Logical
negation |
|
Relations |
|
The Cartesian product |
|
The domain
and the range |
|
Function |
|
Relation
on a set |
|
Reflexive,
symmetric, transitive and equivalent relation |
| |
|
|
|
|
| |
| |
| |
| |
| Definition
of a Set and Notation |
| Set
is a finite or infinite collection of distinct objects. Those
objects are called elements or members of the |
| set. The
notation, |
| A
= {
a, b, c
}
means A equals
the set of elements a,
b
and c. |
|
| Set
membership |
| If
B
is a set and
d
is an object, then the relationship |
|
d is an element of
B
we denote as
d
Î
B,
or |
| d not
Î
of B if d is not an element of B,
i.e., d
does not belong to the
set B. |
|
| Set
builder notation |
| A
set can be described by
specifying the properties which determines its elements, for
example |
| S
= {
n
Î
N |
3
≤
n ≤
8
} |
| denotes
the set S
of all natural numbers n
such that n
is in the range from 3 to
8 inclusive that is, |
| S
= {
3, 4, 5, 6, 7, 8
}. |
|
| Cardinal
number |
| A measure of the size of a set that does not take into account the order of its members, i.e., which only |
| specifies the total
number of its elements is called the cardinal number. |
|
| Ordinal
number |
| A
measure of a set that takes account of the order as well as the
number of its elements is called the ordinal |
| number. |
|
| Equal
sets |
|
Two sets A
and B
are said to be equal if they have the same elements. This is written A
= B. |
|
| Subsets |
| If set
S and T
are two sets such that every element of
S is also an
element of the set T,
then
S is said to be |
| the subset
of the set T,
and is written as
S Í
T.
Every set is a subset of
itself. |
|
| If
S is a subset of T,
but not
equal to T,
then
S is also proper subset
of T.
Therefore, a proper
subset is one strictly contained within a larger
set and excluding some of its elements. |
|
| The
empty set or the null set |
| A
set which has no members is called the empty
set or the null set and is denoted by ø
or { }. |
| The
empty set is
therefore a
subset of every set. |
|
| Universal
set or universe |
| A universal set
U
is a set large enough to include all the elements of any set
relevant to a problem |
|
under consideration.
Hence, the universal set is a set defined by the context. |
|
| Power
set |
| A
power set is a set of which the elements are all the subsets of
a given set
S including the empty
set, |
| written P(S)
or 2S. |
|
| Example: |
If
S
is the set { 1, 2, 3 } then power set of S,
P (S)
= { {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}. |
|
|
| Operations
on Sets and Venn Diagrams |
|
There are three basic set operations:
union, intersection and difference (relative complement).
|
| The union of two sets A
U B
is the set that consists of all elements belonging to either
set A
or set B
|
| (or both).
We
say that an element x
is in A
U B
if either x
is in A
or x
is in B (or
x
belongs
to both). |
| In
formal notation, A
U B
= {
x |
x Î
A or
x Î
B or
both }. |
| The intersection of two sets A
∩ B
is the set of all elements that are elements of both A
and B. |
| In
formal notation, A
∩ B
= {
x |
x Î
A and
x Î
B }. |
|
|
|
|
|
The union and the intersections of sets A
and B
represented by Venn
Diagrams. |
|
| The difference
(or the relative complement of B
in A),
denoted as A − B
(or A
\ B),
is the set of all |
| elements
that are elements of A
but not of B.
In formal notation, A
− B
= {
x |
x Î
A and
x not
Î
of B }. |
| The
complement (or the absolute complement) of A
in U,
denoted as A'
(or Ac),
is the set of all elements |
| of a
given universal set that are not elements of A.
In formal notation, A'
= {
x |
x Î
U
and
x not
Î
of A
}. |
|
|
|
|
|
The difference A
− B
and the complement A'
represented by Venn
Diagrams. |
|
|
| Example: |
Assuming
the set of natural numbers N
is the universal set given are sets, |
|
|
A = {
x Î
N
|
x <
5
},
B
= {
x Î
N
|
3
≤ x <
8 }
and
C
= {
x Î
N
|
x =
2n
− 1,
n
Î N
}. |
|
Find: a) A
∩ B,
b) A
U B,
c)
A
− B,
d)
B
− A
and e)
C'. |
|
| Solution:
As A
= {
x Î
N
|
x <
5
} =
{ 1, 2, 3, 4 }, |
|
B = {
x Î
N
|
3
≤ x <
8 }
=
{ 3, 4, 5, 6, 7 } |
|
and C
= {
x Î
N
|
x =
2n
− 1,
n
Î
N
}
= {
1, 3, 5, 7, . . . } |
|
then a) A
∩ B
=
{ 3, 4 },
b) A
U B
=
{ 1, 2, 3, 4, 5, 6,
7 }, |
|
c)
A
− B
=
{ 1, 2 },
d)
B
− A
=
{ 5, 6, 7 } |
| and
e) C'
= {
x Î
N
|
x =
2n
} = {
2, 4, 6, 8, . . . }. |
|
|
| Partition
of a Set |
| A partition of a set
S is a collection of non-empty disjoint subsets of
S, whose union is
S. Two sets are said |
|
to be
disjoint if they have no elements in common.
|
|
| Example: |
If
given set is {1, 2, 3, 4, 5, 6, 7} then one of its
possible partitions is { {1, 3, 7}, {2}, {4, 5}, {6} }. |
|
|
|
The
Fundamental Laws of the Algebra of Sets |
| associative
law:
(A
U B)
U C
= A
U (B
U C)
and
(A ∩ B) ∩ C
= A ∩ (B ∩ C
) |
| commutative
law:
A
U B
= B U A
and
A ∩ B
= B
∩ A |
| distributive
law:
A
U (B ∩ C) = (A U B) ∩ (A U C)
and
A ∩ (B U C) = (A ∩ B) U (A ∩ C) |
| De
Morgan's laws: A
U B)'
= A' ∩ B'
and
(A ∩ B)'
= A' U B' |
|
|
| The
distributive law A
U (
B ∩ C
) = ( A U B
) ∩ (
A U C
) shown
by Venn Diagrams: |
 |
|
| Sets
and Logic |
| In logic a statement
is a sentence that is either true or false, but not both. The
truth or falsity of a statement |
| is called its truth value. Truth
values can be represented as binary numbers, where 0 denotes
false and 1 |
| denotes true. |
| Compound
statements or proposition are two or more simple statements
joined by connectives. Two |
|
connectives used to make compound statements are the words
“and” and “or.” |
| The compound statement formed by the
word “and” is called the conjunction or the logical
product, and |
| denoted as p
Λ
q.
A conjunctive statement is true only if its statements
(components) are both true. |
| The
compound statement formed by the word “or” is called
the disjunction
or the logical sum, and |
| denoted as p
V
q.
A disjunctive statement is true if
either or both of its statements is true, and false only |
| when
both are false. |
| The
truth tables for the compound statements, p
Λ
q and p
V
q,
and corresponding Venn
Diagrams for the |
| intersection and the union are shown
below. |
| |
p |
q |
p
Λ
q |
| 1 |
0 |
0 |
0 |
| 2 |
1 |
0 |
0 |
| 3 |
0 |
1 |
0 |
| 4 |
1 |
1 |
1 |
|
|
| |
p |
q |
p
V
q |
| 1 |
0 |
0 |
0 |
| 2 |
1 |
0 |
1 |
| 3 |
0 |
1 |
1 |
| 4 |
1 |
1 |
1 |
|
|
| Observe
coincidence between the four combinations
in the truth tables and the corresponding four
numbered |
| areas in the Venn
Diagrams, so |
| -
first combination, that describe the case when an element
doesn't belong to the set A
nor B,
correspond to |
| the part of the
universal
set excluding areas of A
and B,
numbered 1. |
| -
second combination, that describe the case when an element
belong to the set A
but not to B,
correspond |
| to the part of the set A
which is not in B,
numbered 2.
|
| -
third combination, when an element
belong to B
but not to A,
correspond to the area that is numbered 3. |
| -
forth combination, when an element
belong to A
and B,
correspond to the area that is numbered 4 and |
|
which is
shared region between the sets A
and B. |
|
| Logical negation "not
p"
or ~p
denotes negation
of |
| an statement p.
Thus the truth value of the negation |
| of any statement is
always opposite of the truth value |
| of the given
statement, as is shown in the truth table. |
|
|
|
|
| Relations |
| The
Cartesian product of two sets X and
Y, denoted
X
× Y, is
the set of all possible ordered pairs (x,
y) |
| where x is a
member of X
and y
is a member of Y: |
|
X ×
Y
= { (x,
y)
| x
Î
X
and y
Î
Y
} |
| A
relation R
from
X to
Y
is a subset of the
Cartesian product X
× Y. The notations
(x,
y)
is an element of R |
|
and x
R y
(x
is in relation to
y) are equivalent.
Formally, any set of ordered pairs which defines a relation |
|
between the first member of each pair and its corresponding
second member. |
| |
| The
domain of a relation R
is the set of all the first
components of the ordered pairs that constitute the |
|
relation.
The range of R
is the set of all the second components of
every ordered pair in
R.
|
| If each first member of a relation is associated with only one second member, the relation is a
function. |
|
| Example: |
Given is
set S
= {1, 3, 5, 7, 9} and relations on S: |
|
|
| R1 = {(1, 3), (3, 5), (5, 1), (3, 7), (7, 9), (9, 1)}, |
| R2 = {(1, 1), (3, 3), (5, 5), (7, 7), (9, 1)}, |
| R3 = {(1, 5), (3, 7), (7, 1), (9, 5), (1, 1)}, |
| R4 = {S
× S}. |
|
|
|
| Which of these relations is function from
S
to S ? |
| Solution:
A binary relation R, a subset of the Cartesian product A
×
B, is said to be a function from
A to
B if |
| for
each x Î
A there is exactly one
y
Î
B, such that the pair
(x,
y) is in subset R. The set A is called the
|
| domain of the function, and the set
B is called the codomain of the function.
Thus, |
|
R2 = {(1, 1), (3, 3), (5, 5), (7, 7), (9, 1)} is the function from
S
to S. |
|
| Relation
on a Set |
| Let
X
be the given set, then a relation R
on X
is a subset of the Cartesian product of X
with itself, i.e., X
× X. |
| A
relation R
on X
is said to be reflexive if x
R
x
for every x
Î
X. |
| A
relation R
on X is
symmetric if x
R
y
implies that y
R
x. |
| A
relation R
on X is
transitive if x
R
y
and y
R
z imply
that x
R
z. |
| An
equivalence relation is relation on set X
that is reflexive, symmetric and transitive. |
|
| Example: |
Supplement the relation
R
= {(1, 1), (2, 2), (3, 2), (4, 1)}, defined on the set
S
= {1, 2, 3, 4}, with
|
|
| minimal number of elements of the product set
S
×
S
such that the relation becomes symmetric. |
| Solution:
The given relation should be supplemented with pairs (1, 4) and (2, 3). |
|
| The relation
R
= {(1, 1), (1, 4), (2, 2), (2, 3), (3, 2), (4, 1)} is symmetric (in |
|
relation to the main diagonal). |
|
|
 |
|
|
|
|
|
|
|
|
|
|
|
| Copyright
© 2004 - 2012, Nabla Ltd. All rights reserved. |
