Question #303148

1. Let S be the set of all strings of English letters. Determine whether these relations are reflexive, irreflexive, symmetric, antisymmetric, and/or transitive.



a) R1 = {(a, b) | a and b have no letters in common}



b) R2 = {(a, b) | a and b are not the same length}



c) R3 = {(a, b) | a is longer than b}




1
Expert's answer
2022-03-01T13:05:57-0500

a) Given, R1={(a,b)a and b have no letters in common}R_{1}=\{(a, b) \mid a \text{~and~} b \text{~have no letters in common}\}


Since a string cannot have common letters with itself, R1R_{1} is not reflexive,


A string always has letters in common with itself, hence R1R_{1} is irreflexive,


If string aa and bb have no letters in common, then strings bb and aa have no letters in common either. Therefore, R1R_{1} is symmetric.


If string aa and bb have no letters in common and if string bb and aa also have letters in common, then strings aa and bb are not necessarily the same string.

For example, uvwuvw and xyzxyz have no letters in common while they are not the same string.

Hence R1R_{1} is not antisymmetric.


If string aa and bb have no letters in common and if string bb and cc also have no letters in common, then strings aa and cc can contain common letters. For example, if a=xyz,b=pqr and c=evxa = xyz, b = pqr \text{~and~} c = evx we see that string aa and bb have no letters in common and string bb and cc also have no letters in common, but strings aa and cc contains a common letter xx. Thus, R1R_{1} is not transitive.


b. Given, R2={(a,b)a and b are not the same length}R_{2}=\{(a, b) \mid a \text{~and~} b \text{~are not the same length} \}

As a string always has the same length as itself, R2R_{2} is not reflexive,


R2R_{2} is irreflexive because a string always has the same length as itself.


R2R_{2} is symmetric because if string aa and bb do not have the same length, then strings bb and aa do not have the same length.


R2R_{2} is not antisymmetric because if string aa and bb do not have the same length and if string bb and aa also do not have the same length, then strings aa and bb are not necessarily the same string.


If string aa and bb do not have the same length and if string bb and cc do not have the same length, then strings aa and cc can have the same length. Hence R2R_{2} is not transitive.


c. Given,


Since a string is never longer than itself, R3R_{3} is not reflexive.


R3R_{3} is irreflexive because a string is never longer than itself.


R3R_{3} is not symmetric because if string aa is longer than bb, then bb cannot be longer than aa.


R3R_{3} is antisymmetric because "aa is longer than bb and bb cannot be longer than aa" cannot be true except when b=ab= a.


R3R_{3} is transitive because if string aa is longer than bb and if string bb is longer than cc, then string aa has to be longer than cc.


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS