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}
a) Given,
Since a string cannot have common letters with itself, is not reflexive,
A string always has letters in common with itself, hence is irreflexive,
If string and have no letters in common, then strings and have no letters in common either. Therefore, is symmetric.
If string and have no letters in common and if string and also have letters in common, then strings and are not necessarily the same string.
For example, and have no letters in common while they are not the same string.
Hence is not antisymmetric.
If string and have no letters in common and if string and also have no letters in common, then strings and can contain common letters. For example, if we see that string and have no letters in common and string and also have no letters in common, but strings and contains a common letter . Thus, is not transitive.
b. Given,
As a string always has the same length as itself, is not reflexive,
is irreflexive because a string always has the same length as itself.
is symmetric because if string and do not have the same length, then strings and do not have the same length.
is not antisymmetric because if string and do not have the same length and if string and also do not have the same length, then strings and are not necessarily the same string.
If string and do not have the same length and if string and do not have the same length, then strings and can have the same length. Hence is not transitive.
c. Given,
Since a string is never longer than itself, is not reflexive.
is irreflexive because a string is never longer than itself.
is not symmetric because if string is longer than , then cannot be longer than .
is antisymmetric because " is longer than and cannot be longer than " cannot be true except when .
is transitive because if string is longer than and if string is longer than , then string has to be longer than .
Comments