Quantifiers in contrapositive of transitivity of “divide” relation

divisibilitylogicquantifiers

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$ ?

Best Answer

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)$"

Related Question