Wikiversity

Relation theory

☞ This page belongs to resource collections on Logic and Inquiry.

This article treats relations from the perspective of combinatorics, in other words, as a subject matter in discrete mathematics, with special attention to finite structures and concrete set-theoretic constructions, many of which arise quite naturally in applications. This approach to relation theory, or the theory of relations, is distinguished from, though closely related to, its study from the perspectives of abstract algebra on the one hand and formal logic on the other.

Preliminaries

edit

Two definitions of the relation concept are common in the literature. Although it is usually clear in context which definition is being used at a given time, it tends to become less clear as contexts collide, or as discussion moves from one context to another.

The same sort of ambiguity arose in the development of the function concept and it may save some effort to follow the pattern of resolution that worked itself out there.

When we speak of a function   we are thinking of a mathematical object whose articulation requires three pieces of data, specifying the set   the set   and a particular subset of their cartesian product   So far so good.

Let us write   to express what has been said so far.

When it comes to parsing the notation   everyone takes the part   to specify the type of the function, that is, the pair   but   is used equivocally to denote both the triple and the subset   that forms one part of it. One way to resolve the ambiguity is to formalize a distinction between a function and its graph, letting  

Another tactic treats the whole notation   as sufficient denotation for the triple, letting   denote  

In categorical and computational contexts, at least initially, the type is regarded as an essential attribute or an integral part of the function itself. In other contexts it may be desirable to use a more abstract concept of function, treating a function as a mathematical object that appears in connection with many different types.

Following the pattern of the functional case, let the notation   bring to mind a mathematical object that is specified by three pieces of data, the set   the set   and a particular subset of their cartesian product   As before we have two choices, either let   or let   denote   and choose another name for the triple.

Definition

edit

It is convenient to begin with the definition of a  -place relation, where   is a positive integer.

Definition. A  -place relation   over the nonempty sets   is a  -tuple   where   is a subset of the cartesian product  

Remarks

edit

Though usage varies as usage will, there are several bits of optional language that are frequently useful in discussing relations. The sets   are called the domains of the relation   with   being the   domain. If all of the   are the same set   then   is more simply described as a  -place relation over   The set   is called the graph of the relation   on analogy with the graph of a function. If the sequence of sets   is constant throughout a given discussion or is otherwise determinate in context, then the relation   is determined by its graph   making it acceptable to denote the relation by referring to its graph. Other synonyms for the adjective  -place are  -adic and  -ary, all of which leads to the integer   being called the dimension, adicity, or arity of the relation  

Local incidence properties

edit

A local incidence property (LIP) of a relation   is a property that depends in turn on the properties of special subsets of   that are known as its local flags. The local flags of a relation are defined in the following way:

Let   be a  -place relation  

Select a relational domain   and one of its elements   Then   is a subset of   that is referred to as the flag of   with   at   or the  -flag of   an object that has the following definition:

 

Any property   of the local flag   is said to be a local incidence property of   with respect to the locus  

A  -adic relation   is said to be  -regular at   if and only if every flag of   with   at   has the property   where   is taken to vary over the theme of the fixed domain  

Expressed in symbols,   is  -regular at   if and only if   is true for all   in  

Regional incidence properties

edit

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

Suppose that   and choose a subset   Then   is a subset of   that is said to be the flag of   with   at   or the  -flag of   an object which has the following definition:

 

Numerical incidence properties

edit

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

For example,   is said to be  -regular at   if and only if the cardinality of the local flag   is   for all   in   or, to write it in symbols, if and only if   for all  

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

 

Species of 2-adic relations

edit

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

 

If   is tubular at   then   is called a partial function or a prefunction from   to   This is sometimes indicated by giving   an alternate name, say,   and writing  

Just by way of formalizing the definition:

 

If   is a prefunction   that happens to be total at   then   is called a function from   to   indicated by writing   To say that a relation   is totally tubular at   is to say that it is  -regular at   Thus, we may formalize the following definition:

 

In the case of a function   one has the following additional definitions:

 

Variations

edit

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 climes, 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  -place relations, for   with some writers using the Greek forms, medadic, monadic, dyadic, triadic,  -adic, and other writers using the Latin forms, nullary, unary, binary, ternary,  -ary.

The number of relational domains may be referred to as the adicity, arity, or dimension of the relation. Accordingly, one finds a relation on a finite number of domains described as a polyadic relation or a finitary relation, but others count infinitary relations among the polyadic. If the number of domains is finite, say equal to   then the relation may be described as a  -adic relation, a  -ary relation, or a  -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 is derivative in relationship to 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

edit
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

edit
  • 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.

Bibliography

