Transcript Mathematical Ideas

Chapter 2
The Basic
Concepts of
Set Theory
© 2008 Pearson Addison-Wesley.
All rights reserved
Chapter 2: The Basic Concepts of
Set Theory
2.1
2.2
2.3
2.4
2.5
Symbols and Terminology
Venn Diagrams and Subsets
Set Operations and Cartesian Products
Surveys and Cardinal Numbers
Infinite Sets and Their Cardinalities
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-2
Chapter 1
Section 2-1
Symbols and Terminology
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-3
Symbols and Terminology
•
•
•
•
Designating Sets
Sets of Numbers and Cardinality
Finite and Infinite Sets
Equality of Sets
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-4
Designating Sets
A set is a collection of objects. The objects
belonging to the set are called the elements, or
members of the set.
Sets are designated using:
1) word description,
2) the listing method, and
3) set-builder notation.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-5
Designating Sets
Word description
The set of even counting numbers less than 10
The listing method
{2, 4, 6, 8}
Set-builder notation
{x|x is an even counting number less than 10}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-6
Designating Sets
Sets are commonly given names (capital letters).
A = {1, 2, 3, 4}
The set containing no elements is called the
empty set (null set) and denoted by { } or .
To show 2 is an element of set A use the symbol
2 {1, 2,3, 4}
.
a {1, 2,3, 4}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-7
Example: Listing Elements of Sets
Give a complete listing of all of the elements of
the set {x|x is a natural number between 3 and 8}
Solution
{4, 5, 6, 7}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-8
Sets of Numbers
Natural (counting) {1, 2, 3, 4, …}
Whole numbers {0, 1, 2, 3, 4, …}
Integers {…,–3, –2, –1, 0, 1, 2, 3, …}
Rational numbers  p

 p and q are integers, with q  0 
q

May be written as a terminating decimal, like 0.25, or a
repeating decimal like 0.333…
Irrational {x | x is not expressible as a quotient of
integers} Decimal representations never terminate and
never repeat.
Real numbers {x | x can be expressed as a decimal}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-9
Cardinality
The number of elements in a set is called the
cardinal number, or cardinality of the set.
The symbol n(A), read “n of A,” represents the
cardinal number of set A.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-10
Example: Cardinality
Find the cardinal number of each set.
a) K = {a, l, g, e, b, r}
b) M = {2}
c) 
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-11
Finite and Infinite Sets
If the cardinal number of a set is a particular
whole number, we call that set a finite set.
Whenever a set is so large that its cardinal
number is not found among the whole numbers,
we call that set an infinite set.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-12
Example: Infinite Set
The odd counting numbers are an infinite set.
Word description
The set of all odd counting numbers
Listing method
{1, 3, 5, 7, 9, …}
Set-builder notation
{x|x is an odd counting number}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-13
Equality of Sets
Set A is equal to set B provided the following
two conditions are met:
1. Every element of A is an element of B,
AND
2. Every element of B is an element of A.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-14
Example: Equality of Sets
State whether the sets in each pair are equal.
a) {a, b, c, d} and {a, c, d, b}
b) {2, 4, 6} and {x|x is an even number}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-15
Section 2.1: Symbols and
Terminology
1. Which of the following is an example of setbuilder notation?
a) The counting numbers less than 5
b) {1, 2, 3, 4}
c) {x | x is a counting number less than 5}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-16
Section 2.1: Symbols and
Terminology
2. Are sets {6, 7, 8} and {7, 8, 6} equal?
a) Yes
b) No
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-17
Chapter 1
Section 2-2
Venn Diagrams and Subsets
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-18
Venn Diagrams and Subsets
•
•
•
•
•
Venn Diagrams
Complement of a Set
Subsets of a Set
Proper Subsets
Counting Subsets
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-19
Venn Diagrams
In set theory, the universe of discourse is called the
universal set, typically designated with the letter U.
Venn Diagrams were developed by the logician John
Venn (1834 – 1923). In these diagrams, the universal
set is represented by a rectangle and other sets of
interest within the universal set are depicted as circular
regions.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-20
Venn Diagrams
The rectangle represents the universal set,
U, while the portion bounded by the circle
represents set A.
A
U
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-21
Complement of a Set
The colored region inside U and outside the circle is
labeled A' (read “A prime”). This set, called the
complement of A, contains all elements that are
contained in U but not in A.
A
A
U
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-22
Complement of a Set
For any set A within the universal set U, the
complement of A, written A', is the set of all
elements of U that are not elements of A.
That is
A  {x | x U and x  A}.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-23
Subsets of a Set
Set A is a subset of set B if every element of A
is also an element of B. In symbols this is
written A  B.
B
A
U
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-24
Example: Subsets
Fill in the blank with  or 
 to make a true
