2
$\begingroup$

I'm kinda lost at one example in Awodey's: Category Theory.

enter image description here

enter image description here

I am trying to check this example, for that, I made a simple example function:

enter image description here

With this, I mean that there is one function $f$ which associates each element of the codomain. In this case, I can't have an inverse function - I'm not sure if this invalidates it being a category, but I faintly believe it does. Because it seems that in this universe of discourse, the arrows are functions. But I guess I could counter this by creating two pseudo-inverse functions (?!) in the following way:

enter image description here

It doesn't seem to violate the rules, except a little doubt for one of them: The definitions of composition. If I compose $f_{1}^{-1} \circ f$, I have:

$$cod(f)=dom(f_{1}^{-1})$$

$$cod(f_{1}^{-1})=dom(f)$$

I believe this is valid because he speaks about codomain instead of image. But it feels weird, $f_{1}^{-1}$ doesn't goes back entirely to $dom(f)$, that is: It doesn't takes all the elements of $dom(f)$.

Or perhaps I'm utterly confused/lost/stupid/in_need_of_help_for_mental_illness and completely missed the point.

$\endgroup$
11
  • 1
    $\begingroup$ Wait, what exactly is your question? And how does it relate to the question in the box you provided? $\endgroup$
    – Stefan Mesken
    Aug 11, 2016 at 21:00
  • 1
    $\begingroup$ The question is whether the collection whose objects are all sets and whose morphisms between any two sets are the restricted morphisms Awodey describes forms a category. In other words: do identity functions satisfy the required property, and are functions with this property closed under composition? Your "PacMan" has almost no relationship to this question. $\endgroup$
    – Kevin Arlin
    Aug 11, 2016 at 21:04
  • 2
    $\begingroup$ $f^{-1}(b)$ just means the inverse image of $b$, the set of points mapping to it. It is not assumed that $f$ is invertible. In the category you're trying to construct, the two-point set should be a single object, whereas your pictures seem to draw it as two separate objects. $\endgroup$
    – Kevin Arlin
    Aug 11, 2016 at 21:05
  • 2
    $\begingroup$ I want to echo what @KevinCarlson said. The notation $f^{-1}(b)$ does not mean "$f$ has an inverse $f^{-1}$ and we apply it to $b$", but rather, $f^{-1}(b)$ is the set of all elements in the domain which map to $b$. So, $f^{-1}(b)$ is a set, not an element. (When $f$ has an inverse, the set $f^{-1}(b)$ is nothing but the set containing the element $f^{-1}(b)$, so when the two notations overlap, they almost perfectly sync up.) $\endgroup$
    – Jason DeVito
    Aug 11, 2016 at 21:13
  • 2
    $\begingroup$ Yes, the pacman you made is a category, as long as you assume identity maps are implicit. Formally, it is $f:\{1,2\}\to\{a\}$ defined by $f(1)=a$ and $f(2)=a$, $f_1:\{a\}\to\{1,2\}$ defined by $f_1(a)=1$, and $f_2:\{a\}\to\{1,2\}$ defined by $f_2(a)=2$. But this is not really relevant to your exercise. $\endgroup$
    – arctic tern
    Aug 11, 2016 at 21:30

2 Answers 2

Reset to default
5
$\begingroup$

The main problem is that the composition of functions with at most two preimages is not necessarily a function with at most two preimages. In this wanna-be category, there does exist an arrow $\{1,2,3,4\}\to\{1,2\}$ (in fact several) and an arrow $\{1,2\}\to\{1\}$, but no arrow from $\{1,2,3,4\}$ to $\{1\}$.

For the restriction with finite pre-images, this problem does not occur, and you can verify that we indeed obtain a category.

$\endgroup$
4
  • $\begingroup$ My best guess was that this is the intended question... I'm wondering what all the gibberish below is about, then. $\endgroup$
    – Stefan Mesken
    Aug 11, 2016 at 21:06
  • $\begingroup$ Where does the $\{1,2,3,4\}$ came from? $\endgroup$
    – Red Banana
    Aug 11, 2016 at 21:10
  • $\begingroup$ From Hagen's head. $\endgroup$
    – arctic tern
    Aug 11, 2016 at 21:15
  • $\begingroup$ I guess I understand your answer. It was confusing because I was considering only two objects. $\endgroup$
    – Red Banana
    Aug 11, 2016 at 22:34
