We develop an abstract proof calculus for logics whose sentences are ‘Horn sentences’ of the form: $(\forall X)H \Rightarrow c$ and prove an institutional generalization of Birkhoff completeness theorem. This result is then applied to the particular cases of Horn clauses logic, the ‘Horn fragment’ of preorder algebras, order-sorted algebras and partial algebras and their infinitary variants.

ḥeleḳ rishon. Sheʼelot u-teshuvot be-ʻinyanim shonim mi-toratenu ha-ḳedoshah shebi-khetav ṿeshe-be-ʻal peh -- ḥeleḳ sheni. Leḳet mikhtavim u-maʼamarim le-ḥizuḳ ṿe-hitʻorerut ba-ʻavodat ha-Shem yitbarakh -- ḥeleḳ shelishi. Leḳet mikhtavim me-a.m. ṿe-r. ha-Rav Ḥayim Shaʼul z. l.l. h.h. Grainiman baʻal ha-ḥidushim u-veʼurim".

Relations between some theories of semigroups (also known as theories of strings or theories of concatenation) and arithmetic are surveyed. In particular Robinson's arithmetic Q is shown to be mutually interpretable with TC, a weak theory of concatenation introduced by Grzegorczyk. Furthermore, TC is shown to be interpretable in the theory F studied by Tarski and Szmielewa, thus confirming their claim that F is essentially undecidable.

Theoria, Volume 87, Issue 5, Page 1322-1341, October 2021.