A tautology that contains quantifier and logical connective.

Question

It might seem a stupid "question", but I need a logical explanation of it.

If $p(x)$ is a predicate and $q$ is a statement, then $(\forall x:p(x))\wedge q\iff \forall x:(p(x)\wedge q)$, and similarly we get if $\wedge$ and/or $\forall$ replaced by $\vee$ and $\exists$ respectively.

I've tried to name some statements in order to make a truth table to convince myself, but I'm unable to name some explicitly.

$$--------$$ Example: Prove that $$A\cap \left ( \bigcup_{\alpha \in \Lambda}B_{\alpha} \right )=\bigcup_{\alpha \in \Lambda}(A\cap B_{\alpha})$$ where $A$ is a set and $\{ B_{\alpha} \}_{\alpha\in\Lambda}$ is a family of sets. If I understood the logical explanation above then I would prove this way \begin{align} A\cap \left ( \bigcup_{\alpha \in \Lambda}B_{\alpha} \right )&=\left \{ x\mid x\in A \right \}\cap\left \{ x\mid \forall \alpha \in\Lambda:x\in B_{\alpha} \right \}\\ &=\left \{ x\mid \forall \alpha \in\Lambda:(x\in A)\wedge (x\in B_{\alpha}) \right \}\\ &=\left \{ x\mid \forall \alpha \in\Lambda:x\in A\cap B_{\alpha} \right \}\\ &=\bigcup_{\alpha \in \Lambda}(A\cap B_{\alpha}). \end{align}

Answer 1

Why is this so? $(∀x:p(x))∧q⟺∀x:(p(x)∧q)$

Versa: If $p(x)$ is true for any $x$, and $q$ is true (and $x$ is free in $q$), then both $p(x)$ and $q$ are true for any $x$.

Vice versa: If both $p(x)$ and $q$ are true for any $x$ (and $x$ is free in $q$), then $p(x)$ is true for any $x$ and $q$ is true.

$$(∀x:p(x))∧q⟺∀x:(p(x)∧q)$$

---

If $p(x)$ is true for any $x$, or $q$ is true (and $x$ is free in $q$), then either $p(x)$ or $q$ are true for any $x$.

Vice versa: If either $p(x)$ or $q$ are true for any $x$ (and $x$ is free in $q$), then either $p(x)$ is true for every $x$ , or $q$ is true.

$$(∀x:p(x))\vee q⟺∀x:(p(x)\vee q)$$

---

Versa: If $p(x)$ is true for some $x$, and $q$ is true (and $x$ is free in $q$), then both $p(x)$ and $q$ are true for some $x$.

Vice versa: If both $p(x)$ and $q$ are true for some $x$ (and $x$ is free in $q$), then $p(x)$ is true for some $x$ and $q$ is true.

$$(\exists x:p(x))∧q⟺\exists x:(p(x)∧q)$$

---

If $p(x)$ is true for some $x$, or $q$ is true (and $x$ is free in $q$), then either $p(x)$ or $q$ are true for some $x$.

Vice versa: If either $p(x)$ or $q$ are true for some $x$ (and $x$ is free in $q$), then either $p(x)$ is true for some $x$ , or $q$ is true.

$$(\exists x:p(x))\vee q⟺\exists x:(p(x)\vee q)$$

Answer 2

Are you looking for example predicates? How about:

Let the domain be the set of U.S. Presidents. Let $p(x)$ be "$x$ is male", and $q$ be "Barack Obama is black."

Then $(\forall x :p(x)) \wedge q$ holds because every U.S. President is male, and also Barack Obama is black. The statement $\forall x: (p(x) \wedge q)$ is also true, because for each U.S. President, it is the case that that U.S. President is male and Barack Obama is black.

Answer 3

does this help? $$ \forall x \quad p(x) $$ may be envisaged as a conjunction $$ \land_{x \in U} \quad p(x) $$ where $U$ is the relevant universe

similarly $$ \exists x \quad p(x) $$ may be envisaged as a conjunction $$ \lor_{x \in U} \quad p(x) $$

Answer 4

"I've tried to name some statements in order to make a truth table to convince myself"

But truth-tables aren't the appropriate apparatus here.

The only wffs of quantified logic that can be shown to be valid using truth-tables are those wffs where (in a good sense) the quantifiers aren't relevant to the validity -- where we can systematically replace quantified bits like $\forall x Fx$ by simply $P$ and the wff is still valid.

For example, the wff $\forall xFx \to \forall xFx$ is valid because it is just like the wff $P \to P$, and both are instances of the tautologically valid form $\alpha \to \alpha$. You can show the validity of that form using a truth-table (that's what we mean when we say it is tautological) -- but that's because it has nothing essentially to do with quantifiers.

On the other hand although $\forall xFx \to \exists xFx$ is valid it isn't valid by the truth-table test, it isn't valid just because of the truth-functional connective it contains. It isn't an instance of truth-table-valid form such as $\alpha \to \alpha$ or of any other tautologically valid form. Rather it is valid in virtue of the meanings of the two quantifiers

The logically validity of $(\forall xFx \land Q) \equiv \forall x(Fx \land Q)$ is of the second kind. This is not the instance of a truth-table tautology but valid because of the meaning of the quantifiers. And because it isn't an instance of a truth-table tautology, you can't use truth-tables to prove its validity.