Let $\tau=(C, F, R,\textbf{arity})$ be a vocabulary, where $C$ is a set of constant symbols, $F$ is a set of function symbols, $R$ is a set of relation symbols and $\textbf{arity}$ is a function that returns the arity of a relation symbol or a function symbol. From now on we write $\tau=C\cup F\cup R)$ and treat it like a set. A predicate logic formula $\varphi(x_1,\ldots,x_n)$ is said to be satisfiable if theres a $\tau$-structure $\mathcal{A}=(A,(z^\mathcal{A})_{z\in\tau})$ and $(a_1,\ldots,a_n)\in A$ such that $\mathcal{A}\models \varphi[a_1,\ldots,a_n]$.
$\varphi(x_1,\ldots,x_n)$ means, that the set of variables that $\varphi$ uses is a subset of $\{x_1,\ldots,x_n\}\subseteq X$ and $z^\mathcal{A}$ is the interpretation of $z\in \tau$ in $A$.
A predicate logic formula is called positive if the only logical links that are contained in it are $\land$ and $\lor$.
I want to show, that every positive formula is satisfiable.
So basically I think I have to perform an induction on the formula construction. But I have some problems with that. Do I have to first construct the subset of all positive formulas over an arbitrary vocabulary $\tau$ by myself and then perform the induction on that construction?
If I constructed them, I would basically just construct them the same way as I would construct all predicate logic formulas but leave out one step since $\neg$ can't be used in a positive formula:
Let $\tau=C\cup F\cup R$ be a vocabulary and $X$ be a (usually countably infinite) set of individual variables. A term $t$ is a word over $(C\cup F\cup X)^*$ of one of the forms
(a) $t=x\in X$,
(b) $t=c\in C$,
(c) $t=ft_1\ldots t_n$ with a unique $f\in F$ with $\textbf{arity}(f)=n$ and terms $t_1,\ldots,t_n$.
Now we consider $Z=\tau\cup X\cup\{\equiv,(,),\lor,\land,\exists,\forall\}$ and define the atomic formulas as words in $Z^*$ that have one of the forms
(1) $t\equiv t^\prime$ for terms $t,t^\prime$,
(2) $rt_1\ldots t_n$ with $r\in R$ with $\textbf{arity}(r)=n$ and terms $t_1,\ldots,t_n$.
Now we can define the Set $\textbf{Pos}_\tau$ of all positive predicate logic formulas over a vocabulary $\tau$ as the smalles set $M\subset Z^*$ that satisfies
(i) every atomic formula is in $M$,
(ii) $\alpha,\beta\in M\Rightarrow(\alpha \lor\beta)\in M$,
(iii) $\alpha,\beta\in M\Rightarrow(\alpha\land \beta)\in M$,
(iv) $\alpha\in M,x\in X\Rightarrow \exists x\alpha\in M$,
(v) $\alpha\in M,x\in X\Rightarrow \forall x\alpha\in M$.
So the difference in constructing $\textbf{Pos}$ and constructing the set $\textbf{Fml}$ of all predicate logic formulas is, that consider a different alphabet $Z$. We now don't have $\neg$ but we need $\lor,\land$ and $\forall$ since $\{\neg,\lor\}$ is a propositional basis, so we were able to represent $\land$ and all the other symbols by using $\neg$ and $\lor$ and also we were able to represent $\forall$ by using $\neg$ and $\exists$.
So strictly speaking, I now have to prove that I can perform induction on this construction... Another problem I have is the following. I basically have to prove by induction that every formula in $\textbf{Pos}_\tau$ is satisfiable. If I perform the induction, I would start with the base case, that means we consider an atomic positive formula $\alpha$ over $\tau$. I now have to find a $\tau$-structure $\mathcal{A}=(A,\ldots)$ and find a $(a_1,\ldots,a_n)\in A^n$ such that $\mathcal{A}\models \alpha[a_1,\ldots,a_n]$. The problem is, that $\tau$ is completely arbitrary, and the structure depends on the vocabulary, since every element of the vocabulary has to be interpreted by the structure. Right...? I don't know how to handle all that since I am pretty new to this...
Maybe someone of you has a tip or something! Thank you very much for reading and for your help! Kind regards, Max.
Hint: Every positive formula is satisfiable in a structure that only has one element.