Independently generated languages

1 Compositionality versus Independence

How do humans understand the meaning of a complex sentence they have never heard before? The answer is that there is an algorithm that allows to compute the meaning of the complex expression from its parts. While this much seems uncontroversial, semanticists have actually argued that natural languages possess a stronger property, that of compositionality. A language is said to be compositional if the meaning of a complex expression is a function of the meaning of its parts given the mode of composition; thus, a language is compositional if the algorithm computing the meaning can do so without knowing the expressions that carry these meanings. It is this latter property that has been made into a litmus test for formal semantic theories. A theory that provides a compositional account of meaning is preferred over one that does not. But how much of a constraint is compositionality on a language? In other words, what empirical significance does it have to say that a language is compositional? Do noncompositional languages at all exist?

While the introduction of the subject is often credited to Montague, it is perhaps the work that has been done in the wake of Montague that had put compositionality firmly on the agenda of formal semantic theorising, see Janssen (1997) for an account by one of the protagonists. The survey books Barker and Jacobson (2007) and Hinzen et al. (2012) document the persistent interest in this notion. From a mathematical point of view, the question is how much of an empirical content this notion has. Janssen has actually shown that any language is compositional, provided no constraints on syntactic operations are being made (see Janssen (1997)). Though his notion of language is slightly nonstandard, the result holds also for languages in the Saussurean sense, ie relations between expressions and meanings.

However, as Kracht (2011) has pointed out, the dual property, namely that the form of an expression is independent of the meaning of its parts, is actually a well known hypothesis of generative grammar: It is called the autonomy of syntax. It is curious that to our knowlede no definition of this notion with the same explicitness has ever been given in print. In retrospect it seems that a grammar that satisfies both of them simultaneously is really what linguistics have been after, and not compositionality alone. We call this property independence. It has a rather simple mathematical formulation, so the investigation may also be of interest in combinatorial theory.

Moreover, it turns out that the property of independence is actually rather tricky. It is still unclear whether there exists a countable language that is not independently generated. Though we believe that such a language exists, we have not been able to find one. The results here exhibit some positive results (specifying languages that are independently generated) and reduces the complexity of the original problem somewhat.

We thank our reviewer for suggesting ways to improve this paper. Also, Marcus Kracht wishes to thank András Kornai for his friendship and the endless discussions on mathematics, language and life.

2 Autonomy and Compositionality

A language is an arbitrary subset L of E × M, where E and M are given sets of expressions and meanings, respectively. An independent grammar for L is a finite set F ⊆ L and a finite set P of pairs of functions (f_i,g_i), i < m, such that for i < m there is an n_i (the arity of the functions) such that f_i : E^n_iE and g_i : M^n_iM are both partial functions and L is exactly the set that can be generated from F using P. The action of such a pair is defined as usual: (f,g)((e₀,m₀),, (e_ni-1,m_ni-1)) is defined if and only if both f (e₀,,e_ni-1) and g(m₀,,e_ni-1) are defined and in that case

There is an obvious mathematical generalisation. Let R ⊆ ω^d be a relation. Say that R is independently generated if there is a finite set of partial functions f_i^k, k < d, of arity n_i (only dependending on i) such that the product functions (f_i⁰,f_i¹,,f_i^d-1) (of arity n_i) generate R from a finite subset. The limiting case of d = 1 is trivial. Any countable subset of ω can be generated; it suffices to pick one constant and a single unary function. Thus, the case d = 2 is the first really interesting case. Notice also that if there is a relation of arity d that is not independently generated, then there is an example in any higher arity.

Notation. If f is a function and S a set, put f [S] := {f (x) : x ∈ S}. Given L ⊆ ω² we write L_i for the “column” {j : (i,j) ∈ L}. It follows that L = ⋃ _i∈ω{i}× L_i. Dually we write ^jL := {i ∈ ω : (i,j) ∈ L}.

The notion of independence is restrictive. Let L ⊆ E ×M be countably infinite. Then there exists a finite subset F and a finite number of partial functions on E × M (rather than independent functions on E and M) generating L. Indeed, one constant plus a single unary function is enough. Simply enumerate L = {(e_i,m_i) : i ∈ ω}, put F := {(e₀,m₀)} and let f : E × M → E × M be defined by

However, the question was whether it is possible to define the functions in such a way that the actions on E and on M are independent of each other. In the linguistic literature, two weaker notions have been discussed. The most important one is compositionality. The first result will be that all countable languages have a compositional grammar.

Since the set of generating functions is finite, L is at most countably infinite. Thus we can restrict E and M to some countably infinite subset; without loss of generality we can assume them to be the set of natural numbers ω = {0, 1, 2, 3,}. (Formally, there is nothing that distinguishes members of E from members of M.) Thus, from now on E = M = ω. Let p₁ : ω² → ω : (i,j)i and p₂ : ω² → ω : (i,j)j.

