Combinatory interpolation theorems

✍ Scribed by G. McNulty; W. Taylor

• Publisher: Elsevier Science
• Year: 1975
• Tongue: English
• Weight: 983 KB
• Volume: 12
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(75)90034-5

✦ Synopsis

Receivti I7 April t 974

A cnif~~n pru(of is given far various (known) theorems asserting the convexity of a set S of tntegers, e.g., S the set of cardinalities of finite irredundant sets of axioms fgr an quational theory (Tarski), or S the set of cardinalities of complete homomorphic images of a graph (Iiarary, Hzdrtniemi and Prins). The same proof also yields some convexity results for coverings and packings.

In this ~paper we prove Lemma 1 cm the convexity of the range of a function, and apply it to obtain theorems in the domain of' algebra, logic and combinatorics.

any of the theorems are publishled, although usually with a. rather di nt proof. Our principal inspiration was the statement and proof of Tar-ski's theorem which says, in part, that if (a1 9 . . ..Q 1 and CPI y l -,Pm S are irredundant sets of axioms for the (same equa.tional theory T, then T also hzs an irredundant set of axioms1 . . . . 7n ) for every n with k < n 6;; m {see [ 5 J ). As well as corn e take c3 to denoie the 1