In mathematics, a finitary relation has a finite number of "places". In set theory and logic, a relation is a property that assigns truth values to ktuples of individuals. Typically, the property describes a possible connection between the components of a ktuple. For a given set of ktuples, a truth value is assigned to each ktuple according to whether the property does or does not hold.
An example of a ternary relation (i.e., between three individuals) is: "X was introduced to Y by Z", where \left(X, Y, Z\right) is a 3tuple of persons; for example, "Beatrice Wood was introduced to HenriPierre Roché by Marcel Duchamp" is true, while "Karl Marx was introduced to Friedrich Engels by Queen Victoria" is false.
Contents

Informal introduction 1

Relations with a small number of "places" 2

Formal definitions 3

Transitive relations 4

Analogy with functions 5

Examples 6

Suggested reading 7

Notes 8

See also 9

References 10

Bibliography 11

External links 12
Informal introduction
Relation is formally defined in the next section. In this section we introduce the concept of a relation with a familiar everyday example. Consider the relation involving three roles that people might play, expressed in a statement of the form "X thinks that Y likes Z ". The facts of a concrete situation could be organized in a table like the following:
Relation S : X thinks that Y likes Z
Person X

Person Y

Person Z

Alice

Bob

Denise

Charles

Alice

Bob

Charles

Charles

Alice

Denise

Denise

Denise

Each row of the table records a fact or makes an assertion of the form "X thinks that Y likes Z ". For instance, the first row says, in effect, "Alice thinks that Bob likes Denise". The table represents a relation S over the set P of people under discussion:

P = {Alice, Bob, Charles, Denise}.
The data of the table are equivalent to the following set of ordered triples:

S = {(Alice, Bob, Denise), (Charles, Alice, Bob), (Charles, Charles, Alice), (Denise, Denise, Denise)}.
By a slight abuse of notation, it is usual to write S(Alice, Bob, Denise) to say the same thing as the first row of the table. The relation S is a ternary relation, since there are three items involved in each row. The relation itself is a mathematical object defined in terms of concepts from set theory (i.e., the relation is a subset of the Cartesian product on {Person X, Person Y, Person Z}), that carries all of the information from the table in one neat package. Mathematically, then, a relation is simply an "ordered set".
The table for relation S is an extremely simple example of a relational database. The theoretical aspects of databases are the specialty of one branch of computer science, while their practical impacts have become all too familiar in our everyday lives. Computer scientists, logicians, and mathematicians, however, tend to see different things when they look at these concrete examples and samples of the more general concept of a relation.
For one thing, databases are designed to deal with empirical data, and experience is always finite, whereas mathematics at the very least concerns itself with potential infinity. This difference in perspective brings up a number of ideas that may be usefully introduced at this point, if by no means covered in depth.
Relations with a small number of "places"
The variable k giving the number of "places" in the relation, 3 for the above example, is a nonnegative integer, called the relation's arity, adicity, or dimension. A relation with k places is variously called a kary, a kadic, or a kdimensional relation. Relations with a finite number of places are called finiteplace or finitary relations. It is possible to generalize the concept to include infinitary relations between infinitudes of individuals, for example infinite sequences; however, in this article only finitary relations are discussed, which will from now on simply be called relations.
Since there is only one 0tuple, the socalled empty tuple ( ), there are only two zeroplace relations: the one that always holds, and the one that never holds. They are sometimes useful for constructing the base case of an induction argument. Oneplace relations are called unary relations. For instance, any set (such as the collection of Nobel laureates) can be viewed as a collection of individuals having some property (such as that of having been awarded the Nobel prize). Twoplace relations are called binary relations or, in the past, dyadic relations. Binary relations are very common, given the ubiquity of relations such as:

Equality and inequality, denoted by signs such as '=' and '<' in statements like '5 < 12';

Being a divisor of, denoted by the sign '\mid' in statements like '13 \mid 143';

Set membership, denoted by the sign '\in' in statements like '1 \in \mathbb{N}'.
A kary relation is a straightforward generalization of a binary relation.
Formal definitions
When two objects, qualities, classes, or attributes, viewed together by the mind, are seen under some connexion, that connexion is called a relation.
—
[1]
The simpler of the two definitions of kplace relations encountered in mathematics is:
Definition 1. A relation L over the sets X_{1}, …, X_{k} is a subset of their Cartesian product, written L ⊆ X_{1} × … × X_{k}.
Relations are classified according to the number of sets in the defining Cartesian product, in other words, according to the number of terms following L. Hence:

Relations with more than four terms are usually referred to as kary or nary, for example, "a 5ary relation". A kary relation is simply a set of ktuples.
The second definition makes use of an idiom that is common in mathematics, stipulating that "such and such is an ntuple" 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_{1}, …, X_{k} is a (k + 1)tuple L = (X_{1}, …, X_{k}, G(L)), where G(L) is a subset of the Cartesian product X_{1} × … × 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 \mathbf{a} = (a_{1}, …, a_{k}) or the variable element \mathbf{x} = (x_{1}, …, x_{k}).
A statement of the form "\mathbf{a} is in the relation L " is taken to mean that \mathbf{a} is in L under the first definition and that \mathbf{a} 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. Under the first definition, the relation does not uniquely determine a given sequence of domains.

If all of the domains X_{j} are the same set X, then it is simpler to refer to L as a kary relation over X.

If any of the domains X_{j} is empty, then the defining Cartesian product is empty, and the only relation over such a sequence of domains is the empty relation L = \varnothing. Hence it is commonly stipulated 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 definitions, an entity satisfying the second definition may be called an embedded or included relation.
If L is a relation over the domains X_{1}, …, X_{k}, it is conventional to consider a sequence of terms called variables, x_{1}, …, x_{k}, that are said to range over the respective domains.
Let a Boolean domain B be a twoelement set, say, B = {0, 1}, whose elements can be interpreted as logical values, typically 0 = false and 1 = true. The characteristic function of the relation L, written ƒ_{L} or χ(L), is the Booleanvalued function ƒ_{L} : X_{1} × … × X_{k} → B, defined in such a way that ƒ_{L}(\mathbf{x}) = 1 just in case the ktuple \mathbf{x} is in the relation L. Such a function can also be called an indicator function, particularly in probability and statistics, to avoid confusion with the notion of a characteristic function in probability theory.
It is conventional in applied mathematics, computer science, and statistics to refer to a Booleanvalued function like ƒ_{L} as a kplace predicate. From the more abstract viewpoint of formal logic and model theory, the relation L constitutes a logical model or a relational structure that serves as one of many possible interpretations of some kplace 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. This article treats a relation as the settheoretic extension of a relational concept or term. A variant usage 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, some writers of the latter persuasion introduce terms with more concrete connotations, like "relational structure", for the settheoretic extension of a given relational concept.
Transitive relations
Transitive relations are binary relations R on a single set X where for all a, b, c in X, aRb and bRc implies aRc. Transitive relations fall into two broad classes, equivalence relations and order relations. Equivalence relations are also symmetric and reflexive, while order relations are antisymmetric, either reflexive (inclusive order) or antireflexive (strict order), and in the case of total orders, total. The algebraic structure of equivalence relations builds on transformation groups; that of order relations builds on lattice theory.
Analogy with functions
A binary relation R on sets X and Y may be considered to associate, with each member of X, zero or more members of Y. (In the case of a relation T on more than two sets, X or Y or both can be cross products of any of the sets on which T is defined.) X is then referred to as the domain of R. Y is called the range or codomain of R. The subset of Y associated with a member x of X, is called the image of x, written as R(x). The subset of Y associated with a subset ξ of X is the union of the images of all the x in ξ and is called the image of ξ, written as R(ξ).
R is fully defined or total at X, if for every member x of X, there is at least one member y of Y where xRy. R is uniquely defined or tubular at X, if for every member x of X, there is at most one member y of Y where xRy. R is surjective or total at Y, if for every member y of Y, there is at least one member x of X where xRy. R is injective or tubular at Y, if for every member y of Y, there is at most one member x of X where xRy. If R is both fully defined and uniquely defined then R is well defined or 1regular at X (for every member x of X, there is one and only one member y of Y where xRy). If R is both surjective and injective then R is bijective or 1regular at Y. If R is both uniquely defined and injective then R is onetoone.
A function is a well defined relation. A uniquely defined relation is a partial function. A surjective function is a surjection. An injective function is an injection. A bijective function is a bijection.
Relations generalize functions. Just as there is composition of functions, there is composition of relations.
Every binary relation R has a transpose relation R^{−1}, which is related to the inverse function. For a relation R that is both fully defined and injective, the transpose relation R^{−1} is a true inverse in that R^{−1} faithfully restores any element x or subset ξ: R^{−1}(R(ξ)) = ξ.
Examples
This section discusses, by way of example, the arithmetical binary relation of divisibility.
Divisibility
A more typical example of a 2place relation in mathematics is the relation of divisibility between two positive integers n and m that is expressed in statements like "n divides m" or "n goes into m." This is a relation that comes up so often that a special symbol "" is reserved to express it, allowing one to write "nm" for "n divides m."
To express the binary relation of divisibility in terms of sets, we have the set P of positive integers, P = {1, 2, 3, …}, and we have the binary relation D on P such that the ordered pair (n, m) is in the relation D just in case nm. In other turns of phrase that are frequently used, one says that the number n is related by D to the number m just in case n is a factor of m, that is, just in case n divides m with no remainder. The relation D, regarded as a set of ordered pairs, consists of all pairs of numbers (n, m) such that n divides m.
For example, 2 is a factor of 4, and 6 is a factor of 72, which can be written either as 24 and 672 or as D(2, 4) and D(6, 72).
Suggested reading
The logician Richard Dedekind, and others. Russell and A. N. Whitehead made free use of these results in their Principia Mathematica. For a systematic treatise on the theory of relations see R. Fraïssé, Theory of Relations (North Holland; 2000).
Notes

