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: deprecated: logic

Topic: relation theory

Jon Awbrey (Jul 31 2021 at 20:40):

Cf: Survey of Relation Theory

In this take on Relation Theory, relations are viewed from the perspective of combinatorics, in other words, as a topic in discrete mathematics, with special attention to finite structures and concrete set-theoretic constructions, many of which arise quite naturally in applications.  This approach to relation theory is distinct from, though closely related to, its study from the perspectives of abstract algebra on the one hand and formal logic on the other.

Jon Awbrey (Aug 02 2021 at 21:00):

Cf: Relations & Their Relatives • Comment 1

I opened a topic on Relation Theory to discuss the logic of relative terms and the mathematics of relations as they develop from Peirce’s first breakthroughs (1865–1870).  As I have mentioned on a number of occasions, there are radical innovations in this work, probing deeper strata of logic and mathematics than ever before mined and thus undermining the fundamental nominalism of First Order Logic as we know it.

Resource

• Survey of Relation Theory

Morgan Rogers (he/him) (Aug 03 2021 at 09:04):

Hi Jon. You posted a lot of contributions in this format, and it's about time someone engaged with them to see what there is to learn here. I have a few questions.

1. In the linked post on your blog, you claim that Peirce's work "undermines the fundamental nominalism of First Order Logic as we know it". What is the basis for that claim?
2. Peirce's work comes before set theory was developed; do you think set theory provides an adequate formalism in which to discuss "relation theory"?
3. Since this was inspired by other discussions here on Zulip, what insights do you think this can provide into categories of relations (or other category theory material, for that matter)?

Morgan Rogers (he/him) (Aug 03 2021 at 09:09):

(As an aside, I have to say I find it quite strange that you chose the Online Encyclopaedia of Integer Sequences wiki to host all of the related material! How did that come about?)

Jon Awbrey (Aug 04 2021 at 22:45):

Morgan Rogers (he/him) said:

Hi Jon. You posted a lot of contributions in this format, and it's about time someone engaged with them to see what there is to learn here. I have a few questions.

1. In the linked post on your blog, you claim that Peirce's work "undermines the fundamental nominalism of First Order Logic as we know it". What is the basis for that claim?
2. Peirce's work comes before set theory was developed; do you think set theory provides an adequate formalism in which to discuss "relation theory"?
3. Since this was inspired by other discussions here on Zulip, what insights do you think this can provide into categories of relations (or other category theory material, for that matter)?

Thanks for the questions and the opportunity for engagement — the more engagement the better the transmission, so long as no gears get stripped in the process.

As far as the first question goes, I wasn't trying to pick on FOL especially.  What I'm saying applies to any formal system or conceptual framework which assumes a hard and fast ontological distinction between individuals and predicates (generals or universals in the classical argot).  Although the general idea may be shocking in some philosophical cafés, it shouldn't be too outrageous in categorical joints where arrows-only, predicates-only, and element-free styles of jazz are heard.

I have to break here … to be continued …

I linked to a critical passage from Peirce in a previous post.  I'll hunt it up and copy it here.

Morgan Rogers (he/him) (Aug 05 2021 at 08:31):

Does FOL assume a "hard and fast ontological distinction between individuals and predicates", though? Certainly since the advent of (classical) model theory, the interpretation of a relation in a model has been as a subset of a products of basic sorts, meaning that everything can be treated on a single level if so desired, although I suppose it is an abstract rather than concrete level.

Jon Awbrey (Aug 05 2021 at 15:10):

Cf: Relations & Their Relatives • Comment 2

Before I forget how I got myself into this particular briar patch — I mean the immediate occasion, not the long ago straying from the beaten path — it was largely in discussions with Henry Story where he speaks of links between Peirce’s logical graphs and current thinking about string diagrams and bicategories of relations.  Now that certainly sounds like something I ought to get into, if not already witting or otherwise engaged in it, but there are a few notes of reservation I know I will eventually have to explain, so I’ve been working my way up to those.

First I need to set the stage for any properly Peircean discussion of logic and mathematics, and that is the context of triadic sign relations.  I know what you’re thinking, “How can we talk about triadic sign relations before we have a theory of relations in general?”  The only way I know to answer that is by putting my programmer hard-hat on and taking recourse in that practice which starts from the simplest thinkable species of a sort and builds its way back up to the genus, step by step.

Resource

• Survey of Relation Theory

Morgan Rogers (he/him) (Aug 05 2021 at 15:34):

Okay, sure, I can entertain some formal set-up, as long as we don't get bogged down in it. I know what a triadic relation is; what distinguishes a "sign relation" from a generic relation?

Henry Story (Aug 05 2021 at 15:39):

Q: Is a triadic relation $R_3 \subseteq A \times B \times C$ for some types A, B, C ?
or is it a functor from the small category $s, r, p : A \to N$ to Set?

Morgan Rogers (he/him) (Aug 05 2021 at 15:49):

Based on Jon's Resource, it's the former. Without further constraints, the latter includes a lot of things which would typically not be considered relations (consider a functor mapping $N$ to $1$ and $A$ to anything you like, for instance).

Henry Story (Aug 05 2021 at 15:51):

yes, true the latter one is a graph with named arrows.

Jon Awbrey (Aug 05 2021 at 15:54):

Morgan Rogers (he/him) said:

Does FOL assume a "hard and fast ontological distinction between individuals and predicates", though? Certainly since the advent of (classical) model theory, the interpretation of a relation in a model has been as a subset of a products of basic sorts, meaning that everything can be treated on a single level if so desired, although I suppose it is an abstract rather than concrete level.

Thanks, Morgan, you are right, I should not hold any formal system accountable for the uses of its interpreters, and nominal thinking like any other brand of thinking rests in the “i” of the interpreter.  I'll be happy to hear more about other people who view FOL the way you say, as I've been pretty much a loner in my own circles so far.

Over and above their intrinsic beauty as combinatorial species, relations are just the thing I find myself using as models of formulas and theories, and also in another role as the formal languages expressing those theories.

Jon Awbrey (Aug 05 2021 at 16:36):

Cf: Peirce’s 1870 “Logic Of Relatives” • Overview

For people who prefer to Read the Master free of my interpretations, here's a reference and links to the main source I'll be using as a springboard.

• Peirce, C.S. (1870), “Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic”, Memoirs of the American Academy of Arts and Sciences 9, 317–378, 26 January 1870.  Reprinted, Collected Papers (CP 3.45–149), Chronological Edition (CE 2, 359–429).  Online (1) (2) (3).

Morgan Rogers (he/him) (Aug 05 2021 at 16:46):

It sounds like you're building up to something, but I'm hoping I'll get an answer to my other questions at some point..!

Jon Awbrey (Aug 06 2021 at 13:06):

Cf: Relations & Their Relatives • Comment 3

Here's a couple of selections from Peirce's 1870 Logic of Relatives bearing on the proper use of individuals in mathematics, and thus on the choice between nominal thinking and real thinking. 😸

• Mathematical Demonstration & the Doctrine of Individuals • 1
• Mathematical Demonstration & the Doctrine of Individuals • 2

Jon Awbrey (Aug 06 2021 at 19:16):

I'm reworking my initial blog posts on Relations & Their Relatives.  Looking back over them I think they manage to break ground on the most needed concepts in a moderately concrete fashion.  Here is the first one …

Cf: Relations & Their Relatives • 1

Sign relations are special cases of triadic relations in much the same way binary operations in mathematics are special cases of triadic relations.  It amounts to a minor complication that we participate in sign relations whenever we talk or think about anything else but it still makes sense to try and tease the separate issues apart as much as we possibly can.

As far as relations in general go, relative terms are often expressed by slotted frames like “brother of __”, “divisor of __”, and “sum of __ and __”.  Peirce referred to these kinds of incomplete expressions as rhemes or rhemata and Frege used the adjective ungesättigt or unsaturated to convey more or less the same idea.

Switching the focus to sign relations, it’s fair to ask what kinds of objects might be denoted by pieces of code like “brother of __”, “divisor of __”, and “sum of __ and __”.  And while we’re at it, what is this thing called denotation, anyway?

Jon Awbrey (Aug 06 2021 at 19:24):

Resources

• Relation Theory
• Triadic Relations
• Sign Relations
• Peirce’s 1870 Logic Of Relatives

Morgan Rogers (he/him) (Aug 07 2021 at 09:04):

Jon Awbrey said:

I'm reworking my initial blog posts on Relations & Their Relatives....

You don't have to cross-post everything to both here and your blog; if anything, I would argue that just concentrating on the discussion here until it gets going would result in better blog posts. With my moderator hat on, I should also warn you that advertising your blog is not the intended use of this space (Zulip). Don't take that the wrong way, though: I'm looking forward to seeing where this discussion goes!

Sign relations are special cases of triadic relations in much the same way binary operations in mathematics are special cases of triadic relations.

Having skimmed both your links and a few other summaries of the theory of signs, I am curious to see how you will mathematically distinguish signs amongst triadic relations.

Jon Awbrey (Aug 07 2021 at 12:46):

Morgan Rogers (he/him) said:

Hi Jon. You posted a lot of contributions in this format, and it's about time someone engaged with them to see what there is to learn here. I have a few questions.

1. In the linked post on your blog, you claim that Peirce's work "undermines the fundamental nominalism of First Order Logic as we know it". What is the basis for that claim?
2. Peirce's work comes before set theory was developed; do you think set theory provides an adequate formalism in which to discuss "relation theory"?
3. Since this was inspired by other discussions here on Zulip, what insights do you think this can provide into categories of relations (or other category theory material, for that matter)?

Sorry for my tardiness, I was having unusual difficulties with Question 2 because I initially misread “formalism” as “foundation” and that sent me tumbling back to long-and-happily-forgotten crises of yesteryear which clearer eyes show me are not at issue here.

Combining Questions 2 and 3, the short answer is, wait and see as the discussion proceeds how Peirce develops a formalism adequate to express both extensional and intensional aspects of relations, at least to a degree not to be sneezed at, which dual aspects his Lectures on the “Logic of Science” at Harvard (1865) and the Lowell Institute (1866) indicate how to integrate into a genuinely information-theoretic approach to the subject.  Along the way, anyone with category-theoretic sensibilities will be able to recognize distinctively functorial ideas turning up at critical points in the exposition.  (Actually, this is not all that surprising when one considers both the historical sources of category theory and the details of Peirce's biography.)

Morgan Rogers (he/him) (Aug 09 2021 at 08:20):

I was expecting the post above to precede another one, but I suppose a discussion takes two people at least!
Let me rephrase my last post as a question, then: how are signs mathematically distinguished from general triadic relations? What does Peirce (formally) assume about these relations?

Jon Awbrey (Aug 09 2021 at 13:40):

Morgan Rogers (he/him) said:

I was expecting the post above to precede another one, but I suppose a discussion takes two people at least!
Let me rephrase my last post as a question, then: how are signs mathematically distinguished from general triadic relations? What does Peirce (formally) assume about these relations?

I was leery of proceeding at speed with so many yellow flags on the course (or in the harbor for some countries) … trying to find a way to work around your caution against self-promotion.  I normally provide transcripts of short excerpts but it would take a lot of work to reformat everything into this space.  And I see everyone else posting links of all sorts — seriously, what do we spin this web for anyway?

At any rate, I meant to focus on relations in general (well, finite and discrete) under this topic, bringing up sign relations as an unavoidable application, so I'll probably open another topic to focus on sign relations proper.

Cf: Semiotics, Semiosis, Sign Relations • Comment 1

I had been reading Peirce for a decade or more before I ran across a math-strength definition of signs and sign relations.  (A lot of literature out there takes almost anything Peirce wrote about signs as a “definition” but only a handful of those descriptions are consequential enough to support significant theory.)  For my part, the definition of a sign relation coming closest to that mark is one Peirce gave in the context of defining logic itself.  Two variants of that are linked and transcribed below.

Vide: C.S. Peirce • On the Definition of Logic

Selections from C.S. Peirce, “Carnegie Application” (1902)

No. 12.  On the Definition of Logic 

Logic will here be defined as formal semiotic.  A definition of a sign will be given which no more refers to human thought than does the definition of a line as the place which a particle occupies, part by part, during a lapse of time.  Namely, a sign is something, $A,$ which brings something, $B,$ its interpretant sign determined or created by it, into the same sort of correspondence with something, $C,$ its object, as that in which itself stands to $C.$  It is from this definition, together with a definition of “formal”, that I deduce mathematically the principles of logic.  I also make a historical review of all the definitions and conceptions of logic, and show, not merely that my definition is no novelty, but that my non-psychological conception of logic has virtually been quite generally held, though not generally recognized.  (NEM 4, 20–21).

No. 12.  On the Definition of Logic [Earlier Draft]

Logic is formal semiotic.  A sign is something, $A,$ which brings something, $B,$ its interpretant sign, determined or created by it, into the same sort of correspondence (or a lower implied sort) with something, $C,$ its object, as that in which itself stands to $C.$  This definition no more involves any reference to human thought than does the definition of a line as the place within which a particle lies during a lapse of time.  It is from this definition that I deduce the principles of logic by mathematical reasoning, and by mathematical reasoning that, I aver, will support criticism of Weierstrassian severity, and that is perfectly evident.  The word “formal” in the definition is also defined.  (NEM 4, 54).

Reference

• Charles S. Peirce (1902), “Parts of Carnegie Application” (L 75), published in Carolyn Eisele (ed., 1976), The New Elements of Mathematics by Charles S. Peirce, vol. 4, 13–73.  Online.

Morgan Rogers (he/him) (Aug 09 2021 at 15:17):

Jon Awbrey said:

Morgan Rogers (he/him) said:

I was expecting the post above to precede another one, but I suppose a discussion takes two people at least!
Let me rephrase my last post as a question, then: how are signs mathematically distinguished from general triadic relations? What does Peirce (formally) assume about these relations?

I was leery of proceeding at speed with so many yellow flags on the course (or in the harbor for some countries) … trying to find a way to work around your caution against self-promotion.  I normally provide transcripts of short excerpts but it would take a lot of work to reformat everything into this space.  And I see everyone else posting links of all sorts — seriously, what do we spin this web for anyway?

The problem isn't with linking to outside sources, but with you linking exclusively to sources written by yourself (and Peirce, I suppose!), and at times to material that is only tangentially relevant to the discussion at hand. It wasn't a hard criticism; all positive contributions are welcome here. The reason I started this discussion was precisely to investigate what you have to offer :wink:

Jon Awbrey (Aug 10 2021 at 12:57):

There has been a lot of confusion over the years about the difference between logical relatives and mathematical relations.  The following remarks should serve to clear that up.

Cf: Relations & Their Relatives • 2

What is the relationship between “logical relatives” and “mathematical relations”?  The word relative used as a noun in logic is short for relative term — as such it refers to an item of language used to denote a formal object.

What kind of object is that?  The way things work in mathematics we are free to make up a formal object corresponding directly to the term, so long as we can form a consistent theory of it, but it's probably easier and more practical in the long run to relate the relative term to the kinds of relations ordinarily treated in mathematics and universally applied in relational databases.

In those contexts a relation is just a set of ordered tuples and if you are a fan of strong typing like I am, such a set is always set in a specific setting, namely, it's a subset of a specified cartesian product.

Peirce wrote $k$-tuples $(x_1, x_2, \ldots, x_{k-1}, x_k)$ in the form $x_1 : x_2 : \ldots : x_{k-1} : x_k$ and referred to them as elementary $k$-adic relatives.  He treated a collection of $k$-tuples as a logical aggregate or logical sum and often regarded them as being arranged in $k$-dimensional arrays.

Time for some concrete examples, which I will give in the next post.

Morgan Rogers (he/him) (Aug 10 2021 at 13:33):

That seems straightforward and pretty standard in set theory. A relation is a collection of "elementary k-adic relatives" (elements of a cartesian product) and hence a subset of that cartesian product.
You don't need to go overboard on the examples unless there's something major that you haven't mentioned yet.

Jon Awbrey (Aug 10 2021 at 15:56):

Morgan Rogers (he/him) said:

That seems straightforward and pretty standard in set theory. A relation is a collection of "elementary k-adic relatives" (elements of a cartesian product) and hence a subset of that cartesian product.
You don't need to go overboard on the examples unless there's something major that you haven't mentioned yet.

I know, it seems pretty straightforward, and it remains so as long as one sticks to a single disciplinary silo.  It becomes less straightforward in a variety of applications where one has to establish communication among different communities of interpreters, say, abstract mathers, applied mathers, logicians, novices, and that host of novitiate orders we know as computers.

Sorry to be so brief here, but it will be September, at least, before I get out from under a host of pandemic-put-off tasks.

Henry Story (Aug 10 2021 at 17:11):

This whole discussion started with my linking to @Rocco Gangle's book on "Diagramatic immanence" a couple of months ago. Let me quickly look at what he says on this.
p108

Perhaps Peirce’s greatest achievement as a philosopher was to invert the traditional prioritisation of objects over relations in philosophical questioning and to show in a rigorous way how a consist- ent unification of its traditional themes thereby becomes possible.

Henry Story (Aug 10 2021 at 17:13):

a bit further on:

For Peirce all signs are ultimately composed of triadic relations, as we will see, but this does not imply that they are always adequately conceived as such. Indeed, misconceptions concerning the real being of signs – in particular the late medieval victory of nominalism and the carrying over of its dyadic model of concepts and signs into Cartesian and post-Cartesian modernity – are for Peirce at the root of a host of egregious philosophical errors.

Henry Story (Aug 10 2021 at 17:16):

Among the many more or less equivalent definitions of the triadic sign scattered throughout Peirce’s writings, one taken from his rela- tively late (1907) unpublished ‘letter’ on pragmatism is admirably exact and comparatively clear:

I will say that a sign is anything, of whatsoever mode of being, which mediates between an object and an interpretant; since it is both determined by the object relatively to the interpretant, and determines the interpretant in reference to the object, in such wise as to cause the interpretant to be determined by the object through the mediation of this ‘sign’.20

The technique of the composition of arrows used in category theory models this triadic relation well. A sign stands in some relation to something else, its object, such that by being brought into relation with the sign in some appropriate way, some third thing is brought into an appropriately ‘composed’ relation to the object. Roughly speaking, an interpretant is brought into relation with the object by means of the sign.

Henry Story (Aug 10 2021 at 17:17):

So that is where Rocco Gangle starts to try to bring Category Theory and Peirce together, which I think should be the aim of the exercise on these channels here :-)

