Transcript Mathematical Proofs - Kutztown University

Mathematical Proofs
Chapter 1 Sets
•
•
•
•
•
1.1 Describing a Set
1.2 Subsets
1.3 Set Operations
1.4 Indexed Collections of Sets
1.5 Partitions of Sets
Section 1.1 Describing a Set
A set is a collection of objects. The objects that make up the set are
called its elements.
It’s customary to use capital (uppercase) letters (such as A, B, C, S, X,
Y) to describe sets and lowercase letters (for example, a, b, c, s, x,
y) to represent elements of sets.
If a is an element of the set A, then we write aA; if a does not belong
to A, then we write a A.
List All the Elements
If a set consists of a smaller number of elements, then it can be
described by explicitly listing its elements between braces where the
elements are separated by commas.
Example: S = {1, 2, 3} is a set.
Note that the order in which the elements are listed doesn’t matter.
Example: S = {1, 2, 3} = {1, 3, 2} = {2,1,3} etc.
If a set contains too many elements to be listed, then we use the
ellipsis or “three dot notation”.
Example: The set of all positive even integers less than 41 can be
described by X={2, 4, …, 40}
The set of all positive odd integers can be described by Y={1, 3, 5, …}
Empty Set
There is one set that contains no elements, and it is called the empty
set, denoted by . We also write ={}.
Example: The set of real number solutions of equation x2+1=0, then
S=.
Note: The elements of a set may in fact be sets themselves.
Example: The set S={a, b, {c, d}, e, } has 5 elements.
Describe the Property
Often sets consist of those elements satisfying some specified property.
In this case, we can describe it as S={x: p(x)} , which means S
consists of all those elements x satisfying some condition p(x)
concerning x.
Example: T={x: |x|=3}.
For a set S, the cardinality of S is the number of elements in S, denoted
by |S|.
Example: if S={a, b, {c, d}, e, }, then |S|=5. Also, |  |=0.
A set S is finite if |S|=n for some nonnegative integer n. A set S is
infinite if it is not finite.
Special Sets
Some sets are given special notations.
N: the set of natural numbers. (positive integers.) N={1, 2, 3, …}
Z: the set of all integers (positive, negative, and zero).
Z={…,-1, 0, 1, …}
Q: the set of rational numbers. (m/n, where m, n  Z and n 0).
I: the set of all irrational numbers. (a real number that is not rational.)
R: the set of real numbers
R+: the set of positive real numbers.
C: the set of complex numbers. ( a number of the form a+bi, where a, b
 R and i  1 )
Section 1.2 Subsets
A set A is called a subset of a set B is every element of A also belongs
to B. If A is a subset of B, then we write A B. If a set C is not a
subset of D, then we write CD. That is, there must be some
element of C that is not an element of D.
Note that the empty set  is a subset of every set.
If A, B, and C are sets such that A B and B C, then A C.
Moreover, every set is a subset of itself.
For example: N  Z, Q  R, and R  C.
Let S={1, {2}, {1, 2}}.
(a) Determine which are elements of S, (b) Determine which are
subsets of S.
More Definitions
Two sets A and B are equal, A=B, if they have exactly the same
elements. Equivalently, A=B happens if and only if A B and BA.
A set A is a proper subset of a set B if A B but AB. If A is a proper
subset of B, then we write AB. The set consisting of all subsets of
a given set A is called the power set of A and it denoted by P(A).
Example: For each set A below, determine P(A), |A| and |P(A)|.
(a) A= , (b) B={1, 2}, (c) C={a, b, c}, (d) D={, {}}.
Note that |P(A)|=2|A|.
Venn Diagrams
This is an example of Venn diagram:
B
A
x
z
y
w
This presents two sets A and B. A rectangle in a Venn diagram
represents the universal set (the set we are considering).
Note xA, xB; yB, yA; z A, z B; w A, w B.
Interval
Some frequently encountered subsets of R are the so-called “intervals”.
• For a, b  R and a<b, the open interval (a, b) is the set
(a, b)={x  R: a < x < b}.
• For a, b  R and a b, the closed interval [a, b] is the set
[a, b]={x  R: a  x  b}.
• For a, b  R and a b, the half-open interval [a, b), (a, b] are the
sets [a, b)={x  R: a  x < b}, and (a, b]={x  R: a < x  b}.
For a  R, the infinite intervals (-, a), (-, a], (a, ) and [a, ) are
defined as
(-, a)={x  R: x < a}, (-, a]={x  R: x  a},
(a, )={x  R: x >a}, [a, )={x  R: x  a}.
Note that (-, ) is the set R.
Section 1. 3 Set Operations
The union of two sets A and B, denoted by AB, is the set of all
elements belonging to A or B. That is,
AB={x: x  A or x  B}.
A Venn diagram for AB is
Example: Let A={a, b}, B={a, c, d} and C={b, e, g}. Find AB, AC
and BC.
Note: N  Z=Z and Q  I=R.
Intersection
The intersection of two sets A and B, denoted by A  B, is the set of all
elements belonging to both A and B. That is,
A  B={x: x  A and x  B}.
A Venn diagram for A  B is
Example: Let A={a, b}, B={a, c, d} and C={b, e, g}. Find A  B, A  C
and B  C.
Note: N  Z=N and Q  I= .
If two sets A and B have no elements in common, then A  B=  and A
and B are said to be disjoint.
Difference
The difference A-B of two sets A and B is defined as
A - B={x: x  A and x  B}.
A Venn diagram for A - B is
Example: Let A={a, b}, B={a, c, d} and C={b, e, g}. Find A - B, C - B
and A  C.
Note: R-Q=I.
Complement
Suppose that we are considering a certain universal set U. For a set A,
its complement is
A  U  A  {x U and x  A}.
A Venn diagram for
A is
Examples
Example: Let U={1, 2, …, 10} be the universal set, A={1, 2, 4, 8} and
B={1, 3, 5, 7, 9}. Determine each of the following:
(a) B , (b) B- A, (c) A  B, (d) B
Example: Let A={0, {0}, {0, {0}}}.
(a) List all the elements of A,
(b) List all the subsets of A,
(c) Determine |A|,
(d) {0} A, {{0}} A, {{{0}}} A, {0} A, {{0}} A, {{{0}}} A.
Section 1.4 Indexed Collections of Sets
We will often encounter situations where more than two sets are
combined using the set operations described in section 1.3.
The union A B C is defined as
A B C={x: x  A or x B or x C}
Generally, the union of the n2 sets A1, A2,…,An is denoted by
A1A2…An={x: x  Ai for some i, 1in}
n
Thus, for an element a to belong to i 1 Ai , it is necessary that a
belongs to at least one of the sets A1, A2,…,An.
Examples
Example: Let Bi={I, i+1} for i=1, 2, …, 10. Determine each of the
following:
5
a)
8
Bi , b)
i 1
k
Bi ,
Bi , where 1  j  k  8.
c)
i 2
i j
Similarly, the intersection of the n2 sets A1, A2,…,An is denoted by
n
A1  A2  …  An, or
and is defined by
i 1 Ai
n
i 1
Ai ={x: x  Ai for every i, 1in}
Example: Let Bi={I, i+1} for i=1, 2, …, 10. Determine each of the
following:
10
a)
i 1
Bi , b) Bi  Bi 1 ,
k
c)
i j
Bi , where 1  j  k  8.
Indexed Collection of Sets
We introduce a (nonempty) set I, called an index set. For an index
set I, suppose that there is a set S for each   I.
We write {S }  I to describe the collection of all sets S , where 
 I. Such a collection is called an indexed collection of sets.
We define the union of the sets in {S }  I by
 I
S  {x : x  S for some   I }
An element a belongs to S if a belongs to at least one of the sets
in the collection {S }II
We refer to I S as the union of the collection {S }  I
Intersection
We define the intersection of the sets in {S }  I by
 I
S  {x : x  S for all   I }
An element a belongs to
{S }  I
 I
S
if a belongs to every set in the collection
We refer to  I S as the intersection of the collection {S }  I.
Here the variables I and  are “dummy variables” and any appropriate
symbol could be used.
Example
Example: For nN, define Sn={n, 2n}. Then S1S2  S3={1, 2, 4, 8}. If
we let I={1, 2, 4}, then S  S1  S 2  S3
 I
Example: For each nN, define An to be the closed interval [-1/n, 1/n] of
real numbers. That is, An={xR: -1/nx  1/n}.
Then n N An=[-1, 1]. In fact, n N An=0.
Section 1.5 Partitions of Sets
Recall that two sets are disjoint if their intersection is the empty set. A
collection S of subsets of a set A is called pairwise disjoint if every
two distinct subsets that belong to S are disjoint.
A partition of A can be defined as a collection S of nonempty subsets of
A such that every element of A belongs to exactly one subset in S.
Furthermore, a partition of A can be defined as a collection S of subsets
of A satisfying the three properties:
1. X for every set XS;
2. For every two sets X, Y S, either X=Y or XY=;
3. X SX=A.
Example
Example: Let A={1, 2, 3, 4, 5, 6}. Determine which are the partitions of
A.
1. {{1, 3, 6}, {2, 4}, {5}};
2. {{1, 2, 3}, {4}, , {5, 6}};
3. {{1, 2}, {3, 4, 5}, {5, 6}};
4. {{1, 4}, {3, 5}, {2}};
Example:
1. Z can be partitioned into the set of even integers and the set of odd
integers.
2. R can be partitioned into R+, the set of negative real numbers, and
{0}. It can also be partitioned into the set Q and the set I.
Section 1.6 Cartesian Product of Sets
The ordered pair (x, y) is a single element consisting of a pair of
elements in which x is the first coordinate of the ordered pair (x, y)
and y is the second coordinate.
If two ordered pairs (x, y) and (w, z) are equal, that is (x, y)=(w, z), then
x=w and y=z. So if x  y, then (x, y)  (y, x).
The Cartesian product A X B of two sets A and B is the set consisting of
all ordered pairs whose first coordinate belongs to A and whose
second coordinate belongs to B. That is,
A X B = {(a, b): a A and b B}.
Example
Example: If A={x, y, z} and B={1, 2}, then find AXB, BXA, AXA, and
BXB.
Note if A= or B= , then AXB= .
Also, for all finite sets A and B, |AXB|=|A|X|B|.