# 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.