Options

Exercise 24 - Chapter 1

edited June 2018 in Exercises

Write down the surjection corresponding to each of these five partitions:

Figure

Previous Next

Comments

  • 1.
    edited April 2018

    Here is my entry

    ex1_18_drawing2

    I put the 5 function mappings as verticals (columns) in the grid above. Each partition is a column heading (p1,p2,p3,p4,p5).

    From there, it can be easily seen that f1,f2,f3, and f4 map several inputs into same output (blocks). So those are definitely surjective and not injective. function f5 seems to be injective as well surjective, as it maps 1 to 1.

    Comment Source:Here is my entry <a href="https://imgbb.com/"><img src="https://image.ibb.co/mftPhS/ex1_18_drawing2.png" alt="ex1_18_drawing2" border="0"></a> I put the 5 function mappings as verticals (columns) in the grid above. Each partition is a column heading (p1,p2,p3,p4,p5). From there, it can be easily seen that f1,f2,f3, and f4 map several inputs into same output (blocks). So those are definitely surjective and not injective. function f5 seems to be injective as well surjective, as it maps 1 to 1.
  • 2.
    edited April 2018

    Nice! Here's an extra puzzle:

    Puzzle. Given two surjections \(f: A \to P\), \(g: A \to Q\), when do they determine the same partition of \(A\)?

    Comment Source:Nice! Here's an extra puzzle: **Puzzle.** Given two surjections \\(f: A \to P\\), \\(g: A \to Q\\), when do they determine the same partition of \\(A\\)?
  • 3.

    Thank you John.

    WRT the Puzzle above.

    On the first thought, P and Q have ordering (just like in the problem statement of Ex 1.18). That means, for function f and g, to be the same they have to preserve ordering. (and also, I am thinking, they have preserve cardinality of the resulting set).

    In other words, f and g, essentially have to produce the same connections (edges).

    If they preserve ordering, it seems like it is impossible for them, to produce different results (as long as they halt , and not interrupted at some point in the middle (which is why I added the same cardinality requirement)).

    I need to formalize this, to be a proper answer, but cannot come up yet, with a formalism to denote 'produce same connections' or 'produce same order' ...

    Comment Source:Thank you John. WRT the Puzzle above. On the first thought, P and Q have ordering (just like in the problem statement of Ex 1.18). That means, for function *f* and *g*, to be the same they have to preserve ordering. (and also, I am thinking, they have preserve cardinality of the resulting set). In other words, *f* and *g*, essentially have to produce the same connections (edges). If they preserve ordering, it seems like it is impossible for them, to produce different results (as long as they halt , and not interrupted at some point in the middle (which is why I added the same cardinality requirement)). I need to formalize this, to be a proper answer, but cannot come up yet, with a formalism to denote 'produce same connections' or 'produce same order' ...
  • 4.
    edited April 2018

    Vladislav - \(P\) and \(Q\) do not have orderings: they are just finite sets. Orderings play no role in Exercise 1.18: while the elements of some sets have names like 1,2,3, they could equally well be called "fred", "ginger", and "roger".

    A partition of a finite set \(A\) is determined by an onto function (=surjection) from \(f: A \to P\) where \(P\) is any finite set. This is explained starting with Remark 1.16 in Seven Sketches.

    My question is when two such functions determine the same partition. The answer is actually hiding in the book.

    Comment Source:Vladislav - \\(P\\) and \\(Q\\) do not have orderings: they are just finite sets. Orderings play no role in Exercise 1.18: while the elements of some sets have names like 1,2,3, they could equally well be called "fred", "ginger", and "roger". A partition of a finite set \\(A\\) is determined by an onto function (=surjection) from \\(f: A \to P\\) where \\(P\\) is any finite set. This is explained starting with Remark 1.16 in _[Seven Sketches](http://math.mit.edu/~dspivak/teaching/sp18/7Sketches.pdf)_. My question is when two such functions determine the same partition. The answer is actually hiding in the book.
  • 5.
    edited April 2018

    Thank you John. It seems, I incorrectly thought that P (and Q) containing the partitions of A, are both orderable under the 'connectivity function V' -- and that, I thought, was the key 'ingredient' in comparing f and g (without looking and checking that P and Q are isomorphic).

    Given your hint, and looking at remark 1.16. Should the answer be simply: f and g determine the same partitions, if P and Q are isomorphic to each other?

    Comment Source:Thank you John. It seems, I incorrectly thought that P (and Q) containing the partitions of A, are both orderable under the 'connectivity function V' -- and that, I thought, was the key 'ingredient' in comparing f and g (*without* looking and checking that P and Q are isomorphic). Given your hint, and looking at remark 1.16. Should the answer be simply: *f* and *g* determine the same partitions, if P and Q are isomorphic to each other?
  • 6.

    Not quite. Saying that \(P\) and \(Q\) are isomorphic to each other says that the two partitions have the same number of parts.

    Comment Source:Not quite. Saying that \\(P\\) and \\(Q\\) are isomorphic to each other says that the two partitions have the same number of parts.
  • 7.
    edited April 2018

    Thank you. In your reply #6, you said that P and Q are two partitions.

    That's not what I thought, P and Q where in your original question.

    Puzzle. Given two surjections \(f: A \to P\), \(g: A \to Q\), when do they determine the same partition of \(A\)?

    By A, I understood (as an example), the set of 3 elements filled-circle, empty-circle and the star. By P, I understood to be the set of all partitions that result from partitioning A. Reffering back to my picture, my picture in comment 1,\(P={{p_1,p_2, p_3,p_4,p_5}} \). Which is also why I thought, P can have an ordering function (eg the connectivity V, and the Hasse diagram was that representing that ordering). And its cardinality of P was 5.

    I think this were my understand was faulty, as, perhaps, you meant P to be just a letter denoting some other set that's different from A , with surjective map from A.

    Then I tried to justify Q in the following way:

    By Q, I understood another set, that contained all possible partitions of A (just like P), but mapped to a different 'container' objects (with same cardinality as P).

    For a contrived example, let say A were a set of different types apples (one of each type), P would be all the possible baskets that the apple-types could be partitioned, and Q would be something other than baskets. And, so that, thinking justified why f and g could be different in the first place, even both produced the same sets with cardinality 5

    So I interpreted your question as: P and Q are sets, each representing all the partitions of A. f is a function that creates partitions of A and 'stores them' in P. That means, as example that f has to, on its own be a set of functions containing \((f_1,f_2,f_3,f_4,f_5)\). In my mind, then, the question was: can we look at 'insides' or the 'maps' of g and determine if they it would produce the same set of all partitions of A, but in the containers of Q.

    Even writing the above, now, seems like I had applied a 'big stretch of imagination' to what was asked :-).


    Correct me if I am wrong, still, but by P you (and the book authors in remark 1.16) meant any set with a surjective map from A onto it (not the set of all partitions of A, and nothing to do with Ex 1.18 set P with the Hasse graph).

    In that context, you were asking, in the puzzle: when these surjections f and g partition A in the same way. And 'same way' means, that f creates the same 'subsets' of A as g. Where a 'subset' of A - is a set of elements in A that end up (mapped) in the same element p of P by f (or into q of Q, by g).

    -- If the above, corrected interpretation if the question is right. Then, here is how I would answer:

    Puzzle. Given two surjections \(f: A \to P\), \(g: A \to Q\), when do they determine the same partition of \(A\)?

    The two surjections will determine the same partition of A, if there exists a function h, that maps an elements of P into Q. Such that if \(h(p)=q \), there is an the reverse of the function of h, \(h^{-1}\) maps that q into the original p in P ( that is, \(h^{-1}(q)=p \) ).

    I am not sure it is right to call it that, but I would call h to be an equivalence relation between P and Q. I am hesitating on this, because it seems like this function really need to exist for subset of elements in P and Q that are the images of f and g, respectively (not the whole codomains P and Q).

    Comment Source:Thank you. In your reply #6, you said that P and Q are two partitions. That's not what I thought, P and Q where in your original question. >**Puzzle.** Given two surjections \\(f: A \to P\\), \\(g: A \to Q\\), when do they determine the same partition of \\(A\\)? By A, I understood (as an example), the set of 3 elements filled-circle, empty-circle and the star. By P, I understood to be the set of **all** partitions that result from partitioning A. Reffering back to my picture, my picture in comment 1,\\(P={{p_1,p_2, p_3,p_4,p_5}} \\). Which is also why I thought, P can have an ordering function (eg the connectivity V, and the Hasse diagram was that representing that ordering). And its cardinality of P was 5. I think this were my understand was faulty, as, perhaps, you meant P to be just a letter denoting some other set that's different from A , with surjective map from A. Then I tried to justify Q in the following way: By Q, I understood another set, that contained all possible partitions of A (just like P), but mapped to a different 'container' objects (with same cardinality as P). For a contrived example, let say A were a set of different types apples (one of each type), P would be all the possible baskets that the apple-types could be partitioned, and Q would be something other than baskets. And, so that, thinking justified why f and g could be different in the first place, even both produced the same sets with cardinality 5 So I interpreted your question as: P and Q are sets, each representing *all* the partitions of A. f is a function that creates partitions of A and 'stores them' in P. That means, as example that f has to, on its own be a set of functions containing \\((f_1,f_2,f_3,f_4,f_5)\\). In my mind, then, the question was: can we look at 'insides' or the 'maps' of *g* and determine if they it would produce the same set of *all* partitions of A, but in the containers of Q. Even writing the above, now, seems like I had applied a 'big stretch of imagination' to what was asked :-). --- Correct me if I am wrong, still, but by P you (and the book authors in remark 1.16) meant *any* set with a surjective map from A onto it (not the set of all partitions of A, and nothing to do with Ex 1.18 set P with the Hasse graph). In that context, you were asking, in the puzzle: when these surjections *f* and *g* partition A in the same way. And 'same way' means, that *f* creates the same 'subsets' of A as *g*. Where a 'subset' of A - is a set of elements in A that end up (mapped) in the same element *p* of P by *f* (or into *q* of Q, by *g*). -- If the above, corrected interpretation if the question is right. Then, here is how I would answer: >**Puzzle.** Given two surjections \\(f: A \to P\\), \\(g: A \to Q\\), when do they determine the same partition of \\(A\\)? The two surjections will determine the same partition of A, if there exists a function *h*, that maps an elements of P into Q. Such that if \\(h(p)=q \\), there is an the reverse of the function of h, \\(h^{-1}\\) maps that *q* into the original *p* in P ( that is, \\(h^{-1}(q)=p \\) ). I am not sure it is right to call it that, but I would call *h* to be an equivalence relation between P and Q. I am hesitating on this, because it seems like this function really need to exist for subset of elements in P and Q that are the images of *f* and *g*, respectively (not the whole codomains P and Q).
  • 8.

    Puzzle. Given two surjections \(f: A \to P\), \(g: A \to Q\), when do they determine the same partition of \(A\)?

    I am not sure what type of answer John is expecting here. One possibility is to say that we want \(f(a) = f(a') \Leftrightarrow g(a) = g(a') \) for all \(a \in A\), but that is not very CT-like. Another possibility is to say that there must exist an isomorphism \(h: P \rightarrow Q\) such that \(h \circ f = g\) (and thus also \(f = h^{-1}\circ g\)).

    Comment Source:**Puzzle.** Given two surjections \\(f: A \to P\\), \\(g: A \to Q\\), when do they determine the same partition of \\(A\\)? I am not sure what type of answer John is expecting here. One possibility is to say that we want \\(f(a) = f(a') \Leftrightarrow g(a) = g(a') \\) for all \\(a \in A\\), but that is not very CT-like. Another possibility is to say that there must exist an isomorphism \\(h: P \rightarrow Q\\) such that \\(h \circ f = g\\) (and thus also \\(f = h^{-1}\circ g\\)).
  • 9.
    edited April 2018

    Regarding the Puzzle. Denote by \(f^*\) the preimage of \(f\), for any function \(f\). Then surjections \(f : A \to P\) and \(g : A \to Q\) determine the same partition of \(A\) iff for all \(a \in A\) we have \(f^*(\{f(a)\}) = g^*(\{g(a)\})\).

    This is almost too literal of an answer, since \(f(\cdot)\) gives exactly the associated part label in \(P\), and \(f^*(\{\cdot\})\) takes this part label to the part it denotes; and if the different label sets identify the same set of parts, then the partitions are the same.

    I rather prefer Valter's isomorphism-based answer, even if it might take some more thought to produce a clean proof. There does seem to be something functorial about it: we aren't just mapping between \(P\) and \(Q\), but also between \(A \to P\) and \(A \to Q\), making sure that \(f \cong g\).

    Comment Source:Regarding the **Puzzle.** Denote by \\(f^\*\\) the preimage of \\(f\\), for any function \\(f\\). Then surjections \\(f : A \to P\\) and \\(g : A \to Q\\) determine the same partition of \\(A\\) iff for all \\(a \in A\\) we have \\(f^\*(\\{f(a)\\}) = g^\*(\\{g(a)\\})\\). This is almost too literal of an answer, since \\(f(\cdot)\\) gives exactly the associated part label in \\(P\\), and \\(f^\*(\\{\cdot\\})\\) takes this part label to the part it denotes; and if the different label sets identify the same set of parts, then the partitions are the same. I rather prefer Valter's isomorphism-based answer, even if it might take some more thought to produce a clean proof. There does seem to be something functorial about it: we aren't just mapping between \\(P\\) and \\(Q\\), but also between \\(A \to P\\) and \\(A \to Q\\), making sure that \\(f \cong g\\).
  • 10.

    I add some details on the proof for the puzzle below:

    Suppose that there exists an isomorphism \(h: P \rightarrow Q\) such that \(h \circ f = g\) - and thus also \(f = h^{-1}\circ g\). If \( f(a) = f(a') \), then \( (h\circ f)(a) = (h\circ f)f(a') \), hence \( g(a) = g(a') \); similarly in the opposite direction. So we have \(f(a) = f(a') \Leftrightarrow g(a) = g(a') \); this means that \( f \) and \( g \) define the same equivalence relation on \(A\), hence the same partition. So the existence of \(h\) is sufficient.

    Conversely, suppose that \( f \) and \( g \) define the same partition on \(A\). Consider an element \(A_i \) of this partition; then all elements \(a \in A_i \) map into the same \(p_i = f(a) \in P\) and into the same \(q_i = g(a) \in Q\); similarly for all other elements of the partition. Define \(h(p_i) = q_i\); since the functions are surjections, \(h\) is defined in all of \(P\) and is a surjection; it remains to show that it is an injection. Suppose \(h(p_i)=h(p_j)=q\) and consider the partition elements \(A_i\) and \(A_j\) corresponding to \(p_i\) and \(p_j\). By construction, all elements of \(A_i\) map into \(p_i\) via \(f\) and into \(h(p_i)=q\) via \(g\); similarly, all elements of \(A_j\) map into \(p_i\) via \(f\) and into \(h(p_i)=q\) via \(g\). This means that \(A_i\) and \(A_j\) are equivalent with respect to \(g\), hence they must also be equivalent with respect to \(f\) (since we are now assuming that the two functions define the same partition), i.e., \(f\) must send all of them to the same element \(p \in P\) so \(p_i = p_j =p\), which concludes the proof.

    Comment Source:I add some details on the proof for the puzzle below: Suppose that there exists an isomorphism \\(h: P \rightarrow Q\\) such that \\(h \circ f = g\\) - and thus also \\(f = h^{-1}\circ g\\). If \\( f(a) = f(a') \\), then \\( (h\circ f)(a) = (h\circ f)f(a') \\), hence \\( g(a) = g(a') \\); similarly in the opposite direction. So we have \\(f(a) = f(a') \Leftrightarrow g(a) = g(a') \\); this means that \\( f \\) and \\( g \\) define the same equivalence relation on \\(A\\), hence the same partition. So the existence of \\(h\\) is sufficient. Conversely, suppose that \\( f \\) and \\( g \\) define the same partition on \\(A\\). Consider an element \\(A_i \\) of this partition; then all elements \\(a \in A_i \\) map into the same \\(p_i = f(a) \in P\\) and into the same \\(q_i = g(a) \in Q\\); similarly for all other elements of the partition. Define \\(h(p_i) = q_i\\); since the functions are surjections, \\(h\\) is defined in all of \\(P\\) and is a surjection; it remains to show that it is an injection. Suppose \\(h(p_i)=h(p_j)=q\\) and consider the partition elements \\(A_i\\) and \\(A_j\\) corresponding to \\(p_i\\) and \\(p_j\\). By construction, all elements of \\(A_i\\) map into \\(p_i\\) via \\(f\\) and into \\(h(p_i)=q\\) via \\(g\\); similarly, all elements of \\(A_j\\) map into \\(p_i\\) via \\(f\\) and into \\(h(p_i)=q\\) via \\(g\\). This means that \\(A_i\\) and \\(A_j\\) are equivalent with respect to \\(g\\), hence they must also be equivalent with respect to \\(f\\) (since we are now assuming that the two functions define the same partition), i.e., \\(f\\) must send all of them to the same element \\(p \in P\\) so \\(p_i = p_j =p\\), which concludes the proof.
  • 11.

    I was hesitating to look for (or state as a requirement ) for isomorphism between P and Q, or even a full equivalence relation. Because, I thought, P and Q do not have to even the same number of elements. They just need to have this equivalence between elements that map from A into them by f and g.

    Comment Source:I was hesitating to look for (or state as a requirement ) for isomorphism between P and Q, or even a full equivalence relation. Because, I thought, P and Q do not have to even the same number of elements. They just need to have this equivalence between elements that map from A into them by *f* and *g*.
  • 12.
    edited April 2018

    If \(P\) and \(Q\) don't have the same number of elements, then the number of parts in the partitions induced by \(f\) and \(g\) cannot be the same. This is because \(P\) and \(Q\) play the role of "part label" sets: there is one part in the partition for every element in \(P\). (This is most clear in the case of finite sets, but I'm pretty sure this can be formalized in a way compatible with infinite sets too.)

    As a degenerate case, consider any two surjections \(f : A \to \{1\}\) and \(g : A \to \{1, 2\}\). The former defines a trivial partition (the blob), whereas the latter cuts \(A\) into two parts.

    (This is backed up somewhat by #6, where John notes that the presence of an isomorphism shows that the partitions have the same number of parts. I think the key ingredient missing at that time was the relation \(h \circ f = g\), which guarantees not just the same number of parts, but also the same contents within those parts.)

    Comment Source:If \\(P\\) and \\(Q\\) don't have the same number of elements, then the number of parts in the partitions induced by \\(f\\) and \\(g\\) cannot be the same. This is because \\(P\\) and \\(Q\\) play the role of "part label" sets: there is one part in the partition for every element in \\(P\\). (This is most clear in the case of finite sets, but I'm pretty sure this can be formalized in a way compatible with infinite sets too.) As a degenerate case, consider any two surjections \\(f : A \to \\{1\\}\\) and \\(g : A \to \\{1, 2\\}\\). The former defines a trivial partition (the blob), whereas the latter cuts \\(A\\) into two parts. (This is backed up somewhat by #6, where John notes that the presence of an isomorphism shows that the partitions have the same number of parts. I think the key ingredient missing at that time was the relation \\(h \circ f = g\\), which guarantees not just the same number of parts, but also the same contents within those parts.)
  • 13.

    Thx Jonathan. Ok, I think I see that P and Q need to have same number of elements.
    This, I think, stems from the fact that a surjection requires that every element in the set P and Q, to have its domain (or pre-image) in the A. So initially, I thought, say in your 'degenerate case', I could have {1,2,3,11} for P and {1,2,3,25,100} for Q. But then f and g would not be surjections, as there is no element in A that maps in to 3,11 or 3,25, 100.

    Comment Source:Thx Jonathan. Ok, I think I see that P and Q need to have same number of elements. This, I think, stems from the fact that a surjection requires that every element in the set P and Q, to have its domain (or pre-image) in the A. So initially, I thought, say in your 'degenerate case', I could have {1,2,3,11} for P and {1,2,3,25,100} for Q. But then *f* and *g* would not be surjections, as there is no element in A that maps in to 3,11 or 3,25, 100.
  • 14.
    edited April 2018

    Vladislav wrote:

    In your reply #6, you said that \(P\) and \(Q\) are two partitions.

    No, I did not say that. In my puzzle \(P\) and \(Q\) are not partitions. They are sets. A surjection \(f : A \to P\) determines a partition of the set \(A\) as explained in Remark 1.16 of Seven Sketches. Each element \(p \in P\) determines a part of this partition: namely, the subset of \( \{ a \in A: f(a) = p \} \). So, as Jonathan nicely put it, the elements of \(P\) are the "part labels".

    (Later you seem to have gotten everything figured out quite nicely, but I wanted to correct this one thing.)

    Comment Source:Vladislav wrote: > In your reply #6, you said that \\(P\\) and \\(Q\\) are two partitions. No, I did not say that. In my puzzle \\(P\\) and \\(Q\\) are not partitions. They are sets. A surjection \\(f : A \to P\\) determines a partition of the set \\(A\\) as explained in Remark 1.16 of _Seven Sketches_. Each element \\(p \in P\\) determines a part of this partition: namely, the subset of \\( \\{ a \in A: f(a) = p \\} \\). So, as Jonathan nicely put it, the elements of \\(P\\) are the "part labels". (Later you seem to have gotten everything figured out quite nicely, but I wanted to correct this one thing.)
  • 15.
    edited April 2018

    Valter wrote:

    I am not sure what type of answer John is expecting here.

    Congratulations - you guessed the answer I was expecting! Given two surjections \(f: A \to P\), \(g: A \to Q\), they determine the same partition of \(A\) iff there is isomorphism \(h: P \rightarrow Q\) such that \(h \circ f = g\).

    (Normally I would draw this as a little commutative triangle, but it's a bit of a nuisance here.)

    Comment Source:Valter wrote: > I am not sure what type of answer John is expecting here. Congratulations - you guessed the answer I was expecting! Given two surjections \\(f: A \to P\\), \\(g: A \to Q\\), they determine the same partition of \\(A\\) iff there is isomorphism \\(h: P \rightarrow Q\\) such that \\(h \circ f = g\\). (Normally I would draw this as a little commutative triangle, but it's a bit of a nuisance here.)
  • 16.
    edited April 2018

    You can see the kind of triangle I'm talking about here:

    This is how category theorists would talk about this business:

    We say a function \(f : A \to P\) is an object in the category of sets under \(A\). Given two sets under \(A\), say \(f : A \to P\) and \(g: A \to Q\), we say a morphism from one to the other is a function \(h: P \to Q\) such that \(h \circ f = g\). If \(h\) is an isomorphism, we say \(f : A \to P\) and \(g: A \to Q\) are isomorphic in the category of sets under \(A\).

    All this is just to say that the answer Valter gave is the sort that would make a category theorist say "Oh good - this is an example of a familiar concept!"

    Comment Source:You can see the kind of triangle I'm talking about here: * nLab, [Under category](https://ncatlab.org/nlab/show/under+category). This is how category theorists would talk about this business: We say a function \\(f : A \to P\\) is an object in the category of **sets under \\(A\\)**. Given two sets under \\(A\\), say \\(f : A \to P\\) and \\(g: A \to Q\\), we say a morphism from one to the other is a function \\(h: P \to Q\\) such that \\(h \circ f = g\\). If \\(h\\) is an isomorphism, we say \\(f : A \to P\\) and \\(g: A \to Q\\) are isomorphic in the category of sets under \\(A\\). All this is just to say that the answer Valter gave is the sort that would make a category theorist say "Oh good - this is an example of a familiar concept!"
  • 17.

    (Normally I would draw this as a little commutative triangle, but it's a bit of a nuisance here.)

    I thought I'd give it a shot. Would this be an accurate representation?

    Comment Source:> (Normally I would draw this as a little commutative triangle, but it's a bit of a nuisance here.) I thought I'd give it a shot. Would this be an accurate representation? ![](https://i.imgur.com/Z70TcqN.png)
Sign In or Register to comment.