An undecidable problem in the algebra of truth-tables
Jan Kalicki · Journal of Symbolic Logic · 1954
In a previous paper I have described a decision method for testing whether or not two arbitrary finite truth-tables are “equal”, i.e., determine the same set of tautologies. The same problem for the case of infinite truth-tables remained open. In the present note we shall show that the answer to the problem in the case of infinite truth-tables is negative; in fact we shall prove that there exists neither a decision method for testing the equality of arbitrary truth-tables, nor even one for testing the equality of what we call “recursive” truth-tables. The terminology of Kalicki [3] will be used; for brevity's sake the discussion involving the notions of recursiveness and recursive enumerability uses the informal terminology and mode of argumentation employed by Post in [9].