relation

Before describing what a relation^{👁 Mathworld
👁 Planetmath}
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^{👁 Mathworld
👁 Planetmath}
, 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^{👁 Mathworld
👁 Planetmath}
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 .

Remarks.

1. 1.

   In set theory^{👁 Mathworld
   👁 Planetmath}
   , 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 .

2. 2.

   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 .

3. 3.

   In term rewriting theory, a binary relation on a set is sometimes called a reduction, and is written . This is to signify that means that the element is being “reduced” to via .

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.

Remarks.

1. 1.

   Following from the first remark from the previous section^{👁 Planetmath
   👁 Planetmath}
   , 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.

2. 2.

   A relation can also be viewed as a function (which itself is a relation). Let . As a subset of , can be identified with the characteristic function^{👁 Mathworld
   👁 Planetmath
   👁 Planetmath
   👁 Planetmath}
   

   where iff and otherwise. Therefore, an -ary relation is equivalent^{👁 Mathworld
   👁 Planetmath
   👁 Planetmath
   👁 Planetmath
   👁 Planetmath
   👁 Planetmath}
   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).

Title	relation
Canonical name	Relation
Date of creation	2013-03-22 11:43:28
Last modified on	2013-03-22 11:43:28
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	33
Author	CWoo (3771)
Entry type	Definition
Classification	msc 08A02
Classification	msc 03E20
Classification	msc 82C35
Related topic	Poset
Related topic	PartialOrder
Related topic	TotalOrder
Related topic	OrderingRelation
Related topic	Function
Related topic	WellFoundedRelation
Related topic	Property2
Related topic	GroundedRelation
Related topic	RelationBetweenObjects
Defines	unary relation
Defines	binary relation
Defines	ternary relation
Defines	-ary relation
Defines	domain
Defines	range
Defines	nullary relation
Defines	field