I am having trouble with partial order and equivalence relations. I was wondering if someone can guide me through this problem.
Let $Σ$ be the set of letters {$a, b, . . . z$}.
Let $Σ^∗$ be the set of all finite string made of the letters $Σ$, for example “cat” $∈$ $Σ^∗$, “dog” $∈ Σ^∗$, “mathematics” $∈ Σ^∗$, “” $∈ Σ^∗$ (the empty string). We define a permutation relation $P$:
$P =$ {$(x, y)$ $∈ Σ^∗ × Σ^∗$| $x$ is a permutation of $y$}. It contains all the pairs of strings that are permutations of each other, for example
(“flow”, “wolf”) $∈ P$, (“teenager”, “generate”) $∈ P$, (“player”, “replay”) $∈ P$.
Is this relation P an equivalence relation or a partial order relation? Explain.
Reflectivity: Every word is a permutation of itself, so $P$ is reflective.
Symmetric: If $x$ is a permutation of $y$, then clearly $y$ is a permutation of $x$, so $P$ is symmetric.
Transitivity: If $y$ is a permutation of $x$ and $z$ a permutation of $y$ then $z$ is a permutation of $x$ (because all three have the same letters), hence $P$ is transitive.
Therefore $P$ is an equivalence relation.
To see whether it is a partial order we must check if $P$ is antisymmetric. Take $x\neq y$ such that $x$ is a permutation of $y$. By symmetry, $y$ is a permutation of $x$ but $x\neq y$. $P$ is therefore not antisymmetric and therefore not a partial order.