Please help me with this problem.
Prove that if $\land \Phi \models \lor \Psi$ (both $\Phi$ and $\Psi$ infinite) then there exist $\phi_1,...,\phi_n$ from $\Phi$ and $\psi_1,...,\psi_m$ from $\Psi$ such that $\phi_1\land...\land \phi_n\models \psi_1\lor...\lor \psi_m$. This should follow from the Compactness theorem rather easily but I don't unterstand how.
Thanks in advance.
On
By soundness and completeness of propositional logic we only need to prove
If $\bigwedge \Phi \vdash \bigvee \Psi$ then there exist $\phi_1,...,\phi_n$ from $\Phi$ and $\psi_1,...,\psi_m$ from $\Psi$ such that $\phi_1\land...\land \phi_n\vdash \psi_1\lor...\lor \psi_m$.
Proofs are always finite and therefore involve only finitely many steps. So only finitely many of $\phi_i$s can be used in the proof of $\bigwedge \Phi \vdash \bigvee \Psi$. So we have
There exists $\phi_1,...,\phi_n$ such that $\phi_1\land...\land \phi_n\vdash \bigvee \Psi $
With the same reasoning the last step in the proof of $\phi_1\land...\land \phi_n\vdash \bigvee\Psi $ has to be like this:
$\cdots \Rightarrow (\psi_{i_1}\lor \cdots \lor \psi_{i_m}) \Rightarrow \bigvee\Psi$
Which yields:
There exist $\phi_1,...,\phi_n$ and $\psi_1,...,\psi_m$ such that $\phi_1\land...\land \phi_n\vdash \psi_1\lor...\lor \psi_m$.
If the logic you're using admits excluded middle, you could convert the hypothesis to $$ ⋀ Φ ∧ ⋀ ¬ ψ ⊢ ⊥. $$ Then Compactness would imply some finite subset $\phi₁ ∧ … ∧ φ_n ∧ ¬ ψ₁ ∧ … ∧ ¬ ψ_m$ of the left hand side entails a contradiction, and from there you can move $\psi₁$ through $\psi_m$ back to the right hand side.