4
$\begingroup$

I am wondering whether the category of sets, $\mathbf{Set}$, and the category of groups, $\mathbf{Grp}$, are well defined or not.

Suppose we choose a singleton $\{a\}$ from $\mathbf{Set}$. And suppose we choose a singleton $\{b\}$ from $\mathbf{Set}$. How could we possibly know if we have chosen the same singleton or not?

Similarly, if we refer to a singleton $\{a\}$, then how could we possibly refer to it a second time and be convinced that it is indeed the same singleton?

How can I know if $\{\text{“horse”}\}$ and $\{\text{“caballo”}\}$ are different singletons, or simply two expressions of the same singleton?

The same questions come up with trivial groups. Suppose I choose two trivial groups. How do I know if I have chosen the same one twice or not?

And how can I tell whether or not the category $\mathbf{Set}$ contains multiple instances of the same singleton?

It seems that there is no possible language that could make sense of the objects of $\mathbf{Set}$. In that case, it seems fair to admit that $\mathbf{Set}$ is, on some level, ill defined. Please correct me! or please affirm me.

A similar question was asked earlier, How to treat isomorphic objects in a category?, but I don't think the answers address my concerns.

Personally, it would make sense to me if the objects in $\mathbf{Set}$ that are equivalent were defined to be equal, as sets. But that's apparently not the way it works in category theory. You can have many distinct sets that are all equivalent, from what I understand.

$\endgroup$
8
  • 8
    $\begingroup$ Yes, they are well defined. The question is very unclear. $\{a\}$ is the same singleton as $\{b\}$ if and only if $a=b$. the next example you give suggests the question is philosophical rather than mathematical. $\endgroup$ Feb 11, 2020 at 22:26
  • 1
    $\begingroup$ How could you possibly know if a = b ? Indeed, I only used letters to try to communicate my point. I can't imagine how there could be a system that would describe all possible singletons. Note that in set theory, all sets are built from operations on the empty set. Does category theory assume likewise? $\endgroup$ Feb 11, 2020 at 22:46
  • 5
    $\begingroup$ @AndriusKulikauskas: Category theory is not a separate thing from set theory in the way that you seem to imply. Category theory, like all of mathematics, is typically formulated within the logical foundations of set theory. $\endgroup$ Feb 11, 2020 at 23:13
  • $\begingroup$ In any case, this seems to be essentially a duplicate of math.stackexchange.com/questions/3054271/… $\endgroup$ Feb 11, 2020 at 23:19
  • 3
    $\begingroup$ "Category theory as an alternative to set theory" is a deeply misleading notion which tends to be parroted by people who have no idea how the foundations of math work. It simply does not make sense to use the phrase "in category theory" in the way that you are doing because category is not a self-contained foundational system. $\endgroup$ Feb 12, 2020 at 14:51

6 Answers 6

18
$\begingroup$

One of the strengths of category theory is that indeed it gives a convenient framework to define all sorts of notions of "equivalence", some stronger than others.

For instance, you have the notion of isomorphism between objects of the same category: in the category of sets, being isomorphic means having the same cardinality; in the category of groups, it is having the same structure as groups. So all trivial groups are indeed "equivalent" in this sense.

On the other hand, there is one notion that does not change meaning within category theory: equality. Equality is hardwired into mathematics (at least in the framework commonly used by contemporary mathematicians): two objects are equal if they are, very literally, the same. It is a primitive notion. So two singletons $\{a\}$ and $\{b\}$ are always isomorphic in the category of sets, but they are equal only when they are the very same set, meaning that they have the same elements (this is what characterizes a set), so in this case meaning that $a=b$.

Your example with words is sort of non-mathematical. If you define words as sequences of symbols, then "horse" is not the same word as "caballo", so the sets $\{\text{"horse"}\}$ and $\{\text{"caballo"}\}$ are different. If you define a word as a sort of semantic equivalence class, well... give me a correct mathematical definition of what it means and maybe I can say whether "caballo" and "horse" are the same. But the problem here is not with the category of sets, it is that you usage of words as objects is not very well defined.

