ECS 20 — Lecture 10 — Fall 2013 —29 Oct 2013
Phil Rogaway
Today:
Reminder: MT on Thursday
Relations
Recall:
DEF: With A and B sets, a relation R is subset of A B.
o Relations
o Functions
o Comparing the size of infinite sets
R A B
Usually we prefer to write things in infix notation:
x R y
for (x,y) R ~ or <
Often we use symbols, rather than letters, for relations: eg,
x~y if (x,y) ~
Here are some common relations from arithmetic, where A=B are the set of natural number (or the
set of reals):
Another important one for integers: | divides
What about our friends: succ, +, * ?
NO, these are function symbols, not relations
In set theory we have the relation symbol
What about ?
NO, it’s a constant symbol
More examples:
Often X = Y is the same set
Relations on natural numbers, real numbers, strings, etc.
1. X = integers,
2. X = set of strings over some alphabet; x y if is a substring of y
1
3. X = set of lines in the plane; x~y if they are parallel
4. and are regular expressions; ~ if L( ) = L( )
5. x and y are strings of the same length
6. a and b are numbers and n>0 is a number and a Rn b if n | (a-b) ***
7. a and b are real numbers and a~b if a =b.
Equivalence relations – Are relations on X X that enjoy three properties
Reflexive: x R x
Symmetric: x R y y R x Transitive: x R y and y R z x R z
Equivalence classes, quotients
for all x
for all x,y for all x, y, z
If R is an equivalence relation on A x A then [x] denotes the setof all elements related to x:
[x] = {a: aRx}
We call [x] the equivalence class (or block) of x.
The set of all equivalence classes of A with respect to a relation R is denoted A/R , which is read “the quotient set of A by R”, or “A mod R”.
I claim that every equivalence relation on a set partitions it into its blocks. What does this mean?
Define a partitioning of the set A:
Def: {Ai: i I } is a partition of A if each Ai is nonempty set and (1) their union is A, A = Ai, but (2)
their pairwise intersection is empty, Ai Aj = for all ij. Proposition: Let R be an equivalence relation on a set A.
Then the blocks of R are a partition of A.
Proof: -Every element x of A is in the claimed partition: x [x], so the union of blocks covers A. -Suppose that [x] and [y] intersect. I need to argue that they are identical. So suppose there
exists a s.t. a [x] and a [y]. I must show that [x] = [y]. Let b [x]; must show b [y]. So given: aRx (so xRa) aRy thus xRy, yRx
bRx (so xRb)
thus yRb (or bRy).
The relation between equivalence relations and partitions goes both ways: Given a partition {Ai: i I } of a set A,
define a relation R by asserting that x R y iff x and y are in the same block of the partition: there exists and i such that x Ai and y Ai. Then R is an equivalence relation [prove this].
2
Notation: A/R the blocks of A relative to equivalence relation R.
Note: you can talk about the blocks being related to one another by R, that is, [x] R [y] iff x R y.
This is well-defined.
The circles are the points in the base set A. Two points are in the same block if they are related to one another under the equivalence relation.
Now go back to prior examples and identify the blocks in each case.
Eg: strings x and y are equivalent if they have the same length: blocks [], [a], [aa], … Here, using a nice canonical name for each block
Another example: Consider the tiles we spoke of earlier partition the plane (upper right quadrant) if you’re careful at the edges of each tile to make sure that each point is in only one tile. We defined
[a, b) = {x R: a x b)
So a tile with left endpoint at (i , j) is [i, i+1) [j, j+1) and the plane is the disjoint union of tiles
Tij = [i, i+1) x [j, j+1) when i,j N}
An important example in formal-language theory. Let L be a language and define from it the
relation RL by saying that x RL y if for all z, xzL iff yzL. Example: Figure out the blocks when L = { x{a,b}*: |x| is even}
Even-length strings
Odd-length strings
Example: Figure out the blocks when L = { x{a,b}*: x starts with ‘aba’}
aba ab
a
b
b
3
Theorem [Myhill-Nerode]: A language L is regular [you can represent it with a regular expression] iff L/ RL has a finite number of blocks.
Back to: a and b are numbers and n>0 is a number and a Rn b if n | (a-b) *** Key example in computer science and mathematics.
“Ring of integers modulo n.”
Many ways to understand this “thing”.
Ring of integers modulo n, Zn
Z/Rn More common notation Z/nZ
Lots of variant notations
a = b
ab
ab
a mod n = b mod n (now ‘mod’ is a binary operator)
(a and b are point in Zn)
(a and b are congruent mod n)
(mod n)
Functions
Definition: A function f is a relation on A B such that there is one and only one (a, b) R for every in aA.
When f is a function, we write b = f(a) to mean that (a,b) f. -WecallAthedomainoff, Dom(f).
– We call B the codomain (or target) of f. Sometimes the codomain is called the range.
More common, however, is that that the range of f is the set {bB: f(a)=b for some a in A} = f(A) = aA {f(a)}
Also called the image of A under f.
Example 1:
Domain={1,2,3}
f(a) = a^2.
Dom(f) = {1,2,3}
f(A) = {1,4,9}
co-domain: unclear, might be N, might be R, ….
Example 2:
Domain = students in this class, regarded as(month, day) pairs. b(x) = birthdays, encoded as {1,..,12} x {1..31}.
4
b(phil) = (7,31) b(ellen) = (4,1)
Example 3:
f: R R defined by f(x) = x^2
I see lots of “ad hoc” notation. Don’t.
f: A B. f(a) = b. If you’re writing crazy things f(x=a): b I’m likely to give no credit. It’s like answering in a language you haven’t learned to speak when the first requirement of communicating is to be able to speak the language.
Sometimes you might want to show that f takes x to y, a to 2a, etc. Don’t use a symbol for that; write x y, a 2a. With surrounding English, this reads ok. But saying a 2a definitely does not.
One-to-one and onto functions
Def: f: A B is injective (or one-to-one) if f(x)=f(y) x=y “no collisions” Def: f: A B is surjective (or onto) if ( b B) (a A) f(a)=b
“the codomain is the range (image is the domain)
Def: f: A is bijective if is injective and surjective (one-to-one and onto).
Example:
f(n)=x2
ask if it’s 1-1 and onto if the domain/co-domain is Z, N Sometimes it can be tricky to see if a function is 1-1, onto:
f(x) = 3x mod 90 bijective
f(x) = 3x mod 91 not bijective
Inverse of a function
If f(x) = y we say that x is a preimage of y
Does every point in the codomain have a preimage?
No, only points in the image.
Does every point in the image have one preimage?
No, only if it’s an injective function
Does every point the in the domain have an image?
Yes, that’s required for being a function. Might it have two images?
No, only one.
If you do have a bijective function f: A B then the function f 1: B A is well defined:
5
f 1(y) = the unique x such that f(x) = y.
Example: f(x) = exp(x) = ex
Draw picture.
What’s the domain? R
What’s the range / image ? (0,) Is it 1-1 on this image? YES
What’s it’s inverse? y ln(y)
6