Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Binary relation
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Definition == Given sets <math>X</math> and <math>Y</math>, the Cartesian product <math>X \times Y</math> is defined as <math>\{ (x, y) \mid x \in X \text{ and } y \in Y \},</math> and its elements are called ''ordered pairs''. A {{em|binary relation}} <math>R</math> over sets <math>X</math> and <math>Y</math> is a subset of <math>X \times Y.</math><ref name="Codd1970" /><ref>{{harvnb|Enderton|1977|loc=Ch 3. pg. 40}}</ref> The set <math>X</math> is called the {{em|domain}}<ref name="Codd1970" /> or {{em|set of departure}} of <math>R</math>, and the set <math>Y</math> the {{em|codomain}} or {{em|set of destination}} of <math>R</math>. In order to specify the choices of the sets <math>X</math> and <math>Y</math>, some authors define a {{em|binary relation}} or {{em|correspondence}} as an ordered triple <math>(X, Y, G)</math>, where <math>G</math> is a subset of <math>X \times Y</math> called the {{em|graph}} of the binary relation. The statement <math>(x, y) \in R</math> reads "<math>x</math> is <math>R</math>-related to <math>y</math>" and is denoted by <math>xRy</math>.<ref name="Schroder.1895"/><ref name="Lewis.1918"/><ref name=gs/>{{#tag:ref|Authors who deal with binary relations only as a special case of <math>n</math>-ary relations for arbitrary <math>n</math> usually write <math>Rxy</math> as a special case of <math>Rx_1\dots x_n</math> ([[Polish notation|prefix notation]]).<ref>{{cite book | issn=1431-4657 | isbn=3540058192 | author=Hans Hermes | title=Introduction to Mathematical Logic | location=London | publisher=Springer | series=Hochschultext (Springer-Verlag) | year=1973 }} Sect.II.§1.1.4</ref>|group=note}} The {{em|domain of definition}} or {{em|active domain}}<ref name="Codd1970" /> of <math>R</math> is the set of all <math>x</math> such that <math>xRy</math> for at least one <math>y</math>. The ''codomain of definition'', {{em|active codomain}},<ref name="Codd1970" /> {{em|image}} or {{em|range}} of <math>R</math> is the set of all <math>y</math> such that <math>xRy</math> for at least one <math>x</math>. The {{em|field}} of <math>R</math> is the union of its domain of definition and its codomain of definition.<ref name="suppes"> {{cite book |last=Suppes |first=Patrick |author-link=Patrick Suppes |year=1972 |title=Axiomatic Set Theory |publisher=Dover |orig-year=originally published by D. van Nostrand Company in 1960 |isbn=0-486-61630-4 |url-access=registration |url=https://archive.org/details/axiomaticsettheo00supp_0 }} </ref><ref name="smullyan"> {{cite book |last1=Smullyan |first1=Raymond M. |author-link=Raymond Smullyan |last2=Fitting |first2=Melvin |year=2010 |title=Set Theory and the Continuum Problem |publisher=Dover |orig-year=revised and corrected republication of the work originally published in 1996 by Oxford University Press, New York |isbn=978-0-486-47484-7 }} </ref><ref name="levy"> {{cite book |last=Levy |first=Azriel |author-link=Azriel Levy |year=2002 |title=Basic Set Theory |publisher=Dover |orig-year=republication of the work published by Springer-Verlag, Berlin, Heidelberg and New York in 1979 |isbn=0-486-42079-5 }} </ref> When <math>X = Y,</math> a binary relation is called a {{em|[[homogeneous relation]]}} (or {{em|endorelation}}). To emphasize the fact that <math>X</math> and <math>Y</math> are allowed to be different, a binary relation is also called a '''heterogeneous relation'''.<ref name="Schmidt">{{cite book|last1=Schmidt|first1=Gunther|last2=Ströhlein|first2=Thomas|title=Relations and Graphs: Discrete Mathematics for Computer Scientists|url={{google books |plainurl=y |id=ZgarCAAAQBAJ|paged=277}}|date=2012|publisher=Springer Science & Business Media|isbn=978-3-642-77968-8|author-link1=Gunther Schmidt |at=Definition 4.1.1.}}</ref><ref name="FloudasPardalos2008">{{cite book|author1=Christodoulos A. Floudas|author-link1=Christodoulos Floudas|author2=Panos M. Pardalos|title=Encyclopedia of Optimization|year=2008|publisher=Springer Science & Business Media|isbn=978-0-387-74758-3|pages=299–300|edition=2nd|url=https://books.google.com/books?id=1a6lSRbQ4YsC&q=relation}}</ref><ref name="Winter2007">{{cite book|author=Michael Winter|title=Goguen Categories: A Categorical Approach to L-fuzzy Relations|year=2007|publisher=Springer|isbn=978-1-4020-6164-6|pages=x-xi}}</ref> The prefix ''hetero'' is from the Greek ἕτερος (''heteros'', "other, another, different"). A heterogeneous relation has been called a '''rectangular relation''',<ref name="Winter2007"/> suggesting that it does not have the square-like symmetry of a [[#Homogeneous relation|homogeneous relation on a set]] where <math>A = B.</math> Commenting on the development of binary relations beyond homogeneous relations, researchers wrote, "... a variant of the theory has evolved that treats relations from the very beginning as {{em|heterogeneous}} or {{em|rectangular}}, i.e. as relations where the normal case is that they are relations between different sets."<ref>G. Schmidt, Claudia Haltensperger, and Michael Winter (1997) "Heterogeneous relation algebra", chapter 3 (pages 37 to 53) in ''Relational Methods in Computer Science'', Advances in Computer Science, [[Springer books]] {{ISBN|3-211-82971-7}}</ref> The terms ''correspondence'',<ref>Jacobson, Nathan (2009), [https://books.google.com/books?id=hn75exNZZ-EC&q=correspondence Basic Algebra II (2nd ed.)] § 2.1.</ref> '''dyadic relation'''<!---[[Dyadic relation]]---> and '''two-place relation'''<!---[[Two-place relation]]---> are synonyms for binary relation, though some authors use the term "binary relation" for any subset of a Cartesian product <math>X \times Y</math> without reference to <math>X</math> and <math>Y</math>, and reserve the term "correspondence" for a binary relation with reference to <math>X</math> and <math>Y</math>.{{citation needed|reason=Who?|date=June 2021}} In a binary relation, the order of the elements is important; if <math>x \neq y</math> then <math>yRx</math> can be true or false independently of <math>xRy</math>. For example, <math>3</math> divides <math>9</math>, but <math>9</math> does not divide <math>3</math>.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)