MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 get no feedback.

share|cite|improve this question
    
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$? – Hans Stricker Feb 22 '11 at 19:46
2  
@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. – Qiaochu Yuan Feb 22 '11 at 21:18
2  
@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 . – Qiaochu Yuan Feb 22 '11 at 21:20
    
@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? – Hans Stricker Feb 22 '11 at 21:51
2  
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 . – Mike Shulman Feb 23 '11 at 5:16

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.

share|cite|improve this answer
    
I just noticed that the question itself is several years old, although all the answers are fairly recent. I think it is no matter. – Joel David Hamkins Feb 25 at 5:11
    
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.) – Noah Schweber Feb 25 at 5:29
    
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. – Joel David Hamkins Feb 25 at 5:36
    
@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. – Ioannis Souldatos Feb 25 at 13:34
    
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. – Joel David Hamkins Feb 25 at 16:34

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.

2) 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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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