Relation mathematics: Encyclopedia II - Relation mathematics - Formal definitions

Relation mathematics - Formal definitions

There are two definitions of k-place relations that are commonly encountered in mathematics. In order of simplicity, the first of these definitions is as follows:

Definition 1. A relation L over the sets X₁, …, X_k is a subset of their cartesian product, written L ⊆ X₁ × … × X_k. Under this definition, then, a k-ary relation is simply a set of k-tuples.

The second definition makes use of an idiom that is common in mathematics, stipulating that "such and such is an n-tuple" in order to ensure that such and such a mathematical object is determined by the specification of n component mathematical objects. In the case of a relation L over k sets, there are k + 1 things to specify, namely, the k sets plus a subset of their cartesian product. In the idiom, this is expressed by saying that L is a (k+1)-tuple.

Definition 2. A relation L over the sets X₁, …, X_k is a (k+1)-tuple L = (X₁, …, X_k, G(L)), where G(L) is a subset of the cartesian product X₁ × … × X_k. G(L) is called the graph of L.

Elements of a relation are more briefly denoted by using boldface characters, for example, the constant element = (a₁, …, a_k) or the variable element = (x₁, …, x_k).

A statement of the form " is in the relation L " is taken to mean that is in L under the first definition and that is in G(L) under the second definition.

The following considerations apply under either definition:

• The sets X_j for j = 1 to k are called the domains of the relation. In the case of the first definition, the relation itself does not uniquely determine a given sequence of domains.

• If all of the domains X_j are the same set X, then L is more simply referred to as a k-ary relation over X.

• If any of the domains X_j is empty, then the cartesian product is empty, and the only relation over such a sequence of domains is the empty relation L = . As a result, naturally occuring applications of the relation concept typically involve a stipulation that all of the domains be nonempty.

As a rule, whatever definition best fits the application at hand will be chosen for that purpose, and anything that falls under it will be called a 'relation' for the duration of that discussion. If it becomes necessary to distinguish the two alternatives, the latter type of object can be referred to as an embedded or included relation.

If L is a relation over the domains X₁, …, X_k, it is conventional to consider a sequence of terms called variables, x₁, …, x_k, that are said to range over the respective domains.

A boolean domain B is a generic 2-element set, say, B = {0, 1}, whose elements are interpreted as logical values, typically 0 = false and 1 = true.

The characteristic function or the indicator function of the relation L is the boolean-valued function f_L : X₁ × …, × X_k → B, such that f_L() = 1 just in case the k-tuple is in L.

It is conventional in applied mathematics, computer science, and statistics to refer to a boolean-valued function like f_L as a k-place predicate. From the more abstract viewpoints of formal logic and model theory, the relation L is seen as constituting a logical model or a relational structure that serves as one of many possible interpretations of a corresponding k-place predicate symbol, as that term is used in predicate calculus.

Due to the convergence of many different styles of study on the same areas of interest, the reader will find much variation in usage here. The variation presented in this article treats a relation as the set-theoretic extension of a relational concept or term. Another variation reserves the term 'relation' to the corresponding logical entity, either the logical comprehension, which is the totality of intensions or abstract properties that all of the elements of the relation in extension have in common, or else the symbols that are taken to denote these elements and intensions. Further, but hardly finally, some writers of the latter persuasion introduce terms with more concrete connotations, like 'relational structure', for the set-theoretic extension of a given relational concept.

Adapted from the Wikipedia article "Formal definitions", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki