mathdos

mathdos

Tue 03/06/07

10 bej,

11 abcd, 12, 13abcd, 14, 16

20 ef

double check.

R = {(y,x): (x,y) in R}

R in A cross B

R in B cross A, R^-1 relation from B to A

R in A cross B

S in B cross C

then S composition R in A cross C

S composition R = {

there exists a y in B such that (x, y) belongs to r and (y, z) belongs to S

iff (x,z) belongs to S composed with R

lets look at

T composed with S.

S = {(2,4), (3,4), (3,1), (5,5)}

T = {(1,4), (3,5), (4,1)}

start with S and apply T second.

T composed with S = {(2,1), (3,1), (3,4)}

look for connectors

S first, then T .. just like composition of functions.

Number 2.

go two ways

(==>)

assumption that A cross B = B cross A implies A = B

subcase 1. show a is a subset of B.

Let x belong to A.

Sinc B ≠ empty, there exists a y in B such that (x,y) is in A cross B.

therefore (x,y) is in B cross A.

.. so X belongs to B .. so we have subset inclusion that way.

now the other way

(<===)

assume A = B

then A cross B = B cross A.

going one way

Let (x,y) in A cross B. Therefore, x is in A and y is in B.

Since we know that A = B, x in B and y in B

thus, (x,y) is in B cross A.

then go the other directio for this too.

6 g

x,y belongs to W iff |x| <2 or y = 3

1. graph all the points where |x| <2 -- all points (-2,2)

domain .. all x's -- we have at least one y value fro every x.

range ... all y's

Theorem 3.2 b.

Domain of Inverse of R = range of R.

proof .. string of iffs.

Let y in B

y belongs to R iff

thee exists x in A such y,x belongs to R

iff there exists x in a(x,y) is in R)

//y belongs to range

iff y is in the Range of R

so we've strung together the statements.

therefore, the domain of R = range of R.

Theorem 3.3d

R is a relation from A to B

and S is a relation from B to C.

Then (S compositon R) = R composition S

prove this.

Let (z,x) //we'll use that because we're going C to A.

be arbitrary.

Then (z,x) is in (S comp. R) iff

(x,z) is in S comp. R

iff (there exists y in B)((x,y) is in R and (y,z) is in S)

iff (there exists y)((y,x) belongs to R and (z,y) belongs to S)

iff (z,x) belongs to R composed with S

Therefore (S comp. R) = R comp S

another way to represent a relation

Suppose A = {1,2,3}

A cross A -- (1,2) ...

die graph - plot the elements and then draw arrows between the order pairs.

1,1 loops back to itself.

Thu 03/08/07

A = {1,2,3}

Relation = {(1,3), (2,3) ... a subset of A cross A.

in a good diagraph, plot all the points in A.

11 e)

A = {1,2,3}

R = {everything but (1,1), (2,2), (3,3)}

13 a)

use official difinitions.

show Dom(S comp. R) subset Dom(R)

if x is in Dom(R), there exists (x,y) in R

but we have to have an arrow from b to c

Proof

-----

subset inclusion proof

Let x be in Dom(S comp R)

then there exists a z element of C such that (x,z) belongs to S comp R

... there had to be a y in B such that (x,y) is in R and y,z is in x

... therefore x is in the Dom(R)

equivalence relation

Start with A

R is a equivalence relation on A iff

1) reflexivity -- for every element in x(x R x) every x in a has to have x,x in the relation. (x,x) in R.

2) symetry - take any two elements in A x and y .. and you notice that (x,y) in R.

then it must also be true that y R x .

3) transitivity - (for every x in A)(for every y in A)(for every z in A) (xRy and yRz => xRz)

A = integers

xRy <=> x-y in even

claim: R is an equivalence relation.

prove three things.

(1) reflexivity (the tricky one .. we get no assumptions)

Let x be an element of Z. (probably should be A)

Then x-x = 0, which is even. Therefore xRx

(2) symetry

- Let x and y be in Z and assume xRy

Then x-y is even.

So x-y= 2k for some k in Z.

Then y-x = -(2k) = 2(-k) and -k is in Z. Therefore y-x is even.

therefore, yRx

(3) transitivity -

Let x,y,z be in Z.

Assume xRy and yRz.

Then x-y is even and y-z is even.

So x-y = 2k[1] and y-z = 2k[2]

where k[1] and k[2] in Z.

So x-z = (x-y) + (y-z) = 2k[1] + 2k[2] = 2(k[1] + k[2])

and k[1] + k[2] in Z

So x-z is even. Therefore, xRz

once you have an equivalence relation, then you have equivalence classes.

Assume we have an equivalence relation on set A.

Let x in A.

equivalence class of x.

= x/R

= {y in A: x R y}

all the elements that x is related to.

for our statement

1/R = {1, -1, .. all odds)

-------

general principle, from reflexivity -- the elemeent itself is in its own equivalence class.

-------

= set of odd integers

0/R = set of all evens.

5/R = set of odds.

¯4/R = all evens.

takes the set Z and splits it into two parts.

this is called a partition if Z

a partition is a set of substs that cuts the original set into pieces.

no overlap between the sets and the union of the sets is the set Z.

it turns out that this example illustrates a general property -- when you have an equivalence relation in general, it will create a partition(s)

Integers modulo m --

Z[m], where m is some positive integer.

like % in computer science.

modular arithmetic.

so integers modulo m = Z[m]

A -Z

x ---[m] y <=> m|(x-y), ie x-y = km

1,5,9,13 -- is an equivalence classed defined by this if m=4.

Let x be an integer.

Then x-x = 0 = 0m. Therefore, x is related to x "x is congruent to x mod m"

symetry

Let x and y be in Z.

Assume x is congruent to y mod m

then we know that x-y = km, k in Z.

Then y-x= -km = (-k)(m), -k in Z,

therefore y is congruent to x mod m.

Transitivity.

Suppose we have x, y z, in Z.

Assume x is congruent to y mod m. and that y is congruent to z mod m.

Then x-y = k[1]m and y-z = k[2]m

Then

x-z = (x-y)+(y-z)

= k[1]m + k[2]m

= (k[1] +k[2])m,

and k[1] +k[2] is in Z

therefore x is congruent to z mod m.

Fri 03/09/07

#16 -

assume the sets are non-empty

----

assigment

1 bcdil,

2 bcefgh,

4 abcej,

5 bd,

7 befh, 8ab, 9, 10b

12ac, 13, 16abd

double check.

Z mod 4 = {0,1,2,3} with bars over the number.

the bar represents, for example, 0, 4, 8 etc.

for this example 5-bar = 1-bar.

partitioning -- when you form an equivalence relation and look at the corresponding equivalence classes, you partition.

Let A be a set

script-A = collection of famly of subsets of A.

script-A is a _partition_ iff

(1) If X element of script-A, then X ≠ empty set.

(2) If X,Y element of script-A, then X=Y or X intersect Y = empty set

(3) ∪ X, X element of Script A = A

we can name one set in script A by two different names if we need to.

A = {1,2,4,5}

script-A could be {{1,2},{4,5}}

not cutting it up at all is a partition.

other extreme -- chop into all singleton sets.

Theorem 3.5

R is a equivalence relation on A.

x/R - the set y in A such that xRy

Theorem 3.5

(a) For all x in A, x/R is a subset of A and x belongs to x/R (so x/R ≠ empty)

Proof.

x/R subset of A - true by definition of this symbol.

"the set of element in A that .."

x belongs to x/R, since xRx (reflexivity property of equivalence relation)

b) the union x/R (x element of A) = A

Proof.

subset inclusion both ways.

from left to right --

true, since x/R is a subset of A for all x in A -- that's what we proved in A.

and chapter 2 had a theorem that said if each of the sets is a subset, then the union is.

going the other way

Let a be in A.

Then a belongs to a/R

Then a belongs to Union of x/R (x element of A)

that gets us subset inclusion in other direction.

c) xRy iff x/R = y/R

Proof.

(==>)

assume xRy, prove the two are equal

prove that x/R subset of y/R

let z be an element in x/R.

So xRz

We are assuming that xRy

Then yRx by symetry.

then, since yRx and xRz, yRz, by transitivity.

Since yRz, z is in y/R

now prove

y/R subset x/R

Let z is in y/R

Therefore yRz

We know, by assumption thht xRy

Since xRy and yRz, xRz by transitivity

Therefore z belongs to x/R.

so now (<==)

assume x/R = y/R Show that xRy

from a previous part of this theoreum

y belongs to y/R.

Since x/R = y/R, y belongs to x/R

by definition of x/R, xRy.

QED.

part d of theorem 3.5)

x!Ry iff x/R intersect y/R = empty set

(<==) assume x/R intersect y/R = empty set.

y element of y/R

So y is not in x/R

So x is not related to y

so taht's teh proof for that direction

(==>)

Proof by contrapositive.

Assume ~Q --

Assume that x/R intersect y/R is not the empty set

then, there exists z element of x/R intersect y/R

so xRz and yRz

by symetry, zRy

By transitivity, xRy.

QED.

Mon 03/12/07

150-151

#4 -

prove reflexivity, symetry, and transitivity

reflexivity -- start with x and then try to show that its related to x

symetry -- assume x is related to y , show y is related to x.

transitivity - assume that x is related to ... look up.

looking at b)

512 R 15

512 R 3,256,417

reflexivity -

does the natural number have the same

use 3 letters for the natural numbers

verify -- basically a proof - demonstrate that they work.

.. the proofs are kind of talky proof -- kind of an informal proof.

Theorem 3.5

a) x belongs to its own equivalence class

b) union of the equivalence classes, you get the entire set A.

c) xRy iff they both have the same equivalence class. x/R = y/R

d) x!Ry iff the equivalence classes are disjoint.

If R is an equivalence relation, then A/R (look at all possible equivalence classes) = {x/R : x element of A}

s a partition of A

Script-A is a opartition of A iff

1) for every set in the collection, B ≠ empty set

2) Union of all the sets in the collection = the entire set

3) for every B and C in the collection either B=C or B intersect C = empty set

a) in 3.5 satisfies 1

b) satisfies 2

c,d give you 3.

so theorem 3.5 says that when you start with an equivalence relation, the get a partition -- with the equivalence classes.

but suppose we start with a partion of our set -- if we start with a partiton of a set, we can actaully define an equivalence relation with the original sets that we started with.

Suppose A = {1,2,3,4,5,6}

β = {{1,3,4}, {2,6}, {5}}

that creates an equivalence relation

xQy = "x is q related to y" iff

there exists C in β such that x in C and y in C.

Q = {(1,1), (1,3), (1,4), (3,3), (4,4), (4,1), (3,1), (3,4), (4,3),(2,2),(6,6),(2,6),(6,2), (5,5)} subset of A cross A

A/Q = {1/Q, 2/Q, 3/Q, 4/Q, 5/Q, 6/Q}

= { {1,3,4} [any order pair that has 1 in the first part, put down its y], {2,6}, {1,3,4}, {1,3,4}, {5}, {2,6}}

apart from the duplications, this is precisely the same set of partitions? that we started with .

we started with a collection of sets β

we used β to define a relation Q, (we called it an equivalence relation) .. we then used Q to obtain the partition, which we called A/Q

the actual partition we ended up with was for all practical purposes we started with

so the original partition β is actually A/Q

these observations are true in general.

so, theorem 3.6.

Let β be a partition of A

Define the relation Q on A by the rule that xQy iff there exists some C in the given partition (B such that x belongs to C and y belongs to Q

Then (1) Q is an equivalence relation on A

(2) A/Q (the set of equivalence classes) = β. that partition will be the same as the original.

Proof

Prove Q is an equivalence relation

(1) reflexivity -

Let x in A

Since β is a partition, we know that the union (b in β) = A.

So x is in the union (mentioned above)

so there exists a C in β such that x belongs to C.

so there exists C in β such that x belongs to C and x belongs to C.

Therefore xQx.

b) For symetry -

Let x, y be in A

assume that xQy

So there exists some C in β such that x belongs to C and y belongs to C

So there exists a C in β such that y is in C and x is in C

Therefore yQx

c) transitivity

Let x, y, and z be in A

and assume xQy and yQz. Then,

there exists some C in β such that x is in C and y is in C.

Also, there exists D in β such that y is in D and Z is in D.

Since y is in C intersect D, C intersect D ≠ empty set.

(since we're working in a partition) therefore C = D.

So Z is in C. Therefore, there exists a C in B such that x is in C and z is in C.

Therefore xQz.

we'll do part 2 tomorrow. that says that if we form equivalence classes, we wil get back the same partition.

Tue 03/13/07

Had this definition xQy iff there exists at set C in thh collection such taht x belongs to c and y belongs to c.

the conclusions were

1) (we've proved this) the relation Q is an equivalence relation

what we didn't prove - oncle we know that Q is a n equivalence relation, we have A/Q .. the collection of equivalence classes

we know foom theorem 3.5 that the collection does form a partition

what's important is that the partition we get is the same as the partition we started with.

trying to prove A/Q = script-B aka β

this is set equality , but the elements in these sets are sets themselves.

Let x/Q in A/Q

show that x/Q is one of the sets in β.

Find B in β such that x/Q=B

Since x is in A, there exists a B in β such that x belongs to B.

Claim: x/Q = precisely this B.

go both ways

x/Q is subset of B.

Let y be an element of X/Q So xQy by definition.

so there exists C in β such that x is in C and y is in C.

Since x belongs to B intersect C, B intersect C ≠ empty set .. since we're in a partition, therefore B=C.

therefore y belongs to B.

therefore x/Q is a subset of B.

now, the other direction.

prove

B is a subset of x/Q

Let y be in B.

Since x is in B, (since that's how we chose B.)

then there exists a C in β such that x belongs to C and y belongs to C.

Therefore, xQy

Therefore y is in x/Q.

we started with y in B, now we have y belongs to x/Q.

Therefore B is a subset of x/Q.

Therefore x/Q = B.

to finish the proof -- we have to take an arbitrary set from β, then it actually is on eof the equivlances that belong to this set. and that'll complete the proof.

that's on thursday.

Thu 03/15/07

Due tuesday that we come back

2abc, 3ac, 4, 6ae,

7, 8b, 9, 12, 13, 14acd

partial order relation

relation on a set A.

1) reflexivity - fore every element x in A, xRx

2) anti-symmetry - for every x and y in A, if xRy and yRx ==> x = y .. logically equivalent to: (for all ix,y in R) if xRy and x≠y ==> y!Rx

3) transitivity - for all x,y, and z in a -- xRy and yRz ==> xRz

if you take two elements, they are related at most one way.

partial order -

relation of ≤, for natural numbers

Let x in N

Then x ≤ x, so ≤ is a reflexive relation

Transitivity - Suppose x,y,z in N and x≤y and y≤z. Then x≤z.

anti-symmetry - Let x,y be in N. Assume that x≤y and y≤x. So x=y.

So that's anti-symmetry as it pertains to ≤

When we have for every and y in A then either xRy or yRx,

then we call it a total order or linear order

but in general, that last property is not required for a partial order

lets take a look at some aaybe more interesting partial orders. here's another example

suppose that i take the natural numbers again but my relation is going to be the following

xRy iff x|y

so for example, 2R6 'cuz 2 divides into 6. and certainly it doesn't work the other way.

notice that there's not even a garrentee that the relation is going to go even one way -- for 2 and 3 -- they are not related either way.

take reflexivity for example

Let x be in N.

x|x, since x = 1*x

therefore, xRx.

anti-symmetry - Let x and y be in N.

assume that x|y and y|x.

because x|y, y=k[1]x for some k[1] in Z.

and (other way) x=k[2]y, for some k[2] in Z.

Then x=k[2]y=k[1]x=(k[2]k[1])x

So k[2]k[1]=1.

In General, k[1]=k[2]=1 or k[1]=k[2]=-1

We eliminate k[1]=k[2]=-1, since that implies that x or y is neg.

Therefore k[1]=k[2]=1.

Then y = 1x = x.

Transitivity -

Assume x|y and y|z.

So y = k[1]x and z=k[2]y, k[1],k[2] in Z.

So z=k[2]y = k[2]k[1]x = (k[1]k[2])x and k[1]k[2] (the product) is in Z.

Therefore x|z.

if the set we were looking at was integers, then we could arrive , as part of the anti-symmetry proof, we could arrive at y=-x.

an example of why this doesn't work =

3|-3 and -3|3 .. now 3 and -3 are related in two directions .. and they can be related in only one direction.

Let A be a set

Consider Power(A)

BRC iff B is a subset of C.

so if we want to know if two elements of the power set are related we see if they are subsets for this definition

lets look at the various properties.

reflexivity.

Let C be in Power(A)

Then C is a subset of C.

Therefore CRC.

anti-symmetry - Let B,C be in Power(A). Assume that B is a subset of C and C is a subset of B.

Therefore B=C.

transitivity - Let B,C,D be in Power(A). Assume taat B is a subset of C.

and C is a subset of D.

Therefore, B is a subset of D.

(so B is related to D).

loooking at

{1,2,3,4,5,6,7,8,9,10}

and we said

xRy iff x|y

Take the smallest element and put thht on the bottom.

8 9

\4 6 /

\2 / \ 3 5 7

\ 1 / / /

... and 10 is connected to 2 and 5.

arrows going up

tends to have a web like picture

unless we have say total ordering.

take ≤

1 is at the bottom.

2nd level 2.

3rd level 3.

....

10

so in this case, not a web but a string -- so if you hve a partial ordering and it has the extra proerty thht any elemetn will be related to another, then we have string LINEAR ordering.

suppose we take out 1.

how does our original picture change?

take out the 1 and its connections

now all the primes are the lowest level.

and we also created a situation where 7 was not related to anything different from 7.

one more example.

line diagram for our power set

take set A = {a,b,c}

then for our diagram fo the power set.

we put the empty set on the bottom because it is a subset of any set.

next level up are singleton sets.

