COSC 55 – REVIEWER b.
Rule method: A = {x | 1 ≤ x ≤ 10 and x is
a counting number}.
SETS
UNIVERSAL SET AND EMPTY SET
BASIC SETS CONCEPTS
The universal set is the totality of all
SET AND SET ELEMENTS elements under consideration. This is
denoted by the symbol U
A set is a collection of objects called
A set containing no elements is called an
elements.
empty set (or null set). This is denoted by Ø
The elements of a set must be distinct,
or { }. Thus, |Ø| = 0.
unordered and well-defined. So, this means
that a set should not contain duplicates; the
We use the symbol ∈ (“is an element of”)
SET MEMBERSHIP
ordering of elements is insignificant and you
should be able to determine whether or not
x ∈ A (“x is an element of a set A”) if and
to denote set membership. Here, we define
a certain element belongs to a set.
Elements of a set are separated by
A). Otherwise, we write x ∉ A to denote x is
commas and the whole thing is enclosed in only if x is a member of a set A (or, x is in
braces, { }.
Example 1-1 not an element of set A.
The sets {1, 1, 2, 3}, {1, 2, 3, 3}, and {2, 3,
Here, we use the symbol ⊆ (“is a subset
1, 3} can be simply written as a set with SET CONTAINMENT
three elements, i.e.
A is a subset of set B”, denoted by A ⊆ B, if
{1, 2, 3}. of”} to denote set containment. We say “set
A set may be either finite or infinite. If the
elements can be counted or enumerated, and only if every element of set A is an
then the set is element of set B. In this case, we also say
said to be finite. Otherwise, it is infinite. that set A is contained in set B.
SET REPRESENTATIONS NOTE:
The roster method, wherein we just list You can best understand the difference
down or enumerate the elements of a set. between set membership and set
Thus, this method cannot be used to containment if you consider the set symbols
represent infinite sets. {}, as a box. Thus, {1} is “ a box holding 1, “
The rule method, wherein we give a rule while { {1} } is “a box holding a box holding
which states the property satisfied by all of 1.”The only subsets of {1} are {1} and { };
the elements in the set. It is usually of the the subsets of { {1} } are { {1} } and { }.
form {x | “x has the property...”}, which
reads, “ the set of all elements x such that x EXAMPLE:
has the property...” Take note that in Let A = {1}, B = {{1}}, C = {1, {1}}.
A ⊂ C, and B ⊂ C
describing the property, all conditions Here,
should be met for all the elements in the
A ⊄ B, since A ⊈ B, and
set. But,
A ⊄ A, since A = A (although A ⊆ A)
EXAMPLE
a. Roster method: A = {1, 2, 3, 4, 5, 6, 7, 8,
9, 10}, or you can use ellipses (...) to
shorten the list, Every set is a subset of itself, but no set
A = {1, 2, ..., 10}. is an element of itself.
UNARY OPERATIONS ON SET
There is one unary operation on sets, and This gives a graphical representation of set
that is, the power set of a set. The power of properties. The universal set is
all subsets of set A. That is, p (A) = {x | x ⊆
set of a set A, denoted by p (A), is the set of represented by a rectangle, and subsets of
the universal set are represented by circles
A} or any closed polygon.
The following gives the Venn Diagram for
Binary operations on sets the basic set concepts and operations:
Here are more operations that we can
perform on sets.
Complement of A A’ = {x | x ∈ U ˄ x ∉ A}
A’ is the set of all elements that are not in A
(but are in the universal set of U).
Union of A and B A ∪ B = {x | x ∈ A v x ∈ B}
A ∪ B is the set of all elements that are in
either sets A or B.
∈ A ˄ x ∈ B}
Intersection of A and B A ∩ B = {x | x
A ∩ B is the set of all elements that are in
both sets A and B. BASIC COUNTING PRINCIPLES
SUM RULE
∈ A ˄ x ∉ B}
Difference of A and B A – B = {x | x
A – B is the set of all elements that are in
set A but not in set B.
Thus, the difference of A and B can also be
expressed as A – B = A ∩ B’
A△B
= {x |( x ∈ A v x ∈ B) ˄ ~(x ∈ A ˄ x ∈ B)}
Symmetric Difference of A and B
A △ B is the set of all elements that are in
either A or B but not both.
EXAMPLE
EXAMPLE
Let A = {1, 3, 5, 7}, B = {1, 2, 3, 4}, and U = {1,
A ∪ B = {1, 2, 3, 4, 5, 7} A’ = {2, 4, 6, 8, 9,
2, ..., 10}.
10}
A – B = {5, 7}
A ∩ B = {1, 3}
B’ = {5, 6, ..., 10}
A △ B = {2, 4, 5, 7}
B – A = {2, 4}
Venn Diagram
digit is to be repeated, then we only have 6
and 5 choices for the tens and the
hundreds digit, respectively. So there are 5
• 6 • 4 = 120 3-digit numbers with no
repeated digits that can be formed.
INCLUSION-EXCLUSION
PRODUCT RULE
EXAMPLE
For the number to be odd, it should end
with either 1, 3, 5, or 9. Thus, we have 4
choices for the ones digit. And since no
