Define a relation for "is contained in"

Question

Here is my question (should help with my understanding of this new topic):

Consider two words $x, y $ and say that the word $x$ is contained in the word $y$ if it only uses characters from $y$. Only the characters used in the word are relevant, not their order or frequency.

a) I need to define a relation for "is contained in"

This is what I have attempted (note: I don't claim this is at all accurate - just to show that I have actually tried the question before asking)

• Question is saying $x$ is a subset of $y$, therefore $ x \subseteq y$.
• With this I have: $x \subseteq y \iff \forall_{a,b} : (a,b \in x \Rightarrow a,b \in y)$
• $_ax_b \Rightarrow$ $_a y _b$

b) Explain how/what property of a relation is satisfied (is it reflexive, symmetric, transitive or functional)

• I was under the impression 'implies' $\Rightarrow$ is transitive. But I'm not sure.

I hope I can pass on the favor and contribute to someone's question soon.

Thanks!

Answer 1

Note, $x$ and $y$ being words (or strings of characters) do not quite work the same way as sets.

We have the word "apple" and the word "pale" have the same letters appearing but are technically unequal as words.

One could however reword the relation in terms of sets.

For a word $x$, let the set $X$ be the set $X=\{\text{letters appearing in the word}~x\}$

Similarly for the word $y$ and related set $Y$, as well as the word $z$ and related set $Z$.

We have then the nice intuitive rewording as $x\mathcal{R} y \Leftrightarrow X\subseteq Y$.

We ask which of the special properties of relations are satisfied.

• Reflexive: Is it true that for every word $x$, that $x\mathcal{R} x$?

  • Yes since $X\subseteq X$ is true for every set $X$, in particular when $X$ is the set of letters for a word $x$. Since $X\subseteq X$ this implies $x\mathcal{R} x$.

• Symmetric: Is it true that for every word $x$ and word $y$ such that $x\mathcal{R} y$ that you must necessarily also have $y\mathcal{R} x$?

  • No since it is possible that $X\subsetneq Y$ at which point $Y\not\subseteq X$. For example, $x$ being the word "top" and $y$ being the word "option". $y$ has letters appearing in the word which are not letters of $x$, in particular the letters i and n.

• Transitive: Is it true that for every words $x,y,z$ such that $x\mathcal{R} y$ and $y\mathcal{R} z$ that it must follow that $x\mathcal{R} z$?

  • Yes since $x\mathcal{R} y$ and $y\mathcal{R}z$ implies that $X\subseteq Y$ and $Y\subseteq Z$. It is known or easily shown that this implies that $X\subseteq Z$ thus implying that $x\mathcal{R} z$.

• Functional: (I rarely see it referred to as such, so this might be the incorrect property. Let me know if intended something else) Is it true that for every words $x,y,z$ such that $x\mathcal{R} y$ and $x\mathcal{R}z$ that $y=z$?

  • No since even with examples with equal related sets, the words themselves could be different. For example $x=$"top", $y=$"opt, and $z=$"pot". We have that all three of these are related, but none of them are equal.