Factoring logical connectives out of unions and intersections of families of sets

322 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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.