2
$\begingroup$

The standard proof of the completeness theorem in first-order Gödel logic is based on a first-order countable language. I want to know that is there any proof of the completeness theorem in first-order Gödel logic for uncountable language, or is there an example that refute the completeness of first-order Gödel logic in the case of uncountable languages?

Background: The proof of completeness theorem in first-order Gödel logic is based on a Henkin construction. Let $T$ be a complete consistent theory, i.e., all sentences can not be formally deduced from $T$ and for any pair $(\varphi,\psi)$ of sentences either $T\vdash\varphi\to\psi$ or $T\vdash\psi\to\varphi$. define the equivalence relation $\sim$ on the set of sentences as $$\varphi\sim\psi~~~~ \mbox{if and only if}~~~~ T\vdash\varphi\leftrightarrow\psi.$$ The set of equivalence classes of $\sim$ form a countable linearly ordered set $A$ which can be embedded continuously is $[0,1]$. Countability of the language that leads to the countability of $A$ is an essential part of the proof. Using this embedding one could construct a model for $T$ which show that $T$ is satisfiable. (See Hajek: Metamathematics of fuzzy logic).

$\endgroup$
4
$\begingroup$

You didn’t specify the semantics you are interested in.

Gödel–Dummett logic in languages of arbitrary cardinality is complete with respect to safe models over linearly order Gödel algebras, and with respect to appropriate linearly ordered Kripke models.

For uncountable languages, the logic is not complete with respect to the standard algebra $[0,1]_G$, and completeness fails already for propositional logic. Let $(L,\le)$ be a linearly ordered set with a largest element $\infty$. Consider a language with propositional variables (aka nullary predicates) $\{p_a:a\in L\}$, and let $T$ be the theory axiomatized by $$\{(p_b\to p_a)\to p_b:a<b\}.$$ Any finite fragment of $T$ involving $a_1<\dots<a_n<\infty$ has a valuation $v$ in $[0,1]$ with $v(p_{a_1})<\dots<v(p_{a_n})<v(p_\infty)<1$, hence $T\nvdash p_\infty$. However, any model of $T$ where $v(p_\infty)\ne1$ must have $v(p_a)<v(p_b)$ for $a<b$, hence $v$ provides an embedding of $L$ into the algebra of truth values. In particular, if we take e.g. $L=(\omega_1+1,<)$, there is no such model over the $[0,1]$ algebra.

EDIT: I only now noticed that you are talking about satisfiability. This is a misstatement of the completeness theorem, as in absense of classical logic, it is not possible to reduce unprovability to consistency. For propositional logic, consistency in Gödel–Dummett logic (or in any consistent extension of FL_w intuitionistic logic for that matter) is equivalent to consistency in classical logic, hence regardless of cardinality any consistent theory has a $\{0,1\}$ model. This is no longer true for first-order logic. Modifying the construction above, consider a language with predicates $\{P_a(x):a\in L\}$, and let $T$ be the theory axiomatized by $$\{\neg\forall x\,P_\infty(x)\}\cup\{\forall x\,((P_b(x)\to P_a(x))\to P_b(x)):a<b\}.$$ In any model of $T$, the first axiom implies that there is an element $u$ such that the value of $P_\infty(u)$ is less than $1$, and then the values of $P_a(u)$ have to be ordered as a copy of $L$.

$\endgroup$
  • $\begingroup$ I should also point out that questions like this have been thoroughly investigated in the past. I don’t have access to it at the moment, but I’m pretty sure there is relevant material in Chapter VII of the Handbook of Mathematical Fuzzy Logic. If you are learning fuzzy logic, I’d recommend the Handbook anyway; while Hájek’s book is excellent and it gets the credit for basically starting off the field, it is rather outdated by now. $\endgroup$ – Emil Jeřábek supports Monica Mar 12 '14 at 13:42
  • $\begingroup$ Dear Emil, thanks for the useful answer and comment. $\endgroup$ – amin Mar 12 '14 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.