12
$\begingroup$

Infinitary logic considers languages being infinite by infinite conjunctions and disjunctions.

I wonder why it not considers languages being infinite by relations and functions of infinite arity.

Relations of finite arity $n$ over a base set $A$ can be seen as unary predicates of functions $f:[n] \rightarrow A$. Nothing prohibits us to consider more general functions $f:\mathbb{N} \rightarrow A$ or even $f:\mathbb{R}^+_0 \rightarrow A$.

Is there a model theory assuming a language that allows for relations and functions of infinite and even uncountable arity?

I asked this question at MSE but did not get feedback.

$\endgroup$
9
  • $\begingroup$ I assume that not considering relations of infinite arity has to do with the fact, that in practical situations most arities > 2 are considered "many" and ignored. (See: en.wikipedia.org/wiki/Counting#Education_and_development) There are some relations of arity 3 that are taken serious - e.g. betweenness -, very few of arity 4, and I don't know one of arity 5. So why bother about arities like 2011 or even $\omega$? $\endgroup$ Feb 22, 2011 at 19:46
  • 3
    $\begingroup$ @Hans: there is another MO question about operations of higher arity. I mentioned there that a natural example is compact Hausdorff spaces, which can be viewed as sets equipped with J-ary operations for every set J corresponding to ultrafilters on J. $\endgroup$ Feb 22, 2011 at 21:18
  • 3
    $\begingroup$ @Hans: operations of arbitrary arity also naturally occur in the theory of operads and related areas of higher category theory. Arguably many of the binary operations we care about are more naturally thought of as n-ary operations for all finite n that satisfy enough compatibility relations; see, for example, Leinster's Higher operads, higher categories at arxiv.org/abs/math.CT/0305049 . $\endgroup$ Feb 22, 2011 at 21:20
  • $\begingroup$ @Qiaochu: Thank you very much for your valuable hints. Since I never heard of operads before, and got answers/comments concerning operads on two seemingly (at least to me) unrelated questions - mathoverflow.net/questions/55641/… and this one - and since you pointed me to higher category theory concerning a third question - math.stackexchange.com/questions/23120/… - I dare to ask, if YOU can see the interconnection between my three questions, which is hidden to me? $\endgroup$ Feb 22, 2011 at 21:51
  • 3
    $\begingroup$ Generalized operads and multicategories can be applied to theories of arbitrary arity just as well as to ones of finite arity: nlab.mathforge.org/nlab/show/generalized+multicategory . See also nlab.mathforge.org/nlab/show/infinitary+Lawvere+theory . $\endgroup$ Feb 23, 2011 at 5:16

5 Answers 5

9
$\begingroup$

I have several thoughts about this question.

First, to my way of thinking, there is little difference between an infinite-ary relation $R(a_0,a_1,\dots)$ on a set $X$ and a unary relation on a suitable power of that set, such as $X^\omega$ or $X^\alpha$. For example, an $\omega$-ary relation on $\{0,1\}$ is essentially the same thing as a unary relation on Cantor space $2^\omega$. In the one case, we have $R(a_0,a_1,\dots,a_n,\dots)$, and in the second case we have $R(\langle a_0,a_1,\dots,a_n,\dots\rangle)$. It is a mere stylistic difference without substantive difference. An $\omega$-ary relation on the natural numbers $\omega$ is essentially the same as a unary relation on Baire space $\omega^\omega$. A binary relation on Baire space is the same as an $(\omega+\omega)$-ary relation on $\omega$.

For these reasons, it seems to me that mathematics is filled with abundant examples of infinite-ary relations. The lexical $<$ relation on the Cantor set is essentially the same as an $(\omega+\omega)$-ary relation on the two-element set $\{0,1\}$. Binary relations on Baire space $\omega^\omega$ are essentially the same as $(\omega+\omega)$-relations on the natural numbers $\omega$.

I believe that we prefer in these cases to think of the infinite-ary relation as a unary or finite-ary relation on the higher-order space of sequences, for several reasons. First, it is easier to think of the relation as a unary relation in the higher order space of sequences, simply because we don't mind so much going to a higher-order and we are used to finite-arity relations. Secondly, the move to the higher order space allows us to be more precise about exactly which sequences are allowed to be considered. If one has an infinite-arity relation, but doesn't specify the extent of the second-order sequences that are to be considered (from which model of set theory will they be drawn?), then the ontological meaning of that relation is a little ambiguous. But when we think of the relation as a finite-ary relation on a certain space of sequences, specified by a set of sequences, then the extensional nature is more clear.

To give an example, usually one views the axiom of determinacy as concerned with games on $\omega$, so that the players construct a play of the game $a_0,a_1,a_2,\dots$, and the winning condition of a game is a unary condition on Baire space $R(\langle a_0,a_1,\dots\rangle)$. But one could just as easily view the winning condition as an $\omega$-ary relation on $\omega$, as $R(a_0,a_1,\dots)$. And this wouldn't really make any difference; it is an inessential stylistic syntactic difference.

But lastly, let me also point out that there is a literature on infinite-ary functions, undertaken for example by Addison, as in his theory of infinitary Boolean operations. I once had the pleasure of taking a seminar on the topic that he offered in Berkeley on the topic, and he considered many different Boolean operations $f:\{0,1\}^\omega\to\{0,1\}$, and investigated their nature.

$\endgroup$
5
  • $\begingroup$ I just noticed that the question itself is several years old, although all the answers are fairly recent. I think it is no matter. $\endgroup$ Feb 25, 2016 at 5:11
  • $\begingroup$ Infinitary operations on Boolean algebras sound interesting - do you know if Addison/others ever published results on the topic? (Google is not helping me in this.) $\endgroup$ Feb 25, 2016 at 5:29
  • $\begingroup$ I also have struggled to find a good reference. I remember taking a seminar from Addison about it, but unfortunately, I don't seem to have any good references now. $\endgroup$ Feb 25, 2016 at 5:36
  • 1
    $\begingroup$ @JoelDavidHamkins: I don't agree that it "wouldn't really make any difference; it is an inessential stylistic syntactic difference". If the object of investigation was only one structure at a time, then maybe it wouldn't matter. But large parts of model theory would have to be re-worked, if infinite-arity predicates were allowed. The notion of definability would be very different. $\endgroup$ Feb 25, 2016 at 13:34
  • $\begingroup$ My point is that any use of an infinite-ary relation $R(a_0,a_1,\dots)$ in a model $M$ can be seen as a unary relation $R(\langle a_0,a_1,\dots\rangle)$ in the model $M^\omega$. Thus, infinite-ary first-order becomes finite-ary second-order. Furthermore, we are already often doing this, when we quantifier over the reals, Cantor space, etc., which can be seen as infinite-ary over $\mathbb{N}$. Meanwhile, I agree with you that second-order logic has very different theorems and model theory than first-order. $\endgroup$ Feb 25, 2016 at 16:34
7
$\begingroup$

Not sure if this is a comment or an answer:

In the study of infinitary language $L_{\infty,\kappa}$ we usually assume that predicate and function symbols have finite arities. I think there are two reasons for this:

  1. Many theorems for $L_{\infty,\kappa}$ do not hold true if we allow infinite arities. For instance, the downward Lowenheim-Skolem theorem. The closure of a set of size $\kappa$ under a $\omega$-ary function maybe of size $\kappa^\omega$.

Recall that the Lowenheim-Skolem number of a logic is a fixed cardinal $\lambda$ such that any subset $A$ of a structure $M$ with $|A|=\kappa$ will be contained in a substructure of $M$ of size at most $\kappa+\lambda$. If $\lambda<\kappa$, then any $A$ must be contained in a substructure of size $|A|$. Clearly, this can not always be the case if $\kappa^\omega>\kappa$, which also hints that the set-theory starts playing a role.

  1. A formula $\phi(\vec{x})$ where $\vec{x}$ is infinite will necessitate the use of infinitely long sequences of quantifiers, $\forall \vec{x} \phi(\vec{x})$, $\exists\vec{x} \phi(\vec{x})$, or $\forall x_1\exists x_2\ldots \phi(x_1,x_2,\ldots)$. This brings us to the study of the infinitely-deep languages $M_{\infty,\kappa}$, which historically followed the study of the languages $L_{\infty,\kappa}$, trying to remedy some of the restrictions.

See for instance: Maaret Karttunen, Model theoretic results for infinitely deep languages, Proceedings of the Finnish-Polish-Soviet logic conference (Polanica Zdrój, 1981) Studia Logica 42 (1983), no. 2-3, 223--241 (1984).

As far as I know, infinitely-deep languages do not exclude the usage of predicate and function symbols with infinite arity, but I wouldn't be surprised if "nicer" results hold true under the finite arity restriction.

$\endgroup$
5
$\begingroup$

I suppose this is relevant. Let $I$ be a set and $\mathcal{U}$ an ultrafilter over $I$. If $X$ is any compact Hausdorff space then any function $x: I \to X$ converges along $\mathcal{U}$ to exactly one point. This allows us to introduce infinitary operations $f_{I,\mathcal{U}}: X^I \to X$ defined by $$f_{I,\mathcal{U}}(x) = \lim_\mathcal{U} x.$$ It's kind of nice because a subset is closed under these operations iff it is topologically closed, a map from $X$ to $Y$ is an algebraic homomorphism iff it is continuous, and algebraic products equal topological products. In fact the class of compact Hausdorff spaces is a variety in the sense of universal algebra. The "free algebra" construction yields the Stone-Cech compactification, etc. This is a little paper I wrote on the subject when I was a graduate student. It doesn't really seem to go anywhere but I thought it was cute.

$\endgroup$
4
$\begingroup$

Model theory for languages with infinitary predicates has existed for decades, as is well-known to the categorical logic community. Makkai-Paré have written a whole book about it, "Accessible categories: The foundations of categorical model theory" (see also the book by Adamek and Rosicky: "Locally presentable and accessible categories"). Accessible categories are examples of categories of models of infinitary theories $\mathcal{L}_{\kappa, \kappa}$, where infinitary predicates are in particular considered.

Karp ("Languages with expressions of infinite length", 1964) and Dickmann ("Larger infinitary languages", 1975) have also written books about languages with infinitary predicates that contain model-theoretic results (like the completeness theorem or the Löwenheim-Skolem theorem or applications of the back and forth method and $\mathcal{L}_{\infty, \kappa}$-elementary equivalence).

Jouko Väänänen "Models and games" has some chapters on infinite quantifier logics (which contain infinitary predicates) and gives an overview of several results in the model theory of these. Game quantification is also mentioned, and it can involve infinitary predicates, like the generalized Vaught sentences which are treated e.g. in Oikkonen "How to obtain interpolation for $\mathcal{L}_{\kappa^+, \kappa}$" (1988), in which he circumvents the known obstruction by which interpolation fails for infinite quantifier languages by allowing infinitely deep formulas.

Recently I have been working on infinite quantifier languages (with infinitary predicates) and their model theory in my papers with several completeness theorems generalizing those of Karp, as well as generalizations of Beth's definability theorem and of the omitting types theorem for these languages, this latter assuming in addition that the category of models has directed colimits (but where predicates may well be infinitary).

$\endgroup$
3
$\begingroup$

Today I ran into a recent paper that reminded me of this question, so please pardon the rather belated bump. You ask:

Is there a model theory assuming a language that allows for relations and functions of infinite and even uncountable arity?

I think that there is a hidden sub-question here: what precisely constitutes "model theory" as such? Specifically, in my opinion the relevant issue here is the relationship between model theory and universal algebra.

In the classical (= finite-arity) setting, one rather naïve take is the following: universal algebra lives at-or-around the level of equational logic and its mild extensions, whereas model theory lives at-or-around first-order logic or even higher. For me, this is a bit ad hoc, though, in the sense that it situates universal algebra reasonably well, but leaves model theory somewhat confused. Equational logic makes sense to me as something interesting "right at the outset," but why is first-order logic per se the right place for model theory to live?

To save the day, I would turn to the following (pretty ahistorical) narrative: model theory is what you get when, starting with equational logic, you keep adding expressive power until you lose too much tameness. I think this actually describes a fairly coherent process, even if only after the fact. Specifically, there is a fairly tight connection between the tameness properties of FOL — compactness and downward Löwenheim–Skolem in particular — and equational logic: dLS for FOL can be proved by reduction to dLS for equational logic (via Skolem functions), while conversely proving the right compactness property for equational logic ("strong compactness" — remember, every equational theory is trivially satisfiable!) essentially requires us to prove compactness for full FOL. Especially in light of Lindstrom's admittedly-much-later theorem it "makes sense" (to me at least) to stop at FOL: that's the point where we see the tamenesses of equational logic "stretched" to their most expressive natural variants.

That, then, is the narrative I want to pursue for "infinite-arity model theory" (whatever that should be), and that tells us where to start:

What is infinite-arity equational logic like?

As far as I know, the earliest substantial paper observing that infinite-arity equational logic is really quite wild compared to its finite-arity cousin is Slominski, The theory of abstract algebras with infinite arity operations. I'm not sure that that's a good starting point, however; I would tentatively recommend starting with the most recent paper I'm aware of, namely Reggio's Beth definability and the Stone–Weierstrass theorem. Continuing the theme started (to the best of my knowledge) by Slominski, Reggio shows that the equational logic associated to a certain infinite-arity "variety" $\Delta$ (i) has the Beth definability property, which (ii) leads to a proof of Stone–Weierstrass, and (iii) admits a sound-and-complete deductive system. These are results that "feel" close to model theory, in my opinion; they, or more accurately their proofs, indicate that already infinite-arity equational logic has lots of surprising structure and complexity. This is especially true when coupled with the (folklore?) observations that infinite-arity FOL lacks the compactness and dLS properties.

So, to wrap things up:

To the best of my knowledge, "infinite-arity model theory" right now is more-or-less limited to infinite-arity equational logic, and so doesn't really have a character separate from that of infinite-arity universal algebra. The most natural way to get past this, in my opinion, would be to identify some appropriate tameness properties that persist well beyond equational logic even in the infinite-arity setting; however, I don't know of any yet.


Somewhat separately here's an uncritical list of hopefully-relevant sources (including those mentioned above for ease-of-searching). Not all of the following hew in any way to the narrative in the first part of this answer (and I've shamelessly stolen a couple from earlier answers/comments); I just want to collect a bunch of sources in one place. To encourage folks to add to this list themselves as well, I've made this whole answer CW. My one request is to please keep the list chronological-by-publication since I think that helps tell a useful story.

$\endgroup$
4
  • $\begingroup$ Infinite-arity model theory is not limited to equational logic, already Karp in 1964 proved some completeness theorems for $\mathcal{L}_{\kappa, \kappa}$ when $\kappa$ is inaccessible. Surely the completeness theorem counts as model-theoretic. There is also the work of Makkai-Paré and Rosicky on accessible categories which is the model-theoretic aspect of infinitary logic with infinite arities. $\endgroup$
    – godelian
    Nov 28, 2022 at 9:52
  • 1
    $\begingroup$ @godelian I don't believe that Karp's results treat infinite-arity languages; my recollection is that they are restricted to finite-arity (but infinitary) logics. I'm not familiar with Makkai-Pare or Rosicky, though. $\endgroup$ Nov 28, 2022 at 10:12
  • $\begingroup$ She does treat infinite-arity languages (I have the book). I'm writing a separate answer. $\endgroup$
    – godelian
    Nov 28, 2022 at 10:16
  • $\begingroup$ @godelian Oh, awesome! I didn't know that. I look forward to your answer! $\endgroup$ Nov 28, 2022 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.