statement.
a) {a, b, c} ___ { a, c, d}
b) {1, 2, 3, 4} ___ {1, 2, 3, 4}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-25
Set Equality (Alternative Definition)
Suppose that A and B are sets. Then A = B if
A  B and B  A are both true.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-26
Proper Subset of a Set
Set A is a proper subset of set B if A  B
and A  B.
In symbols, this is written A  B.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-27
Example: Proper Subsets
Decide whether  ,  , or both could be placed
in each blank to make a true statement.
a) {a, b, c} ___ { a ,b, c, d}
b) {1, 2, 3, 4} ___ {1, 2, 3, 4}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-28
Counting Subsets
One method of counting subsets involves using a
tree diagram. The figure below shows the use of a
tree diagram to find the subsets of {a, b}.
a subset? b subset? 4 subsets
Yes
No
Yes
No
Yes
No
{a, b}
{a}
{b}

© 2008 Pearson Addison-Wesley. All rights reserved
2-1-29
Number of Subsets
The number of subsets of a set with n elements
is 2n.
The number of proper subsets of a set with n
elements is 2n – 1.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-30
Example: Number of Subsets
Find the number of subsets and the number of
proper subsets of the set {m, a, t, h, y}.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-31
Section 2.2: Venn Diagrams and Subsets
1. Find the complement of {m} if U = {m, n}.
a) {m}
b) {n}
c) U
d) 
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-32
Section 2.2: Venn Diagrams and Subsets
2. Find the number of subsets of { $, #, @ }.
a) 0
b) 3
c) 6
d) 8
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-33
Chapter 1
Section 2-3
Set Operations and Cartesian Products
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-34
Set Operations and Cartesian
Products
•
•
•
•
•
•
•
Intersection of Sets
Union of Sets
Difference of Sets
Ordered Pairs
Cartesian Product of Sets
Venn Diagrams
De Morgan’s Laws
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-35
Intersection of Sets
The intersection of sets A and B, written A B,
is the set of elements common to both A and
B, or
A B  {x | x  A and x  B}.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-36
Example: Intersection of Sets
Find each intersection.
a) {1,3,5, 7,9} {1, 2,3, 4,5, 6}
b) {2, 4, 6} 
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-37
Union of Sets
The union of sets A and B, written A B,
is the set of elements belonging to either of
the sets, or
A B  {x | x  A and x  B}.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-38
Example: Union of Sets
Find each union.
a) {1,3,5, 7,9} {1, 2,3, 4,5, 6}
b) {2, 4, 6} 
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-39
Difference of Sets
The difference of sets A and B, written A – B,
is the set of elements belonging to set A and
not to set B, or
A  B  {x | x  A and x  B}.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-40
Example: Difference of Sets
Let U = {a, b, c, d, e, f, g, h}, A = {a, b, c, e, h},
B = {c, e, g}, and C = {a, c, d, g, e}.
Find each set.
a) A  B
b)  B  A C
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-41
Ordered Pairs
In the ordered pair (a, b), a is called the
first component and b is called the second
component. In general (a, b)  (b, a ).
Two ordered pairs are equal provided that
their first components are equal and their
second components are equal.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-42
Cartesian Product of Sets
The Cartesian product of sets A and B,
written, A  B, is
A  B  {(a, b) | a  A and b  B}.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-43
Example: Finding Cartesian Products
Let A = {a, b}, B = {1, 2, 3}
Find each set.
a) A  B
b) B  B
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-44
Cardinal Number of a Cartesian Product
If n(A) = a and n(B) = b, then
n  A  B   n( B  A)
 n( A)  n( B)  n( B)  n( A)
 ab  ba
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-45
Example: Finding Cardinal Numbers of
Cartesian Products
If n(A) = 12 and n(B) = 7, then find
n  A  B  and n  B  A .
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-46
Venn Diagrams of Set Operations
A B
A
A B
B
A
U
U
A
A
U
B
A B
A
A
B
U
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-47
Example: Shading Venn Diagrams to
Represent Sets
Draw a Venn Diagram to represent the set
A B.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-48
Example: Shading Venn Diagrams to
Represent Sets
Draw a Venn Diagram to represent the set
 A
B C.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-49
De Morgan’s Laws
For any sets A and B,




A
B

A
B
and
A
B



  A B.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-50
