Mathematics | A Singular Contiguity

Multiset operations as binary operations (part 1)

June 9, 2008

Review: Associativity, commutativity, and idempotence

A binary operation $\cdot$ on a set $X$ is a function $\cdot: X\times X \to X$ . It is usually written using an infix notation $x\cdot y$ rather than a functional notation such as $\cdot\left(x, y\right)$ .

The operation $\cdot$ is associative if and only if $a\cdot\left(b\cdot c\right) = \left(a\cdot b\right)\cdot c$ for all $a,b,c\in X$ . It is commutative if and only if $a\cdot b = b\cdot a$ for all $a,b\in X$ . It is idempotent if and only if $a\cdot a = a$ for all $a\in X$ .

We’ve defined four operations on families of multisets $\left\{\mathcal{M}_i\right\}_{i\in I}$ where $\mathcal{M}_i \in \mathbf{MSet}_X$ for all $i\in I$ : sums, products, intersections, and unions. As I’ve already commented in a couple of places, we can restrict our attention to families where $\left|I\right| = 2$ . This provides us with four binary operations on $\mathbf{MSet}_X$ . Today’s post collects together the properties of these binary operations.

Proposition 1: The operations $\uplus$ , $\:\cdot\!\!\!\!\cup$ , $\cap$ , and $\cup$ on $\mathbf{MSet}_X$ are all associative and commutative.

Proof:

Let $\mathcal{M}_1, \mathcal{M}_2, \mathcal{M}_3 \in \mathbf{MSet}_X$ . The first four parts follow directly from the associativity and commutativity of $+$ and $\cdot$ as binary operations on $\mathbf{Card}$ .

Associativity of $\uplus$ .

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \uplus \left(\mathcal{M}_2 \uplus \mathcal{M}_3\right) & \left(X, f_1 + \left(f_2 + f_3\right)\right) \\ & \left(X, \left(f_1 + f_2\right) + f_3\right) \\ & \left(\mathcal{M}_1 \uplus \mathcal{M}_2\right) \uplus \mathcal{M}_3\end{array}$

Commutativity of $\uplus$ .

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \uplus \mathcal{M}_2& \left(X, f_1 + f_2\right) \\ & \left(X, f_2 + f_1\right) \\ & \mathcal{M}_2 \uplus \mathcal{M}_1\end{array}$

Associativity of $\:\cdot\!\!\!\!\cup$ .

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \:\cdot\!\!\!\!\cup\: \left(\mathcal{M}_2 \:\cdot\!\!\!\!\cup\: \mathcal{M}_3\right) & \left(X, f_1 \cdot \left(f_2 \cdot f_3\right)\right) \\ & \left(X, \left(f_1 \cdot f_2\right) \cdot f_3\right) \\ & \left(\mathcal{M}_1 \:\cdot\!\!\!\!\cup\: \mathcal{M}_2\right) \:\cdot\!\!\!\!\cup\: \mathcal{M}_3\end{array}$

Commutativity of $\:\cdot\!\!\!\!\cup$ .

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \:\cdot\!\!\!\!\cup\: \mathcal{M}_2& \left(X, f_1 \cdot f_2\right) \\ & \left(X, f_2 \cdot f_1\right) \\ & \mathcal{M}_2 \:\cdot\!\!\!\!\cup\: \mathcal{M}_1\end{array}$

The remaining parts follow from the following facts:

Let $A, B$ be partially ordered sets. Then $\inf \left(A \cup \left\{\inf B\right\}\right) = \inf\left(A\cup B\right)$ and $\sup \left(A \cup \left\{\sup B\right\}\right) = \sup \left(A\cup B\right)$ whenever the suprema and infima exist.
The supremum and infimum of every set of cardinals exist.

Associativity of $\cap$ .

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cap \left(\mathcal{M}_2 \cap \mathcal{M}_3\right) & \left(X, \inf \left\{f_1, \inf\left\{f_2, f_3\right\}\right\}\right) \\ & \left(X, \inf\left\{f_1, f_2, f_3\right\}\right) \\ & \left(X, \inf \left\{\inf\left\{f_1, f_2\right\}, f_3\right\}\right) \\ & \left(\mathcal{M}_1 \cap\mathcal{M}_2\right) \cap \mathcal{M}_3\end{array}$

Commutativity of $\cap$ .

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cap \mathcal{M}_2& \left(X, \inf \left\{f_1, f_2\right\}\right) \\ & \mathcal{M}_2 \cap \mathcal{M}_1\end{array}$

Associativity of $\cup$ .

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cup \left(\mathcal{M}_2 \cup \mathcal{M}_3\right) & \left(X, \sup \left\{f_1, \sup\left\{f_2, f_3\right\}\right\}\right) \\ & \left(X, \sup\left\{f_1, f_2, f_3\right\}\right) \\ & \left(X, \sup \left\{\sup\left\{f_1, f_2\right\}, f_3\right\}\right) \\ & \left(\mathcal{M}_1 \cup\mathcal{M}_2\right) \cup \mathcal{M}_3\end{array}$

Commutativity of $\cup$ .

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cup \mathcal{M}_2& \left(X, \sup \left\{f_1, f_2\right\}\right) \\ & \mathcal{M}_2 \cup \mathcal{M}_1\end{array}$

