Archive

Archive for January, 2009

1.3 Exercise 4

January 30th, 2009 No comments

This problem was very interesting to me because it demonstrates the nifty idea that you can create an injective function out of any surjective function (hence a bijective function) by grouping members of the domain into equivalence classes -- or, in other words, by "partitioning" the domain appropriately.  Or, from a more poetical point-of-view, by "collecting-doubled-up-string," "string" being the function.  Perhaps what I mean will be clearer by working out the problem.  

"Let  f : A \rightarrow B be a surjective function.  Let us define a relation on  A by setting  a_0 \sim a_1 if

 f(a_0) = f(a_1) .

(a) Show that this is an equivalence relation. 

(b) Let  A^* be the set of equivalence classes.  Show there is a bijective correspondence of  A^* with  B ."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 28.)

-------------

SOLUTION

(a)

Reflexivity, symmetry, and transitivity of the equivalence relation in this case follow from the reflexive, symmetric, and transitive properties of equality.

Reflexivity:  Pick any  a \in A , and apply  f .  By the reflexive property of equality,  f(a) = f(a) .  So  a \sim a  \forall a \in A .

Symmetry: Pick  (a_0, a_1) \in A \times A so that  f(a_0) = f(a_1) , or  a_0 \sim a_1 .  By the symmetric property of equality,  f(a_1) = f(a_0) , or  a_1 \sim a_0 .

Transitivity:  Pick  (a_0, a_1), (a_1, a_2) \in A \times A , such that  f(a_0) = f(a_1) , or  a_0 \sim a_1 and  f(a_1) = f(a_2) , or  a_1 \sim a_2 .  By the transitive property of equality, it is easy to see that  f(a_0) = f(a_2) , or  a_0 \sim a_2 .   

(b)  

Pick an equivalence class,  E \in A^* .  Such  E = \{y \vert y \sim x\} ( y, x \in A ), so  f of any element  y \in E is  f(x) \in B .  In other words,  f(E) = f(x) , and such  f(x) is unique to that equivalence class  (having grouped all elements of  A that mapped to that  f(x) together and because equivalence classes are disjoint).  This shows injectivity.  Surjectivity is established by the fact that  f is surjective and all elements of  A belong to an equivalence class, so  f(E_i) sweeps all of  B .

1.3 Exercise 3

January 29th, 2009 No comments

"Here is a "proof" that every relation  C that is both symmetric and transitive is also reflexive: "Since  C is symmetric,  aCb implies  bCa .  Since  C is transitive,  aCb and  bCa together imply  aCa , as desired.''  Find the flaw in this argument."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 28.)

--------

SOLUTION  

Rephrasing, the argument suggests that every relation that is symmetric and transitive is reflexive, and hence is an equivalence relation.  The problem is that reflexivity must be true for all elements in the base set  A .  Here's a counter-example that disproves the statement. 

Suppose  A = \{1, 2, 3, 4, 5\} , and let's assume we know the relation  C consists of the elements  \{(2, 3), (4, 5)\} .  By following the argument,  C includes elements  \{(3, 2), (5, 4)\} by symmetry, and  \{(2, 2), (3, 3), (4, 4), (5, 5)\} by transitivity.  But the reflexive property of equivalence relations would require that  \{(1, 1)\} be in the relation, which, as we've seen, is not obtainable by symmetry and transitivity alone.  Despite being symmetric and transitive,  C is not, in this case, "totally" reflexive, and therefore it is not an equivalence relation.

1.3 Exercise 2

January 28th, 2009 No comments

This problem is interesting because it shows that restrictions of equivalence relations are also equivalence relations.

"Let   C be a relation on a set  A .  If   A_0 \subset A , define the restriction of   C to   A_0 to be the relation   C \cap (A_0 \times A_0) . Show that the restriction of an equivalence relation is an equivalence relation."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 28.)

----------

SOLUTION 

Reflexivity: Notice that   A_0 \times A_0 will naturally contain those reflexive elements that belong to it (pick a fixed element  a \in A_0 , then  (a, a) \in A_0 \times A_0 ).  By hypothesis of reflexivity of   C , such are included in   C too, because   C contains all reflexive elements in   A \times A . It follows that such a point is also in the restriction.

Symmetry:  We want to show that, picking any point in the restriction, its symmetric point is also in the restriction.  First, notice that for any (fixed) element   (a, b) \in A_0 \times A_0 , its symmetric partner   (b, a) \in A_0 \times A_0 because of the set's square-symmetry.  Now pick   (x, y) \in C \cap A_0 \times A_0 .  Of course, such   (x, y) \in A_0 \times A_0 , and also   (x, y) \in C by the definition of intersection.  Since   (x, y) \in C , there exists a point   (y, x) \in C by hypothesis of its symmetry in   A \times A .    (y, x) is also a point in   A_0 \times A_0 by its square-symmetry.  Therefore   (y, x) \in C \cap A_0 \times A_0 and the restriction is symmetric.

Transitivity:  First, notice that transitivity holds in   A_0 \times A_0 , because it contains all elements that belong to   A_0  in combination with themselves.  Thus, having chosen any three (fixed) elements   a, b, c \in A_0 , specifically these elements   (a, b), (b, c), (a, c) are in   A_0 \times A_0 .  Now pick two elements   (x, y), (y, z) \in C \cap A_0 \times A_0 .  There is an element   (x, z) \in C by hypothesis of its transitivity in   A \times A .  Such exists in   A_0 \times A_0 as well by our aforementioned observation.  Since the element is in both   C and   A_0 \times A_0 , it is in their intersection and therefore in the restriction of   C .

1.3 Exercise 1

January 27th, 2009 No comments

An easy problem that introduces equivalence relations in somewhat a different scenario than the usual "clock arithmetic" ( \mathbb{Z} modulo  n ) context.

"Define two points  (x_0, y_0) and  (x_1, y_1) of the plane to be equivalent if  y_0 - x_0^2 = y_1 - x_1^2 .  Check that this is an equivalence relation and describe the equivalence classes."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 28.)

------------

SOLUTION  

Reflexivity, symmetry, and transitivity of the relation  C is but a re-statement of reflexive, symmetric, and transitive properties of equality.  

Reflexivity:  \forall x \in A, xCx means  \forall (x,y) \in \mathbb{R} \times \mathbb{R}, y + x^2 = y + x^2 \Rightarrow 0 = 0 is a statement of the identity property of equality.

Symmetry:  xCy \Rightarrow yCx means  y_0 - x_0^2 = y_1 - x_1^2 \Rightarrow y_1 - x_1^2 = y_0 - x_0^2 .  This is a statement of symmetry of equality.  

Transitivity:  xCy and  yCz \Rightarrow xCz means  y_0 - x_0^2 = y_1 - x_1^2   and  y_1 - x_1^2 = y_2 - x_2^2 \Rightarrow y_0 - x_0^2 = y_2 - x_2^2 , which is clear by transitivity of equality.

The family of standard parabolas  y = x^2 + K are the equivalence classes ( y - x^2 = K describes the parabolic level curves, and hence all points on a particular parabola are in a particular equivalence class).  The statement  y_0 - x_0^2 = y_1 - x_1^2 is a consequence of transitivity of equality on  K .

1.2 Exercise 6

January 26th, 2009 No comments

This was a really easy problem, that ends the section on functions in Munkres's text.  The next fifteen problems deal with relations, and I am finding them immensely interesting.

"Let  f : \mathbb R \rightarrow \mathbb R be the function  f(x) = x^3 - x .  By restricting the domain and range of  f appropriately, obtain from  f a bijective function  g .  Draw the graphs of  g and  g^{-1} . (There are several possible choices for  g .) "

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 21.)

----------

SOLUTION  

As an example,  g: (-\infty, -1) \rightarrow \mathbb{R}^{-} with rule  g(x) = x^3 -x is bijective.