{a} {b} {c}

next level -- doubleton.

it looks kinda cool -- i'll traw you a picture if you like

suppose B= {{b},{c}}

upper bound - anything in the partial ordering that's above these elements .. so that these elements were related to it.

D in Power(A) such that {b} is a subset of D and {c} is a subset of D.

Then {b,c} is an upperbound

.. and {a,b,c} is ,too.

Least upper bound B: is the set {b,c}

there's only one least upper bound.

of the upper bounds, there can't be two at the lowest level.

there's a corresponding definition for lower bounds and greatest lower bounds.

lower bound - there's only 1 thing below all these elements -- the empty set.

and its also the greatest lower bound -- because its the highest up.

Fri 03/16/07

relation of divisibility as it played out over the first 10 natural numbers.

Hasse -- line diagram.

partial ordering

upper and lower bounds

{2,3,6}

{6,9}

upper bounds

for an eleement to qualify as an upper bound of a set, all the elements hav3e to be in that set.

upper bound for {2,3,6} is just 6

(this is in our divisibility example)

{6,9} - no upper bound for it

least upper bound -- the upper bound that's related to the other upper bounds.

lub sometimes used for this or supremum - sup. B

lowest upper bound in the tree ... 6 in our case -- 'cuz its our only choice

and for {6,9} no least upper bound because no upper bound

look at lower bounds.

is there anything that qualifies as a lower bound -- an element that is related to each of the elements

for {2,3,6} -> 1

for {6,9}, we get {1,3}

among the lower bounds we can talk about the one that's highest up -- the greatest lower bound

glb, or more commonly infimum or inf. B

for {2,3,6}, its 1

for {6,9}, 3 is the greatest lower bound the inf of {6,9}

if you have infinite sets, you may not be able to identify the greatlest lower bound or least upper bound .. but with finite sets you can.

when they exist, they're unique. .. we only put one number.

this is theorem 3.8

Let A be a partially ordered set

Let B be a subset of A. Then the Sup B or the Inf B (if it exists) is unique. -- there's at most one.

what do we mean by that..

x=Sup B iff for all y in B, you would have to be related to x ( that makes it an upper bound

and xRz , for all upper bounds on B.

Proof that the sub is unique when it exists

uniqueness proof -- really really important.

assume two things and then try to prove that they're the same thing.

Proof.

Let x[1]=Sup B and x[2] = Sup B

Since x[2] = Sup B and x[1] is an upper bound on B, x[2]Rx[1]

Since x[1] is the Sup B and x[2] is some upper bound, x[1]Rx[2]

By anti-symmetry, x[1] = x[2]

does claim that there is one, but says there's at most one.

that's a classic way to prove that a certain element with a certain property is unique.

Proof of unique inf.

what do we mean by inf.

x = inf. iff for every y in B, xRy

and zRx for all lower bounds z of B

Let x[1] and x[2] be Inf B.

Since x[2] = inf B and x[1] is a lower bound on B,

x[1]Rx[2]

Since x[1] = inf B and x[2] is a lower bound on B,

x[2]Rx[1]

By anti-symmetry, x[1] = x[2]

total/linear order.

A set A is totally ordered or linearly ordered iff (1) A is partially ordered

(2) for every x,y in A, xRy \/ yRx.

A _well-ordered_ set A is a set such that

(1) A is totally ordered

(2) If B is a subset of A and B ≠ empty set, then B contains a "least" element.

B contains a least element iff (there exists x in B)(for all y in B)(xRy) - element in B such that its related to all the elements in B ..

order relation -- a relation that organizes elements from smaller to larger

natural numbers with a relation of ≤ is a well ordered set.

not all totally ordered sets are well ordered.

Take the integers Z with ≤.

that's a total ordered but not well ordered.

another example -- all of the real numbers with ≤

suppose B= (0,1)

then inf B = 1

but we can't name a least element.

so the reals are totally ordered but not well order

Mon 03/26/07

For friday

3.4

166 - 1 (ns), 2, 3, 5, 7, 8, 12, 14, 22[:-0], 25a,c

tue

176 - 1, 2, 3, 4, 5,6,7,8,10,13,15a,b

prove partition

every member is non-empty

union is the whole thing

if any two overlap, then they're equal.

partial ordered

show

1) reflexive

2) anti-symetric

3) transitive

equivalence relation

3 things!

1) reflex

2) symetric

3) transitive

Graphs of relations

(relation: a set of ordered pairs)

either elements are in a relationship or not; if they are the ordered pari is in there, else it isn't

graphs of relations

a graph is a set of points usually called verticies or nodes and lines (edges) connecting some of the verticies.

not directed.

study of graphs -- graph theory. - huge.

example

suppose you have five people -- a,b,c,d,e

xSy iff x had a conversation with y.

a b c

d e

connect lines based on who had a conversation

five nodes in this graph -- and seven edges in our example

how its draw really doesn't make any difference -- as long as it has all the same edges and nodes.

a graph where the edges don't intersect is nicer, but not necessary . .. as long as you know that the edges don't really intersect and form nodes.

without intersections -- planer graph - we don'' have to go 3d

we like to draw the graph sso its easy to figue out who's conected with whom.

def. 3.20.

A graph G is a pair (V, E) where V is a non-empty set and E is a set of unordered pairs of distinct elements of V.

An element of V is called a vertex and an element of E is called an edge.

for our graph

V = {a,b,c,d,e}

E = {{a,c}, {a,d}, {b,c}, {b,d}, {b,e}, {c,d}, {d,e}}

G' = {1,2,3,4,5}

E' = {{1,3}, {1,4}, {2,3}, {2,4}, {2,5}, {3,4}, {4,5}}

draw a picture

1

2 3

4 5

same graph as we had before, but we have different names for the verticies.

we say that (V,E) and (V', E') are isomorphic - same but change in appearance

formal definition

(V,E) and (V',E') are isomorphic iff there is a 1:1 correspondance between the verticies in V and V' so that there is an edge in E connecting two verticies of V exactly when there is an edge in E' connecting the corresponding verticies in V'.

"essentially the same"

are these two graphs isomorphic.

if they had different numbers of verticies then there's no chance

a --> 2

b --> 3

c --> 4

d --> 1

since we get a 1:1 correspondence here and on the graph, we have an isomorphism.

Terminology

Some graphs contain loops

we could have {a,a}

multigraphs - allow multiple edges between verticies.

-- can have to different edges connecting two veriticies.

but by our definition didn't allow for this, therefore, , 3.20, was for a simple graph

our definition does not allow multiple edges or loops.

notation:

V = {a,b,c,d,e}

can write out the edges without the braces

E = {ab, bc, cd, de}

two veritices u and v are called adjacent iff uv is in E. .. so if the edge is there, then they're adjacent.

Edge uv is said to be incident with u and with v.. so every edge is incident with two verticies.

The degree of a vertex u is the number of edges incident with u.

so degree of a is 3 -- it has 3 edges.

The /order/ of the graph is the number of verticies.

the /size/ of the graph is the number of edges

Tue 03/27/07

order - number of verticies or nodes

size - number of edges

if the size of the graph is zero, we have a null grah.

there are infinitely many -- can have null graph of order 1, of order 2, etc.

in a null graph, every vertex is isolated.

.. every vertex has degree zero.

can have a graph of size 0 but not order zero -- because the verticies have to be a non-empty set.

a graph in which every pair of distinct verticies is adjacent is called a _complete_ graph.

the complete graph of order n is called K[n].

K[1] is just a dot.

k[2] *---*

K[3] triangle 3 and 3

K[4] box with an x through it.

K[5] pentagram

K[n] has how many edges? nC2 = n!/(2!(n-2)!)

Theorem 3.9. The hand-shaking lemma. /* a lemma is usually a small theorem that's proved in the moddle of a big theorem. */

from the big theorem you have correlary.

anyway,

For each graph G, the sum of the degrees of the verticies is even.

b) for every graph G, the number of verticies of G having odd degree is even

A subgraph (V[1], E[1]) of (V[2], E[2]) is a graph such that V[1] is a subset of V[2] and E[1] subset of E[2]

a---b

\c

find all subgraphs.

could have the null graph.

the graph itself is a subgraph of itself.

could have a and b connected only

could have a and c connected.

you have all three ponts and they can have both of the dges, either of the edges or none of the edges

so that's subgraphs of order 3.

subgraphs of order 2. of our original graph

*---* * *

* *

\

* *

*

*

so five subgraphs of order 2.

3 subgraphs of order 1.

and no subgraphs of order 0 -- HAS TO BE A NONEMPTY SET!

A _walk_ in a graph G is a finite alternating sequence of verticies and incident edges beginning and ending with a vertex.

going back to our a,b,c,d,e graph

all we have to do is list the verticies .. because we don't have multiples

ebdca

ebeb

any time you start at a vertex, traverse some of the edges and end up at a vertext -- that's a walk.

another word for walk is a chain. "path" -- but not our book.

A walk _traverses_ the verticies in the sequence.

The first vertex is called the initial vertex

The final vertex is called the terminal vertex.