edit
  • Barr, Michael, and Wells, Charles (1990), Category Theory for Computing Science, Prentice Hall, Hemel Hempstead, UK.
  • Bourbaki, Nicolas (1994), Elements of the History of Mathematics, John Meldrum (trans.), Springer-Verlag, Berlin, Germany.
  • Carnap, Rudolf (1958), Introduction to Symbolic Logic with Applications, Dover Publications, New York, NY.
  • Chang, C.C., and Keisler, H.J. (1973), Model Theory, North-Holland, Amsterdam, Netherlands.
  • van Dalen, Dirk (1980), Logic and Structure, 2nd edition, Springer-Verlag, Berlin, Germany.
  • Devlin, Keith J. (1993), The Joy of Sets : Fundamentals of Contemporary Set Theory, 2nd edition, Springer-Verlag, New York, NY.
  • Halmos, Paul Richard (1960), Naive Set Theory, D. Van Nostrand Company, Princeton, NJ.
  • van Heijenoort, Jean (1967/1977), From Frege to Gödel : A Source Book in Mathematical Logic, 1879–1931, Harvard University Press, Cambridge, MA, 1967. Reprinted with corrections, 1977.
  • Kelley, John L. (1955), General Topology, Van Nostrand Reinhold, New York, NY.
  • Kneale, William; and Kneale, Martha (1962/1975), The Development of Logic, Oxford University Press, Oxford, UK, 1962. Reprinted with corrections, 1975.
  • Lawvere, Francis William; and Rosebrugh, Robert (2003), Sets for Mathematics, Cambridge University Press, Cambridge, UK.
  • Lawvere, Francis William; and Schanuel, Stephen H. (1997/2000), Conceptual Mathematics : A First Introduction to Categories, Cambridge University Press, Cambridge, UK, 1997. Reprinted with corrections, 2000.
  • Manin, Yu. I. (1977), A Course in Mathematical Logic, Neal Koblitz (trans.), Springer-Verlag, New York, NY.
  • Mathematical Society of Japan (1993), Encyclopedic Dictionary of Mathematics, 2nd edition, 2 vols., Kiyosi Itô (ed.), MIT Press, Cambridge, MA.
  • Mili, A., Desharnais, J., Mili, F., with Frappier, M. (1994), Computer Program Construction, Oxford University Press, New York, NY. (Introduction to Tarskian relation theory and relational programming.)
  • Mitchell, John C. (1996), Foundations for Programming Languages, MIT Press, Cambridge, MA.
  • Peirce, Charles Sanders (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 (1870), 317–378. Reprinted (CP 3.45–149), (CE 2, 359–429).
  • Peirce, Charles Sanders (1931–1935, 1958), 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. Cited as (CP volume.paragraph).
  • Peirce, Charles Sanders (1981–), Writings of Charles S. Peirce : A Chronological Edition, Peirce Edition Project (eds.), Indiana University Press, Bloomington and Indianapolis, IN. Cited as (CE volume, page).
  • Poizat, Bruno (2000), A Course in Model Theory : An Introduction to Contemporary Mathematical Logic, Moses Klein (trans.), Springer-Verlag, New York, NY.
  • Quine, Willard Van Orman (1940/1981), Mathematical Logic, 1940. Revised edition, Harvard University Press, Cambridge, MA, 1951. New preface, 1981.
  • Royce, Josiah (1961), The Principles of Logic, Philosophical Library, New York, NY.
  • Runes, Dagobert D. (ed., 1962), Dictionary of Philosophy, Littlefield, Adams, and Company, Totowa, NJ.
  • Shoenfield, Joseph R. (1967), Mathematical Logic, Addison-Wesley, Reading, MA.
  • Styazhkin, N.I. (1969), History of Mathematical Logic from Leibniz to Peano, MIT Press, Cambridge, MA.
  • Suppes, Patrick (1957/1999), Introduction to Logic, 1st published 1957. Reprinted, Dover Publications, New York, NY, 1999.
  • Suppes, Patrick (1960/1972), Axiomatic Set Theory, 1st published 1960. Reprinted, Dover Publications, New York, NY, 1972.
  • Tarski, Alfred (1956/1983), Logic, Semantics, Metamathematics : Papers from 1923 to 1938, J.H. Woodger (trans.), Oxford University Press, 1956. 2nd edition, J. Corcoran (ed.), Hackett Publishing, Indianapolis, IN, 1983.
  • Ulam, Stanislaw Marcin; and Bednarek, A.R. (1977), “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.
  • Ulam, Stanislaw Marcin (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.
  • Ullman, Jeffrey D. (1980), Principles of Database Systems, Computer Science Press, Rockville, MD.
  • Venetus, Paulus (1472/1984), Logica Parva : Translation of the 1472 Edition with Introduction and Notes, Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany.

Syllabus

edit

Focal nodes

edit

Peer nodes

edit

Logical operators

edit

edit

Relational concepts

edit

Information, Inquiry

edit

edit

Document history

edit

Portions of the above article were adapted from the following sources under the GNU Free Documentation License, under other applicable licenses, or by permission of the copyright holders.

Retrieved from "https://en.wikiversity.org/w/index.php?title=Relation_theory&oldid=2480531"