Tuesday, February 22, 2011

Vacuously true

A sentence like $$ \forall a \in A : P(a) $$ is said to be Vacuously true if $A$ is the empty set, no matter what the predicate $P$ was. For example the sentence $$ \forall x \in \mathbb{R}$$ such that $$x^2 < 0 : x = 23 $$ is true (vacuously).

This could be tricky in some cases. An example I found in the exercises of the book Topology 2nd Ed. by Munkres (which is an awesome book btw), showed this sentence and asked if is true or not, if the two sets $A,B$ are guaranteed to be non-empty or not: $$ (A \times B) \subseteq ( C\times D) \implies A \subseteq C \mbox{ and } B \subseteq D $$.

After some time brushing the rust off my brain, this statement turned out to be true (as the intuition would expect) only if $A$ and $B$ are non-empty. Quiet a surprising result. A counter example case occurs when $A$ is empty but $B$ isn't, in which case $ A\times B$ is empty, in which case the statement holds vacuously although $B$ might not be a subset of $D$.

No comments: