Proving tautology by substitution

Question

How do I prove whether the following statement is a tautology or not using substitution?
∃x,P(x)∧∃x,Q(x)⇒∃x,(P(x)∧Q(x))

From what I understood if the expression is of the form A⇒A, then we can substitute values to prove tautology.
But how can I interpret ∃x,P(x) and ∃x,Q(x) on the RHS. Does this mean P∧Q? Where am I going wrong?

Answer 1

To prove the validity of a first-order formula $\varphi$ by substitution, you have to start from a propositional tautology $\alpha$, like $A \to A$ in your example, and find a suitable uniform substitution such that, when applied to $\alpha$, will produce $\varphi$.

Here the key-word is "uniform", i.e. every instance of a propositional letter $A_i$ occurring in $\alpha$ must be replaced with the same "atom".

Thus, form $A \to A$ we can get :

• $\exists x P(x) \to \exists x P(x)$, or

• $(∃x P(x) ∧ ∃x Q(x)) \to (∃x P(x) ∧ ∃x Q(x))$

but never :

$(∃x P(x) ∧ ∃x Q(x)) \to ∃x(P(x) ∧ Q(x))$.