Before describing what a relation is generally, let us define a more specific kind of a relation: a binary relation. Basically, a binary relation involves objects coming from two collections , where the objects are paired up so that each pair consists of an object from , and an object from .
More formally, a binary relation is a subset of the Cartesian product (http://planetmath.org/CartesianProduct) of two sets and . One may write
to indicate that the ordered pair is an element of . A subset of is simply called a binary relation on . If is a binary relation on , then we write
to mean and .
Given a binary relation , the domain of is the set of elements in forming parts of the pairs in . In other words,
and the range of is the set of parts of pairs of coming from :
An example of a binary relation is the less-than relation on the integers, i.e., . , but .
In set theory, a binary relation is simply a set of ordered pairs (of sets or classes, depending on the axiom system used). Notice that, unlike the previous definition, sets (or classes) and are not specified in advance. Given a (binary) relation , the domain of is the set (or class) of elements such that for some , and the range of is the set (or class) or elements such that for some . The union and the domain and the range of is called the field of .
It may be possible to define a relation over a class. For example, if is the class of all sets, then can be thought of as a binary relation on .
From the definition of a binary relation, we can easily generalize it to that of an arbitrary relation. Since a binary relation involves two sets, an arbitrary relation involves an arbitrary collection of sets. More specifically, a relation is a subset of some Cartesian product (http://planetmath.org/GeneralizedCartesianProduct) of a collection of sets. In symbol, this is
where each is a set, indexed by some set .
From this more general definition, we see that a binary relation is just a relation where has two elements. In addition, an -ary relation is a relation where the cardinality of is ( finite). In symbol, we have
It is not hard to see that any -ary relation where can be viewed as a binary relation in different ways, for
where ranges from through .
A common name for a -ary relation is a ternary relation. It is also possible to have a -ary relation, or commonly known as a unary relation, which is nothing but a subset of some set.
Following from the first remark from the previous section, relations of higher arity can be inductively defined: for , an -ary relation is a binary relation whose domain is an -ary relation. In this setting, a “unary relation” and relations whose arity is of “arbitrary” cardinality are not defined.
where iff and otherwise. Therefore, an -ary relation is equivalent to an -ary characteristic function. From this, one may say that a -ary, or a nullary relation is a unary characteristic function. In other words, a nullary relation is just a an element in (or truth/falsity).
|Date of creation||2013-03-22 11:43:28|
|Last modified on||2013-03-22 11:43:28|
|Last modified by||CWoo (3771)|