The length of a walk is the number of edges.

A walk in which all verticies are distinct except perhaps the first and last is called a path.

so ebdca is a path ebeb is not.

acdad is not a path, but getting rid of the last d makes it a path.

A walk that begins and ends at the same vertex is called closed. so acdada is closed.

A path that is closed is called a closed path .. wow.

A closed walk with distinct edges is called a cycle.

a vertex v is said to be reachable from vertex u iff there is a path from u to v.

if v is reachable from u then the number of edges in a path of minimum length from u to v is called the distance from u to v. d(o,v).

distance from u to u = 0.

new graph.

take the shortest path.

d(a,e) = 3

so if you want to find thh distance, first you to make sure that one is reachable from the other .. and the first path you find sort of puts an upper bound on the distancee-- the distance will be ≤ to that path.

G is called connected if every vertex is reachable from every other vertex. Otherwise, its called disconnected.

reachablility determines componants.

reachability is reflexive, symmetric and transative, so reachability is an equivalence relation.

each equivalence class is called a component.

C(V) = {u in V | u is reachable from V}

Thu 03/29/07

take a well ordered set A , b subset of A. If you look at it right you can do it in three lines

assume that b is linearly ordered -- 'cuz I told you.

definitions

a tree is a graph with no cycles.

(cycle is a closed path that doesn't re-use any edge)

we can have a subgraph that is a tree if the original one is not.

a spanning tree is a subgraph that is a tree and that traverses every vertex.

finding a minimal spanning tree. -- a spanning tree such that the sum of all the edges used is a minimum.

Gredy algorithm - start anywhere and keep using the shortest edge.

graph theory started with the bridges of kornixburg problem.

in 1736

is it possible to start at home and take a journey that crosses each bridge exactly once?

Leonhard Euler 1707-1783

studied the problem.

he treated each piece of land as a node.

each bridge was an edge.

Possible iff at most two verticies of odd degree.

Fri 03/30/07

functions

Def 4.1 A function f from A to B is

1) (fo) A relation from A to B (ie, its a subset of A x B

2) (f1) Domain of f = A

3) (f2) If (x,y) in f and (x,z) in f, then y=z.

If A = B, then we can say that f is a function on A.

a function is also called a mapping.

f: A -> B

f "maps" A to B.

B is the codomain of f.

Rng(f) = {y : (exists x)(x,y) in f}

ex: A = {1,2,3}

B = {2,5,6}

r[1] = (1,2), (2,5), (3,6), (2, 6) -- not a function

r[2] = (1,2), (2,5), (3,6) -- fuction

r[3] = {(1,2), (2,5), (3,7)}

not a subset of A cross B

r[4] = {(1,2), (2,5), (3,2)} - function

r[5] = {(1,2), (3,6)} - not a function -- violates f1

r[6] = {(1,2), (2,5), (3,6), (1,2)} - function because (1,2) is the same as (1,2)

r[7] = {(1,2), (2,2), (3,2)}

look at r[8]

r[3] = {(1,2), (2,5), (3,5)}

rng = 2,5

codomain = 2,5,6

nice morrell picture of it here.

Question

let G be the set of all ordred pairs (x,y) element of N cross N, such that y = x +2

is G a function N -> N?

yes

let g = {(x,y) in N cross N : y = x-2}

is g : N -> N? no. .. violates f1

example

H = {(x,y) in Z cross Z : x^2 + y^2 = 2}

(1,1) in H and (1,-1) in H.

therefore it violates f2.

but we could say that H : {1} -> {-1}., that's not very exciting.

so we can make it a function with the right domain and codomain.

Def 4.2 Let f: A -> B

If (x,y) in f, then we write f(x) = y.

if f is a relation and you don't know if its a function, you can't use that notation -- you wouldn't know which y to pick.

y is the value of f at x.

y is the image of x under f.

x is a pre-image of y under f.

elements of A are sometimes called the arguments of f.

examples -

suppose f = {(x,y) in Z cross Z : y = x^2}

F : Z -> Z .

Dom(f) = Z.

codomain(f) = Z.

range(F) = {0, 1, 4, 9, ..}

what is the image of 4? 16.

Preimages of 4 are 2, -2.

empty set : empty set -> empty set

its a function !!

example -

k: R -> R where

k = {(x,3): x in R}

f0 - k subset of R cross R.

let (x,y) in k.

therefore x in R and y=3.

therefore y in R.

therefore (x,y) in R x R.

f1 - show that the domain of k = R.

Domain k subset of R -- by f0 . always.

now subset the other way.

Show R is subset of Dom(k).

let x in R.

therefore (x,3) in K.

therefore x in Dom(k).

done.

f2

Suppose (x,y) in k and (x,z) in k

Therefore y = 3 /\ z = 3

therefore y = z QED.

constant

Range = {3} //always a set.

Suppose U has been specified.

and A is a subset of U.

Define chi[A] : U -> {0,1}

chi[A](x) = 1 if x in A, 0 if x not in A.

this is called the characteristic funtion.

suppose U = R and A=Z.

chi[Z] =

then the graph has 1's for intgers and zero's for everything else.

if A = [3, ∞)

then zero until we get to 3 and then 1 the rest of the way.

Mon 04/02/07

2a

xRy and x≠y => y!Rx

proof by contradiction

suppose the first part and not the second part

suppose xRy and x≠y

we want to show y!Rx.

suppose yRx.

therefore xRy and yRx

therefore x=y (def. of antisymmetric)

-><-

---

fuctions

step functions

suppose {C[1], C[2], .., C[n]} is a partition of A and

every element is non-empty

union of all of them is A

either equal or disjoint.

and {b[1], ... b[n]}

a subset of B.

Define

f : A -> B by f(x) =b[i] for x in C[i]

suppose A = [1,5]

C[1] = [1,2)

C[2] = {2}

C[3] = (2,4)

C[4] = [4,5]

b[1] = 3

b[2] = 1

b[3] = 4

b[4] = 2

line up B[i] and C[i]

b's become y values

another example

Let X be a set and R an equivalence relation on A.

Define f: A -> A/R

by f(x) = x/R

takes elements of our set, and maps it to its equivalence class.

This is a canonical map - canonical -- first one you think of.

ex: R = congruence mod 3 on Z

f(1) = 1/congruence mod 3

f(4) = 4/congruence mod 3 -- but that's the same as 1/congruence mod 3.

infinite elements in A

only 3 in A/R

constant function

Let A be the identity set

then I[A] is a funcion on A.

prove that.

(remember I[A] = {(x,x): x in A}

(f0) show that I is a subset of A.

let (x,y) be in A. Then x in A and y=x

Therefore (x,y) = (x,x) and e of A cross A.

f1 - show that the domain of I[A] = A.

Dom I[A] is subset of A by f0.

now go the other way.

Let x in A

Therefore (x,x) is in I[A] by definition of the identity.

therefore x is in Dom I[A]

f2 - "the function property"

if you have two ordered pairs with the same first element, then the second elements have the be the same.

suppose (x,y) in I[A] and

(x,z) in I[A]

Therefore, y=x and z=x, by def of I[A]

Therefore y=z. QED.

If x in A, then I[A](x) = x.

Let A be a subset of B.

define i: A ->B

by i(x) = x

same as Identity, but the codomain is different.

identity function uses up everything

the little i stands for inclusion -- the inclusion function

takes an element of a subset and says OK its an element of a subset but its also an element of hhe big set.

For functions whose domains and range are subsets of the real numbers, the domain is often left unspecified. The domain is the largest set of numbers that makes sense.

example G(x) = √(x+1)

The domain of G is [-1, ∞)if we only wanted to talk about x being positive, then wed have to specify.

f(x) = 1/(x+7)

domain x ≠ -7

notation.

Let f -> Z cross Z -> Z.

defined by f((x,y)) = x * y

notation is to sometimes write f(x,y) = xy instead of the extra paren.

if we know the domain is ordered pairs, we don't have to write the again

f(2,5) = 10.

another example

Let S be a relation from A to B.

Define projection functions π[1] and π[2]

π[1] S -> π[1] (a,b) = a

π[2] S -> π[2] (a,b) = b

projection funciions

π[1] gives yo the x value -- it projects down to the x axis.

π[2] projects over to the y axis.

f : Z -> Z

f : Z -> R

changing the codomain doesn't really change the function .

we'll treat these as the same function.

IMPORTANT THEOREM COMING UP.

how would you show that two functions are equal.

only way is to say that they're equal as relations, but that's a lot of work.

Theorem 4.1 Two functions f and g are equal iff

1) Dom(f) = Dom(g) and

2) for all x in Dom(f), f(x) = g(x).

we'll prove it next time

homework for a week from friday.

page 185 #1,2,3,4,5,8,9,11,14,18.

Tue 04/10/07

R is transative => R inverse is transative.

suppose R is transative.

show R inverse is transative.

Let (x,y) be in R inverse and (y,z) in R inverse

then (y,x) is in R and (z,y) is in R.

therefore (z,y) is in R and (y,x) is in R because of communitativity of conjunction.

therefore (z,x) is in R.