3
$\begingroup$

In this case, I can't have an inverse function - I'm not sure if this invalidates it being a category, but I faintly believe it does.

No. Morphisms in categories don't necessarily have inverses. For instance, the category $\mathsf{Set}$ of sets with functions for morphisms includes functions which have no inverse (i.e. non-bijections). Most categories we work with will include noninvertible morphisms ($\mathsf{Top,Ring,Grp,Mod,Pos}$ etc.).

Your "pseudoinverses" are called right-inverses (since $f\circ f_1=\mathrm{id}$ has $f_1$ on the right), or what I would call a "pre-inverse" (since one applies $f_1$ before $f$ to get the identity map). In any case, these aren't really relevant to your exercise. As is mentioned in the comments, $f^{-1}(b)$ stands for the preimage of $b$ under $f$, i.e. $\{a\in A:f(a)=b\}$, and it is defined (but possibly empty) whether or not $f$ is invertible in the category.

Simple concepts in mathematics tend to come with definitions that are a ready-made checklist of things to verify in order to confirm that the definition applies to something. So if you want to check that sets and functions with fibers bounded in size by $2$ is a category, you look at the properties in the definition of a category and check that each one is true. Does this category include the identity function for every set? Yes.

The key thing is checking that it's closed under composition. Hagen gives the simplest example of how this can fail. Consider the composition of functions $\{1,2,3,4\}\xrightarrow{g}\{a,b\}\xrightarrow{f}\{x\}$ given by

$\hskip 1.5in$ pic

As you can see, $g^{-1}(a)=\{1,2\}$, $g^{-1}(b)=\{3,4\}$ both have cardinality less than or equal to $2$, and $f^{-1}(x)=\{a,b\}$ has cardinality less than or equal to $2$, however $(f\circ g)^{-1}(x)=\{1,2,3,4\}$ has cardinality greater than $2$. This illustrates how functions with fibers bounded by $2$ in size are not closed under composition.

$\endgroup$
5
  • $\begingroup$ So the size of all the sets must be preserved for us to have a morphism? If yes, it's not entirely clear why is that. $\endgroup$
    – Red Banana
    Aug 12, 2016 at 0:48
  • $\begingroup$ @Voyska No idea what you're talking about. In order to verify "sets with functions whose fibers are bounded by $2$" is a category (well, subcategory of $\sf Set$), you would need to verify that given any two morphisms $g:X\to Y$ and $f:Y\to Z$, their composition $f\circ g:X\to Z$ is also a morphism. However, we have exhibited two functions with fibers bounded by $2$ whose composition has a fiber not bounded by $2$, which means "sets with functions whose fibers are bounded by $2$" is not closed under composition, hence not a category. $\endgroup$
    – arctic tern
    Aug 12, 2016 at 0:56
  • $\begingroup$ I kinda understand what you say. The problem is that until that point in the book, he doesn't mention fibers bounded by some $n$. I don't know if he expects the reader to know this beforehand. So with the information he gave until that point, I do not know how to decide if it is or if it is not a category. $\endgroup$
    – Red Banana
    Aug 12, 2016 at 1:25
  • $\begingroup$ @Voyska Yes, the author does mention fibers that are bounded in size. He just doesn't use the word "fiber" like I do. It's right there in the picture: "for all $b\in B$, the subset $f^{-1}(b)\subseteq A$ has at most two elements," i.e. all fibers are bounded in size by $2$. $\endgroup$
    – arctic tern
    Aug 12, 2016 at 2:10
  • $\begingroup$ I guess I understand it now. We must lay all the possible functions - respecting the definition of function and also the property that for each preimage, it must have two elements. If this is it, it's becoming clear now. $\endgroup$
    – Red Banana
    Aug 12, 2016 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.