Infinitary languages

Abstract
We begin with the following quotation from Karp [1964]: My interest in infinitary logic dates back to a February day in 1956 when I remarked to my thesis supervisor, Professor Leon Henkin, that a particularly vexing problem would be so simple if only I could write a formula which would say x = 0 or x = 1 or x = 2 etc. To my surprise, he replied, "Well, go ahead." Traditionally, expressions in formal systems have been regarded as signifying finite inscriptions which are—at least in principle—capable of actually being written out in primitive notation. However, the fact that (first-order) formulas may be identified with natural numbers (via "Gödel numbering") and hence with finite sets makes it no longer necessary to regard formulas as inscriptions, and suggests the possibility of fashioning "languages" some of whose formulas— such as that in the above quotation—would be naturally identified as infinite sets. A "language" of this kind is called an infinitary language: in this article we discuss those infinitary languages which can be obtained in a straightforward manner from first-order languages by allowing conjunctions, disjunctions and, possibly, quantifier sequences, to be of infinite length. In the course of the discussion we shall see that, while the expressive power of such languages far exceeds that of their finitary (first-order) counterparts, very few of them possess the "attractive" features (e.g., compactness and completeness) of the latter. Accordingly, the infinitary languages that do in fact possess these features merit special attention. In §1 we lay down the basic syntax and semantics of infinitary languages and demonstrate their expressive power by means of examples. §2 is devoted to those infinitary languages which permit only finite quantifier sequences: these languages turn out to be relatively well-behaved. In §3 we discuss the compactness problem for infinitary languages and its..
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
 
Download options
PhilPapers Archive


Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 11,449
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

No references found.

Citations of this work BETA

No citations found.

Similar books and articles
Analytics

Monthly downloads

Sorry, there are not enough data points to plot this chart.

Added to index

2009-01-28

Total downloads

0

Recent downloads (6 months)

0

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Start a new thread
Order:
There  are no threads in this forum
Nothing in this forum yet.