There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself as input. It is known and proved that Ld is a non-Recursively Enumerable Language.
Now Ld can be reduced to the problem ATM (Universal Language) as follows "To see if w ∈ Ld check if <w, w> ∈ ATM."
The theorem 9.7 (Page 393) in Hopcroft Ullman states that if there exists a reduction from P1 to P2, then: if P1 is non RE then so is P2.
According to this theorem, since Ld can be reduced to ATM, and Ld is non-RE, ATM must be non-RE. But we know that ATM is Recursively Enumerable and undecidable. How is this possible?