3
$\begingroup$

The first part of the present question is concerned with Classical Propositional Logic (CPL). The second part involves its fragments or alternative logical systems.

There are in the literature many well-known axiom systems for CPL whose collection of axioms contains three or more distinct atomic sentences / propositional variables / primitive schemas.

  1. Are there known references in the literature for the non-existence of Hilbert-style axiomatizations for CPL that employ only two distinct atomic sentences?

  2. What is known, in general, about fragments of CPL or about non-classical logics axiomatizable with less than three atomic sentences?

$\endgroup$

1 Answer 1

5
$\begingroup$

On what concerns QUESTION 1, a colleague has in the meanwhile called my attention to the fact that its answer was sketched (in Polish) by M. Wajsberg in 1931, and later recovered in:

Gladstone, M. D. On the number of variables in the axioms. Notre Dame Journal of Formal Logic 11 (1970), 1–15.

and

Szczęch, Władysław. On one of Wajsberg's theorems. Reports on Mathematical Logic 1 (1973), 33–37.

On the one hand, according to Szczęch, Wajsberg's theorem states more precisely that $p\to(q\to (r\to p))$ is not deducible by means of substitution and modus ponens from any set of tautologies of the classical propositional calculus in which at most two propositional variables occur. On the other hand, Gladstone has apparently dedicated his PhD to this very topic, in the 60s, and in the above mentioned paper has also provided a partial answer to QUESTION 2, in showing that the system whose axioms consist of all tautologies having not more than two variables is not finitely axiomatizable. Gladstone in fact shows that, in general, a two-valued system containing a classical implication and having as theorems all classical tautologies in which at most $n$ distinct variables occur, for some $n>2$, is axiomatizable (and finitely axiomatizable if its language is generated by a finite number of connectives) iff its language does not contain $m$-place connectives, with $m>n$.

As for the second part of QUESTION 2, to the best of my knowledge, it would appear that the above mentioned general results are yet to be extended so as to cover non-classical logics such as intuitionistic logic and others. At any rate, it is worth mentioning, from an algebraic perspective, that the following paper has proved that many important equational theories (including the theory of Boolean Algebras) cannot be axiomatized by a set of identities containing at most two variables.

Diamond, A. H.; McKinsey, J. C. C. Algebras and their subalgebras. Bulletin of the American Mathematical Society 53 (1947), 959–962.

$\endgroup$
1
  • $\begingroup$ For Question 1, how many atomic sentences does C$\delta$$\delta$0$\delta$p have? I note that since it qualifies as a sole axiom for the extended propositional propositional calculus, it qualifies as sufficient for classical propositional calculus. It is also sound. $\endgroup$ Commented Aug 25, 2016 at 21:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .