Transcript a, b, c

Overview of
Sets an Functions
for ICS 6D
Prof. Sandy Irani
Sets
• A set is an unordered collection of items.
• For example, S = {a, b, c, d}
• Curly braces {} denote that order does not matter:
{a, b, c, d} = {b, a, d, c}
• Each item is called an element of the set.
b is an element of S (b ∈ S)
e is not an element of S (e ∉ S)
Cardinality of Sets
• An infinite set has an infinite number of
elements.
Example: the set of all integers.
• A finite set has a finite number of elements.
Example: the set of students enrolled in ICS 6D Spr 2016.
• If S is a finite set, then the cardinality of S
(denoted |S|) is the number of elements in S.
Example: S = {a, b, c, d}. |S| =
Famous Sets
• ℤ = the set of all integers
• ℝ = the set of real numbers
• ℚ = the set of rational numbers
(A number x is rational if x = c/d, where c and d are
integers and d ≠ 0.)
• ℕ = natural numbers (positive integers)
•  the empty set (sometimes denoted as {})
Specifying a Set
• Roster notation:
– List the elements with curly braces
{1, 3, 5, 9}
– List elements with an inferred pattern in ellipses
{1, 3, 5, …., 99}
• Set builder notation
{x : x ∈ S and some additional conditions on x}
{x ∈ S : additional conditions on x}
• S is a larger set that has already been defined
• “:” is read as “such that”
Subsets
• T is a subset of S (T ⊆ S):
If x ∈ T then x ∈ S
• To show T ⊈ S,
Find x ∈ T and x ∉ S.
• Example:
• S = {a, b, c, d}
• T = {a, b, c}
• V = {a, e}
Set Operations
Union:
x∈A∪B ↔ x∈A∨x∈B
Intersection:
x∈A∩B ↔ x∈A∧x∈B
Complement:
x ∈ A ↔ (x ∈ A)
(all elements and sets contained in a
Universe set, usually denoted by U)
Set Operations Example
A = { x ∈ ℤ : x is odd }
U=ℤ
B = { x ∈ ℤ : 0 < x 20 }
C = {4, 5, 6, 7}
A∩B
C∩A
C ⊆ B?
B ⊆ A?
6 ∈ A∪C?
26 ∈ A ∪ C ?
Power Set
Let A be a finite set. Power set of A (denoted P(A))
is the set of all subsets of A.
Example: A = {a, b, c}
P(A) = { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }
•
•
•
•
{a, b} ∈ P(A) ?
{a, b} ⊆ P(A) ?
a ∈ P(A) ?
{a} ∈ P(A) ?
• { {a} } ⊆ P(A) ?
• Ø ⊆ P(A) ?
• Ø ∈ P(A) ?
Pairs, Triplets and Tuples
• (a, b) is an ordered pair.
– Parens (as opposed to {}) indicate that order matters:
• (a, b) ≠ (b, a)
• {a, b} = {b, a}
• (a, b, c) is an ordered triplet
– b is the second entry of the triplet (a, b, c)
• (a, b, c, d) is an ordered 4-tuple
• (a1, a2 , …, an) is an ordered n-tuple.
Cartesian Product
• Let S and T be sets
Cartesian product of S and T is
S x T = { (s, t) : s ∈ S and t ∈ T }
• Example: S = {a, b, c} T = {1, 2}
– S x T = { (a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2) }
Cartesian Product
• T = {1, 2}
T x T = T2 = { (1, 1), (1, 2), (2, 1), (2, 2) }
T ⊆ T2 ?
• What is ℝ x ℝ?
ℤ x ℤ?
Cartesian Product
Example: Drink = {OJ, Coffee}
Main = {Waffles, Eggs, Pancakes}
Side = {Hash browns, Toast}
• Breakfast Selections = Drink x Main x Side
– (OJ, Eggs, Toast) ∈ Drink x Main x Side
• A1, …, An sets:
A1x … x An = { (a1, …, an) : ai in Ai for 1 ≤ i ≤ n }
Cartesian Product
Let S be a set:
Sn = S x S x … x S = { (s1, .., sn) : each si in S, for 1 ≤ i ≤ n }
• Example: {0, 1}5
• Example: ℝ4
N-tuples and Strings
• If  is a set of single characters, elements in n can be
denoted without the punctuation, in which case they are
called strings.
Example:  = {a, b}
• (a, b, a, b) ∈ 4 (denoted as an n-tuple)
• abab ∈ 4
(denoted as a string)
• {0, 1}3 = set of all binary strings with 3 bits:
– {0, 1}3 = { 000, 001, 010, 011, 100, 101, 110, 111 }
• n-tuple punctuation is important if the underlying set is not a
set of single characters!
Strings
• Concatenation:
x = abba y = bab
Concatenation of x and y is xy = abbabab
Concatenation of x and a is abbaa
• Empty string  has no characters:
– x  = x = x
• The length of a string x (denoted by |x|) is the number of
characters in the string:
Example: |abba| = 4.
Infinite sets of strings
• The set of all strings of any length over an alphabet :
* = 0 ∪ 1 ∪ 2 ∪ …..
Example: {0, 1}* = {, 0, 1, 00, 01, 10, 11, 000,….}
• The set of all strings of any length over an alphabet :
+ = 1 ∪ 2 ∪ 3 ∪ …..
Example: {0, 1}+ = {0, 1, 00, 01, 10, 11, 000,….}
Functions
• A function maps elements of one set onto another:
f: A → B
a
b
c
d
1
A is the domain
A = {a, b, c, d}
B is the target
B = {1, 2, 3, 4, 5}
2
3
4
5
A function maps each element
of the domain to a unique
element in the target set.
Functions
• A function maps elements of one set onto another:
f: A → B
a
b
c
d
1
A is the domain
A = {a, b, c, d}
B is the target
B = {1, 2, 3, 4, 5}
2
3
4
5
The range is the set of elements
y in the target for which there is
an element x in the domain such
that f(x) = y.
Functions on ℝ specified by
an explicit formula
• f: ℝ → ℝ
– f(x) = x2 - 4x + 3
• Examples of non-functions:
– f(x) = ±√x
– f(x) = 2/x
Functions: one-to-one
• A function f: D → T is one-to-one if no two elements in the
domain map on to the same element in the target:
∀ x ∈ D, x’ ∈ D, (x ≠ x’) → f(x) ≠ f(x’)
a
b
c
d
1
a
2
b
3
c
4
5
d
1
2
3
4
5
One-to-one Examples
• f: ℝ → ℝ
f(x) = x2
• f: ℤ → ℤ
f(x) = 2x + 3
• f: {0, 1}3 → {0, 1}3 replace the last bit with 0, f(111) = 110
• f: {0, 1}3 → {0, 1}4 add a 0 to the end f(101) = 1010
• A = {a, b, c}
f: P(A) → ℤ. For X ⊆ A, f(X) = |X|
One-to-one examples
• f: {0, 1}3 → {0, 1}2
drop the last bit
f(101) = 10
If f: D → T is
one-to-one,
then |D| ≤ |T|
If f: D → T and
|D| > |T|
The f can not be
one-to-one.
000
001
00
010
01
011
10
100
11
101
110
111
Functions: onto
• A function f: D → T is onto if every element in the target is
mapped to by some element in the domain
For every y ∈ T, there is an x ∈ D, such that f(x) = y
a
1
a
1
b
2
b
2
c
3
c
3
d
d
Onto Examples
• f: ℝ → ℝ
f(x) = x2
• f: ℤ → ℤ
f(x) = 2x + 3
• f: ℤ → ℤ
f(x) = 2x + 3
• f: {0, 1}3 → {0, 1}3 replace the last bit with 0, f(111) = 110
• f: {0, 1}3 → {0, 1}2 drop the last bit f(101) = 10
• f: {0, 1}3 → {0, 1}3 remove the last bit and concatenate it at the beginning
of the string:
f(101) = 110
f(100) = 010
Onto Examples
Example f: {0, 1}2 → {0, 1}3
add a 0 to the end f(10) = 100
If f:D →T is
onto,
then |T| ≤ |D|
000
00
001
01
010
10
011
11
100
101
If f:D →T and
|T| > |D|
The f can not be
onto.
110
111
Bijections
Definition:
A function f:D→T is a
bijection if it is
one-to-one and onto
If f:D→T and
f is a bijection, then
|D| = |T|
a
1
b
2
c
3
d
4
Inverse of a function
f: D → T
The inverse of f (if it exists) is a function f-1: T → D
For every x ∈ D and y ∈ T, f(x) = y ↔ f-1(y) = x
a
1
1
a
b
2
2
b
c
3
3
c
d
4
4
d
f
f-1
A function f is a
bijection if and only if
f has an inverse
Inverse of a function example
A string is a palindrome if it is the same after it is reversed.
Let P6 be the set of all 6-bit strings that are also palindromes.
Bijection between {0, 1}3 and P6
f: {0, 1}3 → P6 f(x) = xxR
(xR is the reverse of x)