How we model possibilities

Note

The executable cells on this page use Python 3.14 syntax, matching the project configuration. The Quarto kernel is named python3; before rendering with execution, configure that kernelspec to point to a Python 3.14 environment.

The Kolmogorov axioms start by specifying a set $\Omega$ that contains all and only the things that can possibly happen. This set is known as the sample space. So what it means to be a possibility is a brute fact: it’s all and only the things in $\Omega$.

That’s very abstract, so let’s consider a few examples:

$\Omega$ could be the set of all vowel types in a language–e.g. for English $\Omega = \{\text{e, i, o, u, æ, ɑ, ɔ, ə, ɛ, ɪ, ʊ}\}$.
$\Omega$ could be the set of all strings of phonemes in a language–e.g. if $\Sigma$ is the set of phonemes, then $\Omega = \Sigma^* = \bigcup_{i=0}^\infty \Sigma^i$.
$\Omega$ could be the language $\text{eval}(r)$ that a regular expression $r \in R(\Sigma)$ evaluates to.
$\Omega$ could be the set of all regular expressions in a language–e.g. if $\Sigma$ is the set of phonemes, then $\Omega = R(\Sigma)$. That is, $\Omega$ could be possible grammars, which in turn correspond to possible languages.

The axioms then move forward by defining a way of classifying possibilities $\mathcal{F} \subseteq 2^\Omega$. These classes of possibilities are known as events, and the set containing them is known as the event space. It is events, which can contain just a single possibility, that we measure the probability of.¹

The event space is where interesting linguistic structure enters the picture. Let’s look at a few examples of event spaces that assume our first example of a sample space above: $\Omega = \{\text{e, i, o, u, æ, ɑ, ɔ, ə, ɛ, ɪ, ʊ}\}$.

One possible event space distinguishes vowels with respect to highness: $\mathcal{F}_\text{highness} = \{H, L, \Omega, \emptyset\}$, with $H = \{\text{i, u, ɪ, ʊ}\}$ and $L = \Omega - H$.
Another possible event space distinguishes vowels with respect to backness: $\mathcal{F}_\text{backness} = \{B, F, \Omega, \emptyset\}$, with $B = \{\text{u, ʊ, o, ɔ, ɑ}\}$ and $F = \Omega - B$.

emptyset = frozenset()
vowels = frozenset({'e', 'i', 'o', 'u', 'æ', 'ɑ', 'ɔ', 'ə', 'ɛ', 'ɪ', 'ʊ'})

# high v. nonhigh
high = frozenset({'i', 'u', 'ɪ', 'ʊ'})
nonhigh = vowels - high

f_highness = frozenset({
    frozenset(emptyset),
    frozenset(high), frozenset(nonhigh),
    frozenset(vowels)
})

# back v. nonback
back = frozenset({'u', 'ʊ', 'o', 'ɔ', 'ɑ'})
nonback = vowels - back

f_backness = frozenset({
    frozenset(emptyset),
    frozenset(back), frozenset(nonback),
    frozenset(vowels)
})

You’ll notice that beyond having just the set of high v. non-high vowels, or the set of back v. non-back vowels in these event spaces, we also have the entire set of vowels itself alongside the empty set. The reasons for this are technical: to make certain aspects of the formalization of what it means to measure probabilties work out nicely, we need the event space $\mathcal{F}$ to form what is known as a $\sigma$-algebra on the sample space $\Omega$. All this means is that:

$\mathcal{F} \subseteq 2^\Omega$
$E \in \mathcal{F}$ iff $\Omega - E \in \mathcal{F}$ (closure under complement)
$\bigcup \mathcal{E} \in \mathcal{F}$ for all countable $\mathcal{E} \subseteq \mathcal{F}$ (closure under countable union)
$\bigcap \mathcal{E} \in \mathcal{F}$ for all countable $\mathcal{E} \subseteq \mathcal{F}$ (closure under countable intersection)

from collections.abc import Iterable, Iterator
from itertools import chain, combinations
from functools import reduce

type SampleSpace = frozenset[str]
type Event = frozenset[str]
type SigmaAlgebra = frozenset[Event]

def powerset[T](iterable: Iterable[T]) -> Iterator[tuple[T, ...]]:
    """Compute the power set of an iterable.

    See https://docs.python.org/3/library/itertools.html#itertools-recipes

    Parameters
    ----------
    iterable : Iterable
        The set to take the power set of.

    Returns
    -------
    Iterable
        All subsets of the input as tuples.
    """
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

