Theory of relations

Not to be confused with Relational theory.

This article is about the theory of relations with regard to its specifically combinatorial aspects. For a general discussion of the basic definitions, see Binary relation and Finitary relation.

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.

A relation, as conceived in the combinatorial theory of relations, is a mathematical object that in general can have a very complex type, the complexity of which is best approached in several stages, as indicated next.

In order to approach the combinatorial definition of a relation, it helps to introduce a few preliminary notions that can serve as stepping stones to the general idea.

A relation in mathematics is defined as an object that has its existence as such within a definite context or setting. It is literally the case that to change this setting is to change the relation that is being defined. The particular type of context that is needed here is formalized as a collection of elements from which are chosen the elements of the relation in question. This larger collection of elementary relations or tuples is constructed by means of the set-theoretic product commonly known as the cartesian product.

Preliminaries

A relation L is defined by specifying two mathematical objects as its constituent parts:

The first part is called the figure of L, notated as figure(L) or F(L).

The second part is called the ground of L, notated as ground(L) or G(L).

In the special case of a finitary relation, for concreteness a k-place relation, the concepts of figure and ground are defined as follows:

The ground of L is a sequence of k nonempty sets, X₁, …, X_k, called the domains of the relation L.

The figure of L is a subset of the cartesian product taken over the domains of L, that is, F(L) ⊆ G(L) = X₁ × … × X_k.

Strictly speaking, then, the relation L consists of a couple of things, L = (F(L), G(L)), but it is customary in loose speech to use the single name L in a systematically equivocal fashion, taking it to denote either the couple L = (F(L), G(L)) or the figure F(L). There is usually no confusion about this so long as the ground of the relation can be gathered from context.

Definition

The formal definition of a finitary relation, specifically, a k-ary relation can now be stated.

Definition. A k-ary relation L over the nonempty sets X₁, …, X_k is a (1+k)-tuple L = (F(L), X₁, …, X_k) where F(L) is a subset of the cartesian product X₁ × … × X_k. If all of the X_j for j = 1 to k are the same set X, then L is more simply called a k-ary relation over X. The set F(L) is called the figure of L and, providing that the sequence of sets X₁, …, X_k is fixed throughout a given discussion or determinate in context, one may regard the relation L as being determined by its figure F(L).

The formal definition simply repeats more concisely what was said above, merely unwrapping the conceptual packaging of the relation's ground to define the relation in 1 + k parts, as L = (F(X), X₁, …, X_k), rather than just the two, as L = (F(L), G(L)).

A k-ary predicate is a boolean-valued function on k variables.

Local incidence properties

Numerical incidence properties

A numerical incidence property (NIP) of a relation is a local incidence property that depends on the cardinalities of its local flags.

For example, L is said to be c-regular at j if and only if the cardinality of the local flag L_x.j is c for all x in X_j, or, to write it in symbols, if and only if |L_x.j| = c for all x in X_j.

In a similar fashion, one can define the NIPs (< c)-regular at j, (> c)-regular at j, and so on. For ease of reference, a few of these definitions are recorded here:

$L$	is	c-regular	at j	if and only if	$\|L_{x.j}\|$	=	c	for all x in X_j.
$L$	is	(< c)-regular	at j	if and only if	$\|L_{x.j}\|$	<	c	for all x in X_j.
$L$	is	(> c)-regular	at j	if and only if	$\|L_{x.j}\|$	>	c	for all x in X_j.

The definition of a local flag can be broadened from a point x in X_j to a subset M of X_j, arriving at the definition of a regional flag in the following way:

Suppose that L ⊆ X₁ × … × X_k, and choose a subset M ⊆ X_j. Then L_M.j is a subset of L that is said to be the flag of L with M at j, or the M.j-flag of L, an object which has the following definition:

L_M.j

{ (x₁, …, x_j, …, x_k) ∈ L : x_j ∈ M }.

Returning to 2-adic relations, it is useful to describe some familiar classes of objects in terms of their local and their numerical incidence properties. Let L ⊆ S × T be an arbitrary 2-adic relation. The following properties of L can be defined:

$L$	is	total	at S	if and only if	$L$	is	(≥1)-regular	at S.
$L$	is	total	at T	if and only if	$L$	is	(≥1)-regular	at T.
$L$	is	tubular	at S	if and only if	$L$	is	(≤1)-regular	at S.
$L$	is	tubular	at T	if and only if	$L$	is	(≤1)-regular	at T.

If L ⊆ S × T is tubular at S, then L is called a partial function or a prefunction from S to T, sometimes indicated by giving L an alternate name, say, "p", and writing L = p : S $\rightharpoonup$ T.

Just by way of formalizing the definition:

p : S

\rightharpoonup

if and only if

tubular

at S.

If L is a prefunction p : S $\rightharpoonup$ T that happens to be total at S, then L is called a function from S to T, indicated by writing L = f : S → T. To say that a relation L ⊆ S × T is totally tubular at S is to say that it is 1-regular at S. Thus, we may formalize the following definition:

f : S → T

if and only if

1-regular

at S.

In the case of a function f : S → T, one has the following additional definitions:

f	is	surjective	if and only if	f	is	total	at T.
f	is	injective	if and only if	f	is	tubular	at T.
f	is	bijective	if and only if	f	is	1-regular	at T.

Variations

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 depends on whether one uses terms like 'predicate', 'relation', and even 'term' to refer to the formal object proper or else to the allied syntactic items that are used to denote them. Compounded with this variation is still another, frequently associated with philosophical differences over the status in reality accorded formal objects. Among those who speak of numbers, functions, properties, relations, and sets as being real, that is to say, as having objective properties, there are divergences as to whether some things are more real than others, especially whether particulars or properties are equally real or else one derivative of the other. 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.

Examples

See the articles on relations, relation composition, relation reduction, sign relations, and triadic relations for concrete examples of relations.

Many relations of the greatest interest in mathematics are triadic relations, but this fact is somewhat disguised by the circumstance that many of them are referred to as binary operations, and because the most familiar of these have very specific properties that are dictated by their axioms. This makes it practical to study these operations for quite some time by focusing on their dyadic aspects before being forced to consider their proper characters as triadic relations.

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, also separately as an extract, Google Books Eprint. Reprinted, Collected Papers of Charles Sanders Peirce v. 3 paragraphs 45-149, Writings of Charles S. Peirce v. 2, pp. 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.

Bibliography

Barr, M. and Wells, C., Category Theory for Computing Science, Hemel Hempstead, UK, 1990.

Bourbaki, N., Elements of the History of Mathematics, John Meldrum (trans.), Springer-Verlag, Berlin, Germany, 1994.

Carnap, Rudolf, Introduction to Symbolic Logic with Applications, Dover Publications, New York, NY, 1958.

Chang, C.C., and Keisler, H.J., Model Theory, North-Holland, Amsterdam, Netherlands, 1973.

van Dalen, D., Logic and Structure, 2nd edition, Springer-Verlag, Berlin, Germany, 1980.

Devlin, K.J., The Joy of Sets: Fundamentals of Contemporary Set Theory, 2nd edition, Springer-Verlag, New York, NY, 1993.

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

van Heijenoort, J., From Frege to Gödel, A Source Book in Mathematical Logic, 1879–1931, Harvard University Press, Cambridge, MA, 1967. Reprinted with corrections, 1977.

Kelley, J.L., General Topology, Van Nostrand Reinhold, New York, NY, 1955.

Kneale, W. and Kneale, M., The Development of Logic, Oxford University Press, Oxford, UK, 1962. Reprinted with corrections, 1975.

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.

Lucas, John Randolph, Conceptual Roots of Mathematics, Routledge, 1999.

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

Manin, Yu. I., A Course in Mathematical Logic, Neal Koblitz (trans.), Springer-Verlag, New York, NY, 1977.

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.

Mitchell, J.C., Foundations for Programming Languages, MIT Press, Cambridge, MA, 1996.

Peirce, C.S., Collected Papers of Charles Sanders Peirce, vols. 1-6, Charles Hartshorne and Paul Weiss (eds.), vols. 7-8, Arthur W. Burks (ed.), Harvard University Press, Cambridge, MA, 1931–1935, 1958. (= CP)

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. (= W 2)

Poizat, B., A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Moses Klein (trans.), Springer-Verlag, New York, NY, 2000.

Quine, W.V., Mathematical Logic, 1940. Revised edition, Harvard University Press, Cambridge, MA, 1951. New preface, 1981.

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.

Shoenfield, J.R., Mathematical Logic, Addison-Wesley, Reading, MA, 1967.

Styazhkin, N.I., History of Mathematical Logic from Leibniz to Peano, MIT Press, Cambridge, MA, 1969.

Suppes, Patrick, Introduction to Logic, 1st published 1957. Reprinted, Dover Publications, New York, NY, 1999.

Suppes, Patrick, Axiomatic Set Theory, 1st published 1960. Reprinted, Dover Publications, New York, NY, 1972.

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.

Ullman, J.D., Principles of Database Systems, Computer Science Press, Rockville, MD, 1980.

Venetus, P., Logica Parva, Translation of the 1472 Edition with Introduction and Notes, Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany, 1984.