Namespaces
Variants
Actions

Relation

From Encyclopedia of Mathematics
Jump to: navigation, search

A subset of a finite Cartesian power $A^n = A \times \cdots \times A$ of a given set $A$, i.e. a set of tuples $(a_1,\ldots,a_n)$ of $n$ elements of $A$.

A subset $R \subseteq A^n$ is called an $n$-place, or an $n$-ary, relation on $A$. The number $n$ is called the rank, or type, of the relation $R$. The notation $R(a_1,\ldots,a_n)$ signifies that $(a_1,\ldots,a_n) \in R$.

One-place relations are called properties. Two-place relations are called binary relations, three-place relations are called ternary, etc.

The set $A^n$ and the empty subset $\emptyset$ in $R^n$ are called, respectively, the universal relation and the zero relation of rank $n$ on $A$. The diagonal of the set $A^n$, i.e. the set $$ \Delta = \{ (a,a,\ldots,a) : a \in A \} $$ is called the equality relation on $A$.

If $R$ and $S$ are $n$-place relations on $A$, then the following subsets of $A^n$ will also be $n$-place relations on $A$: $$ R \cap S\, \ \ R \cup S\,,\ \ R' = A^n \setminus R\,\ \ R \setminus S \ . $$

The set of all $n$-ary relations on $A$ is a Boolean algebra relative to the operations $\cup$, $\cap$, ${}'$. An $(n+1)$-place relation $F$ on $A$ is called functional if for any elements $a_1,\ldots,a_n$, $a,b$, from $A$ it follows from $F(a_1,\ldots,a_n,a)$ and $F(a_1,\ldots,a_n,b)$ that $a = b$.

See also Binary relation; Correspondence; Predicate.

References

[a1] J.L. Bell, M. Machover, "A course in mathematical logic" , North-Holland (1977)
How to Cite This Entry:
Relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Relation&oldid=55712
This article was adapted from an original article by D.M. Smirnov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article