class FiniteMeasurableSpace:
  """A finite measurable space.

  Parameters
  ----------
  atoms : SampleSpace
      The atoms of the space.
  sigma_algebra : SigmaAlgebra
      The sigma-algebra of the space.
  """
  def __init__(self, atoms: SampleSpace, sigma_algebra: SigmaAlgebra) -> None:
    self._atoms = atoms
    self._sigma_algebra = sigma_algebra

    self._validate()

  def _validate(self) -> None:
    if not isinstance(self._atoms, frozenset):
      raise TypeError("The sample space must be a frozenset")

    if not isinstance(self._sigma_algebra, frozenset):
      raise TypeError("The event family must be a frozenset")

    if not all(isinstance(event, frozenset) for event in self._sigma_algebra):
      raise TypeError("Every event must be a frozenset")

    if frozenset() not in self._sigma_algebra:
      raise ValueError("The event family must contain the empty event")

    if self._atoms not in self._sigma_algebra:
      raise ValueError("The event family must contain the sample space")

    for subset in self._sigma_algebra:
      if not subset <= self._atoms:
        raise ValueError("All events must be a subset of the atoms")

      if not (self._atoms - subset) in self._sigma_algebra:
        raise ValueError("The σ-algebra must be closed under complements")

    for subsets in powerset(self._sigma_algebra):
      subsets = list(subsets)

      # reduce raises on empty iterables
      if not subsets:
        continue

      union = frozenset(reduce(frozenset.union, subsets))
      if union not in self._sigma_algebra:
        raise ValueError(
            "The σ-algebra must be closed under countable union"
        )

      intersection = frozenset(reduce(frozenset.intersection, subsets))
      if intersection not in self._sigma_algebra:
        raise ValueError(
            "The σ-algebra must be closed under countable intersection"
        )

  @property
  def atoms(self) -> SampleSpace:
    """The atoms of the space."""
    return self._atoms

  @property
  def sigma_algebra(self) -> SigmaAlgebra:
    """The sigma-algebra of the space."""
    return self._sigma_algebra

You can check that all of these conditions are satisfied for our two examples above as long as $\Omega$ and $\emptyset$ are both in $\mathcal{F}$. When $\mathcal{F} \subseteq 2^\Omega$ is a $\sigma$-algebra, the pair $\langle \Omega, \mathcal{F} \rangle$ is referred to as a measurable space.

highness_space = FiniteMeasurableSpace(vowels, f_highness)
backness_space = FiniteMeasurableSpace(vowels, f_backness)

The two examples above are close to trivial in the sense that the only “interesting” events are complements of each other. But what if we put both together, distinguishing vowels with respect to both highness and backness? Both have the same sample space, so nothing needs to change there.

Question

Can we simply define $\mathcal{F}_\text{highness-backness} = \mathcal{F}_\text{highness} \cup \mathcal{F}_\text{backness}$?

Answer

No. While Condition 1 above would be satisfied (that’s easy), we would be missing quite a few sets that Conditions 2-4 require: e.g. the high back vowels $H \cap B$ and the high and/or back vowels $H \cup B$.

try:
  highness_space = FiniteMeasurableSpace(vowels, f_highness.union(f_backness))
except ValueError as e:
  print(f"ValueError: {e}")

This point demonstrates an important fact about $\sigma$-algebras: if you design a classification based on some (countable) set of features like highness and backness, the constraint that $\mathcal{F}$ be a $\sigma$-algebra on $\Omega$ implies that $\mathcal{F}$ contains events corresponding to all possible conjunctions (e.g. high and back) and disjunctions (e.g. high and/or back) of those features. So we need to extend $\mathcal{F}_\text{highness} \cup \mathcal{F}_\text{backness}$ with additional sets. We call this extension the $\sigma$-algebra generated by the family of sets $\mathcal{F}_\text{highness} \cup \mathcal{F}_\text{backness}$, denoted $\sigma\left(\mathcal{F}_\text{highness} \cup \mathcal{F}_\text{backness}\right)$.

