Why is the right permutohedron order (aka weak order) on $S_n$ a lattice? This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the strong Bruhat order) on the symmetric group $S_n$ a lattice?
Details:
Let $n$ be a nonnegative integer. Consider the symmetric group $S_n$, with multiplication defined by $\left(\sigma\pi\right)\left(i\right)=\sigma\left(\pi\left(i\right)\right)$ for all $\sigma$ and $\pi$ in $S_n$ and all $i \in \left\lbrace 1,2,\cdots ,n \right\rbrace$. The right permutohedron order is a partial order on the set $S_n$ and can be defined in the following equivalent ways:


*

*Two permutations $u$ and $v$ in $S_n$ satisfy $u \leq v$ in the right permutohedron order if and only if the length of the permutation $v^{-1} u$ equals the length of $v$ minus the length of $u$. Here, the length (also known as "Coxeter length") of a permutation is its number of inversions.

*Two permutations $u$ and $v$ in $S_n$ satisfy $u \leq v$ in the right permutohedron order if and only if every pair $\left(i, j\right)$ of elements of $\{ 1, 2, \cdots, n \}$ such that $i < j$ and $u^{-1}\left(i\right) > u^{-1}\left(j\right)$ also satisfies $v^{-1}\left(i\right) > v^{-1}\left(j\right)$. (In more vivid terms, this condition states that whenever two integers $i$ and $j$ satisfy $i < j$ but $i$ stands to the right of $j$ in the one-line notation of the permutation $u$, the integer $i$ must also stand to the right of $j$ in the one-line notation of the permutation $v$.)

*A permutation $v \in S_n$ covers a permutation $u \in S_n$ in the right permutohedron order if and only if we have $v = u \cdot \left(i, i + 1\right)$ for some $i \in \{ 1, 2, \cdots, n - 1 \}$ satisfying $u\left(i\right) < u\left(i + 1\right)$. Here, $\left(i, i + 1\right)$ denotes the transposition switching $i$ with $i + 1$.
(I have mostly quoted these definitions from a part of Sage documentation I've written a while ago. A "left permutohedron order" also exists, but differs from the right one merely by swapping a permutation with its inverse.)
It is easy to prove the equivalence of the above three definitions using nothing but elementary reasoning about inversions and bubblesort. This made me believe that everything about the permutohedron order is simple.
Now I have read in some sources (which all give either no or badly accessible references) that the poset $S_n$ with the right permutohedron order is a lattice. This is related to the Tamari lattice. (Specifically, there is an injection from the Tamari lattice to the permutohedron-ordered $S_n$ sending each binary search tree to a certain 132-avoiding permutation obtained from a postfix reading of the tree, and there is a surjection in the other direction sending each permutation to its binary search tree. If I am not mistaken, these two maps form a Galois connection.) But I am not able to prove the lattice property! I see some obstructions to the existence of overly simple proofs:


*

*The strong Bruhat order is not a lattice.

*One might think that the meet of two permutations $u$ and $v$ will be a permutation $p$ whose coinversion set (= the set of all pairs $\left(i, j\right)$ of elements of $\{ 1, 2, \cdots, n \}$ such that $i < j$ and $p^{-1}\left(i\right) > p^{-1}\left(j\right)$) will be the intersection of the coinversion sets of $u$ and $v$. This is not the case. A permutation having such a coinversion set might not exist, and the meet has a smaller coinversion set. In particular, it is not always possible to obtain the meet of $u$ and $v$ by bubblesorting each of $u$ and $v$ without ever killing inversions which are common to $u$ and $v$.

*The permutohedron-order lattice is not distributive.
 A: This is a reply to the questions about the Tamari lattice, not to the question in the title. The Tamari lattice is both a sublattice and a quotient lattice of $S_n$, with the inclusion and quotient maps you have described.
Regarding the fact that the map $S_n \to \mathrm{Tamari}$ is a map of lattices, Nathan Reading writes 

The starting point of the present research is the observation that the
  Tamari lattice is a lattice-homomorphic image of the right weak order
  on the symmetric group. This fact has, to our knowledge, never
  appeared in the literature, although essentially all the ingredients
  of a proof were assembled by Björner and Wachs

So Nathan's paper may be the first reference for this fact in print. See Theorem 6.2 for the fact that the quotient map is a map of lattices and 6.5 for the fact that the inclusion is a map of lattices. Nathan writes that, for the Tamari lattice, the result about the inclusion is already in Björner and Wachs.
The goal of Nathan (and later my) work is to define a similar sub-and-quotient lattice story for any Coxeter group and any orientation of the Dynkin diagram; the Tamari lattice corresponds to $A_{n-1}$ with all arrows oriented in the same direction. If we stay in $S_n$ but look at other orientations of the Dynkin diagram, we get other posets whose Hasse diagrams are all various orientations of the $1$-skeleton of the associahedron. See sections 4-6 of Reading's linked paper for what this construction does in type A.

Nathan's paper linked above mostly makes a definition and gives proofs in types A and B. Later research has focused on other types and connections to other areas of math.  Here what I consider the other main papers in this vein. 


*

*Clusters, Coxeter-sortable elements and noncrossing partitions Nathan Reading. Works out the analog of 132 avoiding in all types and develops connections to non-crossing partitions and cluster algebras.

*Sortable elements and Cambrian lattices Nathan Reading. Gives case by case proofs of most of the conjectures from the first paper.

*Noncrossing partitions and representations of quivers Colin Ingalls and Hugh Thomas. Connections between Cambrian combinatorics and qiver representation theory.

*Cambrian fans, Nathan Reading and David Speyer. Generalizes the polyhedral geometry of the normal fan of the associahedron to all finite types; conjectures and almost proves that the $g$-vector fan of a cluster algebra is a coarsening of the Coxeter arrangement.

*Permutahedra and generalized associahedra Christophe Hohlweg, Carsten Lange and Hugh Thomas. Constructs a polytope whose normal fan is the fan from the preceding paper.

*Sortable elements in infinite Coxeter groups Nathan Reading and David Speyer. Redoes the whole theory for infinite Coxeter groups, where the orientation of the Dynkin diagram is required to be acyclic. (Since the finite Dynkin diagrams are trees, the importance of this condition was not clear before.) Also gives uniform proofs of all results which were previously proven by case by case check.

*Sortable Elements for Quivers with Cycles Nathan Reading and David Speyer Removes the acyclicity condition from the previous paper.

*Combinatorial frameworks for cluster algebras Nathan Reading and David Speyer. Connections between Cambrian lattices and cluster algebras. 
A: Stembridge in his article "On the fully commutative elements of Coxeter groups" says "by a theorem of 
Björner [3], one knows that every subinterval of the weak order is at least a lattice."
The reference is to Anders Björner's paper "Orderings of Coxeter groups" available online here. But I cannot figure out how to get MIT libproxy to let me read this article, so I cannot say for sure.
A: I've just got a glimpse of a proof by induction. Given two vertices of a permutohedron, the smallest face containing them is a product of permutohedra. If they are of lower dimension then by induction it is a lattice whose top and bottom will give join and meet of the corresponding permutations. The only case when there is no dimension drop is when the smallest face is the whole permutohedron, and then the join is the top (...321) and the meet is the bottom (123...).
The argument depends on the fact that the product order on the mentioned product of permutohedra coincides with the induced order on the face. This is more or less clear from the geometric picture: the Hasse diagram can be given by the edge graph of the permutohedron, with each edge pointing from bigger value of $c_1\sigma(1)+c_2\sigma(2)+c_3\sigma(3)+...$ to smaller, where $c_1<c_2<c_3<...$ can be arbitrary. I think this can be used to make it clear that the induced orientations of the edges are the same as the original ones on each factor of the product, since these factors correspond to freezing some of the $\sigma(k)$ in the ambient permutohedron. 
Hope this can be made into an actual proof...  
A: A proof is in George Markowsky, "Permutation Lattices Revisited," Mathematical Social Sciences 27 (1994), 59-72. http://www.umcs.maine.edu/~markov/permutationlattices.pdf
A: In my opinion, the most elegant proof is by Björner, Edelman and Ziegler (PDF file). They prove the following generalization: Let $\mathcal{H}$ be a finite set of hyperplanes in $\mathbb{R}^n$. Let $\mathcal{D}$ be the set of connected components of $\mathbb{R}^n \setminus \bigcup_{H \in \mathcal{H}} H$. Choose one region in $\mathcal{D}$; call it $D_0$. Put a poset structure on $\mathcal{D}$ as follows: $D_1 \leq D_2$ iff, whenever a hyperplane $H \in \mathcal{H}$ separates $D_1$ from $D_0$, it also separates $D_2$ from $D_0$.
BEZ prove that, if every $D$ in $\mathcal{D}$ is a simplicial cone, then $\mathcal{D}$ is a lattice.
Apply this to the braid arrangement in $\mathbb{R}^{n-1}$ to get weak order on $S_n$.
A: Berge has a nice proof in Principles of Combinatorics, reproduced in the solution to Exercise 3.185(b) of my book Enumerative Combinatorics, vol. 1. Namely, $v\leq w$ in weak order if and only if the inversion sets $I_v$ and $I_w$ satisfy $I_v\subseteq I_w$. It follows that $v\vee w$ is defined by $I_{v\vee w}=\overline{I_v\cup I_w}$, where the overline denotes transitive closure. Hence the weak order is a join-semilattice. Since it is a finite poset with a unique minimal element, it is in fact a lattice.
Addendum. Here are some more details. If $w=w_1 w_2\cdots w_n$, then define the inversion set $I_w = \{ (w_i,w_j)\,\colon\, i<j, w_i>w_j\}$. A well-known characterization of inversion sets is that they are those subsets $S$ of $X=\{(i,j)\,\colon\, n\geq i >j\geq 1\}$ such that $S$ and its complement $X-S$ are transitive. Thus we need to show that the complement $Y$ of $\overline{I_v\cup I_w}$ is transitive. Hence if $(i,j),(j,k)\in Y$, then we need to show that $(i,k)\in Y$. This only depends on $i,j,k$, i.e., we need only verify it for the subword of $w$ consisting of the letters $i,j,k$. This is a routine verification. 
