Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Relational mathematics

Peiyuan Zhu (Jul 19 2024 at 04:49):

Today I made an interesting discovery. One can use the composition of relations as binary matrices to compute composition in finite categories. For instance, the property that a relation is a category means restricting the relations to those whose all diagonal entires are ones and it is closed under "composition of relations". Then I looked into how to define such as "composition of relations". Clearly, matrix multiplication doesn't make sense. Then I found in the book Relational Mathematics of Gunther Schmidt referenced Schröder. He also said in a footnote "Appendix D.3 shows how difficult it was to arrive at a sufficiently clear concept of quantification suitable for defining composition of relations.". I say ha this is interesting. Then I looked briefly at other parts of his book. He articulates an idea of "homomorphism" as something non-mathematical. That illuminates the exercise of "Galileo and the flight of a bird" in session 1 of the book Conceptual Mathematics by William Lawvere and the quantum logic of Joseph-Maria Jauch. Using relations seems like another way of reasoning in this exercise.

Morgan Rogers (he/him) (Jul 19 2024 at 06:44):

So which part was the discovery?

Rémy Tuyéras (Jul 19 2024 at 10:42):

Peiyuan Zhu said:

For instance, the property that a relation is a category means restricting the relations to those whose all diagonal entires are ones and it is closed under "composition of relations".

There is a semiring $\{0,1\}$ defined by:

• $0*1=1*0=0$
• $1*1=1$
• $0+0=0$
• $1+0= 0+1=1+1=1$

for which I believe compositions of relations are matrix multiplications. In this case, a category would be defined as a matrix $C$ for which $C^2\leq C$ and $\mathsf{Id} \leq C$ hold

Was not sure if that would be of any help to you, but just thought I would mention it

Rémy Tuyéras (Jul 19 2024 at 10:58):

And you can also make a semiring with sets using unions and products (I think), so that you can do something similar with homsets for the categories

Rémy Tuyéras (Jul 19 2024 at 10:59):

But where you would use functions instead of $\leq$

Peiyuan Zhu (Jul 19 2024 at 13:27):

Rémy Tuyéras said:

Peiyuan Zhu said:

For instance, the property that a relation is a category means restricting the relations to those whose all diagonal entires are ones and it is closed under "composition of relations".

There is a semiring $\{0,1\}$ defined by:

• $0*1=1*0=0$
• $1*1=1$
• $0+0=0$
• $1+0= 0+1=1+1=1$

for which I believe compositions of relations are matrix multiplications. In this case, a category would be defined as a matrix $C$ for which $C^2\leq C$ and $\mathsf{Id} \leq C$ hold

Was not sure if that would be of any help to you, but just thought I would mention it

That’s right. I found matrix multiplication doesn’t work with sets that are more than {0,1}. In case anyone hasn’t seen if before, Schröder’s composition is defined as $T=\max_j \min (S_{ij}, R_{jk})$. And then yes we need an inequality <=.

Peiyuan Zhu (Jul 19 2024 at 13:28):

Rémy Tuyéras said:

And you can also make a semiring with sets using unions and products (I think), so that you can do something similar with homsets for the categories

Can you elaborate? Not sure what you mean by this.

Peiyuan Zhu (Jul 19 2024 at 13:30):

Morgan Rogers (he/him) said:

So which part was the discovery?

The discovery is that there’s a way of representing categories as relations. And this connection is quite deep. I suppose every proof do in categories can be done with relations.

Peiyuan Zhu (Jul 19 2024 at 13:31):

One thing that I’d like to confirm though: does anyone thinks the Galileo exercise in Conceptual Mathematics is a precursor to homomorphisms like those mentioned above?

Peiyuan Zhu (Jul 19 2024 at 13:34):

IMG_2304.png

Morgan Rogers (he/him) (Jul 19 2024 at 13:41):

Peiyuan Zhu said:

Morgan Rogers (he/him) said:

So which part was the discovery?

The discovery is that there’s a way of representing categories as relations. And this connection is quite deep. I suppose every proof do in categories can be done with relations.

What does the category $A \rightrightarrows B$ look like as a relation?

Peiyuan Zhu (Jul 19 2024 at 13:47):

It looks to me a key theme of category theory is supervenience relation (for instance, see https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3142092/ where the author quotes “surplus meaning” of Reichenbach as “a hypothesis that something exists, even if that something cannot be measured directly”) or what physicist call “measurement problem”?

Peiyuan Zhu (Jul 19 2024 at 13:47):

Morgan Rogers (he/him) said:

Peiyuan Zhu said:

Morgan Rogers (he/him) said:

So which part was the discovery?

The discovery is that there’s a way of representing categories as relations. And this connection is quite deep. I suppose every proof do in categories can be done with relations.

What does the category $A \rightrightarrows B$ look like as a relation?

Can you equate the two arrows if they have the same input and output?

Morgan Rogers (he/him) (Jul 19 2024 at 14:04):

No.

Peiyuan Zhu (Jul 19 2024 at 14:20):

Ok thanks for mentioning. I’ll think about this. It means that the check needs to be done for every arrow between two objects.

Rémy Tuyéras (Jul 19 2024 at 18:19):

Peiyuan Zhu said:

Rémy Tuyéras said:

And you can also make a semiring with sets using unions and products (I think), so that you can do something similar with homsets for the categories

Can you elaborate? Not sure what you mean by this.

Take two sets $A$ and $B$ and define:

• $A+B = \{x~|~x \in A \textrm{ or }x\in B\}$
• $A \times B = \{(a,b)~|~a \in A\textrm{ and }b \in B\}$

I believe this defines a semiring structure on the objects of $\mathbf{Set}$. Now take a finite set $I$ and take a matrix $M:I \times I \to \mathbf{Set}$ whose coefficients are sets. Therefore, $M(a,b)$ is a set.

You can use the semiring structure (above) to multiply matrices such as $M$. In particular, you have:

$M^2(a,b) = \sum_{c \in I} M(a,c) \times M(c,b) = \{(f,g)~|~\exists c:\,f \in M(a,c)\textrm{ and }g \in M(c,b)\}$

If you now have functions $M^2(a,b) \to M(a,b)$, then you actually have a composition operation (up to associativity and unity axioms).

Rémy Tuyéras (Jul 19 2024 at 18:21):

And you can pass from the context on sets to the semiring $\{0,1\}$ through an emptyness test:

$\mathbf{Set} \to \{0,1\}$
$A \mapsto 0\textrm{ if }A = \emptyset$
$A \mapsto 1\textrm{ if }A \neq \emptyset$

Kevin Carlson (Jul 19 2024 at 20:41):

Well, it’s kind of a semiring. The operations aren’t associative.

Rémy Tuyéras (Jul 19 2024 at 21:00):

Ah yes, the multiplication is not associative, thanks for correcting that!

Rémy Tuyéras (Jul 19 2024 at 21:04):

Associativity would hold if we considered subsets $A$ and $B$ of some disjoint union $\uplus_{n \geq 0} S^n$

Eric M Downes (Jul 20 2024 at 03:56):

Peiyuan Zhu said:

I suppose every proof do in categories can be done with relations.

This would be true for much of the rest of mathematics as well, as every set function is a relation.

If one really wanted to pursue this approach, Freyd and Scedrov’s tome [[Categories, Allegories]] would probably be worthwhile, because despite the heterodox terminology, concerning allegations about Freyd’s personal life, etc.; the “relations are fundamental” standpoint is exactly the approach they take.

Certainly relations make partial operations like $\circ$ simpler to define. I just personally find them distinctly unergonomic, but this is true of much math I have not internalized yet! :)

Certainly relations come up a lot in our semigroup topics seminar. If anyone else is aware of other texts that take a “relations are fundamental” approach to categories, would welcome that, and seems apropos to this topic.

Todd Trimble (Jul 20 2024 at 10:59):

Freyd’s odious personal life

There are well-known allegations out there, but they probably don't bear mentioning here. The weirdnesses of their book of course do.

Eric M Downes (Jul 20 2024 at 11:16):

(I’ve edited my statement to reflect the subjectivity of my knowledge. But if I’m going to recommend a book, and I do think it’s relevant here, I think it’s reasonable for people to have sufficient warning to make their own risk assessments. I also understand my flippancy could amount to prejudicial gossip, which is bad. Hopefully you find my compromise reasonable.)

So do you know other resources, perhaps less advanced, that also take the same approach?

There seems to have been a period, perhaps recurring, where people get really into relations as foundational.

I admit I just convert $X\rho Y$ to a function $XY\overset{\bar{\rho}}{\to}2$ almost immediately. I’m open to the idea that there is wisdom in not doing so (perhaps when studying dagger categories without products?) but it would help to see accounts sharply demonstrating the clarity or utility of thinking in terms of relations.

Todd Trimble (Jul 20 2024 at 11:34):

But if I’m going to recommend a book, and I do think it’s relevant here, I think it’s reasonable for people to have sufficient information to make their own risk assessments.

We may have to disagree on the relevance. I don't believe allegations about someone's personal behavior has any relevance on making evaluations about their scientific work, unless for some reason that behavior would impinge on that work, which I think is not credible here. The writings have to be judged on their own merits.

Eric M Downes (Jul 20 2024 at 13:35):

Thank you for your feedback. It's a complex world, and we each have to make the decisions that seem morally correct to us. There was a discussion on this general topic some months ago. I am happy to shift discussion there if you want to talk about this, so that we don't hijack this thread.

Todd Trimble (Jul 20 2024 at 13:55):

To some degree I think that was a separate issue, although it's not entirely unrelated. Here I'm talking about making a scientific evaluation (e.g., of a book, or of the development of a mathematical theory, etc.) and which criteria should be brought to bear. Over there, there was a question about whether we should be honoring someone who in his personal life was a Nazi, take Witt for example, by naming concepts after him. Freyd's name also came up of course.

[FWIW, I can sympathize with someone who says, "no, I refuse to review that book; he disgusts me", or if they wanted to avoid mentioning you-know-who by any means possible. I don't feel the same way; for me it's all contextual. If someone commits murder and goes to jail for it, but proves a great theorem while in jail, well then, that's at least one good thing they did with their life, and they don't have to be punished in every single sphere.]

Eric M Downes (Jul 20 2024 at 14:57):

Okay, I guess we're talking about this here.

Yeah totally. Judging someone's entire life or works or by their mistakes is cruel and inhumane. Censoring scholarly work out of an emotional reaction is the fastest way to end up in a situation where certain things cannot be said, or can only be said by certain people. That's a toxic environment and horrible and to be avoided. Especially important to avoid that for smart neuro-atypical people who can find social judgement especially painful, and have often been at the nasty end of said judgements just for relating to others differently.

But a scientific evaluation of a scholarly work is not all that's going on here.

Or rather, that evaluation occurs within a social context, the maintenance of which is also important.

To use a different sense of "relational", we are all members of a community, and the health of that community depends on how we relate to one another. If I send the signal, even by accident, that "abuse is beneath discussion" or "these allegations don't matter because the guy who is accused was really smart and we like his work" then I risk telling any abuse victims present that their experiences are unwelcome or worth less, and all the struggles they have to go through to feel safe, to be able to function in professional environments in ways that we might take for granted... well that's all on them, and not our problem. I will not contribute to that, even by accident. (And no one here is trying to do that either! To be 100% clear I am not accusing Todd or anyone else of this at all, people can reach different conclusions than mine and be totally reasonable and good people.)

So, the compromise I make personally is never to elide or censor someone's scholarly work. But also to not elide the uncomfortable stuff, avoid the difficult conversations about potential abuse and bad behavior in any community in which I'm a member, even a junior member like this one. Especially if I'm going to recommend a work, I am going to mention "hey there is this thing about this author I just recommended, just FYI..." ... How to keep that from being prejudicial is a challenge, and maybe I failed in this case. No easy choices with this stuff.

Anyway: Freyd's work is really deep and his articles are generally well-written, even if I find the book I mentioned bizzare and difficult, just be aware of the surrounding miasma and don't get caught unawares.

Peiyuan Zhu (Jul 20 2024 at 15:54):

Thanks, I like the recommendation of Allegories, Categories and will look into it

Peiyuan Zhu (Jul 20 2024 at 17:30):

Does anyone have any extra comment on the homomorphism that I mentioned? I find it quite interesting and I wonder if other examples (category theory, quantum logic, and belief function) I mentioned that I think falls in the same category is correct.

Peiyuan Zhu (Jul 20 2024 at 17:30):

IMG_2312.png
IMG_2313.png

Peiyuan Zhu (Jul 20 2024 at 18:18):

The above paragraphs are from Relational Mathematics of Gunther Schmidt

Peiyuan Zhu (Jul 20 2024 at 18:19):

IMG_2317.png
This is from Probability Calculus of Joseph-Maria Jauch.

Peiyuan Zhu (Jul 20 2024 at 18:20):

IMG_2316.png
And this is from Allocations of Probability of Glenn Shafer.

Peiyuan Zhu (Jul 20 2024 at 18:21):