therefore (x,z) is in R inverse.

4.

suppose A X B = empty

show A = empty or B = empty

Suppose not - therefore ~(A empty or B empty)

... (you got this one right)

5.

Suppose R is reflexive on A and S is reflexive in A.

Show R intersect S is reflexive on A.

Let x be an element of A.

therefore (x,x) is in R and (x,x) is in S - because the two are reflexive.

Therefore (x,x) is an element of R intersect S.

Therefore R intersect S is reflexive.

8.

i) just find an element.

ii) union = R cross R.

subset each way

my part iii

going the other way.

find a such taht (x,y) is in A sub a

find z such that y = a + x.

Let a = y -x.

therefore (x,y) is in A sub a

and we're done.

iii) suppose A[a] intersect A[b] = empty.

therefore there exists (x,y) element of the intersection.

therefore (x,y) is in A[a] and (x,y) is in A[b]

therefore y = a + x and y = b + x

a = y -x..??

therefore

a = b

A[a] = A[b]

office hours this week.

today, tomorrowafter class to noon

10 - 11:15 , 2-3 thursday

10 - 11:30, 1-2 -- homework due at 2. friday

5:00 math club meeting thursday.

theorem 4.1

two functions f and g are equal iff

i) dom(f) = dom(g)

ii) for a x in dom(f), f(x) = g(x)

prove this thing.

lets go => first.

(the "easy" way)

Suppose f=g.

i) Show Dom(f) = Dom(g)

subset both ways.

left to right.

Let x be in dom(f).

therefore there exists a y such that (x,y) is in f.

therefore, (x,y) is in g (Because they're equal)

therefore x is an element of the Dom(g)

similarly, for subset the other way.

ii) Let x be in Dom(f)

therefore, there exists a y such that (x,y) is an element of f