Section 2.3: Set Operations and
Cartesian Products
1. If U = {a, b, c} and A = {a} then find
A .
a) A
b) {b, c}
c) U
d) 
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-51
Section 2.3: Set Operations and
Cartesian Products
2. Which choice indicates the shaded
region below?
a) E
F
G
b) E
F
G
c) E
F
G
E
U
G
H
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-52
Chapter 1
Section 2-4
Surveys and Cardinal Numbers
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-53
Surveys and Cardinal Numbers
• Surveys
• Cardinal Number Formula
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-54
Surveys
Problems involving sets of people (or other
objects) sometimes require analyzing known
information about certain subsets to obtain
cardinal numbers of other subsets. The
“known information” is often obtained by
administering a survey.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-55
Example: Analyzing a Survey
Suppose that a group of 140 people were questioned
about particular sports that they watch regularly and the
following information was produced.
93 like football
40 like football and baseball
70 like baseball
25 like baseball and hockey
40 like hockey
28 like football and hockey
20 like all three
a) How many people like only football?
b) How many people don’t like any of the sports?
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-56
Example: Analyzing a Survey
Construct a Venn diagram. Let F = football,
B = baseball, and H = hockey.
B
F
H
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-57
Cardinal Number Formula
For any two sets A and B,
n  A B   n( A)  n( B)  n( A B).
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-58
Example: Applying the Cardinal
Number Formula
Find n(A) if
n  A B   78, n  A B  =21, and n( B)  36.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-59
Example: Analyzing Data in a Table
On a given day, breakfast patrons were
categorized according to age and preferred
beverage. The results are summarized on
the next slide. There will be questions to
follow.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-60
Example: Analyzing Data in a Table
Coffee
(C)
Juice
(J)
Tea
(T)
Totals
18-25
(Y)
15
22
18
55
26-33
(M)
Over 33
(O)
30
25
22
77
45
22
24
91
Totals
90
69
64
223
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-61
Example: Analyzing Data in a Table
(C)
(J)
(T)
Totals
(Y)
15
22
18
55
(M)
30
25
22
77
(O)
45
22
24
91
Totals
90
69
64
223
Using the letters in the table, find the number of
people in each of the following sets.
a) Y
C
b) O T
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-62
Section 2.4: Surveys and Cardinal
Numbers
1. n( A B)  n( A)  n( B )
a) Always
b) Sometimes
c) Never
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-63
Section 2.4: Surveys and Cardinal
Numbers
2. Find n  ( A B) C .
a) 15
b) 36
c) 10
A
11
10
2
B
13
C
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-64
Chapter 1
Section 2-5
Infinite Sets and Their Cardinalities
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-65
Infinite Sets and Their Cardinalities
• One-to-One Correspondence and Equivalent
Sets
• The Cardinal Number 0 (Aleph-Null)
• Infinite Sets
• Sets That Are Not Countable
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-66
One-to-One Correspondence and
Equivalent Sets
A one-to-one correspondence between two
sets is a pairing where each element of one set
is paired with exactly one element of the
second set and each element of the second set
is paired with exactly one element of the first
set.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-67
Example: One-to-One Correspondence
For sets {a, b, c, d} and {3, 7, 9, 11} a pairing
to demonstrate one-to-one correspondence
could be
{a, b, c, d}
{3, 7, 9, 11}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-68
Equivalent Sets
Two sets, A and B, which may be put in a
one-to-one correspondence are said to be
equivalent, written A ~ B.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-69
The Cardinal Number
0
The basic set used in discussing infinite sets
is the set of counting numbers, {1, 2, 3, …}.
The set of counting numbers is said to have
0
the infinite cardinal number
(aleph-null).
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-70
Example: Showing That {2, 4, 6, 8,…}
Has Cardinal Number 0
To show that another set has cardinal number 0 ,
we show that it is equivalent to the set of
counting numbers.
{1, 2, 3, 4, …, n, …}
{2, 4, 6, 8, …,2n, …}
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-71
Infinite Sets
A set is infinite if it can be placed in a oneto-one correspondence with a proper subset
of itself.
The whole numbers, integers, and rational
numbers have cardinal number 0 .
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-72
Countable Sets
A set is countable if it is finite or if it has
cardinal number 0 .
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-73
Sets That Are Not Countable
The real numbers and irrational numbers are
not countable and are said to have cardinal
number c (for continuum).
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-74
Cardinal Numbers of Infinite Sets
Infinite Set
Cardinal Number
Natural Numbers
0
Whole Numbers
0
Integers
0
Rational Numbers
0
Irrational Numbers
c
Real Numbers
c
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-75
Section 2.5: Infinite Sets and Their
Cardinalities
1. The cardinal number of a finite set is
always less than 0 .
a) True
b) False
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-76
Section 2.5: Infinite Sets and Their
Cardinalities
2. The set {1, 7, 11, 15, 19, …} is
equivalent to
a) the rational numbers.
b) the irrational numbers.
c) the reals.
© 2008 Pearson Addison-Wesley. All rights reserved
2-1-77