It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.3K
- Chat 498
- Study Groups 16
- Petri Nets 7
- Epidemiology 3
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 52
- MIT 2020: Lectures 21
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 65
- Azimuth Code Project 110
- Statistical methods 2
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 707

Options

## Comments

Here is my entry

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.

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

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\)?`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\\)?`

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

fandg, 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,

fandg, 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' ...

`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' ...`

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.

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

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 (

withoutlooking and checking that P and Q are isomorphic).Given your hint, and looking at remark 1.16. Should the answer be simply:

fandgdetermine the same partitions, if P and Q are isomorphic to each other?`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?`

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

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

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.

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

allpartitions 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

allthe 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' ofgand determine if they it would produce the same set ofallpartitions 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

anyset 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

fandgpartition A in the same way. And 'same way' means, thatfcreates the same 'subsets' of A asg. Where a 'subset' of A - is a set of elements in A that end up (mapped) in the same elementpof P byf(or intoqof Q, byg).-- If the above, corrected interpretation if the question is right. Then, here is how I would answer:

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 thatqinto the originalpin P ( that is, \(h^{-1}(q)=p \) ).I am not sure it is right to call it that, but I would call

hto 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 offandg, respectively (not the whole codomains P and Q).`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).`

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\)).

`**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\\)).`

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\).

`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\\).`

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.

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

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

fandg.`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*.`

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

`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.)`

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

fandgwould not be surjections, as there is no element in A that maps in to 3,11 or 3,25, 100.`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.`

Vladislav wrote:

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

`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.)`

Valter wrote:

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

`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.)`

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

`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!"`

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

`> (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)`