Transcript algebra binds

2.1 Sets
‒ Sets
‒ Common Universal Sets
‒ Subsets
2.2 Set Operations
2.3 Functions
2.4 Sequences and Summations
1
Sets
• A set is a collection or group of objects or
elements or members. (Cantor 1895)
– A set is said to contain its elements.
– There must be an underlying universal set U,
either specifically stated or understood.
2
Sets
• Notation:
– list the elements between braces:
S = {a, b, c, d}={b, c, a, d, d}
(Note: listing an object more than once does not
change the set. Ordering means nothing.)
– specification by predicates:
S = {x| P(x)}
• S contains all the elements from U which make the
predicate P true.
– brace notation with ellipses:
S = { . . . , -3, -2, -1},
the negative integers.
3
Common Universal Sets
• R = reals
• N = natural numbers = {0,1, 2, 3, . . . }, the
counting numbers.
• Z = all integers = {. . , -3, -2, -1, 0, 1, 2, 3,4, . .}.
• Z+ ={1,2,3,…},the set of positive integers.
• Q={P/q | p  Z,q  Z and q≠0},the set of
rational numbers.
• Q+={x R | x=p/q, for some positive integers
p and q}
4
Common Universal Sets
• Notation:
x is a member of S or x is an element of S:
x S
x is not an element of S:
xS
5
Subsets
• Definition: The set A is a subset of the set B,
denoted A B, iff x[xA→xB]
• Definition: The void set, the null set, the empty
set, denoted Ø, is the set with no members.
• Note: the assertion x  Ø is always false. Hence
 x[x  Ø → x  B] is always true.
Therefore, Ø is a subset of every set.
• Note: Set B is always a subset of itself.
6
Subsets
• Definition: If A  B but A  B the we say A
is a proper subset of B, denoted A  B.
• Definition: The set of all subset of set A,
denoted P(A), is called the power set of A.
7
Subsets
• Example: If A = {a, b} then
P(A) = {Ø, {a}, {b}, {a,b}}
8
Subsets
• Definition: The number of (distinct)
elements in A, denoted |A|, is called the
cardinality of A.
• If the cardinality is a natural number (in N),
then the set is called finite, else infinite.
9
Subsets
• Example:
– A = {a, b},
|{a, b}| = 2,
|P({a, b})| = 4.
– A is finite and so is P(A).
– Useful Fact: |A|=n implies |P(A)| = 2n
• N is infinite since |N| is not a natural number. It is
called a transfinite cardinal number.
Note: Sets can be both members and subsets of
other sets.
10
Subsets
• Example:
A = {Ø,{Ø}}.
A has two elements and hence four subsets:
Ø , {Ø} , {{Ø}} , {Ø,{Ø}}
Note that Ø is both a member of A and a subset
of A!
11
P. 1
Subsets
• Example:
A = {Ø}. Which one of the follow is incorrect:
(a) ØA
(b) ØA
(c) {Ø} A
(d) {Ø} A
12
P. 1
Subsets
• Russell's paradox: Let S be the set of all sets
which are not members of themselves. Is S
a member of itself?
• Another paradox: Henry is a barber who
shaves all people who do not shave
themselves. Does Henry shave himself?
13
P. 1
Subsets
• Definition: The Cartesian product of A with
B, denoted AB, is the set of ordered pairs
{<a, b> | a A
Λ b B}
n
Notation: 
Ai ={<a1,a2,...,an>|ai  Ai}
i 1
• Note: The Cartesian product of anything
with Ø is Ø. (why?)
14
P. 1
Subsets
• Example:
– A = {a,b} , B = {1, 2, 3}
– AxB = {<a, 1>, <a, 2>, <a, 3>, <b, 1>, <b, 2>, <b,3>}
– What is BxA? AxBxA?
• If |A| = m and |B| = n, what is |AxB|?
15
P. 1
Terms
• Sets
• Subset
16
P. 1
2.1 Sets
2.2 Set Operations
–
–
–
–
Set Operations
Venn Diagrams
Set Identities
Union and Intersection of Indexed Collections
2.3 Functions
2.4 Sequences and Summations
17
P. 1
Set Operations
• Propositional calculus and set theory are
both instances of an algebraic system called
a Boolean Algebra.
• The operators in set theory are defined in
terms of the corresponding operator in
propositional calculus.
• As always there must be a universe U. All
sets are assumed to be subsets of U.
18
P. 1
Set Operations
• Definition: Two sets A and B are equal,
denoted A = B, iff x[x A ↔ x  B].
• Note:
By a previous logical equivalence we have
A = B iff  x[(x  A→ x  B) Λ (x  B → x 
A)] or
A = B iff A  B and B  A
19
P. 1
Set Operations
• Definitions:
– The union of A and B, denoted AB, is the
set {x | xA V xB}
– The intersection of A and B, denoted
AB, is the set {x | xA Λ xB}
FIGURE 1
∪
FIGURE 2
∩
20
P. 1
Set Operations
• Note: If the intersection is void, A and B are said
to be disjoint.
– The complement of A, denoted A , is the set
{x | x  A}={x | ¬(xA)}
• Note: Alternative notation is A C, and {x|xA}.
– The difference of A and B, or the complement of B
relative to A, denoted A - B, is the set A  B
• Note: The complement of A is U - A.
– The symmetric difference of A and B, denoted AB, is
the set (A - B)(B - A).
21
P. 1
Set Operations
• Examples: U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A= {1, 2, 3, 4, 5}, B = {4, 5, 6, 7, 8}. Then
–
–
–
–
–
–
–
AB = {1, 2, 3, 4, 5, 6, 7, 8}
AB = {4, 5}
A = {0, 6, 7, 8, 9, 10}
B = {0, 1, 2, 3, 9, 10}
A - B = {1, 2, 3}
B - A = {6, 7, 8}
A  B = {1, 2, 3, 6, 7, 8}
22
P. 1
Venn Diagrams
• A useful geometric visualization tool (for 3 or less
sets)
– The Universe U is the rectangular box.
– Each set is represented by a circle and its interior.
– All possible combinations of the sets must be
represented.
• Shade the appropriate region to represent the given set
operation.
23
P. 1
Set Identities
• Set identities correspond to the logical
equivalences.
• Example:
The complement of the union is the intersection
of the complements
A B  A B
24
P. 1
Set Identities
• Proof: To show
x[ x  A  B  x  A  B]
To show two sets are equal we show for all x that x is
a member of one set if and only if it is a member of
the other.
• We now apply an important rule of inference
(defined later) called Universal Instantiation
25
Set Identities
• Universal Instantiation
In a proof we can eliminate the universal quantifier
which binds a variable if we do not assume anything
about the variable other than it is an arbitrary
member of the Universe. We can then treat the
resulting predicate as a proposition.
26
Set Identities
• We say 'Let x be arbitrary. '
Then we can treat the predicates as propositions:
Assertion
Reason
Def. of complement
x  A  B  x  [A  B]
Def. of 
x  A  B  ¬[ x  A  B]
 ¬[ x  A  x  B]
Def. of union
 ¬ xA Λ ¬ x B
DeMorgan's Laws
Def. of 
 x A xB
Def. of complement
 x A  xB
Def. of intersection
 x A  B
Hence x  A  B  x  A  B is a tautology.
27
P. 1
Set Identities
Since
– x was arbitrary
– we have used only logically equivalent assertions and
definitions
we can apply another rule of inference called
Universal Generalization
We can apply a universal quantifier to bind a variable
if we have shown the predicate to be true for all values
of the variable in the Universe.
and claim the assertion is true for all x, i.e.,
x[ x  A  B  x  A  B ]
P. 1
Set Identities
• Q. E. D. (an abbreviation for the Latin phrase
“Quod Erat Demonstrandum” - “which was to
be demonstrated” used to signal the end of a
proof)
• Note: As an alternative which might be easier
in some cases, use the identity
A  B [A  B
and
B  A]
29
Set Identities
• Example: Show A(B - A) = Ø
The void set is a subset of every set. Hence,
A (B - A)  Ø
Therefore, it suffices to show
A(B - A) Ø
or
x[x A (B - A) → x  Ø]
30
P. 1
Set Identities
So as before we say 'let x be arbitrary’.
Show x  A  (B- A) → x  Ø is a tautology.
But the consequent is always false.
Therefore, the antecedent better always be
false also.
31
Set Identities
• Solution:
Apply the definitions:
Assertion
x A(B- A)x  A Λ x  (B- A)
 x  A Λ (x  B Λ x A)
(x  A Λ x  A) Λ x  B
0ΛxB
 0 (false)
Reason
by Def. of 
by Def. of by Def. of Associative
by Def. of Complement
by Def. of Domination
32
P. 1
Union and Intersection of Indexed Collections
• Let A1,A2 ,..., An be an indexed collection of
sets.
• Definition: The union of a collection of sets is
the set that contains those elements that are
members of at least one set in the collection.
we use the notation
n