From William Lawvere Conceptual Mathematics: The part of Galileo’s work which we discussed is really concerned with only a small portion of space, say the immediate neighbourhood of the tower of Pisa. Since the ground might be uneven, what could be meant by saying that two points are at the same level? Try to describe an experiment for deciding whether two nearby points are at the same level, without using ‘height’ (distance from an imaginary plane of reference.) Try to use the most elemen­ tary tools possible.

Peiyuan Zhu (Jul 20 2024 at 18:22):

All of them seem to be talking about the supervenience relation as “something that exists but cannot be measured directly”

Peiyuan Zhu (Jul 20 2024 at 18:24):

IMG_2318.png
Here’s another kind of homomorphism. So it looks like there are many ways of defining it.

Peiyuan Zhu (Jul 20 2024 at 18:27):

To put the idea illuminated in English, here’s an excerpt from the book Dream of Reality.
IMG_2319.png

Peiyuan Zhu (Jul 20 2024 at 18:28):

One talks about how one system is “similar” to another mathematically as “homomorphisms”.

Eric M Downes (Jul 20 2024 at 19:08):

Yes, Lawvere is definitely suggesting a morphism.

The term "Morphism" comes from"homomorphism" from group theory etc; in particular monoid homomorphisms preserve multiplication and the identity. Here I'll just emphasize the former
$\phi:X\to Y$
$\phi(xy)=\phi(x)\phi(y)$
This can be written in purely functional form, given multiplications $\mu:XX\to X$ and $\nu:YY\to Y$ we have
$(1)~~~~~\phi\circ\mu=\nu\circ(\phi\times\phi)$
where I have used the universal property of the product to allows us to express the function $\phi\times\phi:XX\to YY$ that acts "elementwise". This corresponds to the diagram

The first page you posted shows a morphism that preserves a relation called a preorder $\leq$, which must be at least transitive
$x\leq y~ \& ~y\leq z\implies x\leq z$
and reflexive $x\leq x$.
These morphisms $\phi$, as the author notes are called monotonic maps:
$\forall x,y\in X; ~x\leq_X y\implies \phi(x)\leq_Y\phi(y)$.
This can be phrased to look more like (1) above.

Lets define $\leq_S:SS\to 2$ where $2=\set{0,1}$. So $\leq(x,y)=1$ just when $x$ is less than or equal to $y$.

Then a monotonic function $\phi$ almost satisfies
" $\leq_Y\circ(\phi\times\phi)=\leq_X$ "
except we can't quite because we do not know for certain that $\phi$ is strict
$\phi(y)\leq_Y\phi(x)\overset{?}{\implies}y\leq_X x$.
Above that reads implies as in the logical operation.

So we can instead use the order on $2$ (where 1 corresponds to true and 0 corresponds to false) and recall some facts about implication;
$0\implies x$ is vacuously true for all $x$
$1\implies 1$ is true, but $1\not\implies0$.
So we are only concerned with avoiding the case where $1\implies0$, which we can capture with a function mapping $0\mapsto1, 1\mapsto1$. That way, if $\phi(x)\leq\phi(y)$ is false, while $x\leq y$ is true the diagram fails to commute (as it should) but otherwise it succeeds.

This can be captured by taking the constant map $!:2\to1$ followed by the truth map $\top:1\to2$; here $1=\set*$ and $\top(*)=1$. (Is this composite a monotonic map on $2$?)

So we have another diagram

Hopefully that diagram makes clear the essential similarity between the two concepts, of a monoid homomorphism, and a montonic map, both of which are morphisms in their own categories. We can do this because logical implies is a preorder!

Reflect this is really just a "functionalization" of the concept of inequality: it encodes the ideas as functions in the category $\sf Set$ instead of leaving them in logic or undefined. More sophisticated approaches will specify categories of morphisms and objects, etc. but the essential insight is that equalities and inequalities can be expressed using diagrams. If you like the above, you might like Lawvere's other intro-level book Sets for Mathematics, which also teaches the set theory etc one needs for mathematics. It is also much more accessible than the book by Freyd I mentioned.

There is much more that might be said, but it will help us if you can do the work to formulate things into a specific question. Posting pages asks us to do a lot of effort interpreting, and we might not even guess what you actually care about. Meet us halfway!

Eric M Downes (Jul 20 2024 at 21:33):

I have phrased everything as a function, above.

If you want to keep everything as a relation, you would need to define $\leq$ on relations directly, which you should be able to figure out, it is kind of like a 2-morphism.