def generate_sigma_algebra(
    atoms: SampleSpace,
    family: SigmaAlgebra,
) -> SigmaAlgebra:
  """Generate a sigma-algebra from a family of sets.

  Parameters
  ----------
  atoms : SampleSpace
      The sample space.
  family : SigmaAlgebra
      The family of sets from which to generate the sigma-algebra.

  Returns
  -------
  SigmaAlgebra
      The smallest sigma-algebra containing the family.
  """

  if not all(event <= atoms for event in family):
    raise ValueError("Every generator must be a subset of the sample space")

  sigma_algebra = {frozenset(), atoms, *family}
  old_sigma_algebra: set[Event] = set()

  while sigma_algebra != old_sigma_algebra:
    old_sigma_algebra = set(sigma_algebra)

    for event in old_sigma_algebra:
      sigma_algebra.add(atoms - event)

    for subsets in powerset(old_sigma_algebra):
      subsets = list(subsets)

      if not subsets:
        continue

      union = reduce(frozenset.union, subsets)
      sigma_algebra.add(union)

      intersection = reduce(frozenset.intersection, subsets)
      sigma_algebra.add(intersection)

  return frozenset(sigma_algebra)

f_highness_backness = generate_sigma_algebra(
    vowels,
    f_highness | f_backness,
)

f_highness_backness

So how do we know this procedure returns the $\sigma$-algebra we want? We will call the procedure the finite closure construction (FCC). It should return the smallest $\sigma$-algebra on the finite sample space $\Omega$ that contains every supplied event.

Before checking that it is the smallest such $\sigma$-algebra, we need to check two things. First, does the procedure stop? At every iteration, the current family only grows, and every event added is a subset of $\Omega$. There are only $2^{|\Omega|}$ such subsets. Thus, the loop can make only finitely many strict additions before it reaches a fixed point.

Second, is the fixed point a $\sigma$-algebra? The initialization supplies $\emptyset$ and $\Omega$. Each pass adds the complement of every event and the union and intersection of every subfamily currently available. At the fixed point, making another pass adds nothing, so the result is closed under these operations. Because the result is finite, a countable collection of its events has only finitely many distinct members; its countable union reduces to the union of a finite subfamily already checked by the procedure. Hence, the fixed point is closed under countable union.

Countable-intersection closure follows separately. Fix a countable collection $E_1,E_2,\ldots$ of events in the fixed point. Complement closure puts every $\Omega-E_i$ in the fixed point, and countable-union closure puts $\bigcup_i(\Omega-E_i)$ there. Taking one more complement and applying De Morgan’s law gives

\[ \Omega-\bigcup_i(\Omega-E_i)=\bigcap_iE_i. \]

The left-hand side belongs to the fixed point by complement closure. Thus, the countable intersection on the right belongs to it as well.

Consider $\Omega=\{a,b,c\}$ with generators $A=\{a,b\}$ and $B=\{b,c\}$. Initialization gives

\[ S_0=\{\emptyset,\Omega,A,B\}. \]

The first pass adds the complements $\{c\}$ and $\{a\}$ and the intersection $A\cap B=\{b\}$, giving $S_1=2^\Omega-\{\{a,c\}\}$. The second pass adds the complement of $\{b\}$, namely $\{a,c\}$, so $S_2=2^\Omega$. A third pass adds nothing. Thus, the fixed point is the full power set, which is the smallest $\sigma$-algebra containing $A$ and $B$ in this example.

It remains to show minimality. Any $\sigma$-algebra $\mathcal{G}$ on $\Omega$ that contains the original family must contain every event the procedure adds. Initially, $\emptyset$ and $\Omega$ belong to $\mathcal{G}$ because they belong to every $\sigma$-algebra. If all events present after one pass belong to $\mathcal{G}$, then closure puts every complement, union, and intersection added on the next pass in $\mathcal{G}$ as well. Thus, every stage of the FCC remains inside $\mathcal{G}$. Since this holds for every such $\mathcal{G}$, the fixed point is contained in every $\sigma$-algebra that contains the generators. The procedure thus returns exactly $\sigma(\mathcal{F}_\text{highness}\cup\mathcal{F}_\text{backness})$ in the running example.

highness_backness_space = FiniteMeasurableSpace(vowels, f_highness_backness)

