Prove partial order of all Strings of digits {0,1...9}, by u ⪯ v if and only if u is a prefix of v

248 Views Asked by At

how would I approach solving this problem?

Question: Consider the set T= {0,1,...,9}* of all string of digits. Define the binary relation ⪯ on T by: u⪯v if and only if u is a prefix of v

for example 0061424 ⪯ 0061424535535
Just to be clear, we also include any string as a prefix of itself
Prove that (T, ⪯) is a partial order

1

There are 1 best solutions below

0
On

You need to verify three things. Let $u,v,w$ be any strings in your set.

  1. Reflexive. By definition, you wanna show $u \preceq u$. That is, you wanna show that $u$ is a prefix of $u$.

  2. Antisymmetric. By definition, you wanna show $u \preceq v$ and $v \preceq u$ implies that $u = v$. That is, if $u$ is a prefix of $v$ and $v$ is a prefix of $u$, then $u$ and $v$ are the same string.

  3. Transitive. By definition, you wanna show $u \preceq v$ and $v \preceq w$ implies that $u \preceq w$. That is, if $u$ is a prefix of $v$, and $v$ is a prefix of $w$, then $u$ is a prefix of $w$.

I hope thats enough to get you started!