Why does the interaction with environment remove the basis ambiguity : decoherence theory In decoherence theory, we try to remove the measurement postulate from Q.M to replace it by unitary evolutions.
Consider a two level system $S$, an apparatus $A$ and the environment $E$.
A first model of measurement is the following :
If $S$ is in $|\psi_S \rangle = \alpha |0\rangle + \beta |1\rangle$, I will have an interaction with the apparatus such that :
$$|\psi_S \rangle |A_i \rangle \rightarrow \alpha |0\rangle |A_0 \rangle + \beta |1 \rangle |A_1\rangle $$
However, this model is not good enough to describe a measurement because, if $\alpha=\beta=\frac{1}{\sqrt{2}}$, I have :
$$\frac{1}{\sqrt{2}} \left( |0\rangle |A_0 \rangle + |1 \rangle |A_1\rangle \right) = \frac{1}{\sqrt{2}}\left( |-\rangle |A_- \rangle + |+ \rangle |A_+\rangle \right) $$
Where I defined $|\pm\rangle = \frac{1}{\sqrt{2}} \left(|0\rangle \pm |1\rangle \right) $ (same idea for the apparatus).
$|0\rangle$ and $|1\rangle$ are eigenstates of $S_z$ spin, and $|+\rangle$ and $|-\rangle$ are eigenstates of $S_x$ spin.
The exact reason why this model is not good are still a little obscure for me (see What was exactly the preferred basis problem in decoherence ). 
But what I understood from it is that it is not a good model because with this way of rewriting the vector, one could say "we measured $S_z$", but another one could say "we measured $S_x$". 
Then, to solve the problem, we say that actually the apparatus+system also entangle with the environment. And this interaction remove the ambiguity of the measurement basis.
In practice it means that we also have :
$$\frac{1}{\sqrt{2}} \left( |0\rangle |A_0 \rangle + |1 \rangle |A_1\rangle \right)|E_i\rangle \rightarrow \frac{1}{\sqrt{2}} \left( |0\rangle |A_0 \rangle |E_0\rangle + |1 \rangle |A_1\rangle |E_1\rangle \right)$$
And then there is apparently no more the ambiguity basis when we take the partial density matrix of $S+A$, it is written in Chap IV, part A of 

Decoherence, einselection, and the quantum origins of the classical

From Zurek.
We have :
$$\rho_{S,A}=\frac{1}{2} \left( |0 A_0\rangle \langle 0 A_0 | + |1 A_1\rangle \langle 1 A_1 | \right) $$
But for me there is still a basis ambiguity.
Indeed, the matrix is the identity in $span(|0 A_0\rangle, |1 A_1 \rangle)$. Then if I write for example : $|\phi_{\pm}\rangle = \frac{1}{\sqrt{2}} \left(|0 A_0 \rangle \pm |1 A_1 \rangle \right) $ for example, I also have :
$$\rho_{S,A}=\frac{1}{2} \left( |\phi_+\rangle \langle \phi_+ | + |\phi_-\rangle \langle \phi_- | \right) $$
Thus, we have a lot of basis in which $\rho_{S,A}$ is diagonal : there is somehow still a basis ambiguity.
However, maybe we are only looking for basis in which the states of the mixture are separable ? And for this case there is only the basis : $(|0A_0\rangle, |1,A_1\rangle)$.
But I am not sure of this.
In summary : how does the interaction with the environment solve the basis ambiguity problem ?
 A:  Warm-up: pure-state version 
The basis ambiguity problem is an artifact of considering only two subsystems, represented by the two factors in $\sum_s c_s |s\rangle|A_s\rangle$. In reality, any useful measurement will compel the thing being measured to influence its surroundings in a prolific way, resulting in a practically irreversible cascade of effects into many uncontrolled parts of the system (the electronics, the table, the atmosphere, and so on). So a more realistic (but still idealized) model of a measurement would be something like
$$
 \sum_s c_s|s\rangle|A\rangle|B\rangle|C\rangle\cdots
 \to
 \sum_s c_s|s\rangle|A_s\rangle|B_s\rangle|C_s\rangle\cdots.