Proposition 2: The operations $\cap$ and $\cup$ on $\mathbf{MSet}_X$ are idempotent.

Proof:

Let $\mathcal{M}\in \mathbf{MSet}_X$ .

Idempotence of $\cap$ .

$\begin{array}{r@{\:=\:}l} \mathcal{M} \cap \mathcal{M}& \left(X, \inf \left\{f, f\right\}\right) \\ & \left(X, f\right) \\ & \mathcal{M}\end{array}$

Idempotence of $\cup$ .

$\begin{array}{r@{\:=\:}l} \mathcal{M} \cup \mathcal{M}& \left(X, \sup \left\{f, f\right\}\right) \\ & \left(X, f\right) \\ & \mathcal{M}\end{array}$

The other two operations—sum and product—are not idempotent. One counterexample is the multiset $\mathcal{M} = \left\{a^3\right\}$ , for which we have

$\mathcal{M}\uplus\mathcal{M} = \left\{a^6\right\} \neq \mathcal{M}$

and

$\mathcal{M}\:\cdot\!\!\!\!\cup\:\mathcal{M} = \left\{a^9\right\} \neq \mathcal{M}$ .

Leave a Comment » | Mathematics, Multisets | Tagged: binary operation, infimum, multiset intersection, multiset product, multiset sum, multiset union, supremum | Permalink
Posted by Michael McCliment

Properties of multiset union

June 4, 2008

We defined the union of a family of multisets last week. Today we’re going to look at some basic properties of the union operation on $\mathbf{MSet}_X$ .

Suppose $\left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I}$ is a family of multisets over $X$ . Then the following relationships hold:

(i) $\mathrm{support}\left(\bigcup_{i\in I}{\mathcal{M}_i}\right) = \bigcup_{i\in I}{\mathrm{support}\left(\mathcal{M}_i\right)}$ .

(ii) $\mathcal{M}_i \subseteq \bigcup_{i\in I}{\mathcal{M}_i}$ for all $i\in I$ .

(iii) $\bigcup_{i\in I}{\mathcal{M}_i} \subseteq \biguplus_{i\in I}{\mathcal{M}_i}$ .

(iv) $\bigcup_{i\in I}{\mathcal{M}_i} \subseteq \:\cdot\!\!\!\!\!\!\;\bigcup_{i\in I}{\mathcal{M}_i}$ provided that all of the multisets $\mathcal{M}_i$ have the same support.

(v) $\bigcap_{i\in I}{\mathcal{M}_i} \subseteq \bigcup_{i\in I}{\mathcal{M}_i}$ .

The proof of part (i), like the similar result for multiset intersections, is a straightforward series of equivalencies:

$\begin{array}{r@{\:\Leftrightarrow\:}l} x\in \mathrm{support}\left(\bigcup_{i\in I}{\mathcal{M}_i}\right) & \sup f_i(x) \neq 0 \\ & \left(\exists i\in I\right)\: f_i\left(x\right)\neq 0 \\ & \left(\exists i\in I\right)\: x\in\mathrm{support}\left(\mathcal{M}_i\right) \\ & x\in\bigcup_{i\in I}{\mathrm{support}\left(\mathcal{M}_i\right)}. \end{array}$

Part (ii) follows directly from the definition of the supremum of a set, since $f_i\left(x\right) \leq \sup f_i\left(x\right)$ for all $x\in X$ and $i\in I$ .

To prove part (iii), start by recalling that the sum of a family of cardinals $\left\{\kappa_i\right\}_{i\in I}$ is given by

$\sum_{i\in I}{\kappa_i} = \left|\bigcup_{i\in I}{A_i}\right|$

where the sets $A_i$ are disjoint and $\kappa_i = \left|A_i\right|$ for all $i\in I$ . Therefore, letting $A_{i,x}$ be a family of disjoint sets such that $\left|A_{i,x}\right| = f_i\left(x\right)$ , we have

$\kappa_x = \sum_{i\in I}{f_i\left(x\right)} = \left|\bigcup_{i\in I}{A_{i,x}}\right| \geq \left|A_{i,x}\right| = f_i\left(x\right)$

for all $i\in I$ and $x\in X$ . This establishes that $\kappa_x$ is an upper bound for $f_i\left(x\right)$ in the linearly ordered set $\left(\mathbf{Card}, \leq\right)$ , and so $\kappa_x \geq \sup f_i\left(x\right)$ . The result in part (iii) follows immediately since this holds for all $x\in X$ .

The proof of part (iv) is similar, but relies on the definition of the product of a family of cardinals. The product of a family of cardinals $\left\{\kappa_i\right\}_{i\in I}$ is given by

$\prod_{i\in I}{\kappa_i} = \left|\prod_{i\in I}{A_i}\right|$

where $\kappa_i = \left|A_i\right|$ for all $i\in I$ . Letting $A_{i,x}$ be a family of sets such that $\left|A_{i,x}\right| = f_i\left(x\right)$ , we have

$\kappa_x = \prod_{i\in I}{f_i\left(x\right)} = \left|\prod_{i\in I}{A_{i,x}}\right| \geq \left|A_{i,x}\right| = f_i\left(x\right)$

for all $i\in I$ and $x\in X$ , provided that $A_{i,x} \neq \emptyset$ for all $i\in I$ . This establishes that $\kappa_x$ is an upper bound for $f_i\left(x\right)$ in the linearly ordered set $\left(\mathbf{Card}, \leq\right)$ whenever $x\in\mathrm{support}\left(\bigcup_{i\in I}{\mathcal{M}_i}\right)$ , which is the common support of all multisets in the family $\left\{\mathrm{M}_i\right\}_{i\in I}$ . If $x$ is not in this support, then $\prod_{i\in I}{f_i\left(x\right)} = 0 = \sup f_i\left(x\right)$ . In either case, $\kappa_x \geq \sup f_i\left(x\right)$ , and part (iv) follows immediately since this holds for all $x\in X$ .

The requirement that all multisets in the family have the same support is necessary; you can see this by considering the product and union of the multisets $\left\{a\right\}$ and $\left\{b\right\}$ .

Finally, part (v) follows immediately from the fact that

$\inf f_i\left(x\right) \leq f_i\left(x\right) \leq \sup f_i\left(x\right)$

for all $i\in I$ and $x\in X$ .

Leave a Comment » | Mathematics, Multisets | Tagged: cardinal product, cardinal sum, multiset intersection, multiset product, multiset sum, multiset union, support | Permalink
Posted by Michael McCliment

Multiset union

May 28, 2008

Over the past two weeks, we’ve introduced three operations on families of multisets: sums, products, and intersections. The other basic operation on families of multisets, unions, is today’s topic. As we did with the other operations, we’ll revisit the characteristic function and then adapt this to the context of multisets.

The union of two sets $A, B\in \wp\left(X\right)$ can, as we’ve already seen, be represented in terms of the characteristic function as

$C=A\cup B \:\Leftrightarrow\: \chi_C = \max\left(\chi_A, \chi_B\right)$

where the maximum is taken in the ordered field $\mathbb{F}_2$ (just as we took the minimum in this field when looking at the intersection). This maximum is, in fact, a supremum:

$\sup\left\{\chi_A\left(x\right), \chi_B\left(x\right)\right\}$ for each $x\in X$ .

For any family of functions $f_i: X\to Y$ , we let

$\begin{array}{lrl}\sup \left\{f_i\right\} := &g:& X\to Y \\ &&x\mapsto \sup \left\{f_i\left(x\right)\right\} \end{array}$

provided that the supremum exists for each $x\in X$ . Since $\mathbb{F}_2$ is finite—which ensures the existence of the suprema—and the characteristic functions are taken over a common domain, the representation of union in terms of characteristic functions extends to any family of subsets of $X$ . That is, for any family $\left\{A_i\right\}_{i\in I}$ where each $A_i \in \wp\left(X\right)$ , we have

$A = \bigcup_{i\in I}{A_i} \:\Leftrightarrow\: \chi_A = \sup\left\{\chi_{A_i}\right\}$ .

This is completely analogous to the situation we encountered with the intersection of a family of subsets of $X$ , including the avoidance of the algebraic properties of $\mathbb{F}_2$ .

With the intersection, we were able to construct a definition on $\mathbf{MSet}_X$ that was analogous to the definition on $\mathbf{SSet}_X$ because both codomains— $\mathbb{F}_2$ and $\mathbf{Card}$ —were well-ordered, so the necessary infima were guaranteed to exist. In $\mathbb{F}_2$ , we know that the suprema exist because the set is linearly ordered and finite. $\mathbf{Card}$ is linearly ordered, but not finite. This raises a question: does every set of cardinals have a supremum?

The answer to this question depends on the set theory in which one is working. In our case, the axiom of choice allows us to actually define cardinals in terms of ordinals; in particular, cardinals are defined to be the initial ordinals. An ordinal is an initial ordinal if it is not equinumerous with any smaller ordinal. Moreover, every set of ordinals has a supremum. Since cardinals are ordinals, any set $\mathcal{K}$ of cardinals has an ordinal supremum $\omega$ . The cardinal $\kappa$ which is equinumerous with $\omega$ is the cardinal supremum of $\mathcal{K}$ .

With this in hand, we’re ready to define the union of a family of multisets.

Definition

Let $\mathrm{M} = \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I}$ be a family of multisets over a set $X$ . The multiset union of $\mathrm{M}$ is the set

$\mathcal{M} = \bigcup_{i\in I}{\mathcal{M}_i} := \left(X, \sup\left\{f_i\right\}\right)$ .

The multiplicity functions $f_i$ are defined on a common domain, and every set of cardinals has a supremum. This ensures that the multiset union is well-defined on $\mathbf{MSet}_X$ . We’ll deal with the properties of this operation in my next post on multisets.

Leave a Comment » | Mathematics, Multisets | Tagged: cardinal, characteristic function, multiset union, ordinal, supremum, union | Permalink
Posted by Michael McCliment

Properties of multiset intersection

May 27, 2008

Today, we’ll examine the properties of the multiset intersection that we defined yesterday.

Suppose $\left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I}$ is a family of multisets over $X$ . Then the following relationships hold:

(i) $\mathrm{support}\left(\bigcap_{i\in I}{\mathcal{M}_i}\right) = \bigcap_{i\in I}{\mathrm{support}\left(\mathcal{M}_i\right)}$ .

(ii) $\bigcap_{i\in I}{\mathcal{M}_i} \subseteq \mathcal{M}_i$ for all $i\in I$ .

(iii) $\bigcap_{i\in I}{\mathcal{M}_i} \subseteq \biguplus_{i\in I}{\mathcal{M}_i}$ .

(iv) $\bigcap_{i\in I}{\mathcal{M}_i} \subseteq \:\cdot\!\!\!\!\!\!\;\bigcup_{i\in I}{\mathcal{M}_i}$ .

The proof of part (i) is a straightforward series of equivalencies:

$\begin{array}{r@{\:\Leftrightarrow\:}l} x\in \mathrm{support}\left(\bigcap_{i\in I}{\mathcal{M}_i}\right) & \inf f_i(x) \neq 0 \\ & \left(\forall i\in I\right)\: f_i\left(x\right)\neq 0 \\ & \left(\forall i\in I\right)\: x\in\mathrm{support}\left(\mathcal{M}_i\right) \\ & x\in\bigcap_{i\in I}{\mathrm{support}\left(\mathcal{M}_i\right)}. \end{array}$

Part (ii) follows directly from the definition of the infimum of a set, since $\inf f_i\left(x\right) \leq f_i\left(x\right)$ for all $x\in X$ and $i\in I$ .

Recalling that the cardinal sum is a monotonic nondecreasing operation, we see that

$\inf f_i\left(x\right) \leq f_i\left(x\right) \leq \sum_{i\in I}{f_i\left(x\right)}$

for all $x\in X$ , which proves part (iii).

Part (iv) requires only slightly more work. To begin with, consider a family $\left\{\kappa_i\right\}_{i\in I}$ of cardinals. If there exists some $i\in I$ such that $\kappa_i = 0$ , then $\prod_{i\in I}{\kappa_i} = 0$ . If, however, no such $i\in I$ exists, then

$\kappa_i\leq\prod_{i\in I}{\kappa_i}$ for all $i\in I$ .

(This relies on the axiom of choice, which we have been assuming from the outset.) In other words, the product of any family of nonzero cardinals is monotonic nondecreasing.

Let $x\in\bigcap_{i\in I}{\mathcal{M}_i}$ . If there exists some $i\in I$ such that $x\not\in\mathcal{M}_i$ , then the multiplicity of $x$ in the intersection would be 0, contradicting the fact that $x$ is a member of the intersection. Since $f_i\left(x\right)\neq 0$ for all $i\in I$ , we have

$\inf f_i\left(x\right) \leq f_i\left(x\right) \leq \prod_{i\in I}{f_i\left(x\right)}$ .

For $x\not\in\bigcap_{i\in I}{\mathcal{M}_i}$ , we have

$\inf f_i\left(x\right) = 0 = \prod_{i\in I}{f_i\left(x\right)}$ .

In either case, $\inf f_i\left(x\right) \leq \prod_{i\in I}{f_i\left(x\right)}$ for all $x\in X$ , and (iv) holds.

Leave a Comment » | Mathematics, Multisets | Tagged: cardinal product, multiset intersection, multiset product, multiset sum, support | Permalink
Posted by Michael McCliment

Multiset intersection

May 26, 2008

Last Monday, I mentioned that multiset products are not the best available extension of the intersection of a family of sets so that it applies to multisets. Now that we’ve talked about the concepts of infima and well-ordering, we’re ready to define multiset intersections.

A bit further back, we discussed how characteristic functions can be used to represent subsets of a set $X$ and the operations on $\wp\left(X\right)$ . At the time, we noted that the intersection of two sets $A, B\in \wp\left(X\right)$ is represented in terms of the characteristic function as

$C=A\cap B \:\Leftrightarrow\: \chi_C = \min\left(\chi_A,\chi_B\right)$

where the minimum is taken in the ordered field $\mathbb{F}_2$ . For each $x\in X$ , this minimum is just $\inf\left\{\chi_A\left(x\right), \chi_B\left(x\right)\right\}$ .

Given a family of functions $f_i: X\to Y$ , we let

$\begin{array}{lrl}\inf \left\{f_i\right\} := &g:& X\to Y \\ &&x\mapsto \inf \left\{f_i\left(x\right)\right\} \end{array}$ .

Since $\mathbb{F}_2$ is well-ordered and the characteristic functions are taken over a common domain, our representation of intersection in terms of characteristic functions extends to any family of subsets of $X$ . That is, for any family $\left\{A_i\right\}_{i\in I}$ where each $A_i \in \wp\left(X\right)$ , we have

$A = \bigcap_{i\in I}{A_i} \:\Leftrightarrow\: \chi_A = \inf\left\{\chi_{A_i}\right\}$ .

We also saw a representation of intersections as the product of the characteristic functions. When dealing with sets in $\wp\left(X\right)$ , the two representations correspond to the same objects and operations in the class $\mathbf{SSet}_X$ . However, there is an important difference between the two: the representation in terms of products relies (exclusively) on the algebraic properties of the codomain, while the representation in terms of infima relies (exclusively) on the order properties of the codomain.

The algebraic properties of the field $\mathbb{F}_2$ and arithmetic on $\mathbf{Card}$ are quite different. However, both of them are well-ordered classes, so their order properties are similar in many respects. This leads us to the following definition:

Definition

Let $\mathrm{M} = \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I}$ be a family of multisets over a set $X$ . The multiset intersection of $\mathrm{M}$ is the set

$\mathcal{M} = \bigcap_{i\in I}{\mathcal{M}_i} := \left(X, \inf\left\{f_i\right\}\right)$ .

The multiplicity functions $f_i$ are defined on a common domain, and $\mathbf{Card}$ is well-ordered by the usual relation $\leq$ . Just as we found with the characteristic function, these facts are sufficient to ensure that the multiset intersection is always well-defined on $\mathbf{MSet}_X$ .

As usual, when $\mathrm{M}$ contains only two multisets, we will use the infix notation $\mathcal{M}_1 \cap \mathcal{M}_2$ for the intersection. In this case, $\cap$ is an associative and commutative binary operation on $\mathbf{Mset}_X$ . Next time, we’ll look at some of the properties of multiset intersections.

2 Comments | Mathematics, Multisets | Tagged: characteristic function, infimum, intersection, multiset intersection, well-order | Permalink
Posted by Michael McCliment

Mathematics and linguistics (part 4)

May 23, 2008

In part 1, I discussed the non-specialist’s experience with mathematics and with linguistics, and suggested that their experience is, in both cases, essentially prescriptivist in nature. Before discussing the relationship between these fields, we needed to move beyond the non-specialist’s perceptions and to understand more about the actual scope of each of these fields. I offered some observations about mathematics in part 2, and addressed linguistics in part 3. In this final part, we’ll look at the relationship between the two fields in light of the preceding discussion.

Now that we have a better understanding of what mathematics and linguistics are, let’s reconsider the question of how they are related to one another. Our initial view was that the two fields were predominantly parallel, and would interact where their respective objects of study happened to coincide (if anywhere). We represented this aspect schematically:

Fields of inquiry and their objects of study
Field of study	Practitioners	Objects studied
linguistics	linguists	language
mathematics	mathematicians	space, number, quantity, and arrangement

Linguistics, as we have now seen, isn’t just an arbitrary study of language. In many cases, philosophers may be said to study language. I’m not convinced that literary criticism can ever avoid studying language. But neither of these are inherently linguistic in nature. (They may be approached from a linguistic perspective; for example, one can apply pragmatics to the study of literature—but one can also study literature without using pragmatics, or any other part of linguistics.) Linguistics is the scientific study of language as a principal phenomenon.

Linguistics naturally studies the patterns that arise in languages. Even linguists who strongly reject any notion of an underlying rule-governed cognitive system propose that there are patterns in the languages that they study. Whether we adopt a rule-governed framework or not, the role of a linguistic theory is to propose that there are certain patterns—ranging from fully systematic “laws” through to weak “tendencies”—that arise in the use of language. The process of drawing conclusions from these basic propositions, and hence the entire act of moving from philosophical opinion to empirical science, is inherently an act of mathematics. Language is not mathematics. Linguistic theorization is not mathematics, but uses mathematics as its tool of reasoning. The evaluation of linguistic theories, however, is intrinsically mathematical. Has the theorist constructed a consistent theory? Do the theorist’s predictions follow from the patterns abstracted from their observations? Are there other predictions that follow from the proposed theory that also need to be evaluated empirically? These questions cannot be answered by the linguistic theory, which takes some aspect of language as its object of study, since these questions naturally take the linguistic theory itself as the object of study.

When physicists propose specific theories, these theories are evaluated not only for agreement with the empirical data and for compatibility with generally known physical properties, but they also evaluate and validate the mathematical properties of these theories. If the theory proposes a set of relationships among the observed patterns that is inconsistent, or if there is no way to construct any object satisfying the properties proposed by the theory, then that theory is rejected. The situation in linguistics is analogous. Just as the study of physical theories is part of physics, the study of linguistic theories is just as much a part of linguistics as the study of languages is.

This relationship, in which mathematics is the instrument by which we analyze linguistic theories, is the more fundamental relationship that I hinted at from the outset. It comes with an immediate corollary: mathematical modeling is necessarily a valid research methodology in linguistics. It does not replace empirical studies or the myriad research methodologies associated with them; it complements such studies. Both aspects are important for the health of linguistics as a science. For the formal evaluation of linguistic theory, however, mathematical modeling may well be the only valid methodology.

1 Comment | Linguistics, Mathematics | Tagged: linguistic theory, research methodology | Permalink
Posted by Michael McCliment

Infima, suprema, and well-orders

May 21, 2008

In the last couple of posts about multisets, we’ve looked at two types of operations we can perform on the class $\mathbf{MSet}_X.$ Sums and products of multisets are defined in terms of sums and products on the class $\mathbf{Card}.$ When we talked about the characteristic function as a way to represent the subsets of a given set, we also considered what happens when we take the maximum and minimum values of the function. This gave us another way to represent intersections and unions of subsets in $\mathbf{SSet}_X,$ which we’re now going to adapt to the context of multisets.

When we discussed cardinals for the first time, we began by taking

$\left|A\right| \leq \left|B\right|$ to mean that there exists an injective (one-to-one) mapping of sets $A\to B;$ and
$\left|A\right| = \left|B\right|$ to mean that there exists a bijective (one-to-one and onto) mapping of sets $A\to B.$

Partial orders: reflexive and irreflexive

There are two common, non-equivalent definitions for a partial order on a set. The two are related in precisely the way one would expect from considering the normal order relations $<$ and $\leq$ on the real numbers.

