Quantifiers in contrapositive of transitivity of "divide" relation

Question

The transitivity of the division relation $|$ is stated as follow:

$ \forall a,b,c \in\mathbb Z : [a |b \land b|c \implies a|c] \tag{1}$

The contrapositive of this statement is:

$\exists a,b,c \in \mathbb Z : [a\nmid c\implies a\nmid b \lor b\nmid c] \tag{2}$

However, I am wondering what are the quantifiers $\forall$ and $\exists$ doing here. I mean I see no difference between the two in this context. The statement $(2)$ would be exactly the same if $\exists$ was replaced by $\forall$ ?

Answer 1

Let $R$ be any relation ( here, $R$ is the "divides" relation).

A relation $R$ is said to be transitive ( on a set ) if and only if

for all elements $a,b,c$ in this set ( meaning: whatever elements $a, b$ and $c$ may be ) IF $aRb$ and $bRc$ holds, THEN $aRc$ also holds.

So, you need a universal quantifyer to define transitivity in general, and to define the transitivity of any particular relation.

Note : the contrapositive of a propostion needs to be equivalent to this proposition ( it says the same thing in another way);in general the contrapositive of " for all $x$, if $P(x)$ then $Q(x)$ " is " for all $x$, if not$-Q(x)$ then not$-P(x)$"

Answer 2

Not necessarily--I think the right way to think about it is that the in the case of the contrapositive, only one case (rather than for every $(a,b,c)\in \mathbb{Z})$; hence the existence) $(a,b,c)\in \mathbb{Z}$ is required such that the implication holds. In other words, I think the contrapositive is correctly stated as you have it in the question.

Answer 3

Only conditionals (i.e. statements of the form $\phi \to \psi$) have a contrapositive ($\neg \psi \to \neg \phi$)

Your statement is not a conditional. It is a universal statement, and there is no such thing as the contrapositive of a universal statement.

Now, that said, I think what you mean (or what the book you are reading means) is something like this:

The body of the universal statement that you have is a conditional. In fact, many universal statements are like that. As such, we can consider the statement that results by taking the contrapositive of that body, and plugging it back into the universal statement. In your case, that gets you:

$$\forall a,b,c \in \mathbb Z : [a\nmid c\implies a\nmid b \lor b\nmid c]$$

Now, what's nice about this statement is that it is equivalent to the original statement. And, that is something true about contrapositives as well: $\neg \psi \to \neg \phi$ is equivalent to $\phi \to \psi$.

Also, one important application of the notion of a contrapositive is that if you have to prove a conditional $\phi \to \psi$, then maybe a good strategy would be to try proving its contrapositive $\neg \psi \to \neg \phi$ instead ... sometimes that's easier to do. Likewise, if you ever have to prove a universal statement of the form $\forall x [\phi \to \psi]$, you could consider trying to prove the equivalent statement $\forall x [\neg \psi \to \neg \phi]$ instead.

Given all that, I can see how someone could extend the notion of 'contrapositive' to cover statements of the form $\forall x [\phi \to \psi]$, and say that the 'contrapositive' of $\forall x [\phi \to \psi]$ is $\forall x [\neg \psi \to \neg \phi]$.

However, your statement $$\exists a,b,c \in \mathbb Z : [a\nmid c\implies a\nmid b \lor b\nmid c]$$

has no such redeeming qualities. It is not equivalent to the original statement, and in fact your statement is next to meaningless: it would be true if there was a single pair of numbers $a$ and $c$ such that $a \nmid c$

Indeed, quantifiers make all the difference:

$$\forall a,b,c \in \mathbb Z : [a\nmid c\implies a\nmid b \lor b\nmid c]$$

is an interesting theorem about numbers, but $$\exists a,b,c \in \mathbb Z : [a\nmid c\implies a\nmid b \lor b\nmid c]$$ is not: they mean different things.

In sum, you can't just ignore or swap quantifiers!