Transcript sets

SETS
A set B is a collection of objects such that for
every object X in the universe the statement:
“X is a member of B”
Is a proposition.
A quick review of basic notation and
set operations.
1. A = {1, 2, ab, ba, 3, moshe, table},
2.1,2, ab, ba, moshe table are “elements.” They
are members of the set A or “belong” to A.
Notation: ab  A
aA
3. V = {a, i, o, u, e} Set of Vowels
O = {1,3,5,7,9} Odd numbers < 10.
4. A1 = {2, 5, 8, 11, …, 101}
A2 = {1, 2, 3, 5, 8, 13,…}
A3 = {2, 5, 10, 17, 26, …, 101}
Basic notation.
1. Set Builder: B = {x | P(x)}
B1 = {x | x = n2 + 1, 1  n  10} (B1 = A3)
B2 = {p | p prime, p = n! + 1, n 

Special sets:
N (non-negative integers, natural numbers)

Q (rational numbers)

Z (integers)

Z+ (positive integers)

R (real numbers)

 (the empty set)
Relations among sets
1. A = B: if x  A  x  B
2. Subsets: A  B
AB A B
AB
3. For every set B:   B
4. A set may have other sets as members:
A = {, {a}, {b}, {a,b}}. Note: A has 4
elements.   A and also   A, {{a}}  A,
a  A, {a}  A.
Set operations
Union: A  B = {x | x  A  x  B} (logic “or”)
Intersection: A  B = {x | x  A  x  B} ( “and”)
Set difference: A \ B = {x | x  A  x  B}
Complement of A: A = {a | a  A} or if U is the
“universe” then A = U \ A (“not”).
Example: If U = {a,b,c,…,z} and A = {i,o,e,u,a}
then A = {n | n is not a vowel}.
Symmetric difference: A  B = (A \ B)  (B \ A)
(“xor”)
The characteristic vector of a set (representing
sets in memory):
Let U = {1,2,…, 15}. Let A = { 3,5,11,13} the
characteristic vector of A is the binary string
00101 00000 10100.
The characteristic vector 10010 01101 10001
represents the set {1,4,7,8,10,11,15}.
00000 00000 00000 represents .
Note: with this representation the union of two
sets is the OR bit operation and the intersection
is the AND.
A simple application.
Problem: find the smallest integer n that satisfies
the following 3 conditions simultaneously:
(n mod 7 = 5), (n mod 11 = 7), (n mod 17 = 9)
Knowing the language “Math” can help us look for
information and use various systems to solve
this problem. The following exolains how to use
SAGE's set operations to solve problems.
We can create three sets:
1.
A = {k | k = 7n + 5, k < 4000}
2.
B = {k | k = 11n + 7, k < 4000}
3.
C = {k | k = 17n + 9, k < 4000}
We can then ask SAGE to find the
intersection of the three sets. The smallest
integer in the intersection (provided there is
one) will be our solution.
Answer: {502, 1811, 3120, ...}
Venn Diagrams
Venn Diagrams : a useful tool for representing
information. For instance, the various sets that
can be formed by the basic set operations can
be viewed by a Venn Diagram.
A
B
C
Proving set equalities:
Either: x  A  x  B or
A  B  B  A.
Example: De Morgan’s law: A  B = A  B
Proof: Let x A  B.
Then: x  A  B.
Or: x  A and x  B
Or: x  A and x  B
Or: x  A B
Conversely, start from the bottom and go up.
QED
Notation:
A1  A2  …  An = {x | x  Ai i = 1, 2, … , n}.
A1  A2  …  An = {x |  ( i, 1i  n) x  Ai.
Use formula to insert intersection.
Assume M = {1,2,5,9} then
= A1  A2  A5  A9
The Power Set
Definition: The Power set of the set A is:
P(A) = {B | B  A}.
has 0 elements. P() has one element:
P() = {}
A = {a} P(A) = {, {a}} P({}) = {, {}}
The cartesian product
Cartesian product :
A x B = {(a,b) | a  A  b  B}
Can be defined using sets only:
A x B = {{a}, {a,b}| a  A  b  B}
Note: (a,b)  (b,a) if a  b.
Cartesian product of n sets: A1x A2 x … x An =
{(a1, a2,…, an) | ai  Ai, i = 1,…,n}
Relations
Definition 1: A relation R, (binary relation)
between two sets A and B is a subset of
A x B (mathematically speaking: R  A x B).
Definition 2: A relation R on a set A is a subset
of A x A.
Relations
There are two common ways to describe
relations on a set or between two sets:
List all pairs belonging to the relation.
Use set builders to describe the pairs.
Example 1: R0 = {(4,3), (9,2), (3,6), (7,5)} is a
relation on N. It is also a relation on A x B
where A = {4,9,3,7} and B = {3,2,6,5}
More examples
Example 2: R2 = {(n,k) | n  N and n + k is a
prime number}.
Example 3: R3 = {(n,k) | n,k  N and |n – k| is a
multiple of 19}.
Example 4: R3 = {(w,m) | w is a woman, m is a
man, w dates m}
Classification of relations
These definitions apply to relations on A.
Definition 3: A relation R on A is reflexive
if (a,a)  R a  A.
Definition 4: A relation R on A is symmetric
if (a,b)  R then (b,a)  R.
R is antisymmetric
if (a,b)  R and (b,a)  R only if a = b.
Definition 5: A relation R on a set A is
transitive
if (a,b)  R  (b,c)  R then (a,c)  R.
The transitive closure
Observation: If R1 and R2 are transitive
relations on a set A then so is R1  R2.
Proof: Obvious.
Definition 6: The transitive closure of a relation
R on a set A is the “smallest” transitive
relation R* on A such that R*  R.
I think I solved it!