Henry Story (Aug 10 2021 at 17:21):

Analysing giving Peirce is quoted as having written:

Take, for example, the relation of giving. A gives B to C. This does not consist in A’s throwing B away and its accidentally hitting C, like the date-stone, which hit the Jinnee in the eye. If that were all, it would not be a genuine triadic relation, but merely one dyadic relation followed by another.

Henry Story (Aug 10 2021 at 17:24):

This leads to the following image in terms of three functors Diagram from p116 of Diagrammatic Immanence

Henry Story (Aug 10 2021 at 17:26):

Then he goes on p121 with

What follows is a constructive attempt, based on Peirce’s triadic semiotics, to sketch a broadly Peircean theory of diagrammatic signs. It is meant to serve as a conceptual preparation for the more formal categorical theory of diagrammatic signs based on presheaves that will be developed in Chapter 4. The schema presented here is intended to follow quite closely the logic of scientific experiment, since Peirce’s triadic conception of the sign is strongly linked to his defence of scientific pragmatism as well as other aspects of his philosophy of science.

Henry Story (Aug 10 2021 at 17:34):

there follows some thoughts on the importance of the diagram as that which relates experiment, selection, evaluation.

What exactly is the structure of diagrammatic signification according to this selection-experimentation-evaluation model? Succinctly put, it is Peirce’s triadic sign-schema made internally relational. Selection corresponds to the relation of interpretant to sign, experimentation to the relation of sign to object, and evalua- tion to the composition of the latter relation following the former.

Henry Story (Aug 10 2021 at 17:36):

So the diagram, which we found to have been name of a famous french Category Theory publication from 1979 onwards following some writings on the topic by Deleuze inspired by Peirce, is somehow central to this conception of thought.

Henry Story (Aug 10 2021 at 17:38):

I'll just add this picture that appears in the text following the above. On the whole that is still a bit thin on the ground in terms of CT. But the nice thing is there is this attempt to link Peirce and Category Theory.

Henry Story (Aug 10 2021 at 17:45):

It may be that the technical details are to be found in other articles by Rocco Gangle. A very quick search pointed me to The sheet of indication: a diagrammatic semantics for Peirce’s EG-alpha from 2014 but there is also his talk to the Topos institute https://www.youtube.com/watch?v=j7Bp6_uiFaQ&t=5s

Jon Awbrey (Aug 10 2021 at 19:08):

Henry Story said:

This whole discussion started with my linking to Rocco Gangle's book on "Diagramatic immanence" a couple of months ago. Let me quickly look at what he says on this.
p108

Perhaps Peirce’s greatest achievement as a philosopher was to invert the traditional prioritisation of objects over relations in philosophical questioning and to show in a rigorous way how a consist- ent unification of its traditional themes thereby becomes possible.

I did eventually get a copy of @Rocco Gangle's Diagrammatic Immanence and hope to get to it when the pandemic pandemonium is past, which may be a while since the U.S. seems to be going backward not forward in many quarters.  But I've been studying C.S. Peirce, category theory, and computing since the late 60s so I've already got some peirce-spective of my own on all that.

As we go I'll try to save this thread for the more generic discussion of Relation Theory and sort the more specific discussion of Sign Relations to its own stream or thread or whatever.

Morgan Rogers (he/him) (Aug 11 2021 at 08:43):

Henry Story said:

This leads to the following image in terms of three functors Diagram from p116 of Diagrammatic Immanence

This is a nice picture at first glance, but the category theory is being abused here, and in a way that contradicts the quote you gave before this. The "giving" diagram appears to be exactly a decomposition of the act of giving into "A’s throwing B away" and then "B hitting C". Meanwhile, the right-hand side of the diagram is supposed to represent a "worldly category"; presumably the objects are "objects", including "gifts" and "people", but what are the morphisms here? Based on the interpretation, the various relations seem fundamentally different in nature (the relationship between giver and gift is surely a different sort of thing than the relationship between giver and recipient) in which case there is no sensible notion of compositionality.

Jon Awbrey (Aug 11 2021 at 11:48):

Morgan Rogers (he/him) said:

Henry Story said:

This leads to the following image in terms of three functors Diagram from p116 of Diagrammatic Immanence

This is a nice picture at first glance, but the category theory is being abused here, and in a way that contradicts the quote you gave before this. The "giving" diagram appears to be exactly a decomposition of the act of giving into "A’s throwing B away" and then "B hitting C". Meanwhile, the right-hand side of the diagram is supposed to represent a "worldly category"; presumably the objects are "objects", including "gifts" and "people", but what are the morphisms here? Based on the interpretation, the various relations seem fundamentally different in nature (the relationship between giver and gift is surely a different sort of thing than the relationship between giver and recipient) in which case there is no sensible notion of compositionality.

Thanks, Morgan, apt observation.

If we take up Peirce's approach to relations, triadic relations, and sign relations, the first stumbling block we come to has to do with the issue of “Triadic Relation Irreducibility” (TRI) or more fully “Triadic Relation Irreducibility And Sufficiency” (TRIAS).

There's a discussion of TRI from various angles, with concrete and simple examples, in the following article.

• Relation Reduction

There's a closely related discussion of relation composition in the following article.

• Relation Composition

Morgan Rogers (he/him) (Aug 11 2021 at 13:40):

I find this definition of (ir)reducibility a little strange. After all, if I have a triadic relation $R \subseteq A \times B \times C$ and I consider its 2-adic projections, there is a canonical way to recover a triadic relation from it, namely $R_{A,B} \times C \cap R_{A,C} \times B \cap R_{B,C} \times A$, where the three components are viewed as subsets of $A \times B \times C$ in the canonical way. This new relation contains $R$, but $R$ can be a strict subset of it: consider the sphere as a subset of the unit cube $[0,1]^3$; the relation constructed as above is the intersection of 3 perpendicular cyclinders, which is strictly larger.

I would argue that it makes sense to think of the latter as "reducible" (recoverable from its projections in the canonical way) while the former is "irreducible" since this is not the case. But by your definition, any triadic relation whatsoever is irreducible in the right company, since your definition of reducibility is a statement of joint injectiveness of the projection operations on a given set of relations. That is, your notion of reducibility is not intrinsic to the relations involved.

Jon Awbrey (Aug 11 2021 at 14:18):

The two kinds of reducibility coming up most often in applications and theoretical discussions are compostional and projective.  All triadic relations are irreducible to dyadic relations under composition since the composition of two dyadic relations is again a dyadic relation.  Reducibilty under projections is kind of a consolation prize but you win it only in special cases.  Not sure what you mean by canonical but all you need for projective irreducibility is for two triadic relations to have exactly the same set of dyadic projections.  This clearly happens in that “bitty” example I gave.

Morgan Rogers (he/him) (Aug 11 2021 at 14:37):

I claim that the triadic relations which are irreducible in the sense you describe are exactly the relations $R \subseteq A \times B \times C$ such that whenever $R(a,b,c)$ and $R(a',b',c')$, we have ($a=a'$ and $b=b'$ and $c=c'$) or ($a \neq a'$ and $b \neq b'$ and $c \neq c'$), which is not a trivial collection by any means, but I don't see the significance of the concept.

I say the construction I described is "canonical" because (unless I'm miscalculating) it's adjoint to the mapping $\mathrm{Rel}(A,B,C) \to \mathrm{Rel}(A,B) \times \mathrm{Rel}(A,C) \times \mathrm{Rel}(B,C)$ formed from the three projection maps; this is the most natural way to reconstruct a triadic relation from three binary relations.

Jon Awbrey (Aug 11 2021 at 15:05):

Cf: Examples of Projectively Irreducible Relations

What do you compute for the 2-adic projections of the following two relations?

• $L_0 ~=~ \{ (x, y, z) \in \mathbb{B}^3 : x + y + z = 0 \}$
• $L_1 ~=~ \{ (x, y, z) \in \mathbb{B}^3 : x + y + z = 1 \}$

And what would you consider the canonical reconstruction of those projections?

Morgan Rogers (he/him) (Aug 11 2021 at 15:19):

As you compute on the linked page, all of the projections are the entirety of $\mathbb{B}^2$, whence the reconstruction is the maximal relation on $\mathbb{B}^3$.

Jon Awbrey (Aug 11 2021 at 15:34):

Morgan Rogers (he/him) said:

As you compute on the linked page, all of the projections are the entirety of $\mathbb{B}^2$, whence the reconstruction is the maximal relation on $\mathbb{B}^3$.

Okay, consensus is good.  That's all we need for projective irreducibility.  As far as absolutely intrinsic properties go, I think I put enough waffling in the intro of that article to suggest I'm not sure there's any such thing.  We can always keep looking for a character worth canonizing but relative thinkers like Peirce and yours truly became wary of ethereal luminaries a long time ago.

Morgan Rogers (he/him) (Aug 11 2021 at 15:55):

Sure, but why is this a feature you're focussing on? $$\{(0,0,1)
Morgan Rogers (he/him) said:

I claim that the triadic relations which are irreducible in the sense you describe are exactly the relations $R \subseteq A \times B \times C$ such that whenever $R(a,b,c)$ and $R(a',b',c')$, we have ($a=a'$ and $b=b'$ and $c=c'$) or ($a \neq a'$ and $b \neq b'$ and $c \neq c'$), which is not a trivial collection by any means, but I don't see the significance of the concept.

This condition was too restrictive, I now see, but I am still in the dark on the motivation for considering this notion of (ir)reducibility.

Morgan Rogers (he/him) (Aug 11 2021 at 15:57):

Jon Awbrey said:

As far as absolutely intrinsic properties go, I think I put enough waffling in the intro of that article to suggest I'm not sure there's any such thing. We can always keep looking for a character worth canonizing but relative thinkers like Peirce and yours truly became wary of ethereal luminaries a long time ago.

You don't believe in intrinsic properties..?

Jon Awbrey (Aug 11 2021 at 16:06):

I just tend to see relational properties being more relevant in this context.

Morgan Rogers (he/him) (Aug 11 2021 at 17:46):

So is the domain of a relation is contingent, then? It didn't seem like it, since you defined a relation as a subset of a specific cartesian product, but perhaps you just didn't mention that you allow that product to be variable?

Jon Awbrey (Aug 11 2021 at 18:30):

Morgan Rogers (he/him) said:

So is the domain of a relation is contingent, then? It didn't seem like it, since you defined a relation as a subset of a specific cartesian product, but perhaps you just didn't mention that you allow that product to be variable?

Not sure I know what you are asking here.  Most of the applications I pursue require strongly typed functions and relations.  There's some discussion of the different points of view in the following article.

• Relation Theory

To stress the strong typing I have thought of using the embedding arrow $L \hookrightarrow X \times Y \times Z$ instead of the usual subset relation $L \subseteq X \times Y \times Z$ but I'm not sure how well that would go over.

Of course, we could always imagine some sort of limit process in expanding universes of discourse but it hasn't really come up yet in my homey patchwork quilt approach to science.

Jon Awbrey (Aug 11 2021 at 19:20):

Not to slight dyadic relations, we can use an old standby from number theory to illustrate Peirce's notation for elementary relatives.

Cf: Relations & Their Relatives • 3

Here are two ways of looking at the divisibility relation, a dyadic relation of fundamental importance in number theory.

Table 1 shows the first few ordered pairs of the relation on positive integers corresponding to the relative term, “divisor of”.  Thus, the ordered pair ${i\!:\!j}$ appears in the relation if and only if ${i}$ divides ${j},$ for which the usual notation is ${i|j}.$

• Elementary Relatives for the “Divisor Of” Relation
  

Table 2 shows the same information in the form of a logical matrix.  This has a coefficient of ${1}$ in row ${i}$ and column ${j}$ when ${i|j},$ otherwise it has a coefficient of ${0}.$  (The zero entries have been omitted for ease of reading.)

• Logical Matrix for the “Divisor Of” Relation
  

Just as matrices in linear algebra represent linear transformations, these logical arrays and matrices represent logical transformations.

Morgan Rogers (he/him) (Aug 12 2021 at 13:01):

Jon Awbrey said:

Morgan Rogers (he/him) said:

So is the domain of a relation is contingent, then? It didn't seem like it, since you defined a relation as a subset of a specific cartesian product, but perhaps you just didn't mention that you allow that product to be variable?

Not sure I know what you are asking here.  Most of the applications I pursue require strongly typed functions and relations.  There's some discussion of the different points of view in the following article.

• Relation Theory

To stress the strong typing I have thought of using the embedding arrow $L \hookrightarrow X \times Y \times Z$ instead of the usual subset relation $L \subseteq X \times Y \times Z$ but I'm not sure how well that would go over.

Of course, we could always imagine some sort of limit process in expanding universes of discourse but it hasn't really come up yet in my homey patchwork quilt approach to science.

I asked because if the domain/typing of a relation is part of the relation, then surely the properties we've discussed so far of notions of (ir)reducibility are intrinsic properties of the relations?

Morgan Rogers (he/him) (Aug 12 2021 at 13:11):

Jon Awbrey said:

Just as matrices in linear algebra represent linear transformations, these logical arrays and matrices represent logical transformations.

This is an analogy that's well-worn in the category theory literature already, and in particular it makes composition of binary relations into matrix multiplication. Not to be blunt, but so far everything you've said has been either unenlightening (by virtue of being part of the basic theory of relations) or mysterious, like what the motivation for the notion of irreducibility is.

Allow yourself to assume that your audience knows a lot more about relations from a mathematical perspective (since the only participating audience members are myself and @Henry Story, I think this is a safe assumption). Anyone that doesn't can just ask or refer to your copious notes. With that in mind, what are the distinguishing features of Peirce's work on relations? Where does it differ from what you interpret to be the dominant discourse on relations, logically or philosophically speaking?

Jon Awbrey (Aug 13 2021 at 19:50):

Morgan Rogers (he/him) said:

Jon Awbrey said:

Morgan Rogers (he/him) said:

So is the domain of a relation is contingent, then? It didn't seem like it, since you defined a relation as a subset of a specific cartesian product, but perhaps you just didn't mention that you allow that product to be variable?

Not sure I know what you are asking here.  Most of the applications I pursue require strongly typed functions and relations.  There's some discussion of the different points of view in the following article.

• Relation Theory

To stress the strong typing I have thought of using the embedding arrow $L \hookrightarrow X \times Y \times Z$ instead of the usual subset relation $L \subseteq X \times Y \times Z$ but I'm not sure how well that would go over.

Of course, we could always imagine some sort of limit process in expanding universes of discourse but it hasn't really come up yet in my homey patchwork quilt approach to science.

I asked because if the domain/typing of a relation is part of the relation, then surely the properties we've discussed so far of notions of (ir)reducibility are intrinsic properties of the relations?

Vide: Relation Reduction

The definition of reducibility I gave at the beginning of the above article — whose overly wordy prose I promise to fix at the next opportunity — is stated relative to a basis and a method of reduction.  How could we have a conception of intrinsic properties except relative to a definition of intrinsic?  Sure, we have a concept of universals in category theory but it is defined relative to a categorical context.

Morgan Rogers (he/him) (Aug 14 2021 at 11:58):

If we have a base cartesian product, we can always consider the collection of all relations of the same arity (ie subsets of the same base), which is an intrinsic extension of the data of the relation, and we can always check reducibility relative to that to obtain an intrinsic notion. I still don't understand the motivation for introducing a notion of reducibility in comparison with other chosen relations over the same base, because you've so far avoided my question of why you did this.

Jon Awbrey (Aug 14 2021 at 12:42):

Morgan Rogers (he/him) said:

If we have a base cartesian product, we can always consider the collection of all relations of the same arity (ie subsets of the same base), which is an intrinsic extension of the data of the relation, and we can always check reducibility relative to that to obtain an intrinsic notion. I still don't understand the motivation for introducing a notion of reducibility in comparison with other chosen relations over the same base, because you've so far avoided my question of why you did this.

Let's leave off on intrinsic for now, as saying “intrinsic relative to” sounds like a clang if not a contradiction in terms to my ear.  Once you've said property $P$ is defined relative to context $Q$, the epithet intrinsic doesn't seem to add any meaning.

Whether one relation can be analyzed, assembled, built up, constructed from, or defined in terms of a specified class of other relations, typically simpler on some measure, seems like such a natural question, so often encountered in every area of math and its applications, I can't imagine why there would be any difficulty motivating it.

Henry Story (Aug 14 2021 at 16:37):

If I had the time, I would proceed by first looking at what concepts CT has developed that are most likely to fit the topic.
Perhaps instead of looking at three place relations in Set, one should look for them in Cat? It seems like Kan extensions are like that, and it has been said that "All Concepts are Kan extensions".

Jon Awbrey (Aug 14 2021 at 17:10):

Henry Story said:

If I had the time, I would proceed by first looking at what concepts CT has developed that are most likely to fit the topic.
Perhaps instead of looking at three place relations in Set, one should look for them in Cat? It seems like Kan extensions are like that, and it has been said that "All Concepts are Kan extensions".

Been there, doing that since '84 at least when I was working on my Logical Graph engine and the Propositions As Types Analogy led me to take a course on Categories, $\lambda$-Calculus, and Combinators from John Gray at UIUC.  But it will take me some time and a search of many old boxes in the basement to warm up those particular gray cells again.  And progress is a bit rougher here than I anticipated — but I think it would be worth the effort …

Jon Awbrey (Aug 15 2021 at 02:54):

Cf: Relations & Their Relatives • Review 1

Peirce's notation for elementary relatives was illustrated above by a dyadic relation from number theory, namely ${i|j}$ for $i ~\mathrm{divides}~ j.$

Cf: Relations & Their Relatives • 3

Table 1 shows the first few ordered pairs of the relation on positive integers corresponding to the relative term, “divisor of”.  Thus, the ordered pair ${i\!:\!j}$ appears in the relation if and only if ${i}$ divides ${j},$ for which the usual notation is ${i|j}.$

• Elementary Relatives for the “Divisor Of” Relation
  

Table 2 shows the same information in the form of a logical matrix.  This has a coefficient of ${1}$ in row ${i}$ and column ${j}$ when ${i|j},$ otherwise it has a coefficient of ${0}.$  (The zero entries have been omitted for ease of reading.)

• Logical Matrix for the “Divisor Of” Relation
  

Just as matrices in linear algebra represent linear transformations, these logical arrays and matrices represent logical transformations.

The capacity of relations to generate transformations gives us a clue to the dynamics of sign relations.

Cf: Relations & Their Relatives • Discussion 1

The divisor of relation signified by $x|y$ is a dyadic relation on the set of positive integers $\mathbb{M}$ and thus may be understood as a subset of the cartesian product $\mathbb{M} \times \mathbb{M}.$  It is an example of a partial order, while the less than or equal to relation signified by $x \le y$ is an example of a total order relation.

The mathematics of relations can be applied most felicitously to semiotics but there we must bump the adicity or arity up to three.  We take any sign relation $L$ to be subset of a cartesian product $O \times S \times I,$ where $O$ is the set of objects under consideration in a given discussion, $S$ is the set of signs, and $I$ is the set of interpretant signs involved in the same discussion.

One thing we need to understand is the sign relation $L \subseteq O \times S \times I$ relevant to a given level of discussion may be rather more abstract than what we would call a sign process proper, that is, a structure extended through a dimension of time.  Indeed, many of the most powerful sign relations generate sign processes through iteration or recursion or similar operations.  In that event, the most penetrating analysis of the sign process or semiosis in view is achieved through grasping the generative sign relation at its core.

Morgan Rogers (he/him) (Aug 16 2021 at 15:13):

So a "sign process" would be a subset $L \subseteq O \times S \times I \times T$, where $T$ is a time domain? Sounds like quadradic(? might be a bit confusingly close to "quadratic"..?) relations are what you want, then.

Jon Awbrey (Aug 16 2021 at 16:01):

Cf: Relations & Their Relatives • Discussion 18

Morgan Rogers (he/him) said:

So a "sign process" would be a subset $L \subseteq O \times S \times I \times T$, where $T$ is a time domain?

There are a couple of ways we usually see the concept of a sign relation $L \subseteq O \times S \times I$ being applied.

• There is the translation scenario where $S$ and $I$ are two different languages and a large part of $L$ consists of triples $(o, s, i)$ where $s$ and $i$ are co-referent or otherwise equivalent signs.

• There is the transition scenario where $S = I$ and we have triples of the form $(o, s, s')$ where $s'$ is the next state of $s$ in some sign process.  As it happens, a concept of process is more basic than a concept of time, since the latter involves reference to a standard process commonly known as a clock.

Henry Story (Aug 16 2021 at 16:22):

Could one not say that Frege also had a three part relation? I guess: for singular terms their Sense and Reference. (on Sense and Reference). His argument could be explained very simply. Imagine you start with a theory of language where words only have referents. Then since in point of fact Hesperus = Phosphorus, The morning Star = The Evening Star, the simple theory of meaning would not allow one to explain how the discovery that they both were the planet Venus, came to be such a big event. So sense cannot be reduced to reference. Equalities can have informational content.

Jon Awbrey (Aug 16 2021 at 16:56):

Cf: Relations & Their Relatives • Discussion 19

Henry Story said:

Could one not say that Frege also had a three part relation? I guess: for singular terms their Sense and Reference. (on Sense and Reference). His argument could be explained very simply. Imagine you start with a theory of language where words only have referents. Then since in point of fact Hesperus = Phosphorus, The morning Star = The Evening Star, the simple theory of meaning would not allow one to explain how the discovery that they both were the planet Venus, came to be such a big event. So sense cannot be reduced to reference. Equalities can have informational content.

Yes, Peirce's take on semiotics is often compared with Frege's parsing of Sinn und Bedeutung.  There's a long tradition concerned with the extension and intension of concepts and terms, also denotation and connotation, though the latter tends to be somewhat fuzzier from one commentator to the next.  The following paper by Peirce gives one of his characteristically thoroughgoing historical and technical surveys of the question.

• C.S. Peirce (1867) • Upon Logical Comprehension and Extension

Jon Awbrey (Aug 16 2021 at 22:12):

The duality, inverse proportion, or reciprocal relation between extension and intension is the generic form of the more specialized galois correspondences we find in mathematics.  Peirce preferred the more exact term comprehension for a compound of many intensions.  In his Lectures on the Logic of Science (Harvard 1865, Lowell Institute 1866) he proposed his newfangled concept of information to integrate the dual aspects of comprehension and extension, saying the measures of comprehension and extension are inversely proportional only when the measure of information is constant.  The fundamental principle governing his “laws of information” could thus be expressed in the following formula.

• $\mathrm {Information} = \mathrm {Comprehension} \times \mathrm {Extension}$

Jon Awbrey (Aug 17 2021 at 12:24):

The development of Peirce's information formula is discussed in my ongoing study notes, consisting of selections from Peirce's 1865–1866 Lectures on the Logic of Science and my commentary on them.

• Information = Comprehension × Extension

Morgan Rogers (he/him) (Aug 17 2021 at 13:19):

Care to make any of this more precise? That formula, for example?

Jon Awbrey (Aug 17 2021 at 14:24):

Cf: Relations & Their Relatives • Discussion 20

Morgan Rogers (he/him) said:

Care to make any of this more precise? That formula, for example?

Yes, it will take some care to make it all more precise, and I've cared enough to work on it when I get a chance.  I initially came to Peirce's 1865–1866 lectures in grad school from the direction of graph-&-group theory in connection with a 19th century device called a “table of marks”, out which a lot of work on group characters and group representations developed.

A table of marks for a transformation group $(G, X)$ is an incidence matrix with $1$ in the $(g, x)$ cell if $g$ fixes $x$ and $0$ otherwise.  I could see Peirce's formula was based on a logical analogue of those incidence matrices so that gave me at least a little stable ground to inch forward on.