Distribution of Quantifiers over Operators

Question

I was looking at this website https://nokyotsu.com/qscripts/2014/07/distribution-of-quantifiers-over-logic-connectives.html and was surprised to find out that quantifiers could be written in this form. Does anyone know what the if then statement written backwards refers to here? Also, if someone has any good resources that proves these statements for a beginner in logic referring to quantifiers like these, that would be really helpful. I am curious to learn.

Answer 1

First, the $\leftarrow$ means that the right side implies the left side. Or, as a logical operator, it would be an 'if .. then ..', but with the right side as the 'if', and the left side as the 'then'. So, for example, $P \leftarrow Q$ would be the same as $Q \rightarrow P$

Second, to understand these equivalences (and why some of these only go one way), notice that an existential can be seen as kind of disjunction, that is, if $a,b,c,...$ denote the objects in your domain, then you can think of an existential like this:

$\exists x \: \varphi(x) \approx \varphi(a) \lor \varphi(b) \lor \varphi(c) \lor ...$

I use $\approx$ since this is technically not a logical equivalence, but if you really want to prove the above equivalence, you'd need to go into formal semantics, and that might be a bit to much to ask for a binner in logic. But, what you would be doing there does follow this basic idea, so let's just leave it more informal.

So, with this 'equivalence', we can show (or at least informally understand) an equivalence like $\exists x \: (P(x) \lor Q(x)) \Leftrightarrow \exists x P(x) \lor \exists x Q(x)$ as follows:

$\exists x (P(x) \lor Q(x)) \approx$

$(P(a) \lor Q(a)) \lor (P(b) \lor Q(b)) \lor (P(c) \lor Q(c)) \lor ... \Leftrightarrow$ (by Association and Commutation we can reorder)

$(P(a) \lor P(b) \lor P(c) ...) \lor (Q(a) \lor Q(b) \lor Q(c) ...) \approx$

$\exists x P(x) \lor \exists x Q(x)$

By thinking of a universal as a kind of conjunction over all objects over the domain, i.e using

$\forall x \: \varphi(x) \approx \varphi(a) \land \varphi(b) \land \varphi(c) \land ...$

you can likewise show that:

$\forall x \: (P(x) \land Q(x)) \Leftrightarrow \forall x \: P(x) \land \forall x \: Q(x)$ (good exercise to do for yourself!)