An n-ary *relation* on the sets `S`

, _{0}`S`

, ..., _{1}`S`

,
is a set of ordered tuples _{n-1}`R⊆S`

.
If _{0}×S_{1}×...×S_{n-1}`∀0≤i≤n-1 S=S`

, then we write _{i}`R⊆S`

.
We say that the relation holds for an n-tuple ^{n}`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*.

The following are examples of binary relations:

` ````
<={(a,b)|a<b}
squared={(a,b)|a=b
```^{2}}

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`

.

Deransart, Pierre, Maluszynski, Jan. *A Grammatical View of Logic Programming.* MIT Press, 1993.

Doets, Kees. *From Logic to Logic Programming.* MIT Press, 1994.

Copyright © 2014 Barry Watson. All rights reserved.