User:Randall Holmes/Sandbox/relation (mathematics)

From Wikipedia, the free encyclopedia

A relation is a mathematical object which implements the logical notion of relation in its fullest generality, that is, of an n-ary predicate. The simplest (and commonest) approach is to implement the n-ary predicate P as the set of all n-tuples (a_1,\ldots,a_n) such that Pa_1,\ldots,a_n is true; there is a more refined approach, described below, under which this object is not the implementation of the relation, but under which it still plays an important role as the graph of the relation implementing the predicate P. In order to preserve neutrality between the two different definitions of relation we consider, we will refer to \{(a_1,\ldots,a_n) \mid Pa_1\ldots a_n\}as the graph of the relation implementing the logical relation P, while recalling that under our first definition the graph of a relation is the relation itself. Under the first definition, any set of n-tuples is an n-ary relation (the set A of n-tuples implements, if nothing else, the logical n-ary predicate A^*a_1\ldots a_n \equiv_{def} (a_1,\ldots,a_n) \in A).

An n-ary relation whose graph is a subset of A_1\times\ldots\times A_n is said to have first domain A1, second domain A2, and in general ith domain Ai for 1 \leq i \leq n. In the case n = 2, A1 is called the domain and A2 the codomain. The sequence (A_1,\ldots,A_n) is said to be a frame for the graph of the relation (there are in general many possible frames for a given graph). Under the second definition of relation, a relation is a pair (F,G), where F is a finite sequence of sets and G is a subset of the cartesian product of F: in this case G is the graph of the relation (F,G), and F is a frame for G incorporating additional information about the intended domains of the relation.


Contents

[edit] Definition

The two alternative formal definitions of a finite arity relation, specifically, a k-ary relation can now be stated.

  • Definition I. A k-ary relation is a set of k-tuples.
  • Definition II. A k-ary 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. If all of the Xj for j = 1 to k are the same set X, then L is more simply called a k-ary relation over X. The set G(L) is called the graph of L.

The formal definitions simply repeat more concisely what was said above.

[edit] History of the two definitions and contrasts between them

Definition I has historically been the definition of the notion of relation in set theory. Definition II has become increasingly popular as category theory has become more widely used. The difference between the two definitions is often invisible to the user of the concept; it becomes significant if one needs to consider the domains of a relation as features of the relation. For example, if one is using Definition I, one cannot say that a function (which is a special case of a 2-ary relation) is "surjective" or "onto": one must say that it is "onto X", providing a specification of the intended codomain (or, as is often done carelessly), trust the reader to deduce the intended codomain from context.

A second contrast between the two definitions is the relationship between k-ary relations for different values of k. Under Definition I, relations of whatever finite arity are a special kind of binary relation, which is thus the most general category. Under Definition II, the different arities of relation do not overlap, so the binary relation is just one sort of relation (the 2-ary) among many.

[edit] Variant terminology

Because the concept of a relation has been developed quite literally from the beginnings of logic and mathematics, and because it has incorporated contributions from a diversity of thinkers from many different times and intellectual climates, there is a wide variety of terminology that the reader may run across in connection with the subject.

One dimension of variation is reflected in the names that are given to k-place relations, with some writers using medadic, monadic, dyadic, triadic, k-adic where other writers use nullary, unary, binary, ternary, k-ary.

One finds a relation on a finite number of domains described as either a finitary relation or a polyadic relation. If the number of domains is finite, say equal to k, then the parameter k may be referred to as the arity, the adicity, or the dimension of the relation. In these cases, the relation may be described as a k-ary relation, a k-adic relation, or a k-dimensional relation, respectively.

A more conceptual than nominal variation has to do with whether one uses the terms 'predicate', 'relation', and even 'term' to refer to the formal object proper or else to the corresponding semiotic or syntactic items that are used to denote it. Historically speaking, just about every combination of modalities has been used by one school of thought or another, but it suffices here merely to indicate how the options are generated.

[edit] Remarks

Because a relation as above defines uniquely a k-ary predicate that holds for x1, …, xk if (x1, …, xk) is in G(R), and vice versa, the relation and the predicate are often denoted with the same symbol. So, for example, the following two statements are considered to be equivalent:

  • (x_1, x_2,\dotsb)\in G(R)
  • R(x_1, x_2,\dotsb)

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: R(x)
  • Binary relation: R(x, y) or x R y
  • Ternary relation: R(x, y, z)
  • Quaternary relation: R(x, y, z, w)

Relations with more than 4 terms are usually called k-ary; for example "a 5-ary relation".

[edit] Sets and classes

Some logical relations (an obvious example is the binary relation of equality) have no graphs in the usual set theory ZFC because there is no set large enough. In a set theory with proper classes such as NBG or Morse-Kelley set theory such relations do have graphs. They will only have frames if a different definition of the ordered pair is used, allowing construction of n-tuples of proper classes. Suitable definitions are described in the ordered pair article. So both Definition I and Definition II can be implemented in this wider context.

[edit] References

  • Peirce, C.S., "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., "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, 1990.

[edit] Bibliography

  • Bourbaki, N., Elements of the History of Mathematics, John Meldrum (trans.), Springer-Velag, Berlin, Germany, 1994.
  • Chang, C.C., and Keisler, H.J., Model Theory, North-Holland, Amsterdam, Netherlands, 1973.
  • Halmos, P.R., Naive Set Theory, D. Van Nostrand Company, Princeton, NJ, 1960.
  • Kelley, J.L., General Topology, Van Nostrand Reinhold, New York, NY, 1955.
  • Lawvere, F.W., and Rosebrugh, R., Sets for Mathematics, Cambridge University Press, Cambridge, UK, 2003.
  • Lawvere, F.W., and Schanuel, S.H., Conceptual Mathematics, A First Introduction to Categories, Cambridge University Press, Cambridge, UK, 1997. Reprinted with corrections, 2000.
  • Mathematical Society of Japan, Encyclopedic Dictionary of Mathematics, 2nd edition, 2 vols., Kiyosi Itô (ed.), MIT Press, Cambridge, MA, 1993.
  • Mili, A., Desharnais, J., Mili, F., with Frappier, M., Computer Program Construction, Oxford University Press, New York, NY, 1994. — Introduction to Tarskian relation theory and its applications within the relational programming paradigm.
  • Peirce, C.S., Writings of Charles S. Peirce: A Chronological Edition, Volume 2, 1867-1871, Peirce Edition Project (eds.), Indiana University Press, Bloomington, IN, 1984. (= CE 2)
  • Royce, J., The Principles of Logic, Philosophical Library, New York, NY, 1961.
  • Runes, D.D. (ed.), Dictionary of Philosophy, Littlefield, Adams, and Company, Totowa, NJ, 1962.
  • Styazhkin, N.I., History of Mathematical Logic from Leibniz to Peano, MIT Press, Cambridge, MA, 1969.
  • Tarski, A., Logic, Semantics, Metamathematics, Papers from 1923 to 1938, J.H. Woodger (trans.), first edition, Oxford University Press, 1956, second edition, J. Corcoran (ed.), Hackett Publishing, Indianapolis, IN, 1983.
  • Ulam, S.M., 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, 1990.

[edit] See also

Category:Logic Category:Set theory