Options

Exercise 37 - Chapter 1

edited April 2018 in Exercises
  1. For any set \(S\) there is a coarsest partition, having just one part. What surjective function does it correspond to?

  2. There is also a finest partition, where everything is in its own partition. What surjective function does it correspond to?

Comments

  • 1.
    edited May 2018

    #1. The constant function, taking all elements to the terminal set, isomorphic with {1}.

    Comment Source: #1. The constant function, taking all elements to the terminal set, isomorphic with {1}.
  • 2.
    1. This one is obviously the surjective function going from S --> 1
    2. The obvious answer is the bijective function going from S <--> S. But for some reason, the absurd function 0 --> S also seems like it can create total discrete partitions although it isn't function at all. Am I crazy or mistaken?
    Comment Source:1. This one is obviously the surjective function going from S --> 1 2. The obvious answer is the bijective function going from S <--> S. But for some reason, the absurd function 0 --> S also seems like it can create total discrete partitions although it isn't function at all. Am I crazy or mistaken?
  • 3.
    edited May 2018

    #2. The identity function, it is also injective. Takes every part/object to unique objects.

    Comment Source: #2. The identity function, it is also injective. Takes every part/object to unique objects.
  • 4.
    1. Since there is only one part, it is the surjective function onto a single part-label, call it 1
    2. Since there is one part-label per single-member part, the function must be in bijection with the part-labels, and the identity function will do, as in Fredrick's answer.
    Comment Source:1. Since there is only one part, it is the surjective function onto a single part-label, call it 1 2. Since there is one part-label per single-member part, the function must be in bijection with the part-labels, and the identity function will do, as in Fredrick's answer.
  • 5.
    edited April 2018

    #2 Michael, the absurd function may not count as surjective, since to be surjective asks for every element of the co-domain to be mapped to by at least one member of the domain, but the empty set has not one element to spare! Also, since the domain is not S, I don't think you could get a useful notion of partition of S from the preimages of the absurd function.

    Remark 1.16 in the book is the first time we meet the relation between surjective functions and partitions in Chapter 1.

    Comment Source:\#2 Michael, the absurd function may not count as surjective, since to be surjective asks for every element of the co-domain to be mapped to by at least one member of the domain, but the empty set has not one element to spare! Also, since the domain is not S, I don't think you could get a useful notion of partition of S from the preimages of the absurd function. Remark 1.16 in the book is the first time we meet the relation between surjective functions and partitions in Chapter 1.
  • 6.
    edited April 2018

    Allan Erskine

    I see your point and realize that \( 0 \rightarrow S \) wouldn't be a appropriate function in the traditional sense. I guess my question really is then does \( 0 \rightarrow S \) generate \( S \)?

    Comment Source:Allan Erskine I see your point and realize that \\( 0 \rightarrow S \\) wouldn't be a appropriate function in the traditional sense. I guess my question really is then does \\( 0 \rightarrow S \\) generate \\( S \\)?
  • 7.

    Michael, the usual sense in which an equivalence relation is determined by a function is by identifying any elements which map to the same value. (The partition is then the set of equivalence classes.) This only works for partitioning the domain relative to the codomain, so \(0 \to S\) would have to generate a partition on \(0\), not on \(S\). We could consider a different construction, in which elements of S are identified if they're mapped to by the same input, but this gives a discrete partition for all functions, not just \(0 \to S\). This is because for a function to be a function, an input can only map to one output; therefore no two values in the codomain can be mapped to by a single value in the domain. Relative to this alternative construction, \(0 \to S\) is not particularly special.

    Comment Source:Michael, the usual sense in which an equivalence relation is determined by a function is by identifying any elements which map to the same value. (The partition is then the set of equivalence classes.) This only works for partitioning the domain relative to the codomain, so \\(0 \to S\\) would have to generate a partition on \\(0\\), not on \\(S\\). We could consider a different construction, in which elements of S are identified if they're mapped to by the same input, but this gives a discrete partition for _all_ functions, not just \\(0 \to S\\). This is because for a function to be a function, an input can only map to one output; therefore no two values in the codomain can be mapped to by a single value in the domain. Relative to this alternative construction, \\(0 \to S\\) is not particularly special.
  • 8.

    Shouldn't this be Exercise 37?

    Comment Source:Shouldn't this be Exercise 37?
  • 9.

    Charles: There has been some relabeling of exercises in recent drafts. I think you'll find that nearly every exercise number here is now off by 2 or more.

    Comment Source:Charles: There has been some relabeling of exercises in recent drafts. I think you'll find that nearly every exercise number here is now off by 2 or more.
Sign In or Register to comment.