2 equivalent definitions of finite cover property

Question

I have 2 different definitions of the finite cover property, f.c.p. a property of first order theory, which I would like to prove equivalent. I was trying to prove this equivalence but I got stuck.

Answer 1

Definition 2.1 defines what it means for a theory $T$ to not have f.c.p. Negating the statement, we find that it says:

A theory has f.c.p. if and only if there exists a formula $\varphi(x;y)$ with the following property, which I'll call $(\star)$: For every integer $n$, there exists a set $A$ in a model of $T$ and a set $p\subseteq \{\varphi(x;a),\lnot\varphi(x;a)\mid a\in A\}$ such that $p$ is inconsistent and every subset of $p$ of size less than $n$ is consistent.

So to show that the two definitions are equivalent, we just need to show that $T$ has a formula with $(\star)$ if and only if $T$ has a formula with f.c.p. according to Definition 4.1. But $(\star)$ and f.c.p. essentially say the same thing. The only substantial difference is that $(\star)$ allows instances of both $\varphi$ and $\lnot \varphi$, while f.c.p. requires just instances of $\varphi$. This can be fixed by the standard trick of coding finitely many formulas (in this case $\varphi$ and $\lnot\varphi$) in a single formula.

Here are the details.

Claim 1: If $\varphi(x;y)$ has f.c.p., then it has $(\star)$.

This is the easy direction. Suppose $\varphi(x;y)$ has f.c.p. Let $n$ be an integer. By f.c.p., there is some $N\geq n$ and $a^0,\dots,a^{N-1}$ such that $$\models \lnot \exists x\, \bigwedge_{k<N}\varphi(x;a^k)$$ and for every $\ell<N$, $$\models \exists x\, \bigwedge_{k<N,k\neq \ell}\varphi(x;a^k).$$ Let $A$ be the set of all elements appearing in the tuples $a^0,\dots,a^{N-1}$, and let $p = \{\varphi(x;a^k)\mid k<N\}$. Then $p$ is inconsistent, but every subset of $p$ of size $(N-1)$ is consistent. Since $N\geq n$, every subset of $p$ of size less than $n$ is contained in a subset of size $(N-1)$, and hence is consistent. So $\varphi(x;y)$ has $(\star)$.

Claim 2: If $\varphi(x;y)$ has $(\star)$, then there is a formula $\psi(x;y,z_1,z_2)$ with f.c.p.

Let $\psi(x;y,z_1,z_2)$ be the following formula: $$((z_1 = z_2)\land \varphi(x;y))\lor ((z_1\neq z_2)\land \lnot \varphi(x;y))$$ Note that $\psi(x;a,c_1,c_2)$ is equivalent to $\varphi(x;a)$ if $c_1 = c_2$ and equivalent to $\lnot\varphi(x;a)$ if $c_1\neq c_2$.

Let $N\geq 3$ be a natural number. By $(\star)$, there exists a set $A$ in a model of $T$ and a set $p\subseteq \{\varphi(x;a),\lnot\varphi(x;a)\mid a\in A\}$ such that $p$ is inconsistent and every subset of $p$ of size less than $N$ is consistent. Since $p$ is inconsistent, by compactness some finite subset of $p$ is inconsistent. Let $q\subseteq p$ be a finite subset of minimal size which is inconsistent, and note that $|q| \geq N$. Let $n = |q|$ (and note that by taking $N$ arbitrarily large, we can make $n$ arbitrarily large). Then we can enumerate $q$ as $$\varphi(x;a^0), \dots \varphi(x;a^{m-1}), \lnot \varphi(x;a^{m}),\dots,\lnot \varphi(x;a^{n-1}).$$

Technical point: A model of $T$ must have at least two elements. Otherwise, there would be at most one tuple which is substitutable for $y$, and hence $q$ would contain at most two formulas, but we took $N\geq 3$. So we can fix arbitrary elements $c_1 \neq c_2$.

Define $b^i = (a^i,c_1,c_1)$ for each $0\leq i < m$, and define $b^i = (a^i,c_1,c_2)$ for each $m\leq i < n$. Then: $$\models \lnot \exists x\, \bigwedge_{k<n}\psi(x;b^k),$$ because $q$ is inconsistent, and for every $\ell<n$, $$\models \exists x\, \bigwedge_{k<n,k\neq \ell}\psi(x;b^k),$$ because no proper subset of $q$ is inconsistent.