Confusion with contraposition of an implication with quantifiers

Question

I'm learning about functions and more specific, surjections and injections. However I'm a little bit confused regarding the use of quantifiers and "contraposition".

Example:

A function $ f: X \rightarrow Y$ is injective if $ \forall x_1, x_2 \in X: x_1 \not = x_2 \implies f(x_1) \not = f(x_2) $, My book says this is equivalent to the contrapostion, that is: $ \forall x_1, x_2 \in X: f(x_1) = f(x_2) \implies x_1 = x_2 $. So in this case the quantifiers don't change.

However if we look at this example, which is an excercise my professor wrote out for us.

The original implication is: $$\forall B \in P(Y): \forall C \in P(Y): f^{-1}(B) \subset f^{-1}(C) \implies B \subset C \implies f $$ is surjective

And our professor said that the contraposition of this implication is: $f$ is not surjective $$ \implies \exists B \in P(Y): \exists C \in P(Y): \neg \left[ f^{-1}(B) \subset f^{-1}(C) \implies B \subset C \right] $$

So in this case the quantifiers do change. I can't seem to find the reason why sometimes they change and other times they don't. If anyone could clarify, I would highly appreciate it!

Answer 1

First case

$$\forall x_1, x_2 \in X: \color{orange}{\big(}x_1 \not = x_2\color{orange}{\big)} \implies f(x_1) \not = f(x_2)$$

$$ \forall x_1, x_2 \in X: f(x_1) = f(x_2) \implies \color{orange}{\big(}x_1 = x_2\color{orange}{\big)}$$

Second case (this should be what your professor actually trying to write)

$$\color{orange}{\big(}\forall B \in P(Y): \forall C \in P(Y): f^{-1}(B) \subset f^{-1}(C) \implies B \subset C\color{orange}{\big)} \implies f \text{ is surjective}$$ has contraposition as following

$$f \text{ is not surjective} \implies \color{orange}{\big(}\exists B \in P(Y): \exists C \in P(Y):\neg \left[ f^{-1}(B) \subset f^{-1}(C) \implies B \subset C \right] \color{orange}{\big)} $$

The problem might be how do you read the invisible bracket, in second case need to bracket the whole 'thing' just because we all know that 'thing' iff $f$ is surjective.

This is similar to when someone ask that how to read $\forall x,P(x)\rightarrow Q$, you can think this as $(\forall x,P(x))\rightarrow Q$ or $\forall x,(P(x)\rightarrow Q)$, but normally it means the second one, I think this is just some unwritten rules when people using those symbols.

Answer 2

Let $P$ be the statement $\forall B \forall C [f^{-1}(B) \subset f^{-1}(C) \rightarrow B \subset C]$.

Let $Q$ be the statement "$f$ is surjective."

Hence, by substitution $P \rightarrow Q$ is logically equivalent to

$\forall B \forall C [f^{-1}(B) \subset f^{-1}(C) \rightarrow B \subset C] \Rightarrow (f$ is surjective$)$

The law of contraposition states

$$P \rightarrow Q \Leftrightarrow \neg Q \rightarrow \neg P$$

Hence, by substitution we have

$\forall B \forall C [f^{-1}(B) \subset f^{-1}(C) \rightarrow B \subset C] \Rightarrow (f$ is surjective$)$

$\Leftrightarrow$

$\neg (f$ is surjective$)$ $ \Rightarrow \neg \forall B \forall C [f^{-1}(B) \subset f^{-1}(C) \rightarrow B \subset C] $

and by Demorgan's Law for Quantifers we have

$\neg (f$ is surjective$)$ $ \Rightarrow \exists B \exists C \neg [f^{-1}(B) \subset f^{-1}(C) \rightarrow B \subset C] $

which is the same as

$(f$ is not surjective$)$ $ \Rightarrow \exists B \exists C \neg [f^{-1}(B) \subset f^{-1}(C) \rightarrow B \subset C] $

Answer 3

Consider $\forall x[P(x)\Rightarrow Q(x)]$.

Since $A\Rightarrow B$ is equivalent to $\neg B\Rightarrow\neg A$, an equivalent statement is

$\forall x[\neg Q(x)\Rightarrow \neg P(x)]$

as required.

---

Moreover, $\forall x[P(x)\Rightarrow Q(x)]$ is equivalent to

$\forall x[\neg(P(x)\wedge \neg Q(x)]$,

since $A\Rightarrow B$ is equivalent to $\neg A\vee B$ or $\neg(A\wedge\neg B)$.

But $\neg \exists x$ means $\forall x \neg$ and so the latter is equivalent to

$\neg\exists x[P(x)\wedge \neg Q(x)]$,

which is by double negation,

$\neg\exists x[\neg ( \neg (P(x)\wedge \neg Q(x)))]$,

and so by De Morgan,

$\neg\exists x[\neg ( \neg P(x)\vee Q(x)]$

and hence by the above equivalence for the implication,

$\neg\exists x[\neg (P(x)\Rightarrow Q(x)]$.