Associative and distributive laws over the intersections and unions of indexed families of sets state that:
$B\cup\bigcup_{i\in I}A_i=\bigcup_{i\in I}B\cup A_i$;
$B\cap\bigcap_{i\in I}A_i=\bigcap_{i\in I}B\cap A_i$;
$B\cup\bigcap_{i\in I}A_i=\bigcap_{i\in I}B\cup A_i$;
$B\cap\bigcup_{i\in I}A_i=\bigcup_{i\in I}B\cap A_i$;

Expressed in predicate logic, the above laws are as follows:
$x\in B\lor (\exists i\in I: x\in A_i)\iff \exists i\in I:(x\in B\lor x\in A_i)$;
$x\in B\land (\forall i\in I: x\in A_i)\iff \forall i\in I:(x\in B\land x\in A_i)$;
$x\in B\lor (\forall i\in I: x\in A_i)\iff \forall i\in I:(x\in B\lor x\in A_i)$;
$x\in B\land (\exists i\in I: x\in A_i)\iff \exists i\in I:(x\in B\land x\in A_i)$;

From this, we can infer the following rule (with some abuse of notation):
If we have an expression in form
enter image description here
then we can factor out this part
enter image description here
and get enter image description here

So my questions are
1) Can we always factor out other binary logical connectives (not only conjunction and disjunction, but also implication, exclusive disjunction etc.) out of the scope of the quantifier and why?
2) Does this also work with the uniqueness quantifier and why?


The equivalence principles you describe are a special case of the Prenex laws (so called since they allow one to rewrite any quantificational statement as one that is in 'Prenex form', whereall of its quantifiers are at the top of the statement):

Where $\psi$ does not contain $x$ as a free variable, and $Q$ Is a quantifier, whether existential, universal, or the unique existential:

$Qx(\phi(x) \lor \psi) \Leftrightarrow Q(x)\phi(x) \lor \psi$ (And of course you can apply Commutation on this)

This also works when the $\lor$ is an $\land$.

BUT: for the conditional you get:

$Qx(\psi \rightarrow \phi(x)) \Leftrightarrow \psi \rightarrow Qx\phi(x)$

$Qx(\phi(x) \rightarrow \psi) \Leftrightarrow Q'x \phi(x) \rightarrow \psi$ (!)

Where Q' is the dual of Q (that is $\exists' =\forall$ and vice versa). So there is still a law for the conditional, but the quantifier changes to its dual if it is the antecedent (if in consequent, then it does stay the same).

To inderstand why the quantifier changes, note:

$Qx(\phi(x) \rightarrow \psi) \Leftrightarrow$

$Qx(\neg \phi(x) \lor \psi) \Leftrightarrow$

$Qx\neg\phi(x) \lor \psi \Leftrightarrow$

$\neg Q'\phi(x) \lor \psi \Leftrightarrow$

$Q'x\phi(x) \rightarrow \psi$

The dual of $\exists !$ is $\neg \exists! \neg$... Which isn't a 'nice' quantifier at all, so probably it's best to say that this law does not apply with the unique existential in the antecedent.

Finally, for the biconditional and XOR there are no nice equivalence principles at all. (Not for the biconditional since it is two conditionals, and as we just noted, the conditional going one way works differently than the conditional going the other way, and the XOR is just the negation of the biconditional so that one does't have a nice principle either.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.