Transitivity on relations $R\subseteq X\times X$ and associativity on binary operators $+:X\times X \to X$ are defined as:

$$\forall x,y,z, \quad xRy\land yRz\to xRz$$

$$\forall x,y,z, \quad (x+y)+z=x+(y+z)$$

I am interested whether there is some notion of a "most non-transitive" relation or "most non-associative" operator. Some seem to be more intransitive or more nonassociative than others.

If we define the formulas $T_R(t):xRy\land yRz\to xRz$ for $t=(x,y,z)$ and $A_+(t):(x+y)+z=x+(y+z)$, then it would be tempting to just say that the minimally transitive relation is the one for which this doesnt satisfy for any $t\in X^3$, but there clearly isnt such a relation. Similar for associativity.

Is there some way that we can formalize the notion of "minimal" transitivity/associativity?

  • $\begingroup$ If you have a way to define associators, you can look at how much of your structure they (in some appropriate sense) generate. $\endgroup$ – Henning Makholm Jun 12 at 13:11
  • $\begingroup$ For relations, you have antitransitivity $\endgroup$ – Wojowu Jun 12 at 22:00
  • $\begingroup$ The Hasse diagram of a finite partial order might be considered minimally transitive. $\endgroup$ – Daniel Schepler Jun 12 at 22:02

You could try to generalize the notion of center $Z(X)$ of a group ( or ring, or etc.) $X$ - namely, the set of elements which commute with everything. Of course, since associativity takes three elements into account, this is a bit stranger; I suspect that the right thing to look at, given a binary function $*$, is the set $$A(X)=\{b: \forall a,c[(a*b)*c=a*(b*c)]\}.$$ Note that $A(X)$ is itself closed under $*$ (this is easy to check) and is itself completely associative, which does suggest that this isn't too terrible a notion.

"Minimal associativity" then could mean that $A(X)$ is as small as possible, in whatever context we're considering. E.g. in an arbitrary magma this would mean $A(X)=\emptyset$; if we commit ourselves to having an identity element $e$, then $A(X)$ must contain it (since $(a*e)*c=a*c=a*(e*c)$) but could in principle consist of just the identity.

Unfortunately, while smallness of center is often important, I'm not aware of any situations where $A(X)$ being "small" is actually interesting. But then I'm not familiar with non-associative algebraic structures in general.


Let S be a set with at least 3 points.
T = SxS is a transitive relation.
For distinct a,b, let R = T - {(a,b)}.
R is not transitive because there is a point c
with aRc and cRb but without aRb.
Thus R is maximally intransitive.

  • $\begingroup$ the empty relation would be "maximally intransitive" under your definition, even though it is transitive. Also, it is not uniquely defined. assume that $xRy$ hold for all $x,y\in \tilde X$ for some subset $\tilde X$. There are multiple relations satisfying the definition that are not isomorphic. Maybe we cannot get around that but it's not obvious to me. $\endgroup$ – user56834 Jun 13 at 8:11
  • $\begingroup$ @user56834. See edit. Maximal things usually are not unique. $\endgroup$ – William Elliot Jun 13 at 12:18
  • $\begingroup$ but this notion is not really sensible. like I said, there are relations that are "transitive" but "maximally intransitive" according to this definition. moreover, a "maximally intransitive" relation $R$ can be made more intransitive (in an intuitive sense), by adding elements to $R$. $\endgroup$ – user56834 Jun 13 at 18:27
  • $\begingroup$ @user56834. See revision. $\endgroup$ – William Elliot Jun 14 at 1:18
  • $\begingroup$ If $R$ is the empty relation, $T$ is transitive. If $R$ is the relation only containing $(a,b)$, $T$ is also transitive. If $R$ is a massive relation with lots of connections, removing only $(a,b)$ doesn’t make it “maximally intransitive” in any meaningful sense. $\endgroup$ – user56834 Jun 14 at 3:22

Your Answer

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

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