Simplest Merge: Set Theory versus Graph Theory

In this blog post, I give a set-theoretic formalization of simplest Merge and a graph-theoretic formalization and then compare the two. The conclusion is that the graph-theoretic definition is more complicated, and involves a violation of the Inclusiveness Condition.

Set Theory

1. Merge (set-theoretic)

For any two distinct syntactic objects SO1 and SO2, Merge(SO1, SO2) = {SO1, SO2}.

2. Syntactic Objects

The definition of Merge is usually given in the context of the definition of syntactic objects:

For any lexical item LI, LI is a syntactic object. If SO1 and SO2 are distinct syntactic objects, Merge(SO1, SO2) = {SO1, SO2} is a syntactic object. Nothing else is a syntactic object.

3. Graph Theory

A graph is defined as an ordered pair G = <V, E>, where V is a set of vertices (nodes), and E is a set of edges (where each edge is an unordered pair of elements from V). 

4. Graph Example

For example, if you have three nodes connected in a triangle, you have the following graph:

V = {n1, n2, n3}

E = {{n1, n2}, {n2, n3}, {n3, n1}}

5. Mother Node

In order to define Merge in graph theory, the Merge operation has to create a mother node dominating two root nodes. So the definition of syntactic object (a graph) has to include a root node:

SO = <V, E, r>, where r is in V (r is the root node in the graph).

6. Lexical Item as a Graph

Before defining Merge, we need to define what the graph for a lexical item is.

For LI a lexical item, SO = <V, E, r>

where: V = {LI}, E = ∅, r = LI

7. Merge (graph-theoretic)

Given this background, Merge can be defined in the following way:

Merge(SO1, SO2) = <V1 ∪ V2 U {m}, E1 ∪ E2 ∪ {{m, r1}, {m, r2}}, m>

where: V1 and V2 are disjoint, SO1 = <V1, E1, r1>, SO2 = <V2, E2, r2>,

m ∉ (V1 ∪ V2 ) (ensuring m is a distinct node from the existing nodes in the tree).

8. Complexity

The complexity of definition 7 is due in large part to having to create new mother nodes and to make sure that they are distinct from the existing nodes. No such node creation is needed for the set theoretic definitions in 1 and 2.

9. Inclusiveness

The definition in 7 clearly violates inclusiveness, which “…bars introduction of new elements (features) in the course of computation: indices, traces, syntactic categories or bar levels, and so on.” (Chomsky 2001:2–3)

In the definition in 7, a new mother node is introduced which is not a lexical item or any kind of feature already present in the derivation.

There exist slightly different alternative formalizations of Merge in the graph-theoretic framework (not shown here). However, they all run into the same fundamental problem. Edges in graph theory can only connect existing vertices. So you cannot merge together two syntactic objects, without first creating the mother node by expanding V. Any operation that adds a new vertex to V during a derivation will necessarily violate inclusiveness.

10. Multi-dominance

Set-theoretic representations given by 1 and 2 can easily be represented as graphs, and the concept of multi-dominance is easily coded in both the set-theoretic representation and the graph-theoretic representation. Multi-dominance in set theory is represented when a single SO is a member of more than one parent set (e.g., X∈Y and X∈Z).

11. Lexical Items Revisited

The representation of lexical items in 6 raises the issue of sentences where the same lexical item appears twice, such as “John saw John.” (“John” appears twice) or “The cat chased the dog.” (“the” appears twice). The question is whether those two lexical items should be distinguished or not. If they are not distinguished, then “John saw John.” will involve multi-dominance. That is, the node “John” will be in two different edges. 

There are at least two ways out of this dilemma. First, one could add diacritics to lexical items so that every lexical item is unique. In other words, there would be John-1 and John-2, and these would count as separate instances of the same lexical item (see Collins and Stabler 2016 for a formalization of such diacritics).

The second way out would be to treat lexical items as labels on a node in a graph. That is, it would be necessary to define a labeling function that maps nodes to lexical items (Label: V -> Lex). Since all the nodes in the graph are distinct, the two instances of “John” in “John saw John.” would label distinct nodes.

I note here that both of these solutions involve further violations of the Inclusiveness Condition (indices on lexical items or graph nodes) similar to the ones I point out in section 9 above.