Definition 1 Let f be a partial n-ary function on ω². We say that f is independent in the first component if for all pairs (i₀,j₀), , (i_n-1,j_n-1) and all pairs (i₀,k₀), , (i_n-1,k_n-1): f ((i₀,j₀),, (i_n-1,j_n-1)) is defined if and only if f ((i₀,k₀),, (i_n-1,k_n-1)) is defined, and if any of them is defined, then the first projection of the values are identical, ie

Dually the notion of independence in the second component is defined.

Proof. Obviously, we need to prove only the first claim. The second follows analogously. (Or instead, apply the method to L^⌣ := {(j,i) : (i,j) ∈ L} and then “switch” the solution.) Now, consider first the language

So M has the form M = {(i,n_i) : i ∈ H} for some H ⊆ ω. Let α be the least member of H, ie the least number such that L_α ⇔ ∅. Introduce a constant for (α,n_α). Next, let k(i,j) be defined as follows. In case j = n_i and there is a q > i such that L_q ⇔ ∅, let k(i,j) := (p,n_p), where p is the smallest number > i such that L_p is nonempty. If no such number exists, or if j ⇔ n_i, put k(i,j) := (i,j). Now put

Next, define a function ν as follows. Given i and j, ν(i,j) := j if either j ℜ L_i or j is the largest member of L_i. Otherwise, ν(i,j) yields the least j′ such that j′ ∈ L_i and j′ > j. Now put

Notice that we have been able to define total functions. Consider a system F of generating (partial) functions on E × M. This system is called compositional if each member f ∈ F is independent in the second component; it is called autonomous if each member f ∈ F is independent in its first component. We can rephrase the previous theorem as follows. A language is compositional (autonomous) if it has a finite compositional (autonomous) set of generating functions.

Here is a surprising consequence.

Proof. Consider the second case, ie assume that L is one-to-many (the other case being dual). Let f : M → E be such that f (j) is the unique i such that (i,j) ∈ L. Define the grammar as in the proof of Theorem 2. Now put

Proof. We generate L ∩ A × B by means of independent partial functions defined on A × B, as shown in Corollary 4. L contains a partial infinite bijection {(a_i,b_i) : i < ω}. Let L-A×B = {(e_i,m_i) : i < ω}. Now add a new unary partial function f : A×B → (E-A) × (M -B) with

The notion of independence for languages is not the conjunction of autonomy and compositionality (if it were, all languages would be independent, by Corollary 3); indeed, it is much stronger than that. For it says that the language has an independent grammar, that is, a grammar where every function is independent in both components. This is what we are going to study now.

3 Basic Results

In using partial functions, here is a trick that will be used on several occasions. Denote by [F]_P the closure of F under P. Let A be the disjoint union of B and C. Let P be a set of partial functions on B, and Q a set of partial function on C. Take B₀ ⊆ B and C₀ ⊆ C. Then [B₀ ∪ C₀]_P∪Q = [B₀]_P ∪ [C₀]_Q. To see that notice that functions from P are undefined on every tuple containing elements from C, and functions from Q are undefined on every tuple containing an element from B. Therefore, functions from P cannot act on outputs of functions from Q, and vice versa.

Indeed, simply take the (disjoint) union of the constants and functions. The following two claims are obvious.

There is a special corollary of this theorem that is worth stating separately. Consider the case where L_i = ∅ for certain i. Denote by U := {i : L_i ⇔ ∅}. If U is infinite there is a bijection ν : U → ω. Consider the language L^∙ := (ν, id_M)[L]. We have (L^∙)_i = L_ν(i) ⇔ ∅ for all i ∈ ω.

If U is finite, L is independently generated anyway, by the next theorem.

Proof. The first claim is easy. Just introduce a constant for every element of L. The second claim follows immediately. To show the third claim introduce a constant for (0, 0), and two unary functions: one sending (i,j) to (i + 1,j), and one sending (i,j) to (i,j + 1). The fourth claim is proved thus. For each j < n take a constant for (0,j). Finally, add a single unary function sending (i,j) to (i + 1,j). For the last claim, let L = ω × ω -{(i_k,j_k) : k < n}. Put E₀ := {i_k : k < n}, E₁ := ω - E₀; M₀ := {j_k : j < n}, M₁ := ω - M₀. Now L ∩ E₀ × M₀ is finite; L ∩ E₀ × M₁ = E₀ × M₁, L ∩ E₁ × M₀ = E₁ × M₀, and L ∩ E₁ × M₁ = E₁ × M₁. The first is independently generated since it is finite. The others are independently generated because they are a simple product of at most countable sets. Now use Lemma  6. □

Say that L is essentially bounded if L ⊆ n × ω or L ⊆ ω × n.

Proof. >From Lemma 10 by repeated application of Lemma 6. □

Next we are going to reduce of the problem even further. Let H ⊆ ω such that for every i ∈ H there is a j ℜ H and L_j = L_i. Then put

Proof. Suppose that L^-H is independently generated. For j ℜ H put

Thus we can restrict our search for nonindependent languages to those subsets of ω² where all columns are different and all rows are different.

4 Main Theorems

We are going to investigate three conditions under which languages are independently generated. The second and third conditions both generalise the first, in slightly different directions. Examples will show that the generalisations are proper.

Notice that by definition, A_i ⊈ A_j for i ⇔ j. For if A_i ⊆ A_j we have A_i ⊆ A_j ⊆ L_j, from which by definition i = j.

Proof. Let {A_i : i ∈ ω} be a discriminating family for L. Let A_i be a sequence of length n that enumerates A_i, possibly repeating an element to reach length n. (Eg if n = 4 and A₂ = {3, 6, 7} then A₂ = ⟨3, 6, 7, 7⟩ is a possible choice.) For each member of {(0,i) : i ∈ A₀} we introduce a constant. Now we define the following n-ary functions f^k, k < n. Let h be the kth member of A_i+1.

(1)

Clearly this function is independent: on the first component it gives i + 1 if all arguments are identical to i and is undefined otherwise. On the second component it gives h if the arguments are exactly given as in A_i, and is undefined else. The partiality seems to be essential here.

Now define a single n + 1-ary function g with the following action. For each i we assume L_i - A_i to be enumerated as {k_jⁱ : j < κ_i} where κ_i < ω + 1 (so κ_i can be finite or = ω).

(2)

So defined g is independent. On the first coordinate the output is i if all inputs equal i; and is undefined elsewhere. On the second coordinate it yields the next element in the enumeration if there is one (and repeats the element if it is the last in the enumeration), provided the first n arguments equal A_i; and is undefined elsewhere.

It now remains to be shown that this set of functions generates exactly L. There are two parts: (i) the functions generate all of L; (ii) L is closed under the functions.

To prove (i), we shall first show that all {i}× A_i are generated using the f^k and the constants. Recall that all members of {0}× A₀ are values of some constant. Now by induction assume that {i}× A_i is generated. Thus all pairs (i,j_p) exist, p < n, where j_p ∈ A_i. Then, using the functions f^k, we can generate (i + 1,h), where h is the kth member of A_i+1. Since all elements of A_i+1 appear at least once in A_i+1, all of {i + 1}× A_i+1 is thus generated. Next we show that for every i, {i}× L_i is generated from {i}× A_i using the function g. To that end, recall that L_i - A_i is enumerated as k₀ⁱ, k₁ⁱ and so on for indices in κ_i. If κ_i = 0, nothing needs to be done. If κ_i > 0, we get (i,k₀ⁱ) as the value of g((i,j₀), (i,j₁),, (i,j_n-1), (i,j_n-1)), and (i,k_p+1ⁱ) as the value of g((i,j₀), (i,j₁),, (i,j_n-1), (i,k_pⁱ)). By induction, all values are generated.

Finally, we need to show that L is closed under the functions. Consider

Proof. By Lemma 12 we can reduce this to the case where for i ⇔ j L_i ⇔ L_j. Define I(j) := {i : |L_i| = j} and L^j := ∪_i∈I(j)L_i. By Lemma 6, we need to show only that each of the L^j is independently generated. To this end, it is enough to show that {L_i^j : i ∈ I(j)} is a j-discriminating family. This is easy to verify. □

As an application, consider the language L = {(i,i), (i,i²) : i ∈ ω}. Here we can simply take A_i := L_i. Indeed, this is a 2-discriminating family. For |A_i| ≤ 2, the sets are nonempty, pairwise distinct ({i,i²} = {j,j²} iff i = j), and, finally, if {i,i²} ⊆ L_j then j = i; for if {i,i²} = {j,j²} then either the sets contain both two members, and then since i < i², j < j² we have i = j; or they contain one member and then have the form {i} = {j}, from which again i = j. So, by the previous result the language is independently generated.

A more complex example, to which this result cannot be applied, though, is {(i,i^k) : i,k ∈ ω}. It is a consequence of the next theorem that this language is independently generated.

In particular, if A_i ⊆ A_j then we must have L_j ⊆ L_i. Clearly, all n-discriminable languages are also weakly n-discriminable, but the converse does not hold, as the example just given shows. For if L is n-discriminable, we must have L_i ⊈ L_j for all i ⇔ j. (For if i ⇔ j and L_i ⊆ L_j, then since A_i ⊆ L_i we also have A_i ⊆ L_j, which is excluded.) But the language {(i,i^k) : i,k ∈ ω} fails this: we have L₂ ⊆ L₄. On the other hand, the family defined by A_i := {i,i²} is a weakly discriminating family. For if A_i ⊆ L_j then i = j^p for some p, whence L_i = {i^k : k ∈ ω} ⊆ {j^p : p ∈ ω}. The next theorem establishes that this language is independently generated.

Proof. Let M := {i : for no j < i: A_j = A_i}. Furthermore, let B(i) = {j : A_i = A_j}. Thus, M consists of all minimal members of the sets B(i). Now let m and n be unary partial functions with the following action. m(j) is undefined if j is maximal in M, and otherwise it is m(j) := min{k : k ∈ M,j < k}. n(j) is undefined if j is maximal in B(j), and n(j) := min{k : k ∈ B(j),k > j} otherwise.

We need three sets of functions in addition to constants for the members of {0}× A₀. The first contains the functions f^k, k < n. Define the sequences A_i as above, with the exception that we require A_i = A_j if B(i) = B(j) (that is, if A_i = A_j).

(3)

The second set consists of the h^k, k < n.

(4)

Finally, we define the function g as above:

(5)

These functions are independent.

Again, we need to show that (i) L is generated from the functions, and (ii) L is closed under these functions. As for (i), we note that by definition, we can generate all A_i where i ∈ M from {0}× A₀. Next, we can generate the {j}× A_j for all j ∈ B(j) just by applying the h^k, since we have generated its minimal members. Third, by using g we generate the columns L_i.

Now we show that L is also closed under the functions. Consider

Finally, we need to show that L is closed under g. Consider

Every n-discriminable language is boundedly discriminable; just take M := ω. The sets B(i) each have only one member in this case, so n′ := 1.

Actually, it follows that for each i,j ∈ M, i ⇔ j, A_i ⇔ A_j. For if i,j ∈ M and i ⇔ j, the last clause implies j ℜ B(i), that is, A_j ⊈ L_j, so that A_j ⇔ A_i, since A_i ⊆ L_i.

Notice that allowing M to be finite would not gain anything, as then the set of indices would be finite, bounded by some multiple of |M|. So the only remaining interesting case is where M is infinite. Moreover, we could assume n = n′ to simplify the definition.

Proof. Without loss of generality we may assume that all the i ∈ M are minimal in B(i); in particular, the least element of B(0) is 0 ∈ M. If i ℜ M let j < i be the least element of B(i). Then j ∈ M and we put A_j := A_i.

First we introduce constants for {0}×A₀. Next we introduce functions f^k and h^k, k < n, as in the previous proof. Finally, for k < n′, let z^k be an n + 1-ary function, defined similar to g above. Let P(i,k) be the statement: i is the kth number in B(i). As before, order the elements of L_i - A_i for each i ∈ ω, and align the elements of A_i in a sequence k_jⁱ of length n.

(6)

It remains that to show that (i) the functions generate L, (ii) L is closed under these functions. (i) is reasonably clear. We generate A_i, i ∈ M, using the functions f^k, and then all the A_i using the g^k as in the previous proof. Finally, the z^k allow to generate all of L_i for P(i,k). Since for each number i there is a k < n′ such that P(i,k), we generate L_i from A_i using z^k essentially as we used g. Now on to (ii). Closure under f^k. Consider

5 Progressive Functions

The method has so far been to enumerate L by going through the L_i in increasing order. The interest in this method stems from using grammars to generate languages. We think of a grammar as producing complex expressions from less complex expressions. In that sense, a formation step produces a strictly more complex expression. Consider now an ordering of the E of expressions in increasing complexity. Extend this to a linear order, and number the expressions with natural numbers. We expect now that the meaning of expression j is produced from some of the expressions 0, 1,j - 1. This way of generating expressions is called progressive.

We extend this now to functions on ω² as follows. If f is an independent function on ω² then it has the form (f₁( ),f₂()). We say that f is (strictly, weakly) progressive if f₁ is.

The functions in the previous proofs have generally been weakly progressive. The following theorem shows why we cannot strengthen this to strongly progressive functions.

Proof. Suppose that F is a finite set of strictly progressive independent partial functions. Let γ be the cardinality of F, and ζ the maximal arity of these functions. We may wlog assume that γ = ζ. Then by progressivity, a member from L_i is obtained by applying a function to the members of ⋃ _j<iL_j. If their number is bounded by k_i, then there are at most ζk_i^ζ elements. Thus, choose the following sequence of numbers.

6 Conclusion

We have shown that all countable languages are compositional and autonomous. Moreover, some results have been obtained concerning languages that are independently generated. However, it is open whether all countable languages are independently generated. It is also unclear whether or not allowing partial functions rather than total functions makes a difference.

The conjecture is that there exist nonindependent countable languages. However, no example has been found.

References