A reflexive partial order on a class $X$ is a relation on $X$ that is reflexive, transitive, and antisymmetric. An arbitrary reflexive partial order is usually written as $\leq.$ This may also be called a non-strict or weak partial order.

An irreflexive partial order on a class $X$ is a relation on $X$ that is irreflexive and transitive. An arbitrary irreflexive partial order is usually written as $<.$ This may also be called a strict or strong partial order. Irreflexive partial orders are necessarily asymmetric.

(Since we’re using results about cardinals rather than discussing the theory of cardinals, I’m still going to sidestep the construction that justifies a number of assertions about them. I might put together a series of posts on that subject sometime later.) The class $\mathbf{Card}$ admits a (total, reflexive) order that is consistent with these ideas. That is, $\left(\mathbf{Card}, \leq\right)$ is

reflexive: $\kappa\leq\kappa$ for all $\kappa\in\mathbf{Card};$
transitive: $\kappa\leq\lambda \wedge \lambda\leq\nu \:\Rightarrow\: \kappa\leq\nu$ for all $\kappa,\lambda,\nu\in\mathbf{Card};$
antisymmetric: $\kappa\leq\lambda \wedge \lambda\leq\kappa \:\Rightarrow\: \kappa = \lambda$ for all $\kappa,\lambda\in\mathbf{Card};$ and
total: $\kappa\leq\lambda \vee \lambda\leq\kappa$ for all $\kappa,\lambda\in\mathbf{Card}.$

The last property is often expressed by saying that every pair of cardinals are comparable. The pair $\left(\mathbf{Card}, \leq\right)$ is a special case of a (reflexive) partially-ordered class. The relation $\leq$ in such a class is reflexive, transitive, and antisymmetric, but not necessarily total.

We need just a bit more of the vocabulary of partially-ordered classes.

Definition

Let $\mathcal{X} = \left(X,\leq\right)$ be a reflexive partially-ordered class, $A\subseteq X,$ and $L_A = \left\{x\in X \:|\: \left(\forall a\in A\right)x\leq a\right\}.$ $l\in L_A$ is called a lower bound of $A$ in $\mathcal{X}.$ If, furthermore, $x\leq l$ for all $x\in L_A$ , then $l$ is called the infimum of $A$ and is denoted $\inf{A}$ .

In general, there is no guarantee that either a lower bound or an infimum exist. If $\inf{A}$ exists, however, it is unique. (To see this, consider what happens if there are two infima for a particular set.) We also have the following dual relationship:

Definition

Let $\mathcal{X} = \left(X,\leq\right)$ be a reflexive partially-ordered class, $A\subseteq X,$ and $U_A = \left\{x\in X \:|\: \left(\forall a\in A\right)a\leq x\right\}.$ $u\in U_A$ is called an upper bound of $A$ in $\mathcal{X}.$ If, furthermore, $u\leq x$ for all $x\in U_A,$ then $u$ is called the supremum of $A$ and is denoted $\sup{A}.$

As with lower bounds and infima, upper bounds and the supremum do not necessarily exist, and the supremum is unique whenever it does exist.

$\left(\mathbf{Card}, \leq\right)$ has an additional property (at least in NBG set theory, including the axiom of choice): for every subclass $X \subseteq\mathbf{Card},$ $\inf X$ exists. Since $\leq$ has this property and is a total order on $\mathbf{Card},$ it well-orders $\mathbf{Card},$ and the partially-ordered class is said to be well-ordered.

3 Comments | Mathematics, Set theory | Tagged: infimum, partial order, supremum, well-order | Permalink
Posted by Michael McCliment

Multiset products

May 19, 2008

When we looked at the characteristic function for the subset of a set, we started by examining both sums and products of the characteristic function in $\mathbb{F}_2.$ Last week, we looked at the multiset sum, which we defined in terms of the cardinal sum that we’ve been using for a while now. To consider the multiset analogue of the products of characteristic functions, we need another bit of cardinal arithmetic.

Definition

Let $I$ be a set, $\left\{\kappa_i\right\}_{i\in I}$ be a family of cardinals, and $\left\{A_i\right\}_{i\in I}$ be a family of sets such that $\left|A_i\right| = \kappa_i$ for $i\in I$ . The product of this family of cardinals is

$\prod_{i\in I} \kappa_i := \left| \prod_{i\in I} {A_i} \right|.$

For infinite index sets $i\in I,$ the axiom of choice ensures that the set product $\mathcal{A} = \prod_{i\in I}{A_i}$ is not empty. As with the sum, it is possible to prove that $\left|\mathcal{A}\right|$ does not depend on the choice of sets $A_i,$ and so the product is well-defined.

Definition

Let $\mathcal{M} = \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I}$ be an indexed family of multisets. The multiset product of $\mathcal{M}$ is the multiset

$\cdot\!\!\!\!\!\!\:\bigcup_{i\in I} \mathcal{M}_i := \left(X, \prod_{i\in I}f_i\right).$

As we saw with the multiset sum, $\mathrm{dom}\left(f_i\right) = X$ for all $i\in I.$ The cardinal product on the right is therefore well-defined, and the result is again a multiset over $X.$ Unsurprisingly, we also use the infix notation $\mathcal{M}_1 \cdot\!\!\!\!\cup\, \mathcal{M}_2$ when dealing with just a pair of multisets. This binary operation on $\mathbf{MSet}_X$ is both commutative and associative.