therefore (x,y) is an element of g ('cuz they equal).

We know that f(x) = y

and g(x) = y

therefore f(x) = g(x)

proof that direction is a bit of overkill

important part is the other direction.

<=

suppose part i and part ii.

show f=g

subset both ways.

left to right.

let (x,y) be an element of f.

therefore x is in the Dom(f).

therefore x is in Dom(g) (by part i)

therefore there exists a z such that (x,z) is an element of g.

therefore f(x) = y and g(x) = z.

therefore y = z (by part ii).

therefore (x,y) is an element of g. QED that way.

similarly the other way

qed the whole thing.

so to show two functions are equal, show that they hhve the same domain and that they agree on their domain.

Let A = {1,2,3}

B = {c,d}

how many functions are there from A to B.

domain has to be all of A.

1. (1,c), (2,c), (3,c) // constant function.

two choices for each of the ordered pairs. -- 2 * 2 * 2 = 8. 2^3

how many functions from B to A? .. 3^2

so can figure out the number of functions if you know the amount of elements in the domain and codomain.

Thu 04/12/07

construction of functions

let F : A -> B

F {(x,y) : (y,x) in F}

any relation has an inverse, bbut it may or may not be a function

example

suppose F = {(x,y) : y = 2x +1}

therefore

F inverse = {(x,y) : (y,x) in F}

= {(x,y): x = 2y + 1

= {(x,y): y = (x-1)/2}

and in this case, that is a function

example another

suppose G = {(x,y) : y = x^2}

then G-inverse = {(x,y) : (y,x) is in G}

= {(x,y): x = y^2 }

= {(x,y): y = +/-√x}

not a function.

Compositions

let F(x) = 2x +1, G(x) = x^2

G composed F = {(x,z): for some y in R, (x,y) in F and (y,z) in G}

= {(x,z): (there exists y in R) y = 2x + 1 and z = y^2 }

= {(x,z): z = (2x+1)^2 }

this is a function.

function's inverse may or may not be functions

composition -

Theorem 4.2

If F is a function from A to B and G is a function from B to C.

then G composed F is a function from A to C

Proof.

F0. G composed F is a relation from A to C - because we studied that when we did relations.

F1. Need only show A is a subset of Dom (G composed F)

Let x be an element of A.

Therefore x is in Dom(F).

Therefore there exists a b in B such that (x,b) is in F.

since b is in B, be is in the Dom(G) //because G is a function from B to C.

Therefore there exists c in C such that (b,c) is in G.

Therefore (x,b) in F and (b,c) is in G.

Therefore (x,c) is in G composed F.

Therefore x is in Dom(G composed F) QED

F2. Suppose (x,y) is in G composed F and (x,z) is in G o F.

there exists u in B such that (x,u) is in F and (u,y) is in G.

there exists v in B such that (x,v) is in F and (v,z) is in G.

Therefore u=v by (F2) for F.

Therefore y=z by F2 for G.

QED.

(x,y) is in G o F iff (x,z) is in F and (z,y) is in G for some z.

iff z = f(x) and y = g(z) for some z.

therefore (G o F)(x) = y

= G(z)

= G(F(x)) .. which is what we learned.

from above (G o F)(x) = G(F(x))

= G(2x+1)

= (2x + 1)^2

Theorem 4.3

The composition of functions is associative.

ie, if F is a function from A to B, G is a function from B to C and H is a fucntion from C to D

then (h o g) o f = h o (g o f).

Proof.

Dom of (h o g) o f = Dom(f).

Dom of (h o (g o f)) = Dom(g o f) = Dom(f). .. = A.

let x in A

((h o g) o f)(x) = (h o g)(f(x))

= h(g(f(x)))

= h((g o f) (x))

= h o (g o f)(x) . qed.

f: A -> B

g: B -> C

g o f: A -> C.

Theorem 4.4. Let f: A -> B.

Then f o I[A] = f and I[B] o f = f.

Proof. f o I[A] = f.

Dom(f o I[A]) = Dom(I[A]) = A = Dom(f).

so the domains are equal

ii)

(f o I[A])(x) =

// start with the more complicated one and break it down.

(f o I[A])(x) = f(I[A](x))

= f(x). QED.

Theorem 4.5

Let f: A->B with Rng(f) = C.

if F-inverse is a function, then f-inverse o f = I[A]

f o f-inverse = I[C]

Proof of f-inverse o f = I[A]

Dom(f-inverse o f) = Dom(f) = A = Dom(I[A])

let x be in A.

suppose f(x) = y. Therefore (x,y) is in f.

Therefore, (y,x) is in f-inverse

Therefore (x,x) is in f-inverse o f

therefore f-inverse o f(x) = x = I[A](x). QED for the first part of the theorem.

Recall from Calc II.

sine : (R -> [-1,1] did not have an inverse.

(horizontal line test)

Restrict the domain & get a new function same as before but the domain is [-π/2, π/2]

this new function is called the sin restricted to [-π/2, π/2]

Def 4.3 Let be a function from A to B and let B be a subset of A.

The restriction of f to D, denoted f|[d] is defined by

f|[D] = {(x,y) : (x,y) in f and (x,y) in D}

f|[D] = D -> B

for tuesday

195: 1bfj, 4, 5, 6, 8, 12, 16, 18(do the last part first). 19 (proofs to grade).

Fri 04/13/07

f|[D] = D -> B

function.

Domain = D

codomain = B

prove that its a function from D -> B

f0

let (x,y) be in f|[D]

then (x,y) in f and x in D

...

there x in D an y in B.

Therefore (x,y) is in D x B .. so its a relatin from D to B.

f1. Need only show D is a subset of Dom(f|[D]).

we proved the other way in f0.

Let x in D.

Then x is in A because D is a subset of A.

Therefore x in Dom(f)

Therefore there exists a y such that (x,y) in f.

Therefore (x,y) in f and x in D.

Therefore (x,y) in f|[D]

Therefore x element of Dom(f|[D]).

f2. Let (x,y) in f|[D] and (x,z) in f|[D].

Therefore (x,y) in f and x in D and (x,z) in f and x in D.

Therefore (x,y) in f and (x,z) in f.

Therefore y=z. by f2 for f.

Suppose h and g are functions

Is h intersect g a function?

yes (exercize 8).

ex: h {(1,2),(5,7),(3,-9)}

g = {(1,8),(5,7),4,8}

h intersect g = {(5,7)}

h union g .. not a function!

intersection of two functins is a restriction.

show that h intersect g is always a restriction.

so h union g isn't a function in this particular case.

Theorem 4.6

Let h and g be functions such that Dom(h) = A, Dom(g) = B, and A intersect B = empty set.

Then h union g is a function with Domain A union B.

h union g is an extension of h (and also of g).

prove that h union g is a function.

f0 - Show that Dom (h union g) is a subset of A union B.

let x in Dom(h union g).

therefore there exists y such that (x,y) in h union g.

Therefore (x,y) in h or (x,y) in g

Therefore x in Dom(h) or x in Dom(g)

Therefore x in A or x in B.

Therefore x in A union B.

f1 show that A union B is a subst of Dom (h union g)

Let x in A union B

Therefore x in A or x in B.

case 1. Suppose x in A.

Therefore x in Dom(h)

Therefore exists a y such that (x,y) in h.

Therefore (x,y) in h union g.

Therefore x in Dom(h union g)

case 1. Sup x in B.

Therefore x in Dom(g)

Therefore exists a y such that (x,y) in g

Therefore (x,y) in h union g

Therefore x in Dom(h union g)

Therefore, in either case, x in Dom(h union g).

Therefore, A union B is a subset of Dom(h union g)

f2. Let (x,y) be in h union g and (x,z) be in h union g.

Therefore [(x,y) in h or (x,y) in g] and [(x,z) in h or (x,z) in g]

four possibilities (2 * 2)

(x,y) in h (x,z) in h

(x,y) in h (x,z) in g

(x,y) in g (x,z) in h

(x,y) in g (x,z) in g

case 1 & 4.

therefore y = z.

case 2

x in Dom h and x in Dom g.

x in A and x in B.

Therefore x in A intersect B.

Therefore x in empty set.

contradiction.

case 3 also leads to a contradiction.

Therefore All possible cases lead to y=z

QED f2.

examples - f(x) = x^2 for x < 0, x+1 for x ≥0

let h = x^2 for x < 0

let g = x+1 for x ≥ 0

because the domains don't intersect, this is a function.

g(x) x^2 for x≤0 and x+1 for x ≥ 0.

that's not a function because we get two values at 0.

f(x) = x^2 for x≤0, x for x ≥ 0.

this thing is a function even though the domains are disjoint.

because they agree on the intersection of their domains.

exercise 11

Let h : A -> B, g : C->D

suppose E = A intersect C.

Then h union g is a function from A union C to B union D

iff h|[E] = g|[E]

Proof

Suppose h union g : A union C -> B union D

show h|[E] = g|[E]

Let (x,y) in h|[E]

show (x,y) in g|[E]

Therefore, (x,y) in h and x in E

therefore (x,y) in h union g and x in A intersect C.

Therefore x in A and x in C.

Therefore x in C.

Therefore x in Dom(g).

Therefore exists z such that (x,z) in g.

Therefore (x,z) in h union g.

Therefore y =z by f2 for h union g.

Suppose h|[E] = g|[E]

show h union g is a function from A union C to B union D.

f0 and f1 as in theorem 4.6.

f2.

Let (x,y) in h union g and (x,z) in h union g.

Then (x,y) in h or (x,z) in g and (x,z) in h or (x,z) in g.

same four cases.

for case 1 y=z -- by f2 for h.

case four is easy, too.

case 2.

then x in Dom(h) and x in Dom(g).

therefore x in A and x in C.

then x in A intersect C.

then x in E.

therefore (x,y) in h|[E] and (x,z) in g|[E]

but we assumed that those restrictions were equal.

so y=z

so all four possibilities lead to y = z.

Mon 04/16/07

onto and one-to-one

Def 4.4

A function f from A to B is onto B iff the range of f = B.

f : A->B with an onto on the arrow.

In this case, f is also called a surjection, surjective "sur" means on ..

if Rng = codomain, its onto.

f: A -> rng(f). every function is onto its own range. every function is onto something.

f: A -> B is onto iff B is a subset of the rng(f) .. we already know from f0 that its a subset the other way.

iff (for every b in B)(there exists an a in A such that f(a) = b)

"take an arbitrary element of the codomain, show its in the rng."

A to B vs. A onto B.

f: A -> Rng(f) is always onto. every function is onto its own rng

ex: f: R-> R f(x) = 2x -3 is onto.

prove it. .. probably in the form of prove or disprove.

this one looks onto -- lets see if we can prove it.

take an arbitrary element of the codomain -- let y in Real numbers.

show y in Rng(f)

Therefore we have to show

there exists x in R such that f(x) = y

show that there there exists an x such that 2x-3 = y.

solve for x.

2x = y +3

x = (y+3)/2.

how do we knw this is the solution ? plug it in and see what happens

f(x) = f((y+3)/2)

2(y+3)/2 - 3

= y

therefore y in Rng(f) .

therefoe onto.

g: R -> R = x^2+1

show 0 is not an element of the rng(g)

suppose there exists an x such that g(x) = 0.

then x^2 +1 = 0

x^2 = -1

x = +/- √ -1 .. not a real number

so there's no real number that gets mapped to.

if we wanted to force this function to be onto, we could change it to

g : R -> [1,∞)

h : R -> R onto?

h(x) = x^3 + 2x + 17

yes -- because its an x^3 function.

so you can decide graphicaally.

ex: f : Z x Z -> Z defined by f(x,y) = xy is onto.

let y in Z

f(1,y) = y

so its onto.

define F: N x N -> N by F(m,n) = (2^(m - 1))(2n-1)

F(2,3 = 2^1 * (2*3 -1) = 10.

Let s in N. Find (m,n) in N x N such that f(m,n) = s.

Suppose s is even.

thefore s = 2^k * t for some k, where t is odd.

therefore t = 2l -1 for some l in N.

F(k+1, l) = 2^(k+1-1) * (2l -1) .. so for even numbers, it works.

Suppose s is odd.

so s = 2^1 - 1

f(1, l) = 2^(1-1) * (2l-1) = s.

Find (m,n) such that F(m,n) = 120.

2^3 * 15

F(4,8).

= 120.

theorem 4.7

if f is a function from A onto B and g is a function from B onto C.

Then g o f is a function from A onto C.

proof is one of the homeworks.

Let c in C . and go from there.. show that everything in the codomain is in the rng.

theorem 4.8

suppose f : A -> B

G : B -> C

g o f: A onto C.

then g is onto C.

prove this.

Let c be in C.

show taat c is in the rng of g.

Therefore c is in Rng(g o f ) because gof is onto.

Therefore there exists a in A such that gof(a) = c.

therefore g(f(a)) = c.

therefore c is in Rng(g) because g of something, f(a) equals c.

Must f also be onto?

no.. find a counter example.

f -- two dots

g -- 3 dots

c - 2 dots.

map f to two of b's dots -- its not onto

but g is.

Def 4.5 A fuction F from A to B is said to be one-to-one, written with a 1-1 on top of the arrow.

iff (x,y) in f and (z,y) in f -> x = z

or

f(x) = f(z) -> x =z

or (contrapositive)

x ≠ z => f(x) ≠ f(z).

injective -- means one-to-one.

a one-to-one function is called an injection.

F: R -> R, defined by f(x) = 2x -3.

show f is one-to-one

generally use the function notation unless talking about inverses

suppose f(x) = f(z)

f(x) = 2x -3

f(z) = 2z -3

therefore x = z

therefore one-to-one

1-1 is frequently easy to show.

example

G(x) = x^2 +3

suppose that G(x) = G(z)

therefore x^2 +3 = z^2 + 3.

x^2 = z^2

therefore x = +/- z.

yikes

find two elements taht are mapped to the same number

g(1) = 4

g(-1) = 4

therefore not 1-1.

every function is 1-1 from somewhere - changing the domain.

g: [0, ∞) -> R

is 1-1

g = G|[[0, ∞]

so you can always make a function 1-1 by getting rid of all the duplicate pairs.

F: N X N -> N F(m,n) = 2^(m-1) * (2n-1) is 1-1

Suppose F(m,n) = F(r,s)

show that (m,n) = (r,s)

First

Show m = r.

without loss of generality, m ≤ r

therefore 2^(m-1)(2n-1) = 2^r-1) (2s-1)

divide both sides by 2^(r-1)

2^(m-r)(2n-1)=2s-1

2s -1 is odd

therefore m-r 0.

therefore m = r.

then

2n-1 = 2s-1

n=s

therefore 1-1

for friday

page 205

1 (ns), 2(same parts from number 1, don't give proofs), 4, 5, 6, 9ab, 14b, 17

Tue 04/17/07

Theorem 4.9

Let f: A -> B

f-inverse is a function from Rng(f) -> A iff F is 1-1.

furthermore, if F-inverse is a function, then F-inverse is 1-1. excercise 5.

proof of first part.

<=

Suppose F: A -> B is 1-1.

show that F-inverse is a functin from Rng(F) -> A.

f0 and f1 are true by definition of f-inverse

show f2.

Let (x,y) be in F inverse and (x,z) in F inverse.

what to prove that y=z.

therefore (y,x) in F and (z,x) in f.

Therefore y = z, since f is 1-1.

---

<= suppose f inverse is a function; show f is 1-1.

let (x,y) be in F and (z,y) in F

Therefore (y,x) in F inverse and (y,z) in f-inverse.

therefore x=z by property f2 for f inverse.

Note: if F: A-> B that's 1-1, then F-inverse is a function from rng(f) -> A that's 1-1 .. that's what we just proved..

suppose F: A->B (1-1) and also onto.

then F-inverse: B -> A, which is 1-1 and onto

this is correllary 4.10

theorem 4.11

if F : A -> B (1-1) and G : B->C (1-1)

then G o F: A -> C (1-1)

Proof.

Suppose g o f(x) = g o f(z).

therefore g(f(x)) = g(f(z))

therefore f(x) = f(z), since g is 1-1.

x = z, since f is 1-1.

qed.

4.13 if F: A->B g: B-> C

and g o f : A -> C is 1-1

then F: A->B is 1-1

proof of this is an exercize.

start: suppose f(x) = f(z).

g need not be 1-1.

Def 4.6 A function that is both 1-1 and onto is called a one-to-one and onto.. or a "1-1 correspondence". - bijective

example. f: R -> R f(x) = 2x-3

ex2: f: [0,1] -> [5,100] f(x) = 95x + 5 is 1-1 and onto.

prove it.

proof

1-1. suppose f(x)=f(z)

therefore 95x+5 = 95z+5.

95x = 95z, x=z.

onto.

let y in [5,100].

find x in [0,1] such that f(x) =y.

95x +5 = y

95x = y-5

x = (y-5)/95

f(x) = 95x+5 = .. = y.

now is it in the right intervol.

solve the inequality for x

5 ≤ y ≤ 100

0 ≤ y-5 ≤ 95

0 ≤ y-5/95 ≤ 1

therefore x in [0,1].

how did we come up with this function?

we took the starting and ending points and calcualted the equation of that line.

(0,1) to (5,100)

.. use the same formula.

proof would be the same, just open intervals.

another example

f: (-π/2,π/2) -> R

the function that is 1-1 onto is tan(x).

..

describe how to find a 1-1 onto function from (0,1) to R.

(-π/2, π/2) -> R works.

now we want (0,1)

take the composition of those functions.

g o f (0,1) -> R (1-1 onto).

another example.

F: N x N -> N, F(m,n) = 2^(m-1)(2n-1)

is 1-1 onto.

we proved that yesterday!

Theorem 4.12 if f:A-> B and g: B->C and each is a 1-1 correspondance, then

a) g o f: A->C is a 1-1 correspondance.

b) f-inverse: B->A is a 1-1 correspondance.

we already proved this .. we just need to write it in one theorem -- 'cuz its important.

Theorem 4.14. Let F: A->B and G: B->A.

then G: F-inverse iff gof = I[A] and fog = I[B].

Proof

=> Theorem 4.5

show <=

suppose gof = I[A] and fog = I[B]

I[A] is 1-1. therefore F is 1-1 (by some theorem from before).

I[B] is onto therefore F is onto.

therefore F-inverse is a function //because f is 1-1

from B -> A.

F-inverse = F-inverse o I[B].

= F-inverse o (f o g)

= (f-inverse o f) o g

= I[A] o g

= g.

QED.

Theorem 4.15

a) a restriction of a 1-1 function is 1-1.

b) if h : A onto C, g: B onto D and A n B = empty

