Finitary relation

In mathematics, a finitary relation over a sequence of sets Template:Nowrap is a subset of the Cartesian product Template:Nowrap; that is, it is a set of n-tuples Template:Nowrap, each being a sequence of elements x_i in the corresponding X_i.Template:Sfn<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> Typically, the relation describes a possible connection between the elements of an n-tuple. For example, the relation "x is divisible by y and z" consists of the set of 3-tuples such that when substituted to x, y and z, respectively, make the sentence true.

The non-negative integer n that gives the number of "places" in the relation is called the arity, adicity or degree of the relation. A relation with n "places" is variously called an n-ary relation, an n-adic relation or a relation of degree n. Relations with a finite number of places are called finitary relations (or simply relations if the context is clear). It is also possible to generalize the concept to infinitary relations with infinite sequences.Template:Sfn

Definitions

When two objects, qualities, classes, or attributes, viewed together by the mind, are seen under some connexion, that connexion is called a relation.{{#if:Augustus De MorganTemplate:Sfn|{{#if:|}}

— {{#if:|, in }}Template:Comma separated entries

}}

{{#invoke:Check for unknown parameters|check|unknown=Template:Main other|preview=Page using Template:Blockquote with unknown parameter "_VALUE_"|ignoreblank=y| 1 | 2 | 3 | 4 | 5 | author | by | char | character | cite | class | content | multiline | personquoted | publication | quote | quotesource | quotetext | sign | source | style | text | title | ts }}

Definition

R is an n-ary relation on sets Template:Nowrap is given by a subset of the Cartesian product Template:Nowrap.Template:Sfn

Since the definition is predicated on the underlying sets Template:Nowrap, R may be more formally defined as the (Template:Nowrap)-tuple Template:Nowrap, where G, called the graph of R, is a subset of the Cartesian product Template:Nowrap.

As is often done in mathematics, the same symbol is used to refer to the mathematical object and an underlying set, so the statement Template:Nowrap is often used to mean Template:Nowrap is read "x₁, ..., x_n are R-related" and are denoted using prefix notation by Template:Nowrap and using postfix notation by Template:Nowrap. In the case where R is a binary relation, those statements are also denoted using infix notation by Template:Nowrap.

The following considerations apply:

• The set X_i is called the Template:Itcoth domain of R.Template:Sfn In the case where R is a binary relation, X₁ is also called simply the domain or set of departure of R, and X₂ is also called the codomain or set of destination of R.
• When the elements of X_i are relations, X_i is called a nonsimple domain of R.Template:Sfn
• The set of Template:Nowrap such that Template:Nowrap for at least one Template:Nowrap is called the ith domain of definition or active domain of R.Template:Sfn In the case where R is a binary relation, its first domain of definition is also called simply the domain of definition or active domain of R, and its second domain of definition is also called the codomain of definition or active codomain of R.
• When the Template:Mvarth domain of definition of R is equal to X_i, R is said to be total on its ith domain (or on X_i, when this is not ambiguous). In the case where R is a binary relation, when R is total on X₁, it is also said to be left-total or serial, and when R is total on X₂, it is also said to be right-total or surjective.
• When Template:Nowrap Template:Nowrap Template:Nowrap, where Template:Nowrap, Template:Nowrap, Template:Nowrap, and Template:Nowrap is a partition of Template:Nowrap, R is said to be unique on Template:Nowrap, and Template:Nowrap is called a primary keyTemplate:Sfn of R. In the case where R is a binary relation, when R is unique on Template:Mset, it is also said to be left-unique or injective, and when R is unique on Template:Mset, it is also said to be univalent or right-unique.
• When all X_i are the same set X, it is simpler to refer to R as an n-ary relation over X, called a homogeneous relation. Without this restriction, R is called a heterogeneous relation.
• When any of X_i is empty, the defining Cartesian product is empty, and the only relation over such a sequence of domains is the empty relation Template:Nowrap.

Let a Boolean domain B be a two-element set, say, Template:Nowrap, whose elements can be interpreted as logical values, typically Template:Nowrap and Template:Nowrap. The characteristic function of R, denoted by χ_R, is the Boolean-valued function Template:Nowrap, defined by Template:Nowrap if Template:Nowrap and Template:Nowrap otherwise.

In applied mathematics, computer science and statistics, it is common to refer to a Boolean-valued function as an n-ary predicate. From the more abstract viewpoint of formal logic and model theory, the relation R constitutes a logical model or a relational structure, that serves as one of many possible interpretations of some n-ary predicate symbol.

Because relations arise in many scientific disciplines, as well as in many branches of mathematics and logic, there is considerable variation in terminology. Aside from the set-theoretic extension of a relational concept or term, the term "relation" can also be used to refer to the corresponding logical entity, either the logical comprehension, which is the totality of intensions or abstract properties shared by all elements in the relation, or else the symbols denoting these elements and intensions. Further, some writers of the latter persuasion introduce terms with more concrete connotations (such as "relational structure" for the set-theoretic extension of a given relational concept).

Specific values of n

Nullary

Template:Main article Nullary (0-ary) relations count only two members: the empty nullary relation, which never holds, and the universal nullary relation, which always holds. This is because there is only one 0-tuple, the empty tuple (), and there are exactly two subsets of the (singleton) set of all 0-tuples. They are sometimes useful for constructing the base case of an induction argument.

Unary

Unary (1-ary) relations can be viewed as a collection of members (such as the collection of Nobel laureates) having some property (such as that of having been awarded the Nobel Prize).

Every nullary function is a unary relation.

Binary

Binary (2-ary) relations are the most commonly studied form of finitary relations. Homogeneous binary relations (where Template:Nowrap) include

• Equality and inequality, denoted by signs such as = and < in statements such as "Template:Nowrap", or
• Divisibility, denoted by the sign | in statements such as "Template:Nowrap".

Heterogeneous binary relations include

• Set membership, denoted by the sign ∈ in statements such as "Template:Nowrap".

Ternary

Ternary (3-ary) relations include, for example, the binary functions, which relate two inputs and the output. All three of the domains of a homogeneous ternary relation are the same set.

Example

Consider the ternary relation R "x thinks that y likes z" over the set of people Template:Nowrap, defined by:

Template:Nowrap.

R can be represented equivalently by the following table:

Relation R "x thinks that y likes z"

x	y	z
Alice	Bob	Denise
Charles	Alice	Bob
Charles	Charles	Alice
Denise	Denise	Denise

Here, each row represents a triple of R, that is it makes a statement of the form "x thinks that y likes z". For instance, the first row states that "Alice thinks that Bob likes Denise". All rows are distinct. The ordering of rows is insignificant but the ordering of columns is significant.Template:Sfn

The above table is also a simple example of a relational database, a field with theory rooted in relational algebra and applications in data management.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> Computer scientists, logicians, and mathematicians, however, tend to have different conceptions what a general relation is, and what it is consisted of. For example, databases are designed to deal with empirical data, which is by definition finite, whereas in mathematics, relations with infinite arity (i.e., infinitary relation) are also considered.

History

The logician Augustus De Morgan, in work published around 1860, was the first to articulate the notion of relation in anything like its present sense. He also stated the first formal results in the theory of relations (on De Morgan and relations, see Merrill 1990).

Charles Peirce, Gottlob Frege, Georg Cantor, Richard Dedekind and others advanced the theory of relations. Many of their ideas, especially on relations called orders, were summarized in The Principles of Mathematics (1903) where Bertrand Russell made free use of these results.

In 1970, Edgar Codd proposed a relational model for databases, thus anticipating the development of data base management systems.Template:Sfn

See also

• Incidence structure
• Hypergraph
• Logic of relatives
• Logical matrix
• Partial order
• Predicate (mathematical logic)
• Projection (set theory)
• Reflexive relation
• Relation algebra
• Relational algebra
• Relational model
• Relations (philosophy)

Bibliography

• Template:Citation
• Template:Citation
• Template:Cite journal
• Template:Cite book
• Template:Citation
• Template:Citation
• Template:Citation
• Lewis, C.I. (1918) A Survey of Symbolic Logic, Chapter 3: Applications of the Boole–Schröder Algebra, via Internet Archive
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Cite book
• Peirce, C.S. (1870), "Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic", Memoirs of the American Academy of Arts and Sciences 9, 317–78, 1870. Reprinted, Collected Papers CP 3.45–149, Chronological Edition CE 2, 359–429.
• Peirce, C.S. (1984) Writings of Charles S. Peirce: A Chronological Edition, Volume 2, 1867–1871. Peirce Edition Project, eds. Indiana University Press.
• Template:Citation
• Template:Citation
• Template:Citation 2nd edition, J. Corcoran, ed. Indianapolis IN: Hackett Publishing.
• Ulam, S.M. and Bednarek, A.R. (1990), "On the Theory of Relational Structures and Schemata for Parallel Computation", pp. 477–508 in A.R. Bednarek and Françoise Ulam (eds.), Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators, University of California Press, Berkeley, CA.
• Template:Citation
• Template:Citation