i 1
Ai  A1  A2  ...  An
to denote the union of the sets A1,A2 ,..., An
33
P. 1
Union and Intersection of Indexed Collections
• Definition: The intersection of a collection of sets is
the set that contains those elements that are
members of all the set in the collection.
we use the notation
n

i 1
Ai  A1  A2  ...  An
to denote the intersection of the sets A1,A2 ,..., An
34
Union and Intersection of Indexed Collections
• Examples:
• Let
Ai  [i, ),1  i  
n

Ai  [1, )
n
Ai  [n, )
i 1

i 1
35
P. 1
Terms
•
•
•
•
•
•
Boolean Algebra
Set operations
Union
Intersection
Complement
Difference
•
•
•
•
•
Symmetric difference
Venn Diagram
Set Identities
Universal Instantiation
Universal Generalization
36
P. 1
2.1 Sets
2.2 Set Operations
2.3 Functions
‒ Functions
‒ Injections, Surjections and Bijections
‒ Inverse Functions
‒ Composition
2.4 Sequences and Summations
37
P. 1
Functions
• Definition: Let A and B be sets. A function
(mapping, map) f from A to B, denoted
f :A→ B, is a subset of A×B such that
x[ x  A  y[ y  B   x, y  f ]]
and
[ x, y1  f   x, y2  f ]  y1  y2
38
P. 1
Functions
• Note: f associates with each x in A one and only
one y in B.
– A is called the domain
– B is called the codomain.
• If f(x) = y
– y is called the image of x under f
– x is called a preimage of y
• (note there may be more than one preimage of y
but there is only one image of x).
39
P. 1
Functions
• The range of f is the set of all images of
points in A under f. We denote it by f(A).
• If S is a subset of A then f(S) = {f(s) | s in S}.
• Q: What is the difference between range
and codomain?
40
P. 1
Functions
• Example:
1.
2.
3.
4.
5.
6.
7.
f(a) =
the image of d is
the domain of f is
the codomain is
f(A) =
the preimage of Y is
the preimages of Z
are
8. f({c,d}) =
Z
Z
A = {a, b, c, d}
B = {X, Y, Z}
{Y, Z}
b
a, c ,d
{Z}
41
P. 1
Injections, Surjections and Bijections
• Let f be a function from A to B.
• Definition: f is one-to-one (denoted 1-1) or
injective if preimages are unique.
Note: this means that if a  b then f(a)  f(b).
• Definition: f is onto or surjective if every y in B has
a preimage.
Note: this means that for every y in B there must
be an x in A such that f(x) = y.
• Definition: f is bijective if it is surjective and
injective (one-to-one and onto).
42
P. 1
Injections, Surjections and Bijections
• Examples: The previous Example function is
neither an injection nor a surjection. Hence
it is not a bijection.
43
P. 1
Injections, Surjections and Bijections
• Note: Whenever there is a bijection from A to B,
the two sets must have the same number of
elements or the same cardinality.
• That will become our definition, especially for
infinite sets.
44
P. 1
Injections, Surjections and Bijections
• Examples:
Let A = B = R, the reals. Determine which
are injections, surjections, bijections:
1.
2.
3.
4.
5.
f(x) = x,
f(x) = x2,
f(x) = x3,
f(x) = | x |,
f(x) = x + sin(x)
45
P. 1
Injections, Surjections and Bijections
• Let E be the set of even integers {0, 2, 4, 6, . . . .}.
• Then there is a bijection f from N to E , the even
nonnegative integers, defined by f(x) = 2x.
• Hence, the set of even integers has the same
cardinality as the set of natural numbers.
• OH, NO! IT CAN’T BE....E IS ONLY HALF AS BIG!!!
• Sorry! It gets worse before it gets better.
（見山是山，見水是水前，會先見山不是山，見
水不是水）
46
P. 1
Inverse Functions
• Definition: Let f be a bijection from A to B.
Then the inverse of f, denoted f-1, is the
function from B to A defined as
f-1(y) = x iff f(x) = y
47
P. 1
Inverse Functions
• Example: Let f be defined by the diagram:
• Note: No inverse exists unless f is a bijection.
48
P. 1
Inverse Functions
• Definition: Let S be a subset of B.
Then f-1(S) = {x | f(x)  S}
• Note: f need not be a bijection for this
definition to hold.
49
P. 1
Inverse Functions
• Example: Let f be the
following function:
f-1({Z}) =
f-1({X, Y}) =
{c, d}
{a, b}
50
P. 1
Composition
• Definition: Let f: B→C, g: A → B. The
composition of f with g, denoted f  g, is the
function from A to C defined by
f  g(x) = f(g(x))
51
P. 1
Composition
• Examples:
• If f(x) =x 2 and g(x) = 2x + 1, then
f(g(x)) =(2 x  1) 2 and g(f(x)) = 2x 2 + 1
52
P. 1
Floor and Ceiling
• Definition: The floor function, denoted f (x)
= x or f(x) = floor(x), is the largest integer
less than or equal to x.
• The ceiling function, denoted f (x) = x or
f(x) = ceiling(x), is the smallest integer
greater than or equal to x.
• Examples: 3.5 = 3, 3.5 = 4.
• Note: the floor function is equivalent to
truncation for positive numbers.
53
P. 1
Composition
• Example:
Suppose f: B→C, g: A→B and fg is injective.
• What can we say about f and g?
– We know that if a  b then f(g(a))  f(g(b)) since the
composition is injective.
– Since f is a function, it cannot be the case that g(a)= g(b)
since then f would have two different images for the
same point.
– Hence, g(a)  g(b)
– It follows that g must be an injection.
– However, f need not be an injection (you show).
54
P. 1
Terms
•
•
•
•
•
Function
Image
Preimage
Range
Injective (one-toone)
• Surjective
• Bijective
•
•
•
•
•
Cardinality
Inverse function
Composition
Floor function
Ceiling function
55
P. 1
2.1
2.2
2.3
2.4
‒
‒
‒
‒
‒
Sets
Set Operations
Functions
Sequences and Summations
Sequences and Summations
Summation Notation
Cardinality
Some Countably Infinite Sets
Cantor Diagonalization
P. 1
Sequences and Summations
• Definition: A sequence is a function from a
subset of the natural numbers (usually of
the form {0, 1, 2, . . . } to a set S.
• Note: the sets {0, 1, 2, 3, . . . , k} and {1, 2,
3, 4, . . . , k} are called initial segments of
N.
P. 1
Sequences and Summations
• Notation: if f is a function from {0, 1, 2, . . .}
to S we usually denote f(i) by ai and we
k
k
{
a
,
a
,
a
,
a
,...}

{
a
}

{
a
}
write
0
1
2
3
i i 0
i 0
where k is the upper limit (usually ∞).
P. 1
Sequences and Summations
• Examples:
Using zero-origin indexing, if f(i) = 1/(i + 1).
then the sequence f = {1, 1/2 ,
1/3 ,1/4, . . . } = {a0, a1, a2, a3, . . }
Using one-origin indexing the sequence f
becomes {1/2, 1/3, . . .} = {a1, a2, a3, . . .}
P. 1
Summation Notation
k
{
a
}
• Given a sequence i 0 we can add together
a subset of the sequence by using the
summation and function notation
n
ag ( m)  ag ( m1)  ...  ag ( n )   ag ( j )
j m
or more generally
a
jS
j
P. 1
Summation Notation
• Examples:
n
r  r  r  r  ...  r   r j
0
1
2
3
n
0
• If S = {2, 5, 7, 10} then
a
jS

1 1 1
1
1     ...  
2 3 4
1 i
n
a2m  a2( m1)  ...  a2( n)   a2 j
j m
j
 a2  a5  a7  a10
• Similarly for the product
notation:
n
a
j
 am am 1...an
j m
P. 1
Summation Notation
• Definition: A geometric progression is a sequence
2
3
4
a
,
ar
,
ar
,
ar
,
ar
,....
of the form
• Your book has a proof that
n 1
n
r
1
i
r 
if r  1

r 1
i 0
(you can figure out what it is if r = 1).
• You should also be able to determine the sum
– if the index starts at k vs. 0
– if the index ends at something other than n (e.g., n-1,
n+1, etc.).
P. 1
Cardinality
• Definition: The cardinality of a set A is equal to
the cardinality of a set B, denoted |A| = |B|, if
there exists a bijection from A to B.
• Definition: If a set has the same cardinality as a
subset of the natural numbers N, then the set is
called countable.
If |A| = |N|, the set A is countably infinite.
The (transfinite) cardinal number of the set N is
aleph null = ‫ﭏ‬0.
If a set is not countable we say it is uncountable.
P. 1
Cardinality
• Examples:
The following sets are uncountable (we show
later)
– The real numbers in [0, 1]
– P(N), the power set of N
• Note: With infinite sets proper subsets can have
the same cardinality. This cannot happen with
finite sets.
• Countability carries with it the implication that
there is a listing of the elements of the set.
P. 1
Cardinality
• Definition: | A | ≤ | B | if there is an injection from A to B.
Note: as you would hope.
• Theorem: If | A | ≤ | B | and | B | ≤ | A | then | A | = | B |.
This implies
– if there is an injection from A to B
– if there is an injection from B to A then
– there must be a bijection from A to B
• This is difficult to prove but is an example of demonstrating
existence without construction.
• It is often easier to build the injections and then conclude
the bijection exists.
P. 1
Cardinality
• Example:
Theorem: If A is a subset of B then | A | ≤ | B |
Proof: the function f(x) = x is an injection from A to B.
• Example: | {0, 2, 5} | ≤ ‫ﭏ‬0
The injection f: {0, 2, 5} →N defined by f(x) = x is
shown below:
Some Countably Infinite Sets
• The set of even positive integers E ( 0 is considered
even) is countably infinite. Note that E is a proper
subset of N!
• Proof: Let f(x) = 2x. Then f is a bijection from N to E
• Z+, the set of positive integers is countably infinite.
P. 1
Some Countably Infinite Sets
• The set of positive rational numbers Q+ is countably
infinite.
The position on the path (listing) indicates the image
of the bijective function f from N to QR:
• f(0) = 1/1, f(1) = 1/2, f(2) =
2/1, f(3) = 3/1, and so forth.
• Every rational number
appears on the list at least
once, some many times
(repetitions).
• Hence, | N | = | QR | = ‫ﭏ‬0.
• Q. E. D.
• The set of all rational numbers Q, positive and negative, is
countably infinite.
P. 1
Some Countably Infinite Sets
• The set of (finite length) strings S over a finite
alphabet A is countably infinite.
• To show this we assume that
- A is nonvoid
- There is an “alphabetical” ordering of the symbols in A
• Proof: List the strings in lexicographic order:
– all the strings of zero length,
– then all the strings of length 1 in alphabetical order,
– then all the strings of length 2 in alphabetical order, etc.
• This implies a bijection from N to the list of strings
and hence it is a countably infinite set.
P. 1
Some Countably Infinite Sets
• For example: Let A = {a, b, c}.
Then the lexicographic ordering of A is
{ , a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc,
aaa, aab, aac, aba, ....}
={f(0), f(1), f(2), f(3), f(4), . . . .}
P. 1
Some Countably Infinite Sets
• The set of all C programs is countable .
• Proof: Let S be the set of legitimate characters which can
appear in a C program.
– A C compiler will determine if an input program is a
syntactically correct C program (the program doesn't
have to do anything useful).
– Use the lexicographic ordering of S and feed the strings
into the compiler.
– If the compiler says YES, this is a syntactically correct C
program, we add the program to the list.
– Else we move on to the next string.
In this way we construct a list or an implied bijection from
N to the set of C programs. Hence, the set of C programs is
countable.
Q. E. D.
P. 1
Cantor Diagonalization
• An important technique used to construct an object which is
not a member of a countable set of objects with (possibly)
infinite descriptions.
• Theorem: The set of real numbers between 0 and 1 is
uncountable.
• Proof: We assume that it is countable and derive a
contradiction.
If it is countable we can list them (i.e., there is a bijection from
a subset of N to the set).
We show that no matter what list you produce we can
construct a real number between 0 and 1 which is not in the list.
Hence, there cannot exist a list and therefore the set is not
countable
P. 1
Cantor Diagonalization
It's actually much bigger than countable. It is said to
have the cardinality of the continuum, c.
• Represent each real number • THE LIST....
in the list using its decimal
r1 = .d11d12d13d14d15d16. . . . .
expansion.
e.g., 1/3 = .3333333........
r2 = .d21d22d23d24d25d26 . . . .
1/2 = .5000000........
r3 = .d31d32d33d34d35d36 . . . .
= .4999999........
If there is more than one
expansion for a number, it
doesn't matter as long as
our construction takes this
into account.
P. 1
Cantor Diagonalization
• Now construct the number
x = .x1x2x3x4x5x6x7. . . .
xi = 3 if dii  3
xi = 4 if dii = 3
Then x is not equal to any number in the list.
Hence, no such list can exist and hence the interval
(0,1) is uncountable.
Q. E. D.
P. 1
Terms
•
•
•
•
•
•
•
•
•
Sequence
Summation
Cardinality
Zero-origin indexing
One-origin indexing
Geometric progression
Countable infinite
Uncountable
Cantor diagonalization
•
•
•
•
•
•
•
•
•
Sequence
Summation
Cardinality
Zero-origin indexing
One-origin indexing
Geometric progression
Countable infinite
Uncountable
Cantor diagonalization
P. 1