En general, una paradoja es un enunciado (o conjunto de enunciados) o una situación, que implica o conduce a una contradicción (ya sea lógica o intuitiva): parece verdadera pero es falsa, o parece falsa pero es verdadera.
Ejemplo: Consideremos los números naturales 1, 2, 3, 4, 5, 6,... y el subconjunto de los números pares 2, 4, 6, ... De acuerdo al sentido común, los números naturales son más (son de una cardinalidad mayor) que los números pares. Esta última afirmación es aparentemente verdadera, pues --podría uno argumentar-- los pares están contenidos en los naturales y, en consecuencia, éstos deben ser más.
"Los números naturales son más que los números pares" es una afirmación verdadera, pero solamente en apariencia. Porque, visto desde otro punto de vista, se puede establecer una biyección entre los naturales y los pares: la correspondencia i<-->2i nos lleva a concluir que el conjunto de los números naturales y el conjunto de los números pares tienen la misma cardinalidad, es decir, tienen el mismo número de elementos.
Ver más sobre paradoja en http://es.wikipedia.org/wiki/Paradoja