The cardinal product satisfies the equation $0\cdot\kappa = 0$ for all $\kappa\in\mathbf{Card}.$ It follows that $x\in\mathrm{support}\left(\mathcal{M}\right)$ if and only if $f_i(x) \neq 0$ for all $i\in I.$ This gives us the following identity:

$\mathrm{support}\left(\;\cdot\!\!\!\!\!\!\;\bigcup_{i\in I} \mathcal{M}_i\right) = \bigcap_{i\in I} \mathrm{support}\left(\mathcal{M}_i\right).$

As a binary operation on $\mathbf{MSet}_X,$ the multiset product is not in general idempotent. Unlike the multiset sum, however, the class of multisets $\left(X, f_i\right)$ where $f_i\left(X\right)\subseteq\left\{0,1\right\}$ is closed under multiset products. For this class, it is even idempotent. Even more suggestive is the fact that $x\in \mathcal{M}_1 \cdot\!\!\!\!\cup\, \mathcal{M}_2$ if and only if $x\in\mathcal{M}_1$ and $x\in\mathcal{M}_2.$

These observations raise a question: is the multiset product a good candidate to be viewed as an extension to multisets of the intersection of sets? Let’s consider the set $X = \left\{a, b, c\right\}$ and the multisets $\mathcal{M}_1 = \left\{a^2, b^4, c^2\right\}$ and $\mathcal{M}_1 = \left\{a, b^0, c^5\right\}$ (the expression $x^\kappa$ indicates that $\kappa = f\left(x\right)$ is the multiplicity of $x$ in the given multiset). Here, we have

$\mathcal{M}_1 \cdot\!\!\!\!\cup\, \mathcal{M}_2 = \left\{a^2, b^0, c^{10}\right\} \not\subseteq \mathcal{M}_1.$

This is contrary to the intuitive idea that an intersection should always be contained in every multiset that participates in the intersection. Counterintuitive results aren’t always wrong. Given the notation, however, we can easily guess that we will soon see an operation that is a better choice to consider as an intersection of multisets.

1 Comment | Mathematics, Multisets | Tagged: cardinal product, intersection, multiset product | Permalink
Posted by Michael McCliment

Mathematics and linguistics (part 3)

May 16, 2008

In part 1, I discussed the non-specialist’s experience with both mathematics and linguistics, and suggested that their experience is, in both cases, essentially prescriptivist in nature. Before discussing the relationship between these fields, we must move beyond the non-specialist’s perceptions and understand more about the actual scope of each of these fields. In part 2, I offered some observations about mathematics. In this part, I’ll address the question of linguistics.

To start with, I’ll turn once again to my trusty OED. As a substantive, we find that linguistic is “the science of languages; philology”, and is almost always used in the plural form linguistics (linguistic, sense B.a, b). Turning to philology, we find that the pertinent sense of the word is

3. spec. (in mod. use) The study of the structure and development of language; the science of language; linguistics. Now usu. restricted to the study of the development of specific languages or language families, esp. research into phonological and morphological history based on written documents. (Really one branch of sense 1.)

This sense has never been current in the U. S. Linguistics is now the more usual term for the study of the structure of language, and, with qualifying adjective or adjective phrase, is replacing philology even in the restricted sense.

For the non-specialist, this doesn’t add too much beyond what we experienced in terms of grammar, and possibly pronunciation drills in a foreign language course (courtesy of something that looks, after all, like its related to the “Hooked on Phonics” products). And, of course, theres that odd term, morphological.

Mark Liberman recently provided a wordbite that does a much better job at suggesting the range of phenomena studied by linguists:

The usual division is into six levels [of linguistic analysis], named as pragmatics (how language is used to communicate), semantics (the meaning of words and phrases), syntax (the structure of sentences), morphology (the structure of words), phonology (the inventory of sounds and their systematic arrangement into words), and phonetics (the physical facts of speech).

An important point here is that linguistics is the scientific study of these phenomena. A linguist will not provide a list like the following (from Richard Johnson-Sheehan’s Technical Communication Today, 2nd ed., p. 218):

Eight Guidelines for Plain Sentences

Guideline 1: The subject of the sentence should be what the sentence is about.

Guideline 2: The subject should be the “doer” in the sentence.

Guideline 3: The verb should state the action, or what the doer is doing.

Guideline 4: The subject of the sentence should come early in the sentence.

Guideline 5: Eliminate nominalizations.

Guideline 6: Avoid excessive prepositional phrases.

Guideline 7: Eliminate redundancy in sentences.

Guideline 8: Write sentences that are “breathing length.”

People who study and teach the art of communication may well provide well-reasoned arguments in favor of following some or all of these guidelines under certain circumstances. However, no such argument is part of linguistics, any more than a rule that says “Do not stop on tracks” is part of physics. It’s a perfectly good traffic guideline, and well-supported by an argument that a train hitting a car generally has negative consequences. The reason that it isn’t physics is that there’s nothing about the physical nature of cars and railroad tracks that prevents a car from stopping in such close proximity to the tracks. The reason that the eight guidelines aren’t linguistics is that they are not a property of language, but rather a recommendation on how we use a specific language.

Linguistics, unlike writing advisors or publication style manuals, is the scientific study of language. The linguist doesn’t ask “what should people do?” (that’s rhetoric), but rather “what do people do?” and “how do people do what they do?” These questions can be from several different standpoints. For example, we might look at a corpus—a collection of written or spoken language that has been collected from various sources—and examine the phenomena that appear in that corpus. We can also treat corpora as being just a sample of the actual and / or possible range of language use, and study some aspects of the larger collection from which the sample is drawn.

The corpora-based approaches, whether drawn from real corpora or some form of virtual corpus, are often aggregates over some group of people. A fundamentally different approach is to study how a specific person uses language. One form that this type of research takes is to correlate specific linguistic tasks with imaging studies of the brain. Functional magnetic resonance imaging (fMRI) studies are one of the current tools in this vein. Evaluation and study of people with impaired language capabilities also lend themselves to this type of individual study.

The scientific tools that are deployed in linguistics are quite varied. Some of the biological investigations use highly technical instruments like the imaging systems that collect data for the fMRI studies. Other types of investigation, such as how language use correlates with sociological factors, may use surveys and interviews as their primary tools. But no matter what research tools are used, linguistic questions are always fundamentally concerned with what actually happens when people create and consume language.

1 Comment | Linguistics, Mathematics | Tagged: prescriptivism, science of language | Permalink
Posted by Michael McCliment

Multiset sums

May 14, 2008

On Monday, we considered how the sets $A\in\wp\left(X\right)$ can be represented as functions $\chi_A: X\to \mathbb{F}_2.$ In fact, for every function $\chi:X\to\mathbb{F}_2,$ we can define $A_\chi = \left\{x\in X \:|\:\chi\left(x\right) = 1\right\}.$ Combining this with the definition of the characteristic function, we have the identities

$A_{\chi_A} = A$ and $\chi_{A_\chi} = \chi.$

This actually provides the bijection between $\wp\left(X\right)$ and the functions $\chi$ that I mentioned immediately following the definition of the characteristic function.

Structurally, the class

$\mathbf{SSet}_X := \left\{\left(X, \chi\right) \:|\: \chi: X\to\mathbb{F}_2\right\}$

is very similar to the class

$\mathbf{MSet}_X := \left\{(\left(X, f\right) \:|\: f: X\to\mathbf{Card}\right\}$

of multisets over $X.$ Our ability to represent the set operations on $\mathbf{SSet}_X$ by well-defined operations in the ordered field $\mathbb{F}_2$ suggests that we look at some of the well-defined operations on $\mathbf{Card}$ as a basis for formally defining the multiset operations on $\mathbf{MSet}_X.$

One operation on $\mathbf{Card}$ that we have already used is the cardinal sum $\sum_{i\in I}\kappa_i,$ which is defined for every set of cardinals $\left\{\kappa_i\right\}_{i\in I}.$

Definition

Let $\mathcal{M} = \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I}$ be an indexed family of multisets. The multiset sum of $\mathcal{M}$ is the multiset

$\biguplus_{i\in I} \mathcal{M}_i := \left(X, \sum_{i\in I}f_i\right).$

Since $\mathrm{dom}\left(f_i\right) = X$ for all $i\in I,$ the cardinal sum on the right is well-defined and the multiset sum does indeed give us another multiset over $X.$ For a pair of multisets, we will generally write the multiset sum in infix notation as $\mathcal{M}_1 \uplus \mathcal{M}_2.$

As the notation suggests, the multiset sum is related to the union operation on sets. Multiset sums, like the union of sets are both commutative and associative—these follow directly from the corresponding properties of the cardinal sum. Cardinal sums are also monotonic nondecreasing; for any cardinal sum $\kappa = \sum_{i\in I} {\kappa_i}$ we have $\kappa_i \leq \kappa$ for all $i\in I.$ One consequence of this is that a cardinal sum is 0 if and only if all of its summands are 0, and so we have the following relationship between support, multiset sums, and set unions:

$\mathrm{support}\left(\biguplus_{i\in I} {\mathcal{M}_i}\right) = \bigcup_{i\in I} {\mathrm{support}\left(\mathcal{M}_i\right)}.$

The monotonicity of cardinal sums also ensures that the multiset sum of a family of multisets contains each of the multisets in the family:

$\mathcal{M} = \biguplus_{i\in I}{\mathcal{M}_i}\:\Rightarrow\:\left(\forall i\in I\right)\left(\mathcal{M}_i\subseteq\mathcal{M}\right).$

Here’s a way in which the multiset sum differs from the union of sets. Set union is idempotent—for any set $X,$ we have $X\cup X = X.$ The multiset sum, on the other hand, is not idempotent, as we can see by considering the sum

$\left\{a\right\}\uplus\left\{a\right\} = \left\{a, a\right\} \neq \left\{a\right\}.$

This last example also shows that the class of multisets with all multiplicities equal to 1 is not closed under multiset sums.

7 Comments | Mathematics, Multisets | Tagged: cardinal sum, characteristic function, idempotent, multiset sum, union | Permalink
Posted by Michael McCliment

A Singular Contiguity

Multiset operations as binary operations (part 1)

Properties of multiset union

Multiset union

Properties of multiset intersection

Multiset intersection

Mathematics and linguistics (part 4)

Infima, suprema, and well-orders

Multiset products

Mathematics and linguistics (part 3)

Multiset sums

Pages

Recent Posts

Archives