I have shown some metatheorems like $P(\Gamma):=(\Gamma\vdash\psi\Leftrightarrow\Gamma\vDash\psi)$ or $Q(\Gamma):=(\Gamma\vdash\psi\Leftrightarrow\ \vdash\bigwedge\Gamma\rightarrow\psi)$ for all finite sets of formulas $\Gamma$. Now I would like to extend these to infinite $\Gamma$.

My idea is to show that finite subsets $(\Phi_n)_{n\in\mathbb{N}}$ with $\Gamma\,{=}\,\bigcup_{n\in\mathbb{N}}\Phi_n$ exist such that $P(\Phi_n)$ is valid for all $n\in\mathbb{N}$. I feel like this should be possible using the compactness theorem.

Next, I would like to use $Q$ for a definition over infinite sets, e.g. $\Gamma\vdash\psi$ iff there are finite subsets $(\Phi_n)_{n\in\mathbb{N}}$ with $\Gamma\,{=}\,\bigcup_{n\in\mathbb{N}}\Phi_n$ such that $\vdash\bigwedge\Phi_n\rightarrow\psi$ for all $n\in\mathbb{N}$. How can I argue for the existence of such subsets, and is my idea correct? If not, how is this usually done?

EDIT: Don't we have by compactness $\Gamma\vDash\psi$
$\Leftrightarrow\Gamma\cup\{\lnot\psi\}$ unsatisfiable
$\Leftrightarrow$ $\exists$ finite $\Phi\subseteq\Gamma\cup\{\lnot\psi\}:\Phi$ unsatisfiable
$\Leftrightarrow$ $\exists$ finite $\Phi\subseteq\Gamma:\Phi\cup\{\lnot\psi\}$ unsatisfiable
$\Leftrightarrow$ $\exists$ finite $\Phi\subseteq\Gamma:\Phi\vDash\psi$,
and thus $P(\Phi)$ for finite $\Phi$ directly shows $P(\Gamma)$ for infinite $\Phi$ ?
And isn't $\Gamma\vdash\psi$ thus equivalent to $\Gamma\vDash\psi$ which is equivalent to $\exists$ finite $\Phi\subseteq\Gamma:~\vdash\bigwedge\Phi\rightarrow\psi$ ?


1 Answer 1


Yes, that's correct. The following are true for all sets $\Gamma$, regardless of whether $\Gamma$ is finite:

  • $\Gamma\vdash\varphi\iff\Gamma\models\varphi$

  • $\Gamma\vdash\varphi\iff \Phi\vdash\varphi$ for some finite $\Phi\subseteq\Gamma$

  • $\Gamma\vdash\varphi\iff\vdash\bigwedge\Phi \implies\varphi$ for some finite $\Phi\subseteq\Gamma$.

Everything here that works for finite collections works for infinite ones as well. (Note that we don't even have to assume that $\Gamma$ is countable, which was implicit in your first attempt.)

  • $\begingroup$ Thanks. I was very tired yesterday and made many mistakes, so I just had to make sure to be right this time. $\endgroup$
    – xamid
    May 1, 2017 at 12:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .