Hilbert's paradox of the Grand Hotel
Hilbert's paradox is a veridical paradox: it leads to a counter-intuitive result that is provably true. The statements "there is a guest to every room" and "no more guests can be accommodated" are not equivalent when there are infinitely many rooms. An analogous situation is presented in Cantor's diagonal proof.