The fact that Gödel's famous incompleteness theorem and the archetype of all logical paradoxes, that of the Liar, are related closely is, of course, not only well known, but is a part of the common knowledge of the community of logicians. Indeed, almost every more or less formal treatment of the theorem makes a reference to this connection. Gödel himself remarked in the paper announcing his celebrated result :The analogy between this result and Richard's antinomy leaps to the eye;there is (...) also a close relationship with the ‘liar’ antinomy, since … we are… confronted with a proposition which asserts its own unprovability.In the light of the fact that the existence of this connection is commonplace it is all the more surprising that very little can be learnt about its exact nature except perhaps that it is some kind of similarity or analogy. There is, however, a lot more to it than that. Indeed, as we shall try to show below, the general ideas underlying the three central theorems concerning internal limitations of formal deductive systems can be taken as different ways to resolve the Liar paradox. More precisely, it will turn out that an abstract formal variant of the Liar paradox, which can almost straightforwardly inferred from its original ordinary language version, is a possible common generalization of Gödel's incompleteness theorem, the theorem of Tarski on the undefinability of truth, and that of Church concerning the undecidability of provability. (shrink)

Boolos's proof of incompleteness is extended straightforwardly to yield simple “diagonalization-free” proofs of some classical limitative theorems of logic.

N´emeti remarked that the notion of compactness of cylindric of algebras corresponds to the notion of universality of models in logic [5]. The purpose of this paper is to formulate this correspondence in a purely algebraic setting.

The algebra of all binary relations on a given set is the most important example of a relation algebra . In this note we will examine the possible isomorphisms within some subclasses of a closely related class ; A is a relation set algebra with base U if its Boolean reduct is a field of sets with unit element 2 U, its universe A contains the identity relation on U and it is closed under the operations −1 and |, where (...) R |S = { : ∈ R, ∈ S for some z} and R−1 = { : ∈ R} for any R, S ⊆ 2 U. The class of all relation set algebras is denoted by Rs. (shrink)