$\endgroup$
5
  • $\begingroup$ @Captain_Lama, may I ask, what is a set? What are the possible elements of a set? $\endgroup$ Feb 12, 2020 at 7:24
  • $\begingroup$ @Captain_Lama, how do we know if two singletons are simply two instances of the same singleton, or two copies of the same singleton, or in fact are the same singleton? If I define a copy of a set, how do I know which is the copy and which is the original? How do I know they are the same set or not? If I refer to a set, how do I know whether I am refering to the set or to a reference to the set? $\endgroup$ Feb 12, 2020 at 7:49
  • 8
    $\begingroup$ @AndriusKulikauskas It sounds like you've got a programming language background. At least in usual logics in math there is no notion of copies and references. If $a=b$ in math, there is no way to distinguish them anymore. At all places where writing $a$ is valid, instead writing $b$ is valid as well. There cannot be more than one instance of the same object, or, rather let's say that within math you could not detect this since if they are equal, they are indistinguishable. $\endgroup$
    – ComFreek
    Feb 12, 2020 at 9:07
  • $\begingroup$ @AndriusKulikauskas You can have a look at ZF set theory for a commonly used theory on how one could define sets -- mind you, there are many other set theories out there. $\endgroup$
    – ComFreek
    Feb 12, 2020 at 9:11
  • $\begingroup$ @AndriusKulikauskas If you're looking for a collection in mathematics that allows for duplicate elements, check out the multiset: en.wikipedia.org/wiki/Multiset $\endgroup$ Feb 12, 2020 at 17:16
6
$\begingroup$

On choosing existential instantiations

Suppose we choose a singleton $\{a\}$ from $\mathbf{Set}$. And suppose we choose a singleton $\{b\}$ from $\mathbf{Set}$. How could we possibly know if we have chosen the same singleton or not?

If you mean the usual equality ($=$) when you say "same"1, then you cannot know.

Compare the following closely related question: let's say we have $\exists x \in \mathbb{N}. x \ \text{even}$ as an assumption lying around. If we use the usual natural deduction calculus rules, we can now apply the "existential elimination" rule to a) get a fresh variable, say $y$, and to b) get the statement $y\ \text{even}$ as a new assumption. Let's apply elimination again on the same statement to again get another fresh variable $z$ and the new assumption $z\ \text{even}$. Can we infer whether $y = z$? No, we cannot.

One could argue you did the same in your question. You assumed $\exists w. \{w\} \in \mathbf{Set}$ and instantiated that twice using fresh variables $a$, $b$.

Similarly, if we refer to a singleton $\{a\}$, then how could we possibly refer to it a second time and be convinced that it is indeed the same singleton?

The same questions come up with trivial groups. Suppose I choose two trivial groups. How do I know if I have chosen the same one twice or not?

Again, you cannot. Compare with $\exists G \in \mathbf{Grp}. G\ \text{trivial}$.

Note that all parts of category theory are invariant under isomorphisms.2 This means that it never matters "which fresh variable" you choose as long as they are guaranteed to be isomorphic. Indeed, all trivial groups are isomorphic, so you can apply existential elimination on $\exists G \in \mathbf{Grp}. G\ \text{trivial}$ as many times as you wish and insert all the acquired fresh variables at arbitrary places and in arbitrary orders into any places expecting trivial groups. Invariance under isomorphisms guarantees you that it doesn't matter.

Equality in math and ZF

Let me explain some part of what equality is in usual math excluding any more advanced topics like homotopy type theory. I would dare to say that all equality signs you have seen so far are the equality sign of first-order logic (FOL). The usually assumed ZF set theory is also a theory over FOL. That means we take FOL as our underlying logic and add the ZF axioms into our context of assumptions.

If two expressions $\varphi$ and $\psi$ are structurally equal (from the POV of the level meta to FOL), then we can deduce $\varphi = \psi$ within the logic. On the other hand, if they are not structurally equal, then generally we are kind of stuck without further axioms in our FOL theory. Consider the following equality which should definitely be true, right? $$\{a \in \mathbb{Z} \ |\ a\ \text{even}\} = \{a \in \mathbb{Z} \ |\ (a+1)\ \text{odd}\}$$

But the LHS and RHS are not structurally equal. Fortunately, if we assume to work in ZF, we can call ZF's axiom of extensionality to the rescue. It offers to reduce equality of sets to memberships within the sets: $$\forall x\ y.\ (\forall z. z \in x \Leftrightarrow z \in y) \Rightarrow x = y$$

Then in turn the membership relation often reduces to equality of objects within a set. Let's say we ask $c \in \{a, b, c, d\}$. Equivalently we can ask whether $c=a \vee c=b \vee c=c \vee c=d$. With that spirit we can say that the axiom of extensionality reduces equality of sets even to equality of members of these sets.

Why we cannot extend equality to isomorphisms (easily)

Now you might ask why we don't do the same with, say, isomorphic groups:

$$\forall \ \text{groups } G\ H.\ (G \ \text{isomorphic to}\ H) \Rightarrow G = H$$

And the reason is that this axiom -- when used in our usual ZF set theory context -- immediately leads to contradictions. To show one easy contraidiction let us denote the underlying set of a group $G$ by $\mathcal{U}(G)$. Then, we can write the following true statement:

Let $G$ be the group of integers under addition. Let $x \in \mathcal{U}(G)$. Then $x \in \mathcal{U}(G)$.

Now pick a group isomorphic to $G$, say, the group generated by some fixed $a$, i.e. $H := \langle a \rangle$. Basic group theory tells us that $G$ and $H$ are isomorphic as groups. Hence, by our tentative axiom we would get $G = H$. This in turn in context of FOL and the usual natural deduction rules means that we can take any true statement and replace occurrences of $G$ by $H$ -- even only at some places.

So let's apply this on the previous true statement to get:

Let $G$ be the group of integers under addition. Let $x \in \mathcal{U}(G)$. Then $x \in \mathcal{U}(H)$.

Note that I replaced the last $G$ by $H$. Now that statement is wrong since $\mathcal{U}(G) = \mathbb{Z}$ but $\mathcal{U}(H) = \{a^i\ |\ i \in \mathbb{Z}\}$.

(On a side note, a much easier example would use the encoding of groups as tuples of the underlying set, the operator and the proofs of the group axioms. Then, from $G = H$ we could immediately deduce the contradiction $\mathcal{U}(G) = \mathcal{U}(H)$. However, to not make the impression that the inconsistencies rely on encodings as tuples, I chose another example.)

Conclusion: In the usual ZF setting we cannot just account for isomorphisms via FOL-built-in equality by adding another axiom. Mind you, the whole business of defining a suitable equality is non-trivial and debatable philosophically. There are some growing branches of mathematics just trying to come up with new foundations and right notions for equality.


1 Particularly in the context of category theory we should be careful here what we mean by "same". Usually, people in that field mean by that "isomorphic" wrt. some category.

2 At least the "morally correct" parts.

$\endgroup$
1
  • $\begingroup$ I appreciate your answer very much, your detail and clarity. I think you are expressing what I have been supposing is the case. I need to think more about this. $\endgroup$ Feb 12, 2020 at 15:52
2
$\begingroup$

It's a very interesting question! This is an "ontological question"; the answer depends on your underlying theory of what things there are and what their relationships are.

If you're working in ZFC or a similar theory (such as NBG, which has proper classes, or TG, in which every set is contained in a universe), then the answer is given by the axiom of extensionality, which states that a set $x$ equals a set $y$ if and only if every element of $x$ is an element of $y$ and vice versa.

So:

Suppose we choose a singleton $\{a\}$ from $\mathbf{Set}$. And suppose we choose a singleton $\{b\}$ from $\mathbf{Set}$. How could we possibly know if we have chosen the same singleton or not?

These two singletons are the same if and only if $a$ is the same as $b$. Depending on the exact manner in which you "chose" these two singletons, it may or may not be possible to determine whether or not they are the same singleton.

Likewise:

How can I know if $\{\text{“horse”}\}$ and $\{\text{“caballo”}\}$ are different singletons, or simply two expressions of the same singleton?

They are different singletons if $\text{“horse”} \ne \text{“caballo”}$ and they are the same singleton if $\text{“horse”} = \text{“caballo”}$. If I saw a mathematician writing about an object $\text{“horse”}$ and an object $\text{“caballo”}$, I would generally assume that those two objects are unequal by definition.

Similarly, if we refer to a singleton $\{a\}$, then how could we possibly refer to it a second time and be convinced that it is indeed the same singleton?

By the axiom of reflexivity, $\{a\} = \{a\}$. (But this only works if, in between the first mention of $\{a\}$ and the second mention of $\{a\}$, you haven't discarded the meaning of the letter $a$ and assigned it a new meaning.)

The same questions come up with trivial groups. Suppose I choose two trivial groups. How do I know if I have chosen the same one twice or not?

A group consists of three components: a set of elements, a distinguished identity element, and an operation. Given a trivial group $G$ and a trivial group $H$, if they have the same set of elements, then the other two components must be the same as well, and so $G$ is the same group as $H$. Alternatively, if they have the same identity element, then the other two components must be the same as well, and so $G$ is the same group as $H$. If, on the other hand, the groups have different sets of elements, or different identity elements, then they are not the same group.

As above, with the singletons $\{a\}$ and $\{b\}$, depending on the exact way you "chose" the two groups, it may or may not actually be possible to determine whether they're the same group or not.

And how can I tell whether or not the category $\mathbf{Set}$ contains multiple instances of the same singleton?

The collection of objects in $\mathbf{Set}$ is a class, and for any thing $x$, either $x$ is an element of the class or it is not an element of the class. Here, "is an element" refers to the elementhood relation $\in$ which comes from the underlying set theory.

There's no mechanism by which a class could "contain multiple instances of the same singleton"; that's not even a well-defined concept.

The above goes for ZFC and similar theories; probably more than 99% of all mathematical practice is done in a theory in which the above holds true.

There are alternative base theories, such as homotopy type theory, in which all of the above answers change. In homotopy type theory, the category $\mathbf{Set}$ only contains one singleton (because there only is one singleton), and the category $\mathbf{Grp}$ only contains one trivial group (because there only is one trivial group). Needless to say, homotopy type theory is weird.

$\endgroup$
1
  • $\begingroup$ Your answer is very helpful, @TannerSwett, thank you! What I am realizing is that in set theory, the axiom of extensionality works in terms of elements. But in category theory, the category Set has no concept of elements. There are just objects (sets) and arrows (set functions). Thus the category Set may be implemented in a variety of set theories, but in principle, it doesn't have to reference any set theory. In the category Set, you know you have singleton because it is a terminal object. Two terminal objects are the same if they have the same identity morphism. $\endgroup$ Feb 13, 2020 at 10:17
1
$\begingroup$

In short: you can't; but that is OK. It is perhaps one of the less intuitive insights of modern mathematics, that you only really need to identify things 'up to isomorphism' - in a sense, when two objects are isomorphic, they are essentially the same.

Take your example from $\mathcal{Set}$. An isomorphism in $\mathcal{Set}$ is a bijection; but what does a bijection actually do? One can say that it simply relabels the elements; the essential nature of a set is nothing more than it cardinality: the number of elements, if the set is finite. A set of three apples is no different from a set of three apples - when we look at sets, we are simply not interested in what the elements are; that is why it set theory and not element theory ;-)

Edit:

The first thing to bear in mind is that mathematics is intensely practical - it is a tool, or perhaps better, a toolbox. Whether the tool is set theory, category theory, group theory or topology, they are just tools. You pick one up, when it fits the job at hand and put it down when you're done.

A set is not something mystical - it is just a handy concept for referring to collections of stuff. Set theory is simply a framework for talking about sets in general - that is, when you are exploring the properties and constructions that are common to all sets, regardless of what the elements are. The fundamental concept to understand in set theory is the membership relation, $\in$ - and there is nothing mysterious about that either; it simply encapsulates the idea that a set consists of its members.

Category theory is also just a tool. It can look somewhat similar to set theory, because in set theory you can construct functions - if you have sets $A$ and $B$ then you can define a function $f \colon A \rightarrow B$ - and in category theory you talk about objects, say $a$ and $b$, with arrows between them: $f \colon a \rightarrow b$. But the focus is completely different; in set theory, the functions are secondary constructions: you have sets, that are defined by the elements they contain, and you can construct functions between sets; in category theory, you focus on the relations between objects. The objects are not important except as something where arrows can start or end; category theory is the study of 'arrow algebra', if you will.