^ De Morgan, A. (1858) "On the syllogism, part 3" in Heath, P., ed. (1966) On the syllogism and other logical writings. Routledge. P. 119,
See also
References

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.

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.
Bibliography

Bourbaki, N. (1994) Elements of the History of Mathematics, John Meldrum, trans. SpringerVerlag.

Carnap, Rudolf (1958) Introduction to Symbolic Logic with Applications. Dover Publications.

Halmos, P.R. (1960) Naive Set Theory. Princeton NJ: D. Van Nostrand Company.

Lawvere, F.W., and R. Rosebrugh (2003) Sets for Mathematics, Cambridge Univ. Press.

Lucas, J. R. (1999) Conceptual Roots of Mathematics. Routledge.

Maddux, R.D. (2006) Relation Algebras, vol. 150 in 'Studies in Logic and the Foundations of Mathematics'. Elsevier Science.

Merrill, Dan D. (1990) Augustus De Morgan and the logic of relations. Kluwer.

Peirce, C.S. (1984) Writings of Charles S. Peirce: A Chronological Edition, Volume 2, 18671871. Peirce Edition Project, eds. Indiana University Press.

Russell, Bertrand (1903/1938) The Principles of Mathematics, 2nd ed. Cambridge Univ. Press.

Suppes, Patrick (1960/1972) Axiomatic Set Theory. Dover Publications.

Tarski, A. (1956/1983) Logic, Semantics, Metamathematics, Papers from 1923 to 1938, J.H. Woodger, trans. 1st edition, Oxford University Press. 2nd edition, J. Corcoran, ed. Indianapolis IN: Hackett Publishing.

Ulam, S.M. (1990) Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators in A.R. Bednarek and Françoise Ulam, eds., University of California Press.
External links

Cartesian Product, Relation, Function @ ProvenMath
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.