I have a question about definability in a partial structure.
By a partial structure, I mean a structure $\mathfrak{A}$ that assigns to each predicate symbol $R$ two disjoint sets $R^{+}_\mathfrak{A}$ and $R^{-}_\mathfrak{A}$ such that $\mathfrak{A}$ thinks $R(x)$ is true of all members of $R^{+}_\mathfrak{A}$, $R(x)$ is false of all members of $R^{-}_\mathfrak{A}$, and $R(x)$ is undefined for all members outside $R^{+}_\mathfrak{A}\cup R^{-}_\mathfrak{A}$.
Also, I was working under the assumption that the valuation of complex formulas in a partial structure is given according to the Strong Kleene 3-valued logic. That is, a disjunction is true if and only if one of the disjuncts is true, false if both are false, and undefined otherwise; a conjunction is true if and only if both conjuncts are true, false if any one of them is false, undefined otherwise. One can think of universal quantifier as infinitary conjunction, and of existential quantifier as infinitary disjunction.
In such partial structures, it makes sense to distinguish two notions of definability.
Let's say a formula $\varphi(x)$ positively defines a set $S\subseteq|\mathfrak{A}|$ if and only if $\mathfrak{A}$ thinks $\varphi(x)$ is true of exactly those $s\in S$. Notice that it is not required that $\varphi(x)$ be false for $s\not\in S$. We say that $S$ is positively definable if some formula positively defines it.
Also, let's say that a formula $\varphi(x)$ totally defines a set $S$ if $\varphi(x)$ positively defines $S$ and $\neg\varphi(x)$ positively defines the complement $\bar{S}$ of $S$. $S$ is totally definable if there is a formula $\varphi$ that totally defines it.
It is trivial that if a set $S$ is totally definable then both $S$ and $\bar{S}$ are positively definable. My question is whether the converse holds. Namely, assuming $S$ and $\bar{S}$ are positively definable, is $S$ totally definable?
Given the assumption, there are two formulas $\varphi(x)$ and $\psi(x)$ such that $\varphi(x)$ positively defines $S$ and $\psi(x)$ positively defines $\bar{S}$. If $\psi(x)$ is the same formula as $\neg\varphi(x)$, then we are done. So assume that they are different. My intuition was that we should be able to find a formula $\chi(x)$ that totally defines $S$ by combining two formulas together in a certain way. But somehow I am having trouble finding one. Perhaps, I was misguided in my approach.
I am not sure if there is a well known result regarding this question. Thanks for your help in advance!
Here is a counterexample:
The universe is $\{1,2\}$, and the logical language contains just two predicates $p$ and $q$: $$ \begin{array}{c|cc} x & p(x) & q(x) \\ \hline 1 & T & ? \\ 2 & ? & T \end{array} $$ The set $\{1\}$ is positively defined by $p$ and its complement is positively defined by $q$.
Now suppose there is a $\varphi(x)$ that totally defines $\{1\}$. Since the universe is finite, $\varphi(x)$ can be expanded to a quantifier-free formula, and then we can replace every application of $p$ or $q$ to $1$ or $2$ by its value according to the model -- namely, represent $T$ by $p(x)\lor q(x)$, $F$ by $\neg(p(x)\lor q(x))$, and $?$ by $p(x)\land q(x)$.
So $\varphi(x)$ is equivalent (in this particular structure) to some propositional combination of $p(x)$ and $q(x)$ -- say, $\varphi(x)\equiv \psi[p(x),q(x)]$.
Now all your connectives are monotonic in "unknown", in that once the output is not unknown, changing one of the inputs from unknown to either of the known values will not affect the output. This will also be true for any composition of them.
Since $\psi[T,?]$ must be $T$, monotonicity means that $\psi[T,T]=T$.
But since $\psi[?,T]$ must be $F$, monotonicity means that $\psi[T,T]=F$. This is a contradiction.