therefore H u G is a function from A u B to C u D .. and this thing is onto.

c) if h: A -> C (1-1

g: B-> D (1-1

A n B = empty

and C n D = empty

then H u G : A u B to C u D is 1-1.

Thu 04/19/07

problem 1j.

fog(x) = f(g(x))

if x ≤ 2, f(7-2x)

is this thing less than 3 or greater than or equal to three.

7-2x ≥ 3. so we use the 2nd half of f for x ≤ 2.

so (7-2x)^2

x > 2 f(x+1)

again x>3

so (x+1)^2

so our final asnwer is

= (7-2x)^2 x≤2

(x+1)^2 x>2

now we'll look at gof

g(f(x))

x < 3 g(2x+3)

2x + 3 ≤2

x ≤ -1/2

so if ≤ -1/2 (7-2)(2x+3) x ≤ -1/2

(2x+3)+1 for -.5 < x<3

x^2+1 x ≥ 3

......

Theorem 4.15

a) a restriction of a 1-1 function is 1-1.

b) if h : A onto C, g: B onto D and A n B = empty

therefore H u G is a function from A u B to C u D .. and this thing is onto.

c) if h: A -> C (1-1

g: B-> D (1-1

A n B = empty

and C n D = empty

then H u G : A u B to C u D is 1-1.

...

proof of part a.

Suppose f: A -> B (1-1) show taht F restricted to E is 1-1

let (x,y) in F|[E] and (z,y) in F|[E].

Prove that x=z.

then (x,y) F and x in E

z,y in F and z in E

Therefore (x,y) in F and (z,y) in F.

Since F is 1-1, therefore x=z.

so the restriction info is really extraneous.

b)

Suppose h: A->C is onto

and g: B->D is into

and A n B is empty

show h U g : AuB -> C u D is onto.

wanna show that the range is the codomain

let y in C u D.

therefore y in C or y in D.

Case 1. y in C.

therefore y in Rng(h).

exists x in A such that (x,y) in h

therefore (x,y) is in h u g.

therefore y in Rng(h u g).

case 2. y in D.

therefore y in Rng(g)

therefore exists x in B such that (x,y) in g.

therefore (x,y) in h u g.

therefore y in Rng(h u g).

in both cases y in Rng(h u g). therefore hug is onto.

c)

suppose h u g (x) = (h u g)(y).

therefore x in Dom(h u g)

and y in Dom (h u g).

therefore in A u B and y in A u B.

therefore x in A or X in B and y in A or y in B.

(x in A and y in A) or

(x in A and y in B) or

(x in B and y in A) or

(x in B and y in B)

(h u g)(x) = h(x)

(h u g)(y) = h(y)

so h(x) = h(y) .. by subtititution with original supposition

so x=y

since h is 1-1

that was case 1.

case 2.

(h u g)(x) = h(x)

(h u g)(y) = g(x)

h(x) in C

g(y) in D

therefore (h u g)(x) in C n D.

but we said in the given that C n D was the empty set.

the 3rd case is also a contradiction.

so we have two cases where they work and two contradictions

so x=y and its 1-1.

images of sets.

def 4.7

Let f: A->B. if X subset of A, then the image of X under f is f(X) {y in B : y = f(x) for some x in X}

if Y is a subset of B, then the inverse image of Y is f-inverse(Y) is the set of all x in A such that (x) in Y.

diagram

f({1,2,3}) = {a,b,c}

f({3,4}) = {c}

f-inverse({a,b,c}) = {1,2,,3,4}

f-inverse({e}) = empty set

f(empty set) = empty set.

f(A) = {a,b,c,d}

= rng(f)

image of entire domain is rng.

Note: f: P(A) -> P(B)

f-inverse: P(B) -> P(A).

induced set functions.

you can write f-inverse even if f doesn't have an inverse.

loook at a real example.

f(x) = x^2

f({2}) = {4}

f-inverse({4}) = {-2,2}

f-inverse is not a function but we can still find an induced set function.

f([1,2]) = [1,4]

f-inverse((1,2) = (1, √2) u (-√2, 1).

so the preimage can be the union of two separate intervols.

theorem 4.16

let f: A->B

C subset of A

D subset of A

E subset of B

F subset of B

the image of the interesection is a subset of the images.

b) the unions are equal

c) f-inverse(e interesect f) = f-inverse(e) n f-inverse(F)

d) inverse of the unions equals the unions of the inverses.

a) prove

let y in f(C n D)

therefore exists x in C n D such that y = f(x)

so, x in C and x in D.

therefore, y in f(C) and f in f(D).

therefore y in f(C) n f(D).

. - .

. / .

. /

{1} n {2} = empty set

f({1} n {2}) empty set.

f({1}) = {a}

f({2}) = {a}

f({1}) n f({2}) = {a}

which is not the empty set

so that's equals, just subset.

homework from this section -- last section for test.due tuesday

211 - 1b, 2, 4, 5, 7, 10, 14b, 17

Fri 04/20/07

theorem 4.16

c)

show that f inverse E intersect f = the intersect of the inverses.

show subset both ways

way 1.

let a in F-inverse( E n F).

then f(a) in E n F.

therefore f(a) in E and f(a) in F.

then a in f-inverse(E)

and a in f-inverse(F)

therefore a in f^-1(E) n f^-1(F).

this proof is reversable, but write it out just to be safe.

ex 14e.

show D is a subset of f-1(f(D)).

Let x in D.

then, f(x) in f(D)

therefore x in f-1(f(D))

QED.

btw, equal wouldn't work here.

part f.