\tag{1}
$$
In this model, each factor represents some chunk of the system that is complex enough so that different values of $s$ lead to almost-exactly-mutually-orthogonal states of that chunk. 
To see why this eliminates the basis ambiguity problem, consider the state
$$
|\psi\rangle =
|0\rangle|A_0\rangle|B_0\rangle
+
|1\rangle|A_1\rangle|B_1\rangle,
\tag{2}
$$
where both terms are understood to be non-zero, and each factor in the first term is understood to be orthogonal to the corresponding factor in the second term. I'll call this a "superposition of factor-by-factor orthogonal terms." The claim is that there is no basis ambiguity in this case. To see why the $0/1$ basis has a unique status, consider some other orthonormal basis $2/3$ and write
$$
|0\rangle=a|2\rangle+b^*|3\rangle
\hskip2cm
|1\rangle=b|2\rangle-a^*|3\rangle.
\tag{3}
$$
(The coefficients are arranged to respect the orthogonality of $|0\rangle$ and $|1\rangle$.) Let $P$ be the operator that projects the first factor onto $|2\rangle$. Applying $P$ to (2) gives
$$
 P|\psi\rangle = 
 |2\rangle\otimes \big(a|A_0\rangle|B_0\rangle + b|A_1\rangle|B_1\rangle\big).
\tag{4}
$$
The factor in parentheses is separable (non-entangled) if and only if either $a$ or $b$ is zero, in which case the $2/3$ basis is just a relabeling of the $0/1$ basis. This shows that the $0/1$ basis has a unique status in the state (2), so there is no basis ambiguity with respect to this factorization of the Hilbert space.

 Resolving the basis ambiguity: mixed-state version 
The OP asks specifically about the mixed state
$$
 \rho\propto |0 A_0\rangle\langle 0 A_0|
 + |1 A_1\rangle\langle 1 A_1|,
\tag{5}
$$
which is obtained from (2) by tracing over $B$ (which was denoted $E$ in the OP). The $0/1$ basis still has a unique status in the bipartite mixed state (5), just as it did in the tripartite pure state (2), and the proof is similar. To see that the $0/1$ basis still has a unique status, define $P$ as before, and consider the (unnormalized) density matrix $P\rho P$. The result is
$$
P\rho P\propto |2\rangle\langle 2|\otimes\Big(
  |a|^2|A_0\rangle\langle A_0| + 
  |b|^2|A_1\rangle\langle A_1|
 \Big).
\tag{9}
$$
This shows that if $a$ and $b$ are both non-zero, then $P\rho P$ is a mixed state; but if either $a$ or $b$ is zero (in which case the $2/3$ basis is just a relabeling of the $0/1$ basis), then $P\rho P$ is a pure state. This shows that the $0/1$ basis has a unique status in the state (5), so there is no basis ambiguity.

 Perspective 
As mentioned earlier, we really ought to have lots of tensor factors, not just three and certainly not just two. In the many-partite case, there are no simple (i.e., few-factor) observables that are sensitive to interference between those two terms. In other words, we have no practical way of determining the relative phase of those two terms. In such a situation, we might as well replace the superposition of the factor-by-factor orthogonal terms with an appropriately-weighted mixture of those same terms. This doesn't involve taking any partial trace; it only involves discarding the relative phase information that we aren't able to access with any manageably simple observables anyway. I assume this is where the name "decoherence" came from. 
The formalism in which different subsystems are modeled by different tensor factors in the Hilbert space is often convenient, but it has a limitation: it forces us to choose boundaries between those "subsystems." Such choices are clearly artificial. This is not a limitation of quantum theory; it's only a limitation of the (convenient) formalism that tries to use a factorization of the Hilbert space to represent a list of "subsystems."
More importantly, no matter what formalism we use, decoherence theory doesn't solve the measurement problem. It only allows us to recognize when (and to what degree) something has been "measured," so that we know when we can safely use Born's rule. 
