An asymptotically tight bound on countermodels for Łukasiewicz logic (Q2506811): Difference between revisions

Results of \textit{S. Aguzzoli} and \textit{A. Ciabattoni} [J. Logic Lang. Inf. 9, No.~1, 5--29 (2000; Zbl 0951.03024)] show that for a formula \(\varphi\) in a Łukasiewicz infinite-valued propositional logic that is not a tautology, there is an upper bound for the cardinality of the MV-chain of countermodels of \(\varphi\). If \(l\) is the length of \(\varphi\), i.e., the total number of occurrences of \(n\) distinct variables in \(\varphi\), this bound is given by the expression \(\lfloor (l/n)^n \rfloor + 1\). In this paper it is shown that \(b(n,l)=(l/n)^n+1\) yields an asymptotically tight upper bound on the maximum cardinality of the smallest MV-algebras having countermodels for formulas of length \(l\). The result follows from the construction of a sequence of denumerably many non-tautologous formulas over \(n\) distinct propositional variables \(\Phi(n)=\{\varphi(n,l) \mid l \geq 2n \}\) such that the cardinality of the countermodels for \(\varphi(n,l)\) grows asymptotically to \((l/n)^n\) as \(l\) tends to \(\infty\). This construction relies on Schauder hats techniques. It should be noted that this paper starts with a comprehensive introduction to Łukasiewicz infinite-valued propositional logic. Also the basic notions from integral polyhedral geometry are recalled, making this paper highly self-reliant.