Search code examples
mathlogicdiscrete-mathematics

How to write relations with predicate logic


How to write predicate logic to express the following relationships.

Rxy is irreflexive
Rxy is intransitive
Rxy is not a partial order

Just need to express the following above relationships with predicate logic and quantifiers.


Solution

  • A relation is reflexive when xRx for all x. In predicate logic, we might write forall x . xRx. Now, irreflexive might mean two things: either that the relation simply isn't reflexive, or that there are no elements at all related to themselves. These have different predicate logic sentences: exists x . not xRx, vs forall x . not xRx.

    A relation is transitive when xRy and xRz implies xRz for all x, y and z. In predicate logic, we might write forall x. forall y. forall z. (xRy and yRz) implies xRz. Again, we might understand by intransitive either that R is simply not transitive, or that there are no x, y and z that have xRy, yRz and xRz true simultaneously; these have predicate logic sentences exists x. exists y. exists z. xRy and yRz and not xRz and forall x. forall y. forall z. not (xRy and yRz and xRz), respectively.

    A relation is a partial order when it is reflexive, anti-symmetric and transitive (at least, using the definition here, reasonable people may use variations:https://www.geeksforgeeks.org/partial-order-relation-on-a-set/). We could write this as one big predicate logic sentence like forall x. forall y. forall z. xRx and not (x =/= y and xRy and yRx) and ((xRy and yRz) implies xRz). The negation of this just changes the forall to exists and not's the condition (this is a general rule): exists x. exists y. exists z. not [xRx and not (x =/= y and xRy and yRx) and ((xRy and yRz) implies xRz)]. The not'ed condition can be simplified using De Morgan's law if desired.

    Note: "irreflexive" and "intransitive" probably just mean "not reflexive" and "not transitive", seems that the words for the other things are "antireflexive" and "antitransitive" maybe.