D = f-1(f(D) iff f(A-D) in B-f(D).

Proof.

=>

Suppose D = f-1(f(D).

Show f(A-D) is subset of D - f(D)

Let y in f(A-D)

therefore exists x in A - D such that y = f(x).

therefore y in Rng(f)

therefore y in B.

Show y not in f(D)

Suppose y is in F(D) (IP)

f(x) in f(D)

x in f-1(f(D))

therefore x in D by given

But x in A - D

therefore x not in D.

-><-

<=

Suppose f(A-D) is a subset of B- f(D)

Show D = f-1(f(D))

subset one way was done in part e.

show f-1(f(D)) is subset of D.

Let x in f-1(f(D))

prove x in D

Suppose supose x not in D

therefore x in A-D

f(x) in f(A-D)

f(x) in B - f(D)

f(x) in B and f(x) is not an element of f(D)

-><-

exercize 16

Let f: A -> B

f is 1-1

iff f(X) n f(Y) = f(X n Y) for all X, Y subset of A.

=>

Suppose f is 1-1.

show f(X) n f(Y) = f(X n Y) for all X, Y subset of A.

right to left.

theorem 4.16a says that this is true.

left to right.

let b in f(X) n f(Y)

therefore b in f(X) /\ b in f(Y).

then exists x in X such that b = f(x) and exists y in Y such that b= f(y).

therefore f(x) = f(y).

therefore x=y since the function is 1-1.

therefore x in X and x in Y.

therefore x in X n Y

therefore f(x) in f(X n Y)

therefore b in f(X n Y)

QED implies one way.

<=

Suppose f(X) n f(Y) = f(X n Y) for all X, Y subset of A.

Show f is 1-1.

Suppose f(x) = f(y).

then. f({x}) = f({y})

also f({x}) n f({y}) = f({x} n {y})

f({x}) n f({y}) ≠ empty set by the previous statement.

therefore f({x} n {y}) ≠ empty set.

therefore {x} n {y} ≠ empty set -- 'cuz then the image would be empty.

Therefore x = y.

Mon 04/23/07

9 b -- for onto - just make sure that y gets hit once.

so break up the codomain into two sets.

just make sure that every y value is accounted for.

lets break at 0

case 1. y < 0

case 2. y ≥ 0.

case 1. y <0.

find an x ≤ -2 such that y = f(x).

then f(x) = x+4.

y = x+4

so x = y-4

Since y < 0, x ≤ -2 .. so we found an x that uses this part of the domain

and we should finish it off by plugging it in and getting y.

2nd part

find x≥2 such that y = f(x).

scrap work

y = x-4

x = y+4.

since y ≥ 0, y +4 ≥ 2

therefore f(x) = f(y+4) = y +4 -4 = y.

-----------

Chapter 5.

Cardinality -

Definition 5.1 Two sets A and B are equivalent

iff there exists a 1-1 function from A onto B.

So we say that A and B are in a 1-1 correspondance.

A ~~ B (with the squiggles on top of each other)

A = {2,4,5}

B = {a,0,empty set}

f(2) = a

f(4) = 0

f(5) = empty set

f is a 1-1 correspondance.so we've found a function and proven that those two sets are equivalent.

let E = set of even integers.

let D = set of odd integers.

show E ~~ D.

need f: E -> D that's 1-1 and onto.

define f by f(x) = x+1.

show its 1-1 and onto

Suppose f(x) = f(z)

then x+1 = z+1.

... QED.

show its onto.

Let y in D.

therefore y is an odd integer.

therefore y = 2k +1 for some k in Z.

note that 2k is even and f(2k) = 2k+1 = y.

Let script-F = the set of functions from N -> {0,1}

show script-F is equivalent to the powerset of N.

a little motivation.

number of elements in the power set 2^3

number of elements in a set of 3 cross a set of 2 -- 2^3

so the number of functions from a set to doubleton 0,1 should be 2^something.

so even though we cant coulnt them , we can show a 1-1 correspondance.

define H : script-F to Power(N) by

H(g) = {all x in N: g(x) = 1. }

// g: N -> {0,1}

clearly, H is a function from script-F to Power(N).

show H is 1-1.

suppose g[1] and g[2] in script-F.

suppose g[1] != g[2]

show that h(g[1]) != h(g[2])

therefore exists n in N such that g[1](n) != g[2](n). since they wouldn't agree on their domain.

Suppose g[1](n)=1 and g[2](2) =0 WLOG (we don't care which is which).

n in {x in N: g[1](x) =1} = H(g[1])./

n not in {x in N: g[2](x) =1} .. since g[2]=0. = H(g[2]).

therefore H(g[1]) != H(g[2]).

onto

Let A be in POwer(N)

then A is a subset of N.

we need a function such thht H of that function = A.

Consider chi[a]: N->{0,1}

chi[a] is a subset of script_F

because it aa function from N to 0,1

H(chi[a]) =

{x in N: chi[a](x) = 1}

= A .

therefore A in Rng(H)

therefore H is onto.

theorem 5.1

the relation ~~ is a n equivalence relation on the class of all sets.

this is going to be one of the homework problems for next tuesday.

what does it mean for one set to be equivalent to another -

there exists a function

reflexive .. let a be any set -- find a 1-1 onto function from A to A .. don't have to prove 1-1 and onto for that .. we did that.

find a function from a to b .. find it from b back to a.

Tue 04/24/07

two sets are equivalent if they are in a 1-1 correspondance.

to prove that they're equivalent - find a function from one to the other .. show its 1-1 and onto.

theorem 5.2

suppose A, B, C, D are sets with

A ~~ C, B ~~ D.

a) A x B ~~ C x D

b) if A and B are disjoint and C and D are disjoint, then A u B ~~ C u D.

Proof sketch

a) We know that A ~~ C and B ~~ D.

there exists f: A-> C that's 1-1 and onto.

and there exists g: B ->D that's 1-1 and onto

need a function from

A x B -> C x D

f x g : A x B -> C x D.

let h = f x g

h(a,b) =(f(a),g(b))

we proved that this is a function for number 18 in homework.

ex 2. prove that its 1-1 and onto

b)

f u g : A u B -> C u D is 1-1 and onto .. that was 4.15 b,c

notation - N[k] = {1,2,3 .. k} .. integers from 1 to k.

N[2] = {1,2}

def. 5.2

A set S is finite iff

S = empty set or S ~~ N[k] for some natural number k. If S = empty set, we say the cardinal, number of S is 0. S-bar-bar =0.

empty set-bar-bar =0.

If S ~~ N[k], we say that S has cardinal number k and S-bar-bar = k.

A set S is infinite if its not finite.

if A = {a,b,c,d,e}, then the cardinal number of A is 5., since A is equivalent to N[5].

A is finite.

N[k] is finite for any k.

because N[k] ~~ N[k]

theorem 5.3

suppose A is finite.

and A ~~ B.

then B is finite.

transitive.

lemma 5.4 if S is finite with cardinality k and x is any object not in S, then S u {x} is finite and has cardinality k+1.

Lemma 5.5

every subset of N[k] is finite.

Theorem 5.6

Every subset of a finite set is finite.

Theorem 5.7

a) if A and B are finite disjoint sets, then A u B is finite and (A u B)-bar-bar = A-bar-bar + B-bar-bar.

b) If A and B are finite, then A u B is finite

c) If A[1] .. A[n] are finite then

U i=1 to n of A[i] is finite.

Theorem 5.9 - "the pigeon hole principle"

pigeon hole - little cubbies.

Let n and r in N. If f: N[n] -> N[r] and n>r, then f is not 1-1.

.. if you have more pigeons than pigeon holes, there haas to be at least one pigeon hole with mooe than one pigeon.

so one of the codomain has to double up.

correlary 5.10

A finite set is not equivalent to any of its proper subsets.

.. a proper subset would have less elements.

if it is equivalent to one of its proper subsets, then its infinite.

infinite sets.

theorem 5.11

the set of natural numbers is infinite.

prove it.

Suppose not. IP

suppose N is finite .

N = empty set // 1 is a natural number

therefore N ~~ N[k] for some k.

Therefore exists g: N -> N[k] 1-1, onto.

g|[N[k+1]] : N[k+1] -> N[k].

therefore g|[N[k+1]] is 1-1.

-><- Pigeon hole principle.

Def 5.3.

A set is denumerable iff it is equivalent to N.

A denumberable set S has cardinal number aleph null

..

If a set is finite or denumerable, it is called countable. Otherwise, uncoutable

for example

the Set E+ of even positive integers is denumerable

Define f: N -> E+ by

f(x) = 2x.

1-1

suppose f(x) = f(z)

then 2x = 2z.

x = z. therefore 1-1

onto

let y in E+

therefore y is an even natural number.

therefore y = 2k for some natural number k.

therefore y = f(k) = 2k

therefore y in Rng(f).

therefore onto.

Note: N is equivalent to one of its proper subsets. therefore N is infinite.

for tuesday:

228 - 1, 2, 5(dont prove) 6b, 7, 12, 21a,

235 - 1cd, 3, 5.

that's the last official homework to turn in.

to look at

245 1

253 1, 8

Thu 04/26/07

The integers have cardinal number infinity-0. So its denumerable.

find a 1-1 and onto funtion from N to Z.

f: N -> Z.

lets map the evens to the positives and the odds to 0 and negatives.

so f(x) = x/2 for x even

(1-x)/2 for x odd.

Prove that f is 1-1 and onto.

1-1.

Suppose f(x) = f(y).

case 1. both even

then x/2 = y/2 therefore x=y.

case 2. both odd

1-x/2 = 1-y/2 .. x=y

one even and one odd.

for x and y

then f(x) is positive, f(y) is negative, therefore f(x) cannot equal f(y)

similarly for x odd, y even.

now show onto.

Let w in Z.

Let w > 0.

therefore 2w is even and 2w in N

therefore f(2w) = 2w/2 = w.

QED positive

if w ≤ 0, then 1-2w is odd, in N

so f(1-2w) = 1-(1-2w)/2 = w.

so in either case, w is in the range.

Theref