Strings in a dictionary. A partial order, strict order, and total order?

874 Views Asked by At

Question: The domain is the set of all words in the English language (as defined by, say, Webster's dictionary). Word $x$ is related to word $y$ if $x$ appears as a substring of y. For example, "ion" is related to the word "companions" because the letters i-o-n appear in order in the word "companions". Is it a partial order, strict order, and is it a total order?

My thoughts: It is reflexive because a $x$ being a substring of $y$ makes it a substring of itself. It is transitive because if it is a substring of $y$ and $y$ is a substring of $z$ then it is a substring of $z$. It is antisymmetric because if $x$ is a substring of $y$ and $y$ is a substring of $x$ then they are the same.

Am I doing this right?

1

There are 1 best solutions below

3
On

Yes, you're doing it right, however you have to use the fact that words are finite in order to prove that this is antisymmetric. Consider the infinite case, the word $abababab\ldots$ then it is a substring of the word $babababa\ldots$ and vice versa, but they are not equal.

So it is a partial order. The other two do not hold, but I'll leave it to you to figure out why.