Relation

An n-ary relation on the sets S0, S1, ..., Sn-1, is a set of ordered tuples R⊆S0×S1×...×Sn-1. If ∀0≤i≤n-1 S=Si, then we write R⊆Sn. We say that the relation holds for an n-tuple t if t∈R. A relation on pairs is called a binary relation. Sometimes binary relations are written aRb for the relation R when (a,b)∈R.

A binary relation that has no infite path, aRbRcR..., is called well-founded.

Example

The following are examples of binary relations:

	
<={(a,b)|a<b}
squared={(a,b)|a=b2}	  
	
      

Types

If R is a binary relation on the set S, then

• R is called reflexive if sRs for all s∈S,
• R is called transitive if sRt∧tRu⇒sRu for all s,t,u∈S,
• R is called symmetric if sRt⇒tRs for all s,t∈S,
• R is called antisymmetric if sRt∧tRs⇒s=t for all s,t∈S.

References

Deransart, Pierre, Maluszynski, Jan. A Grammatical View of Logic Programming. MIT Press, 1993.
Doets, Kees. From Logic to Logic Programming. MIT Press, 1994.