$\endgroup$
6
  • $\begingroup$ Thank you for your answer. I imagine we're on a similar wavelength, for better or worse, perhaps. I am thinking about a set that consists of a horse, cow and pig. Would set theory consider that a set? Well, no, because it is not built up out of the empty set. But it could be mapped to any set with three elements. But what would you map it with, given that its not a set? so there could be no bijection to map it? $\endgroup$ Feb 12, 2020 at 15:55
  • $\begingroup$ In category theory, I imagine that perhaps there could be a set that consists of a horse, cow and pig. You don't have to worry about how the elements are implemented. You should treat the horse, cow and pig as elements, and define set functions accordingly. But then there is absolutely no end to the possible sets we could create because a copy of this set would also be a set in its own right, for example. $\endgroup$ Feb 12, 2020 at 15:59
  • $\begingroup$ Also, I think that this is the whole point of category theory. It leaves this issue undefined and simply gets away with that. As you say, it is working "up to isomorphism" and doesn't get hung up about it. But I'm thinking that this is fundamentally different than having set theoretic foundations. And I'm curious what is lurking under the assumptions. $\endgroup$ Feb 12, 2020 at 16:02
  • 2
    $\begingroup$ @AndriusKulikauskas You write "In category theory, I imagine that perhaps there could be a set that consists of a horse, cow and pig." Category theory is not a replacement for a set theory. If this set was undefinable in your set theory, it is also undefinable in category theory formulated over that set theory. $\endgroup$
    – ComFreek
    Feb 13, 2020 at 7:03
  • $\begingroup$ I am thinking, @CornFreek, the issue is that the category Set has no notion of element. There are only objects (sets) and arrows (set functions). So it is straightforward to have a set consisting of a horse, cow, and pig, because all that the category Set cares about is that this set have well defined arrows (set functions) to all the other sets. Thus the issue of what is a horse, cow or pig never comes up. But what does come up is, What are the possible sets? And the answer is that there are no inherent limits. In that sense, it is completely undefined. $\endgroup$ Feb 13, 2020 at 10:22
1
$\begingroup$

When you denote the sets with the symbolic names "{a}" and "{b}," you are also intrinsically utilizing the labels "a" and "b" as names referring to certain objects. When two symbolic names X and Y, for example, are simply two names with the same referent, then we write "X=Y," which is supposed to mean that the two names refer to the same object. By the definition of equality for sets, the set named "{a}" and the set named "{b}" are the same set when the object named "a" and the object named "b" are the same object. So your question defers to that of when objects are numerically identitical in general, or at least when the objects that are elements of sets are numerically identical. The answer will be context dependent, i.e. it will depend on the nature of the objects or the type of object to which your labels are referring, in so much as the type or nature of the object will determine the properties of that object that constitute its numerical identity.

Language in general, however, is a social construct. You have to agree with your audience about what your symbols mean or else you can't even get off the ground. For example, I can read your question and understand what it means, and try to answer it. But to do that I have to parse your language and assign meanings to the sentences you have written in accordance with the English language, otherwise successful communication with you is impossible. You likewise must be able to comprehend my message here for that communication to occur. Do you understand what I mean?

You have to understand that the letter "a," for example, is the same symbol with the same context-dependent functions as any other letter "a," independent of font or position or time. The same question that you ask could be asked of the symbols you use to refer to an object. For example, how do I know that the symbol you used in referring to the set {a} is even the same symbol you used when referring to a set {a} the second time, let alone whether it is referring to the same object?

The answer is that we both understand each other, we both speak English, and we have social agreements about how we practice communication.

$\endgroup$
0
0
$\begingroup$

In any category, object $b$ is identical to object $a$ if and only if $b$ is the target of the identity morphism $id_a$, which we know must exist for every object $a$.

$\endgroup$
3
  • $\begingroup$ Thank you, @gandalf61, that makes a lot of sense. I will think about that. $\endgroup$ Feb 12, 2020 at 15:47
  • 4
    $\begingroup$ This is a circular answer: when you say "$b$ is the target of the identity morphism $id_a$", the word "is" stands for equality of objects. $\endgroup$ Feb 12, 2020 at 16:08
  • $\begingroup$ For me, this answer helpfully shifts the criteria of identity from the objects to the identity morphism. Thus if two possibly different objects have the same identity morphism, then they are different references (morning star, evening star) to the same object (Venus). In other words, it distinguishes levels, so that there can be a local discrepancy (regarding the objects) which is resolved by inspecting the identity morphism. $\endgroup$ Feb 13, 2020 at 10:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .