Transitivity in Equational Logic

Stream: new members

[Julius Hamilton]

Equational logic is a fragment of first order logic which only uses universal quantification, the equality relation, and no logical connectives (I think).

Transitivity is the condition for a relation $R$ that $\forall x, y, z, xRy \wedge yRz \to xRz$.

I would like to prove or disprove that any structure which models a transitive relation $R$ cannot be axiomatized by a purely equational theory.

My background is I have been studying logic for about a year.

I am thinking there could be a syntactic proof using term rewriting. In a confluent, terminating reduction system, every term has a unique normal form (I think), which allows us to decide equality for two terms. Maybe I can show how a certain class of first-order formulae have a reduction system where the normal forms are equational theories, or something.

I also think there could be a semantic proof where I compare the class of models of a theory of a transitive relation $R$, and a class of models for an arbitrary equational theory, to show that they are distinct.

I'm very new to this, so interested in getting some feedback. Thanks.

[Notification Bot]

This topic was moved here from #Equational > Transitivity in Equational Logic by Kevin Buzzard.

[Zoltan A. Kocsis (Z.A.K.)]

I would like to prove or disprove that any structure which models a transitive relation R cannot be axiomatized by a purely equational theory.

You can disprove this by way of counterexample. Of course, equality itself is a transitive relation, it is definable, and clearly axiomatizable by a purely equational theory (the empty theory with no axioms).

Less trivially, the theory of semilattices (associative, commutative, idempotent magmas) is purely equational, and defines a partial order relation by the formula x + y = x. Partial order relations are of course transitive.

[Kevin Buzzard]

@Julius Hamilton I moved your question to a more appropriate channel.