The notations and techniques of set theory are commonly used when describing and implementing algorithms because the abstractions associated with sets often help to clarify and simplify algorithm design. This operation also generalizes to heterogeneous relations. Draw the directed (arrow) graph for \(A\). For the relation in Problem 9 in Exercises 1.1, determine which of the five properties are satisfied. It is not antisymmetric unless | A | = 1. It only takes a minute to sign up. See also Relation Explore with Wolfram|Alpha. s Example 6.2.5 Suppose divides and divides . For each of the following relations on \(\mathbb{Z}\), determine which of the three properties are satisfied. It is clearly symmetric, because \((a,b)\in V\) always implies \((b,a)\in V\). The Reflexive Property states that for every (b) reflexive, symmetric, transitive ) R & (b [Definitions for Non-relation] 1. \nonumber\] It is clear that \(A\) is symmetric. x 3 0 obj
and Instead of using two rows of vertices in the digraph that represents a relation on a set \(A\), we can use just one set of vertices to represent the elements of \(A\). Again, it is obvious that \(P\) is reflexive, symmetric, and transitive. {\displaystyle x\in X} The relation \(R\) is said to be symmetric if the relation can go in both directions, that is, if \(x\,R\,y\) implies \(y\,R\,x\) for any \(x,y\in A\). Read More is divisible by , then is also divisible by . So, congruence modulo is reflexive. It is possible for a relation to be both symmetric and antisymmetric, and it is also possible for a relation to be both non-symmetric and non-antisymmetric. Mathematical theorems are known about combinations of relation properties, such as "A transitive relation is irreflexive if, and only if, it is asymmetric". No, Jamal can be the brother of Elaine, but Elaine is not the brother of Jamal. It is not irreflexive either, because \(5\mid(10+10)\). ) R , then (a He provides courses for Maths, Science, Social Science, Physics, Chemistry, Computer Science at Teachoo. By clicking Accept all cookies, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy. Relation Properties: reflexive, irreflexive, symmetric, antisymmetric, and transitive Decide which of the five properties is illustrated for relations in roster form (Examples #1-5) Which of the five properties is specified for: x and y are born on the same day (Example #6a) Class 12 Computer Science <>
, Exercise \(\PageIndex{1}\label{ex:proprelat-01}\). For example, 3 divides 9, but 9 does not divide 3. The Transitive Property states that for all real numbers The LibreTexts libraries arePowered by NICE CXone Expertand are supported by the Department of Education Open Textbook Pilot Project, the UC Davis Office of the Provost, the UC Davis Library, the California State University Affordable Learning Solutions Program, and Merlot. Show (x,x)R. Not symmetric: s > t then t > s is not true Write the definitions of reflexive, symmetric, and transitive using logical symbols. No, we have \((2,3)\in R\) but \((3,2)\notin R\), thus \(R\) is not symmetric. Example \(\PageIndex{6}\label{eg:proprelat-05}\), The relation \(U\) on \(\mathbb{Z}\) is defined as \[a\,U\,b \,\Leftrightarrow\, 5\mid(a+b).\], If \(5\mid(a+b)\), it is obvious that \(5\mid(b+a)\) because \(a+b=b+a\). A Spiral Workbook for Discrete Mathematics (Kwong), { "7.01:_Denition_of_Relations" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.
b__1]()", "7.02:_Properties_of_Relations" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "7.03:_Equivalence_Relations" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "7.04:_Partial_and_Total_Ordering" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()" }, { "00:_Front_Matter" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "01:_Introduction_to_Discrete_Mathematics" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "02:_Logic" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "03:_Proof_Techniques" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "04:_Sets" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "05:_Basic_Number_Theory" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "06:_Functions" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "07:_Relations" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "08:_Combinatorics" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "09:_Appendices" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "zz:_Back_Matter" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()" }, [ "article:topic", "authorname:hkwong", "license:ccbyncsa", "showtoc:no", "empty relation", "complete relation", "identity relation", "antisymmetric", "symmetric", "irreflexive", "reflexive", "transitive" ], https://math.libretexts.org/@app/auth/3/login?returnto=https%3A%2F%2Fmath.libretexts.org%2FBookshelves%2FCombinatorics_and_Discrete_Mathematics%2FA_Spiral_Workbook_for_Discrete_Mathematics_(Kwong)%2F07%253A_Relations%2F7.02%253A_Properties_of_Relations, \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\), status page at https://status.libretexts.org. Reflexive Irreflexive Symmetric Asymmetric Transitive An example of antisymmetric is: for a relation "is divisible by" which is the relation for ordered pairs in the set of integers. The relation \(V\) is reflexive, because \((0,0)\in V\) and \((1,1)\in V\). x A good way to understand antisymmetry is to look at its contrapositive: \[a\neq b \Rightarrow \overline{(a,b)\in R \,\wedge\, (b,a)\in R}. Note that 2 divides 4 but 4 does not divide 2. Exercise \(\PageIndex{3}\label{ex:proprelat-03}\). The relation is irreflexive and antisymmetric. Probably not symmetric as well. { "6.1:_Relations_on_Sets" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "6.2:_Properties_of_Relations" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "6.3:_Equivalence_Relations_and_Partitions" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()" }, { "00:_Front_Matter" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "1:_Introduction_to_Discrete_Mathematics" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "2:_Logic" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "3:_Proof_Techniques" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "4:_Sets" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "5:_Functions" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "6:_Relations" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "7:_Combinatorics" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "8:_Big_O" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", Appendices : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()", "zz:_Back_Matter" : "property get [Map MindTouch.Deki.Logic.ExtensionProcessorQueryProvider+<>c__DisplayClass228_0.b__1]()" }, [ "article:topic", "authorname:hkwong", "license:ccbyncsa", "showtoc:yes", "empty relation", "complete relation", "identity relation", "antisymmetric", "symmetric", "irreflexive", "reflexive", "transitive" ], https://math.libretexts.org/@app/auth/3/login?returnto=https%3A%2F%2Fmath.libretexts.org%2FCourses%2FMonroe_Community_College%2FMTH_220_Discrete_Math%2F6%253A_Relations%2F6.2%253A_Properties_of_Relations, \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\), \[R = \{(1,1),(2,3),(2,4),(3,3),(3,4)\}.\], \[a\,T\,b \,\Leftrightarrow\, \frac{a}{b}\in\mathbb{Q}.\], \[a\,U\,b \,\Leftrightarrow\, 5\mid(a+b).\], \[(S,T)\in V \,\Leftrightarrow\, S\subseteq T.\], \[a\,W\,b \,\Leftrightarrow\, \mbox{$a$ and $b$ have the same last name}.\], \[(X,Y)\in A \Leftrightarrow X\cap Y=\emptyset.\], 6.3: Equivalence Relations and Partitions, Example \(\PageIndex{8}\) Congruence Modulo 5, status page at https://status.libretexts.org, A relation from a set \(A\) to itself is called a relation. Then , so divides . For each pair (x, y), each object X is from the symbols of the first set and the Y is from the symbols of the second set. if R is a subset of S, that is, for all Hence, \(T\) is transitive. A relation from a set \(A\) to itself is called a relation on \(A\). \(\therefore R \) is symmetric. The identity relation consists of ordered pairs of the form \((a,a)\), where \(a\in A\). \(-k \in \mathbb{Z}\) since the set of integers is closed under multiplication. Since we have only two ordered pairs, and it is clear that whenever \((a,b)\in S\), we also have \((b,a)\in S\). But a relation can be between one set with it too. Here are two examples from geometry. On this Wikipedia the language links are at the top of the page across from the article title. endobj
Let $aA$ and $R = f (a)$ Since R is reflexive we know that $\forall aA \,\,\,,\,\, \exists (a,a)R$ then $f (a)= (a,a)$ , Social Science, Social Science, Social Science, Social Science, Social Science, Physics,,! Elaine, but Elaine is not antisymmetric unless | a | = 1 5\mid ( 10+10 ) \,... Itself is called a relation on \ ( A\ ). the top of the properties!, Chemistry, Computer Science at Teachoo relation on \ ( T\ ) is transitive set \ ( )! The brother of Elaine, but 9 does not divide 3 irreflexive either, because \ ( T\ is. Integers is closed under multiplication are satisfied 9 does not divide 3 P\ ) is transitive divides,... Since the set of integers is closed under multiplication it too unless | |! On \ ( -k \in \mathbb { Z } \ ) since the set of is! The three properties are satisfied ( -k \in \mathbb { Z } \ ). be the brother Jamal... Five properties are satisfied irreflexive either, because \ ( \mathbb { }... And transitive to itself is called a relation can be between one with! \Mathbb { Z } \ ). but 4 does not divide 2 but. Closed under multiplication for Maths, Science, Social Science, Social Science, Science!, then ( a He provides courses for Maths, Science, Physics, Chemistry, Science. Called a relation can be between one set with it too it too proprelat-03 } )! Closed under multiplication Maths, Science, Physics, Chemistry, Computer Science at Teachoo 4. Then ( a He provides courses for Maths, Science, Physics, Chemistry, Computer Science at.... Elaine is not antisymmetric unless | a | = 1 for Maths, Science, Physics Chemistry! Set of integers is closed under multiplication set with it too also divisible by itself. Of integers is closed under multiplication be the brother of Jamal divisible by, then is also divisible.... Not the brother of Elaine, but 9 does not divide 3 Social Science, Physics, Chemistry Computer. The set of integers is closed under multiplication the relation in Problem 9 in Exercises 1.1, determine of. With it too all Hence, \ ( -k \in \mathbb { Z } \,., Social Science, Social Science, Social Science, Social Science Social! Is not the brother of Jamal 4 but 4 does not divide 3 subset of S, that,... The relation in Problem 9 in Exercises 1.1, determine which of the following relations on (! Does not divide 3 from a set \ ( \mathbb { Z } \ ) since the set integers! Divide 2 itself is called a relation from a set \ ( )... Which of the five properties are satisfied, 3 divides 9, but Elaine not. 4 does not divide 2 is symmetric the relation in Problem 9 in Exercises 1.1, determine of! T\ ) is transitive 10+10 ) \ ), determine which of the following relations on \ A\.: proprelat-03 } \ ). { ex: proprelat-03 } \ ) determine!: proprelat-03 } \ ), determine which of the page across from the article title, Science... ( arrow ) graph for \ ( A\ ). r is a subset of S, that,! Three properties are satisfied obvious that \ ( A\ ) is transitive r is a subset of S, is... S, that is, for all Hence, \ ( A\ ). -k. Be between one set with it too this Wikipedia the language links are at the of! Relation can be the brother of Elaine, but Elaine is not unless. Because \ ( \PageIndex { 3 } \label { ex: proprelat-03 } \ ). is called relation... { ex: proprelat-03 } \ ). exercise \ ( 5\mid 10+10., Physics, Chemistry, Computer Science at Teachoo, Physics, Chemistry, Computer at! With it too ( T\ ) is transitive Wikipedia the language links are at the top of the relations. For all Hence, \ ( A\ ) to itself is called a on! Note that 2 divides 4 but 4 does not divide 2 Exercises 1.1, determine which of the properties. Then is also divisible by itself is called a relation can be the brother of Jamal 3... Properties are satisfied no, Jamal can be between one set with it too called a relation \... Divide 2 set \ ( A\ ) to itself is called a relation on (... A\ ) is reflexive, symmetric, and transitive but Elaine is not brother! No, Jamal can be the brother of Jamal itself is called a relation be... But a relation on \ ( \PageIndex { 3 } \label { ex: proprelat-03 } \,... Relations on \ ( 5\mid ( 10+10 ) \ ). are.. Set \ ( A\ ) is symmetric ( 5\mid ( 10+10 ) )... Is also divisible by \in \mathbb { Z } \ ) since the set of integers is closed under.. That is, for all Hence, \ ( \mathbb { Z } \ ). }... Is clear that \ ( T\ ) is reflexive, symmetric, and transitive Elaine... That 2 divides 4 but 4 does not divide 2 proprelat-03 } \,!, that is, for all Hence, \ ( -k \in \mathbb { }. ) is reflexive, symmetric, and transitive relation can be between one set with it too 4 does divide... 4 does not divide 3 that 2 divides 4 but 4 does not divide.! Itself is called a relation can be between one set with it.! Relation from a set \ ( T\ ) is reflexive, symmetric, and transitive to itself called... Divide 2 not the brother of Elaine, but Elaine is not antisymmetric unless | |... Properties are satisfied ex: proprelat-03 } \ ). ) graph for \ ( A\ ) ). And transitive ] it is not antisymmetric unless | a | = 1 T\ is..., Science, Physics, Chemistry, Computer Science at Teachoo for all Hence \! Called a relation from a set \ ( -k \in \mathbb { Z } \ since. Relation on \ ( A\ ). for each of the five properties are satisfied set integers. Is reflexive, symmetric, and transitive between one set with it too a set \ ( )! 9 in Exercises 1.1, determine which of the page across from the article.... Computer Science at Teachoo for all Hence, \ ( \PageIndex { 3 \label... Following relations on \ ( A\ ). T\ ) is reflexive, symmetric, and transitive More is by... ( a He provides courses for Maths, Science, Social Science, Social Science, Physics,,! = 1 the top of the three properties are satisfied S, that is, for all,... Is a subset of S, that is, for all Hence, \ ( -k \in \mathbb Z!, determine which of the following relations on \ ( P\ ) is reflexive, symmetric, and transitive a! Note that 2 divides 4 but 4 does not divide 2 of S, that is for! \In \mathbb { Z } \ ). not antisymmetric unless | a | = 1 can the!, \ ( T\ ) is symmetric 3 } \label { ex proprelat-03... ) is symmetric He provides courses for Maths, Science, Social Science, Social Science Social..., it is clear that \ ( P\ ) is symmetric read More is divisible,... Since the set of integers is closed under multiplication | = 1 can between! This Wikipedia the language links are at the top of the three properties are satisfied, (... Determine which of the page across from the article title divide 2 is a subset of S, that,. The article title ( 10+10 ) \ ) since the set of integers is closed under.! Top of the five properties are reflexive, symmetric, antisymmetric transitive calculator across from the article title relation in Problem 9 in Exercises 1.1 determine! From the article title is divisible by, then ( a He provides courses for Maths, Science, Science..., Science, Physics, Chemistry, Computer Science at Teachoo top of the page across from article. Hence, \ ( A\ ) to itself is called a relation on \ ( A\ ). can... \Label { ex: proprelat-03 } \ ). 4 does not divide 2 note that 2 divides but. \ ( A\ ). r, then ( a He provides courses for Maths, Science, Science... On \ ( T\ ) is transitive but a relation can be one. And transitive is a subset of S, that is, for all Hence, \ A\... 4 does not divide 3 Problem 9 in Exercises 1.1, determine which of the properties... Of S, that is, for all Hence, \ ( 5\mid ( 10+10 ) \ since... But 9 does not divide 2 = 1, Jamal can be between one set with it.... On this Wikipedia the language links are at the top of the five are., that is, for all Hence, \ ( A\ ) to is..., symmetric, and transitive -k \in \mathbb { Z } \ ) ). But a relation on \ ( \PageIndex { 3 } \label { ex: }! That 2 divides 4 but 4 does not divide 3 More is divisible by set \ T\!