¿Cuál es el error en esta prueba?

Question

Durante una larga noche sin dormir me las arreglé para llegar hasta con una prueba de una afirmación que sabe que es falsa, y por la vida de mí no puedo averiguar lo que hice mal. Donde está mi error?

Teorema: Vamos a $f:A\to B$ ser cualquier función. Hay un bijection de a sobre B.

Prueba: Por contradicción. Suponga que no hay bijection de a sobre B. Considere la declaración "Si f es una surjection, entonces f es una inyección." Este enunciado es verdadero si f no es un surjection o f es una inyección (esto es material de implicación). Pero esta afirmación es falsa, ya que si f es una surjection no se puede ser una inyección porque no hay bijections. Así que, a continuación, la declaración de "Bien f no es un surjections o es una inyección que" es falso, lo que significa que f es una surjection y no una inyección (demorgan). Pero si f no es una inyección de entonces o bien f no es una inyección o es un surjection. El uso de material implicación de nuevo, esto es equivalente a la afirmación "si f es una inyección, entonces es un surjection," lo cual es falso, porque entonces no sería un bijection. Así que f es una inyección y no un surjection, que es claramente una contradicción.

Esto es obviamente absurdo, pero estoy teniendo problemas para pensar en línea recta. Dónde está mi error?

Answer 1

Su material implicación mezcla de las variables:

"Si f es una surjection, entonces f es una inyección." Este enunciado es verdadero si f no es un surjection o f es una inyección (esto es material de implicación).

debe ser:

"Si f es una surjection, entonces f es una inyección." Esta declaración es verdadera si existe una función de $g$ tal que $g$ no es una inyección y $g$ es un surjection o para todos $g$ $g$ no es un surjection (esto es material de implicación).

lo cual es falso, por lo que su aplicación de materiales de aplicar más de dos veces en realidad es falso.

---

Editar Este fue el origen del error y de las siguientes afirmaciones son sólo consecuencias de la negación de esta declaración. Lea esto si usted quiere entender claramente donde está el minstakes:

Vamos a reescribir su prueba:

Prueba: Por contradicción. Suponga que no hay bijection de $A$ a $B$. Considere la declaración : $$P \, \, \text{ "If f is a surjection, then f is an injection."}$$

$P$ no depende de $f$ , por lo que esta declaración de $P$ es verdadera si y sólo si cada surjection es una inyección. (esto es claramente falso)

Este enunciado es verdadero si f no es un surjection o f es una inyección (esto es material de implicación).

Primero que todo, usted no puede resolver cualquier función de $f$, por lo que esta sería: esta declaración es verdadera si y sólo si cada surjection es una inyección. Pero el problema de la prueba es el hecho de que parece que han corregido una función en el biginig pero no solucionar cualquier función. Si queremos seguir a analizar la prueba que tenemos que arreglar una función de $f$ así que vamos a reiniciar la prueba y la revisión de una función:

Prueba: Por contradicción. Suponga que no hay bijection de $A$ a $B$. Arreglar una función de $f$,Considere la posibilidad de la declaración : $$P_f \, \, \text{ "If f is a surjection, then f is an injection."}$$

Ahora estoy de acuerdo en que esta declaración se ajusten a tus pensamientos y satisfacer su creteria:

Esta declaración de $P_f$ es cierto si f no es un surjection o f es una inyección (esto es material de implicación).

ahora tu razonamiento es correcto y de esta manera se sigue fácilmente.

Pero esta afirmación es falsa, ya que si f es una surjection no se puede ser una inyección porque no hay bijections. Así que, a continuación, la declaración de "Bien f no es un surjections o es una inyección que" es falso,

• Así que si $f$ es un surjection, a continuación, la declaración de $P_f$ es falso
• Lo que si $f$ no es un surjection?, si investigamos un poco, resulta que $P_f$ es cierto.

Y esto no es correcto , la conclusión de que $P_f$ es falso, pero no $P_f$ no es falso para cada función de $f$ , es falsa sólo para las funciones de $f$ que no surjective (a) y de aquí a fin de pasar este paso debemos asumir desde el principio que la $f$ es un surjection pero cada cosa no va a funcionar, simplemente porque lo que estamos tratando de demostrar que no es correcto!

Answer 2

Considerar estas dos afirmaciones:

Si $f$ es un surjection, a continuación, $f$ es una inyección.

Si $f$ es un surjection, a continuación, $f$ no es una inyección.

Como se señaló, su suposición de que no hay bijections implica la segunda declaración debe ser cierto. El resto de su razonamiento equivale a la afirmación de que sólo una de las dos afirmaciones pueden ser verdaderas. Pero ese no es el caso. Ambas afirmaciones son verdaderas si la premisa, de que $f$ es un surjection, es falso. Dijo simbólicamente,

$$((P\implies Q)\land(P\implies\lnot Q))\iff \lnot P$$

Answer 3

Sugerencia: trate de un ejemplo sencillo: por ejemplo, vamos a $A = \{1\}$$B = \{1, 2\}$, entonces no es una función de$A$$B$, por ejemplo, la función de $f$ que se asigna a$1$$1$. Ahora trabajo a través de su argumento para ver dónde se rompe.