So far, we’ve seen a case where the sample space is finite. How about when the sample space is infinite? For example, what if we define $\Omega$ to be the set of all strings $\Sigma^*$? In that case, our event space will be a subset of $2^{\Sigma^*}$–i.e. it will consist of languages on $\Sigma$. This pairing of a sample space (the strings on $\Sigma$) and an event space (the languages on $\Sigma$) is what underlies all language models.

Because an event space on $\Sigma^*$ is simply a set of languages, one natural way to define the event space is using a grammar.

Question

Do the regular languages on $\Sigma$–i.e. the image of $R(\Sigma)$ under $\text{eval}$–form a $\sigma$-algebra?

Answer

No. And the reason has to do with the fact that the set of regular languages on $\Sigma$ are not closed under countable union. We will prove this later in the course when we discuss the pumping lemma for regular languages.

An alternative is to take the event space to be all languages, $2^{\Sigma^*}$. If $\Sigma$ is finite or countable, then $\Sigma^*$ is countable even though its power set is uncountable. This size difference does not prevent $2^{\Sigma^*}$ from being a valid $\sigma$-algebra.

A Borel $\sigma$-algebra is defined only after a topology has been chosen: it is the $\sigma$-algebra generated by that topology’s open sets. Equip $\Sigma^*$ with the discrete topology. Every singleton string is then open, and every language is a countable union of singleton strings. Thus,

\[ \mathcal B(\Sigma^*)=2^{\Sigma^*} \]

under the discrete topology. Other topologies on strings may generate smaller Borel $\sigma$-algebras, and on uncountable spaces such as $\mathbb R$ the usual Borel $\sigma$-algebra is strictly smaller than the full power set. In these notes, language models on $\Sigma^*$ use the discrete topology and hence the full power-set event space; real-valued models use the Borel $\sigma$-algebra generated by the usual Euclidean topology.

Footnotes

Don’t ask me why, but $\mathcal{F}$ is standard notation for the event space. Why we don’t use $\mathcal{E}$ is beyond me. It might be some convention from measure theory I’m not aware of; or it might have to do with not confusing the event space with the expectation $\mathbb{E}$, which we’ll review below.↩︎

--- title: How we model possibilities bibliography: ../references.bib jupyter: python3 --- ::: {.callout-note} The executable cells on this page use Python 3.14 syntax, matching the project configuration. The Quarto kernel is named `python3`; before rendering with execution, configure that kernelspec to point to a Python 3.14 environment. ::: The Kolmogorov axioms start by specifying a set $\Omega$ that contains all and only the things that can possibly happen. This set is known as the *sample space*. So what it means to be a possibility is a brute fact: it's all and only the things in $\Omega$. That's very abstract, so let's consider a few examples: 1. $\Omega$ could be the set of all vowel types in a language–e.g. for English $\Omega = \{\text{e, i, o, u, æ, ɑ, ɔ, ə, ɛ, ɪ, ʊ}\}$. 2. $\Omega$ could be the set of all strings of phonemes in a language–e.g. if $\Sigma$ is the set of phonemes, then $\Omega = \Sigma^* = \bigcup_{i=0}^\infty \Sigma^i$. 3. $\Omega$ could be the language $\text{eval}(r)$ that a regular expression $r \in R(\Sigma)$ evaluates to. 4. $\Omega$ could be the set of all regular expressions in a language–e.g. if $\Sigma$ is the set of phonemes, then $\Omega = R(\Sigma)$. That is, $\Omega$ could be possible grammars, which in turn correspond to possible languages. The axioms then move forward by defining a way of classifying possibilities $\mathcal{F} \subseteq 2^\Omega$. These classes of possibilities are known as *events*, and the set containing them is known as the *event space*. It is events, which can contain just a single possibility, that we measure the probability of.^[Don't ask me why, but $\mathcal{F}$ is standard notation for the event space. Why we don't use $\mathcal{E}$ is beyond me. It might be some convention from measure theory I'm not aware of; or it might have to do with not confusing the event space with the expectation $\mathbb{E}$, which we'll review below.] The event space is where interesting linguistic structure enters the picture. Let's look at a few examples of event spaces that assume our first example of a sample space above: $\Omega = \{\text{e, i, o, u, æ, ɑ, ɔ, ə, ɛ, ɪ, ʊ}\}$. 1. One possible event space distinguishes vowels with respect to highness: $\mathcal{F}_\text{highness} = \{H, L, \Omega, \emptyset\}$, with $H = \{\text{i, u, ɪ, ʊ}\}$ and $L = \Omega - H$. 2. Another possible event space distinguishes vowels with respect to backness: $\mathcal{F}_\text{backness} = \{B, F, \Omega, \emptyset\}$, with $B = \{\text{u, ʊ, o, ɔ, ɑ}\}$ and $F = \Omega - B$. ```{python} emptyset = frozenset() vowels = frozenset({'e', 'i', 'o', 'u', 'æ', 'ɑ', 'ɔ', 'ə', 'ɛ', 'ɪ', 'ʊ'}) # high v. nonhigh high = frozenset({'i', 'u', 'ɪ', 'ʊ'}) nonhigh = vowels - high f_highness = frozenset({ frozenset(emptyset), frozenset(high), frozenset(nonhigh), frozenset(vowels) }) # back v. nonback back = frozenset({'u', 'ʊ', 'o', 'ɔ', 'ɑ'}) nonback = vowels - back f_backness = frozenset({ frozenset(emptyset), frozenset(back), frozenset(nonback), frozenset(vowels) }) ``` You'll notice that beyond having just the set of high v. non-high vowels, or the set of back v. non-back vowels in these event spaces, we also have the entire set of vowels itself alongside the empty set. The reasons for this are technical: to make certain aspects of the formalization of what it means to measure probabilties work out nicely, we need the event space $\mathcal{F}$ to form what is known as a [$\sigma$-algebra](https://en.wikipedia.org/wiki/%CE%A3-algebra) on the sample space $\Omega$. All this means is that: 1. $\mathcal{F} \subseteq 2^\Omega$ 2. $E \in \mathcal{F}$ iff $\Omega - E \in \mathcal{F}$ (*closure under complement*) 3. $\bigcup \mathcal{E} \in \mathcal{F}$ for all countable $\mathcal{E} \subseteq \mathcal{F}$ (*closure under countable union*) 4. $\bigcap \mathcal{E} \in \mathcal{F}$ for all countable $\mathcal{E} \subseteq \mathcal{F}$ (*closure under countable intersection*) ```{python} from collections.abc import Iterable, Iterator from itertools import chain, combinations from functools import reduce type SampleSpace = frozenset[str] type Event = frozenset[str] type SigmaAlgebra = frozenset[Event] def powerset[T](iterable: Iterable[T]) -> Iterator[tuple[T, ...]]: """Compute the power set of an iterable. See https://docs.python.org/3/library/itertools.html#itertools-recipes Parameters ---------- iterable : Iterable The set to take the power set of. Returns ------- Iterable All subsets of the input as tuples. """ s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) class FiniteMeasurableSpace: """A finite measurable space. Parameters ---------- atoms : SampleSpace The atoms of the space. sigma_algebra : SigmaAlgebra The sigma-algebra of the space. """ def __init__(self, atoms: SampleSpace, sigma_algebra: SigmaAlgebra) -> None: self._atoms = atoms self._sigma_algebra = sigma_algebra self._validate() def _validate(self) -> None: if not isinstance(self._atoms, frozenset): raise TypeError("The sample space must be a frozenset") if not isinstance(self._sigma_algebra, frozenset): raise TypeError("The event family must be a frozenset") if not all(isinstance(event, frozenset) for event in self._sigma_algebra): raise TypeError("Every event must be a frozenset") if frozenset() not in self._sigma_algebra: raise ValueError("The event family must contain the empty event") if self._atoms not in self._sigma_algebra: raise ValueError("The event family must contain the sample space") for subset in self._sigma_algebra: if not subset <= self._atoms: raise ValueError("All events must be a subset of the atoms") if not (self._atoms - subset) in self._sigma_algebra: raise ValueError("The σ-algebra must be closed under complements") for subsets in powerset(self._sigma_algebra): subsets = list(subsets) # reduce raises on empty iterables if not subsets: continue union = frozenset(reduce(frozenset.union, subsets)) if union not in self._sigma_algebra: raise ValueError( "The σ-algebra must be closed under countable union" ) intersection = frozenset(reduce(frozenset.intersection, subsets)) if intersection not in self._sigma_algebra: raise ValueError( "The σ-algebra must be closed under countable intersection" ) @property def atoms(self) -> SampleSpace: """The atoms of the space.""" return self._atoms @property def sigma_algebra(self) -> SigmaAlgebra: """The sigma-algebra of the space.""" return self._sigma_algebra ``` You can check that all of these conditions are satisfied for our two examples above as long as $\Omega$ and $\emptyset$ are both in $\mathcal{F}$. When $\mathcal{F} \subseteq 2^\Omega$ is a $\sigma$-algebra, the pair $\langle \Omega, \mathcal{F} \rangle$ is referred to as a [measurable space](https://en.wikipedia.org/wiki/Measurable_space). ```{python} highness_space = FiniteMeasurableSpace(vowels, f_highness) backness_space = FiniteMeasurableSpace(vowels, f_backness) ``` The two examples above are close to trivial in the sense that the only "interesting" events are complements of each other. But what if we put both together, distinguishing vowels with respect to both highness and backness? Both have the same sample space, so nothing needs to change there. ::: {.callout-caution} ## Question Can we simply define $\mathcal{F}_\text{highness-backness} = \mathcal{F}_\text{highness} \cup \mathcal{F}_\text{backness}$? ::: ::: {.callout-tip collapse=true} ## Answer No. While Condition 1 above would be satisfied (that's easy), we would be missing quite a few sets that Conditions 2-4 require: e.g. the high back vowels $H \cap B$ and the high and/or back vowels $H \cup B$. ::: ```{python} #| colab: {base_uri: 'https://localhost:8080/'} #| outputId: 930414ce-e929-4bab-8581-11c4718ee218 try: highness_space = FiniteMeasurableSpace(vowels, f_highness.union(f_backness)) except ValueError as e: print(f"ValueError: {e}") ``` This point demonstrates an important fact about $\sigma$-algebras: if you design a classification based on some (countable) set of features like highness and backness, the constraint that $\mathcal{F}$ be a $\sigma$-algebra on $\Omega$ implies that $\mathcal{F}$ contains events corresponding to all possible conjunctions (e.g. high and back) and disjunctions (e.g. high and/or back) of those features. So we need to extend $\mathcal{F}_\text{highness} \cup \mathcal{F}_\text{backness}$ with additional sets. We call this extension the $\sigma$-algebra *generated by the family of sets* $\mathcal{F}_\text{highness} \cup \mathcal{F}_\text{backness}$, denoted $\sigma\left(\mathcal{F}_\text{highness} \cup \mathcal{F}_\text{backness}\right)$. ```{python} #| colab: {base_uri: 'https://localhost:8080/'} #| outputId: 73f585f7-b3ad-4d73-c852-425dfd570166 def generate_sigma_algebra( atoms: SampleSpace, family: SigmaAlgebra, ) -> SigmaAlgebra: """Generate a sigma-algebra from a family of sets. Parameters ---------- atoms : SampleSpace The sample space. family : SigmaAlgebra The family of sets from which to generate the sigma-algebra. Returns ------- SigmaAlgebra The smallest sigma-algebra containing the family. """ if not all(event <= atoms for event in family): raise ValueError("Every generator must be a subset of the sample space") sigma_algebra = {frozenset(), atoms, *family} old_sigma_algebra: set[Event] = set() while sigma_algebra != old_sigma_algebra: old_sigma_algebra = set(sigma_algebra) for event in old_sigma_algebra: sigma_algebra.add(atoms - event) for subsets in powerset(old_sigma_algebra): subsets = list(subsets) if not subsets: continue union = reduce(frozenset.union, subsets) sigma_algebra.add(union) intersection = reduce(frozenset.intersection, subsets) sigma_algebra.add(intersection) return frozenset(sigma_algebra) f_highness_backness = generate_sigma_algebra( vowels, f_highness | f_backness, ) f_highness_backness ``` So how do we know this procedure returns the $\sigma$-algebra we want? We will call the procedure the **finite closure construction** (FCC). It should return the smallest $\sigma$-algebra on the finite sample space $\Omega$ that contains every supplied event. Before checking that it is the *smallest* such $\sigma$-algebra, we need to check two things. First, does the procedure stop? At every iteration, the current family only grows, and every event added is a subset of $\Omega$. There are only $2^{|\Omega|}$ such subsets. Thus, the loop can make only finitely many strict additions before it reaches a fixed point. Second, is the fixed point a $\sigma$-algebra? The initialization supplies $\emptyset$ and $\Omega$. Each pass adds the complement of every event and the union and intersection of every subfamily currently available. At the fixed point, making another pass adds nothing, so the result is closed under these operations. Because the result is finite, a countable collection of its events has only finitely many distinct members; its countable union reduces to the union of a finite subfamily already checked by the procedure. Hence, the fixed point is closed under countable union. Countable-intersection closure follows separately. Fix a countable collection $E_1,E_2,\ldots$ of events in the fixed point. Complement closure puts every $\Omega-E_i$ in the fixed point, and countable-union closure puts $\bigcup_i(\Omega-E_i)$ there. Taking one more complement and applying De Morgan's law gives $$ \Omega-\bigcup_i(\Omega-E_i)=\bigcap_iE_i. $$ The left-hand side belongs to the fixed point by complement closure. Thus, the countable intersection on the right belongs to it as well. Consider $\Omega=\{a,b,c\}$ with generators $A=\{a,b\}$ and $B=\{b,c\}$. Initialization gives $$ S_0=\{\emptyset,\Omega,A,B\}. $$ The first pass adds the complements $\{c\}$ and $\{a\}$ and the intersection $A\cap B=\{b\}$, giving $S_1=2^\Omega-\{\{a,c\}\}$. The second pass adds the complement of $\{b\}$, namely $\{a,c\}$, so $S_2=2^\Omega$. A third pass adds nothing. Thus, the fixed point is the full power set, which is the smallest $\sigma$-algebra containing $A$ and $B$ in this example. It remains to show minimality. Any $\sigma$-algebra $\mathcal{G}$ on $\Omega$ that contains the original family must contain every event the procedure adds. Initially, $\emptyset$ and $\Omega$ belong to $\mathcal{G}$ because they belong to every $\sigma$-algebra. If all events present after one pass belong to $\mathcal{G}$, then closure puts every complement, union, and intersection added on the next pass in $\mathcal{G}$ as well. Thus, every stage of the FCC remains inside $\mathcal{G}$. Since this holds for every such $\mathcal{G}$, the fixed point is contained in every $\sigma$-algebra that contains the generators. The procedure thus returns exactly $\sigma(\mathcal{F}_\text{highness}\cup\mathcal{F}_\text{backness})$ in the running example. ```{python} highness_backness_space = FiniteMeasurableSpace(vowels, f_highness_backness) ``` So far, we've seen a case where the sample space is finite. How about when the sample space is infinite? For example, what if we define $\Omega$ to be the set of all strings $\Sigma^*$? In that case, our event space will be a subset of $2^{\Sigma^*}$–i.e. it will consist of languages on $\Sigma$. This pairing of a sample space (the strings on $\Sigma$) and an event space (the languages on $\Sigma$) is what underlies all [language models](https://en.wikipedia.org/wiki/Language_model). Because an event space on $\Sigma^*$ is simply a set of languages, one natural way to define the event space is using a grammar. ::: {.callout-caution} ## Question Do the regular languages on $\Sigma$–i.e. the image of $R(\Sigma)$ under $\text{eval}$–form a $\sigma$-algebra? ::: ::: {.callout-tip collapse=true} ## Answer No. And the reason has to do with the fact that the set of regular languages on $\Sigma$ are not closed under countable union. We will prove this later in the course when we discuss the pumping lemma for regular languages. ::: An alternative is to take the event space to be all languages, $2^{\Sigma^*}$. If $\Sigma$ is finite or countable, then $\Sigma^*$ is countable even though its power set is uncountable. This size difference does not prevent $2^{\Sigma^*}$ from being a valid $\sigma$-algebra. A [Borel $\sigma$-algebra](https://en.wikipedia.org/wiki/Borel_set) is defined only after a topology has been chosen: it is the $\sigma$-algebra generated by that topology's open sets. Equip $\Sigma^*$ with the discrete topology. Every singleton string is then open, and every language is a countable union of singleton strings. Thus, $$ \mathcal B(\Sigma^*)=2^{\Sigma^*} $$ under the discrete topology. Other topologies on strings may generate smaller Borel $\sigma$-algebras, and on uncountable spaces such as $\mathbb R$ the usual Borel $\sigma$-algebra is strictly smaller than the full power set. In these notes, language models on $\Sigma^*$ use the discrete topology and hence the full power-set event space; real-valued models use the Borel $\sigma$-algebra generated by the usual Euclidean topology.