Inversion set determine an element in a symmetric group. Let $S_n$ be the symmetric group over $\{1,2,\ldots,n\}$. The inversion set of a element $w$ in $S_n$ is defined by $Inv(w)=\{(i,j): i<j, w^{-1}(i)>w^{-1}(j)\}$. I think that if $w, w' \in S_n$ and $Inv(w)=Inv(w')$, then $w = w'$. Is this true? Thank you very much.
 A: I use the definition $Inv(w) = \{ (i,j) \mid i < j \text{ and } w(i) > w(j) \}$, see Derek Holt's comment.
Giving a permutation $w$ is the same as giving a total order $<_w$, i.e. $w(1) <_w w(2) <_w ... <_w w(n)$, on the set $\{1,...,n\}$.
On the other hand the relation $<_w$ is completely determined by the set $Inv(w)$: For $i \neq j$ we have
\begin{align}
i <_w j
\iff& \left( i > j \text{ and } w(i) < w(j) \right) \text{ or } \\
    & \left( i < j \text{ and } w(i) < w(j) \right) \\
\iff& (j,i) \in Inv(w) \text{ or } \\
    & \left( i < j \text{ and } (i,j) \notin Inv(w) \right)
\end{align}
In summary we have bijections between:
$$ S_n \overset{1:1}\leftrightarrow \text{total orders on [n]} \overset{1:1}\leftrightarrow \text{inversion sets}$$
A: For each $n>0$, let $A_n=\{1,...,n\}$. Let us use the definition
$$\text{Inv}(w):=\{(i,j):i<j,w(i)>w(j)\}.$$
Suppose $w,w'\in S_n$ and $w\neq w'$. We want to show that $\text{Inv}(w)\neq\text{Inv}(w')$. 
Let $T$ be the set on which $w$ and $w'$ differ: $$T=\{x\in A_n:wx\neq w'x\}.$$ Then the images $w(T)$ and $w'(T)$ are equal; let us denote this set by $S$. Note that $w'w^{-1}$ can be considered as a bijection $S\rightarrow S$ that is not the identity (otherwise $w$ and $w'$ would be equal in $S_n$).  For convenience, write $m:=|S|$. By identifying $S$ and $A_m$, we can view $w'w^{-1}$ as an element of $S_m.$ Let the image of $i$ under $w'w^{-1}$ be denoted $x_i$.
Now we claim that any non-identity element of $S_m$ changes the ordering on at least one pair of elements in $A_m$. Assuming this has been proven, and viewing $w'w^{-1}\in S_m$, we can find $i,j\in A_{m}, i< j$, such that $x_i>x_j$. Without loss of generality, suppose that $$w^{-1}(i) = w'^{-1}(x_i) > w'^{-1}(x_j) = w^{-1}(j)$$ in $T$. Then the pair $(w^{-1}(i),w^{-1}(j))\in\text{Inv}(w)$ but is not in $\text{Inv}(w')$. Hence $\text{Inv}(w)\neq\text{Inv}(w')$, which completes the proof.
To show the claim, we use induction. Clearly it is true for $m=2$. Now suppose that it is true for $m=k$. If we have a non-identity element $c$ in $S_{k+1}$, it either has no fixed elements in $S_{k+1}$ or at least one fixed element. In the case that it has at least one fixed element, this reduces to the case for $m=k$, where we already have the conclusion by the inductive hypothesis. If it does not have any fixed elements, then it cannot be order-preserving on $S_{k+1}$. For suppose it were order-preserving. Then in particular we would have that $$c(1) < c(2) < ... < c(k+1).$$ But since $c(1) \neq 1$, this means $x_k > n$, a contradiction, proving the claim.
