What inversion sets of permutations of $123\ldots n$ are possible? Given a sequence of integers $\sigma = a_1 a_2 a_3 \ldots a_n$, let's define an inversion of $\sigma$ to be a pair $(a_i,a_j)$ of entries of $\sigma$ such that $a_i < a_k$ and $i > k$. For example, in the sequence $21345$, the pair $(1,2)$ is an inversion, since $1<2$ but $2$ comes before $1$ in the sequence. The inversion set of $\sigma$ is just the set of all inversions of $\sigma$. (This may not be the usual definition of inversion, but I didn't know what else to call it.) Now my question is this:

What are the possible inversion sets of permutations of $123\ldots n$?

Clearly, not all subsets of $\{(a,b) \in \mathbb{Z}^2 \mid 1 \leq a < b \leq n  \}$ can occur as inversion sets; for example, if the inversions $(3,4)$ and $(1,3)$ occur, then so too must $(1,4)$. More generally, if $a < b < c$, any inversion set containing $(a,b)$ and $(b,c)$ must contain $(a,c)$. But I'm not sure if this fact alone is enough to characterize all inversion sets. How do I proceed?
 A: Here is one way to think about it relating to @darijgr's comment. Let's denote $[n]:= \{1,2,\dots,n\}$. We want to prove that a subset $I$ of $X=\{(i,j)\in [n]^2\mid i<j\}$, with the property that both $I$ and $X\setminus I$ are transitive, uniquely determines a permutation. If you are familiar with totally ordered sets, notice that total orderings on $[n]$ are in natural correspondence with permutations. For example, if $\prec$ denotes our total ordering on the set $[4]$ defined by $1\prec 4\prec 2\prec 3$, it corresponds to the permutation $1423$. 
Now given such a set $I$ as above, how do we define a total ordering? Given $i<j$, if $(i,j)\in I$ then define $j\prec i$ in our ordering. Otherwise $(i,j)\in X\setminus I$ and we define $i\prec j$ in our ordering. The property that both $I$ and $X\setminus I$ are transitive is exactly what we need for $\prec$ to satisfy the transitivity property (you need to consider a few cases to show this), and it is a total ordering because for every pair $(i,j)$ with $i<j$, either it is in $I$ or $X\setminus I$.
Thus there is a natural correspondence between subsets $I$ with the above properties and permutations on $n$. It is not hard to see that $I$ is the inversion set of the corresponding permutation, as you have defined it.
