FACTOID # 29: 73.3% of America's gross operating surplus in motion picture and sound recording industries comes from California.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Relation (mathematics)

In mathematics, the concept of a relation is a generalization of 2-place relations, such as the relation of equality, denoted by the sign "=" in a statement like "5 + 7 = 12," or the relation of order, denoted by the sign "<" in a statement like "5 < 12". Relations that involve two places or roles are called binary relations by some and dyadic relations by others, the latter being historically prior but also useful when necessary to avoid confusion with binary (base 2) numerals. In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ... In mathematics, two mathematical objects are considered equal if they are precisely the same in every way. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ... The binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. ...


The next step up is to consider relations that can involve more than two places or roles, but still a finite number of them. These are called finite place or finitary relations. A finitary relation that involves k places is variously called a k-ary, a k-adic, or a k-dimensional relation. The number k is then called the arity, the adicity, or the dimension of the relation, respectively. See the formal definitions below. The mathematical term arity sprang from words like unary, binary, ternary, etc. ... 2-dimensional renderings (ie. ...

Contents

Informal introduction

The definition of relation given in the next Section formally captures a concept that is actually quite familiar from everyday life. For example, consider the relationship, 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 overuse 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, that carries all of the information from the Table in one neat package. Set theory is the mathematical theory of sets, which represent collections of abstract objects. ...


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. A relational database is a database that conforms to the relational model, and refers to a databases data and schema (the databases structure of how that data is arranged). ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...


For one thing, databases are designed to deal with empirical data, and experience is always finite, whereas mathematics is nothing if not concerned with infinity, at the very least, potential infinity. This difference in perspective brings up a number of ideas that are usefully introduced at this point, if by no means covered in depth.


Example: divisibility

A more typical example of a 2-place 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 "n|m" for "n divides m." In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...


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 n|m. 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 2|4 and 6|72 or as D(2, 4) and D(6, 72).


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 X1, …, Xk is a subset of their cartesian product, written LX1 × … × Xk. Under this definition, then, a k-ary relation is simply a set of k-tuples. In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ... In mathematics, the Cartesian product is a direct product of sets. ... In mathematics, a tuple is a finite sequence (also known as an ordered list) of objects, each of a specified type. ...


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 X1, …, Xk is a (k+1)-tuple L = (X1, …, Xk, G(L)), where G(L) is a subset of the cartesian product X1 × … × Xk. 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} = (a1, …, ak) or the variable element mathbf{x} = (x1, …, xk).


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 Xj 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 Xj are the same set X, then L is more simply referred to as a k-ary relation over X.
  • If any of the domains Xj is empty, then the cartesian product is empty, and the only relation over such a sequence of domains is the empty relation L = varnothing. As a result, naturally occurring 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. In mathematics, the domain of a function is the set of all input values to the function. ...


If L is a relation over the domains X1, …, Xk, it is conventional to consider a sequence of terms called variables, x1, …, xk, 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. 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 of the relation L, written fL or χ(L), is the boolean-valued function fL : X1 × … × Xk → B, defined in such a way that fL(mathbf{x}) = 1 just in case the k-tuple mathbf{x} is in the relation L. The characteristic function of a relation may also be called its indicator function, especially in probability and statistics. Some mathematicians use the phrase characteristic function synonymously with indicator function. ... A boolean-valued function, in some usages a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain. ... In the mathematical subfield of set theory, the indicator function, or characteristic function, is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Remark. ...


It is conventional in applied mathematics, computer science, and statistics to refer to a boolean-valued function like fL 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. In mathematics, a predicate is either a relation or the boolean-valued function that amounts to the characteristic function or the indicator function of such a relation. ... Logic (from ancient Greek &#955;&#8057;&#947;&#959;&#962; (logos), meaning reason) is the study of arguments. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ... Interpretation, or interpreting, is an activity that consists of establishing, either simultaneously or consecutively, oral or gestural communications between two or more speakers who are not speaking (or signing) the same language. ... First-order logic (FOL) is a universal language in symbolic science, and is in use everyday by mathematicians, philosophers, linguists, computer scientists and practitioners of artificial intelligence. ...


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. Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In any of several studies that treat the use of signs, for example, linguistics, logic, mathematics, semantics, and semiotics, the extension of a concept, idea, or sign consists of the things to which it applies, in contrast with its comprehension or intension, which consists very roughly of the ideas, properties... In logic, the comprehension of an object is the totality of intensions, that is, attributes, characters, marks, properties, or qualities, that the object possesses, or else the totality of intensions that are pertinent to the context of a given discussion. ... Intension refers to the meanings or characteristics encompassed by a given word. ... The word property, in philosophy, mathematics, and logic, refers to an attribute of an object; thus a red object is said to have the property of redness. ...


Example: coplanarity

For lines L in three-dimensional space, there is a ternary relation picking out the triples of lines that are coplanar. This does not reduce to the binary symmetric relation of coplanarity of pairs of lines. A set of points is said to be coplanar if and only if they lie on the same geometric plane. ... In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a. ...


In other words, writing P(L, M, N) when the lines L, M, and N lie in a plane, and Q(L, M) for the binary relation, it is not true that Q(L, M), Q(M, N) and Q(N, L) together imply P(L, M, N); although the converse is certainly true (any pair out of three coplanar lines is coplanar, a fortiori). There are two geometrical reasons for this.


In one case, for example taking the x-axis, y-axis and z-axis, the three lines are concurrent, i.e. intersect at a single point. In another case, L, M, and N can be three edges of an infinite triangular prism. In geometry, a triangular prism or three-sided prism is a polyhedron made of a triangular base, a translated copy, and 3 faces joining corresponding sides. ...


What is true is that if each pair of lines intersects, and the points of intersection are distinct, then pairwise coplanarity implies coplanarity of the triple.


Remarks

Relations are classified according to the number of sets in the cartesian product, in other words the number of terms in the expression:

  • Unary relation or property: L(u)
  • Binary relation: L(u, v) or u L v
  • Ternary relation: L(u, v, w)
  • Quaternary relation: L(u, v, w, x)

Relations with more than four terms are usually referred to as k-ary, for example, "a 5-ary relation". The word property, in philosophy, mathematics, and logic, refers to an attribute of an object; thus a red object is said to have the property of redness. ...


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–378, 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.

Charles Sanders Peirce (IPA: /pɝs/), (September 10, 1839 – April 19, 1914) was an American polymath, physicist, and philosopher, born in Cambridge, Massachusetts. ... Stanisław Ulam in the 1950s. ...

Bibliography

  • Bourbaki, N. (1994), Elements of the History of Mathematics, John Meldrum (trans.), Springer-Verlag, Berlin, Germany.
  • Halmos, P.R. (1960), Naive Set Theory, D. Van Nostrand Company, Princeton, NJ.
  • Lawvere, F.W., and Rosebrugh, R. (2003), Sets for Mathematics, Cambridge University Press, Cambridge, UK.
  • Maddux, R.D. (2006), Relation Algebras, vol. 150 in 'Studies in Logic and the Foundations of Mathematics', Elsevier Science.
  • Peirce, C.S. (1984), Writings of Charles S. Peirce: A Chronological Edition, Volume 2, 1867-1871, Peirce Edition Project (eds.), Indiana University Press, Bloomington, IN.
  • Royce, J. (1961), The Principles of Logic, Philosophical Library, New York, NY.
  • Tarski, A. (1956/1983), Logic, Semantics, Metamathematics, Papers from 1923 to 1938, J.H. Woodger (trans.), 1st edition, Oxford University Press, 1956. 2nd edition, J. Corcoran (ed.), Hackett Publishing, Indianapolis, IN, 1983.
  • Ulam, S.M. (1990), Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators, A.R. Bednarek and Françoise Ulam (eds.), University of California Press, Berkeley, CA.
  • Venetus, P. (1984), Logica Parva, Translation of the 1472 Edition with Introduction and Notes, Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany.

Nicolas Bourbaki is the collective allonym under which a group of (mainly French) 20th-century mathematicians wrote a series of books presenting an exposition of modern advanced mathematics, beginning in 1935. ... Paul Halmos Paul Richard Halmos (born March 3, 1916) is a Hungarian-born American mathematician who has done research in the fields of probability theory, statistics, operator theory, ergodic theory, and functional analysis (in particular Hilbert spaces). ... Francis William Lawvere is a mathematician who is known for his work in category theory and the philosophy of mathematics. ... Roger Maddux (born 1948) is an algebraist and logician currently tenured at Iowa State University. ... Marvin Lee Minsky (born August 9, 1927), sometimes affectionately known as Old Man Minsky, is an American scientist in the field of artificial intelligence (AI), co-founder of MITs AI laboratory, and author of several texts on AI and philosophy. ... Seymour Papert Seymour Papert (born March 1, 1928 Pretoria, South Africa) is an MIT mathematician, computer scientist, and prominent educator. ... The perceptron is a type of artificial neural network invented in 1957 at the Cornell Aeronautical Laboratory by Frank Rosenblatt. ... Charles Sanders Peirce (IPA: /pɝs/), (September 10, 1839 – April 19, 1914) was an American polymath, physicist, and philosopher, born in Cambridge, Massachusetts. ... Josiah Royce (November 20, 1855, Grass Valley, California. ... // Alfred Tarski (January 14, 1902, Warsaw, Russian-ruled Poland – October 26, 1983, Berkeley, California) was a logician and mathematician who spent four decades as a professor of mathematics at the University of California, Berkeley. ... Stanisław Ulam in the 1950s. ... Paul of Venice or Paulus Venetus (1368-1428) was Roman Catholic theologian of the Hermits of the Order of Saint Augustine. ...

See also

In logic and mathematics, relation construction and relational constructibility have to do with the ways that one relation is determined by an indexed family or a sequence of other relations, called the relation dataset. ... In logic and mathematics, the composition of relations is the generalization of the composition of functions. ... In logic and mathematics, relation reduction and relational reducibility have to do with the extent to which a given relation is determined by an indexed family or a sequence of other relations, called the relation dataset. ... A relational database is a database that conforms to the relational model, and refers to a databases data and schema (the databases structure of how that data is arranged). ... Relational algebra, an offshoot of first-order logic, is a set of relations closed under operators. ... The relational model for database management is a database model based on predicate logic and set theory. ... In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ... Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. ... In computing , a database can be defined as a structured collection of records or data that is stored in a computer so that a program can consult it to answer queries. ... In mathematics and statistics, a direct relationship is a positive relationship between two variables in which they both increase or decrease in conjunction. ... A negative, or inverse relationship is a mathematical relationship in which one variable decreases as another rises. ... Logic of relatives, short for logic of relative terms, is a term used to cover the study of relations in their logical, philosophical, or semiotic aspects, as distinguished from, though closely coordinated with, their more properly formal, mathematical, or objective aspects. ... A logical matrix, in the finite dimensional case, is a k-dimensional array with entries from the boolean domain B = {0, 1}. Such a matrix affords a matrix representation of a k-adic relation. ... In set theory, a projection is one of two closely related types of functions or operations, namely: A set-theoretic operation typified by the jth projection map, written , that takes an element of the cartesian product to the value . ... A sign relation is the basic construct in the theory of signs, or semiotic theory, as developed by Charles Sanders Peirce (1839-1914). ... In logic and mathematics, a tacit extension is in formal respects the simplest or the logically least committal of the several possible set operations that are inverse to the set-theoretic operation of projection. ... The theory of relations treats the subject matter of relations in its combinatorial aspect, as distinguished from, though related to, its more properly logical study on one side and its more generally mathematical study on another. ... In logic, mathematics, and semiotics, a triadic relation or a ternary relation is an important special case of a polyadic or finitary relation, one in which the number of places in the relation is three. ...

External links

  • Cartesian Product and Relation at ProvenMath

  Results from FactBites:
 
Binary Relation (2105 words)
Relation, a mathematical concept, is a set of ordered pairs.
With the definition of a relation explicitly stated, one is able to not only construct examples, but also define an algebra (used vaguely, not as the mathematical concept in the branch of mathematics called algebra) on relations.
Another interesting topic in the study of relation is the study of relation on a set X. In this case, both the domain and range of the relation are subsets of X. On these relations, mathematicians use a few adjectives to describe the different elementary types of relation on a given set.
Relation (mathematics) - Wikipedia, the free encyclopedia (1794 words)
Relations that involve two 'places' or 'roles' are called binary relations by some and dyadic relations by others, the latter being historically prior but also useful when necessary to avoid confusion with binary (base 2) numerals.
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.
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.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m