### Archive

Archive for January, 2009

## 1.3 Exercise 4

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$.

Categories:

## 1.3 Exercise 3

"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.

Categories:

## 1.3 Exercise 2

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$.

Categories:

## 1.3 Exercise 1

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$.

Categories:

## 1.2 Exercise 6

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.

Categories: