Proving string relation is a partial order ?

[tangibleLime]

Homework Statement

A string u is defined to be a substring of v if v=xuy for some strings x and y. Prove that the substring relation on any set of strings is a partial order.

Homework Equations

Relation R is reflexive if it always holds for an element and itself.
Relation R is antisymmetric if you can switch the variables in a true instance (and the variables aren't equal) you get a false instance.
Relation R is transitive if you can chain two true instances involving the same variable y to get a true instance. e.g. (x,y)^(y,z) -> (x,z)
And a partial order is when it has all three of these properties.

The Attempt at a Solution

Okay... so I know that to be a partial order the relation needs to be reflexive, antisymmetric and transitive.

Reflexive:
I can't figure out how to prove it's reflexive... because doesn't that mean it would be v=xuy <--> v=xux? But what if x and y are different strings?

Anti-symmetric:
I can prove this (but maybe my proof is wrong) by saying that I can switch x and y which will change the string if they are different. If x="hello", u="there", y="world", v=xuy=hellothereworld, but v=yux=worldtherehello, which are not equal and therefore false.

Transitive:
I'm really just at a loss as to how to prove this... I don't even know where to start.

Any help would be extremely appreciated, but I don't want the answers. Just a push in the right direction.

 

[Mark44]

Homework Statement

A string u is defined to be a substring of v if v=xuy for some strings x and y. Prove that the substring relation on any set of strings is a partial order.

Homework Equations

Relation R is reflexive if it always holds for an element and itself.
Relation R is antisymmetric if you can switch the variables in a true instance (and the variables aren't equal) you get a false instance.
Relation R is transitive if you can chain two true instances involving the same variable y to get a true instance. e.g. (x,y)^(y,z) -> (x,z)
And a partial order is when it has all three of these properties.

The Attempt at a Solution

Okay... so I know that to be a partial order the relation needs to be reflexive, antisymmetric and transitive.

Reflexive:
I can't figure out how to prove it's reflexive... because doesn't that mean it would be v=xuy <--> v=xux? But what if x and y are different strings?

No, if u is a substring of u, then u = xuy for some strings x and y. I'm assuming that "some string" includes the possibility of an empty string, a string with no characters in it.

Anti-symmetric:
I can prove this (but maybe my proof is wrong) by saying that I can switch x and y which will change the string if they are different. If x="hello", u="there", y="world", v=xuy=hellothereworld, but v=yux=worldtherehello, which are not equal and therefore false.

That's not right. It's not that you can switch x and y, but that you can switch u and v. You have u as a substring of v, which is "hellothereworld". Is v also a substring of u ("there")? If so, it would have to be the case that u = xvy. Is "there" the same string as "hellohellothereworldworld"?

Transitive:
I'm really just at a loss as to how to prove this... I don't even know where to start.

If u is a substring of v, and v is a substring of w, will it also be true that u is a substring of w?

Think about it in terms of examples, like you were doing before.

Any help would be extremely appreciated, but I don't want the answers. Just a push in the right direction.