I teach a class in discrete mathematics and formal language theory. On my most recent final exam, I asked a question that involved a crossover between equivalence relations and formal languages. Here's the setup. Recall that an equivalence relation over a set $A$ is a set $R \subseteq A^2$ with these three properties:
$$\begin{aligned}\text{(I)}&\quad \forall x \in A. (x, x) \in R \\ \text{(II)}&\quad \forall x \in A. \forall y \in A. ((x, y) \in R \to (y, x) \in R) \\ \text{(III)}&\quad \forall x \in A. \forall y \in A. \forall z \in A. ((x, y) \in R \land (y, z) \in R \to (x, z) \in R)\end{aligned}$$
Based on this, here's a new definition. An equivalence language over an alphabet $\Sigma$ is a language $L \subseteq \Sigma^\star$ with the following three properties:
$$\begin{aligned}\text{(I)}&\quad \forall x \in \Sigma^\star. xx \in L \\ \text{(II)}&\quad \forall x \in \Sigma^\star. \forall y \in \Sigma^\star. (xy \in L \to yx \in L) \\ \text{(III)}&\quad \forall x \in \Sigma^\star. \forall y \in \Sigma^\star. \forall z \in \Sigma^\star. (xy \in L \land yz \in L \to xz \in L)\end{aligned}$$
Essentially, this is what you get if you translate $(x, y) \in R$ to $xy \in L$, hence the name "equivalence language."
On the exam itself I asked a question that isn't relevant here (it was basically a standard equivalence relation proof translated into formal language theory). After the exam, though, I started wondering about what sorts of languages these equivalence languages happen to be. What do they look like? What properties do they have?
To begin with, it's not too hard to show the following.
Every equivalence language $L$ contains the empty string $\varepsilon$ (apply property (I) to $\varepsilon$).
Every equivalence language $L$ is closed under concatenation. Specifically, if $x \in L$ and $y \in L\text,$ then because $x\varepsilon \in L$ an $\varepsilon y \in L$ by property (III) we have $xy \in L\text.$
Restating (1) and (2), every equivalence language $L$ over $\Sigma$ is a submonoid of the free monoid $\Sigma^\star\text.$
Suppose we let $ER(\Sigma)$ denote the class of all equivalence languages. Then $ER(\Sigma)$ is closed under infinite union. In particular, the language $\bigcap ER(\Sigma)$ is itself an equivalence language, and is the minimal equivalence language over $\Sigma$ from an order-theoretic perspective.
This last property is the source of my ultimate question, which is the following:
Question (v1): What is $\bigcap ER(\Sigma)$?
I have a limited answer to this question in the specific case where $\Sigma$ is small. Let $\Sigma$ be a language and let $Z(\Sigma) = \{ w \in \Sigma^\star \ | \ \text{every character in } \Sigma \text{ appears an even number of times in } w \}\text.$ So, for example, $\mathtt{ababcc} \in Z(\{\mathtt{a}, \mathtt{b}, \mathtt{c})$. It intuitively makes sense that strings of this form will be in $\bigcap ER(\Sigma)$ because property (I) immediately gives us a bunch of strings that have even character counts. My conjecture is the following:
Conjecture: $\bigcap ER(\Sigma) = Z(\Sigma)$.
I'm able to prove the following:
Theorem: If $|\Sigma| \le 2\text,$ then $\bigcap ER(\Sigma) = Z(\Sigma)\text.$
Proving this isn't too hard. First show that the language $Z(\Sigma)$ is an equivalence language, then show that every element of $Z(\Sigma)$ belongs to every equivalence language. In the case where $|\Sigma| = 1$ this isn't too tricky to do. I thought it would be informative to include my proof for the case of $|\Sigma| = 2$ here, because it relies on a point that I'll need later on in this question.
Proof for $|\Sigma| = 2$: First check that indeed $Z(\Sigma)$ satisfies the three rules for equivalence languages (it does; this proof is independent of $|\Sigma|$ so I'll skip it here). Next we need to show that if $L$ is an equivalence language, then $Z(\Sigma) \subseteq L\text.$ So choose some arbitrary equivalence language $L$. We're assuming $|\Sigma| = 2\text,$ and assume WLOG that $\Sigma = \{\mathtt{a}, \mathtt{b}\}$. We need to show that $Z(\Sigma) \subseteq L\text,$ and we'll do that by induction on the length of the strings in $Z(\Sigma)$.
First, our base cases: strings of lengths 0, 2, and 4. Note that $\varepsilon \in Z(\Sigma)$ and that $\varepsilon \in L$ as well (as described above). Next note that $\mathtt{aa}$ and $\mathtt{bb}$ are the only length-two strings in $Z(\Sigma)$, and each belongs to $L$ by property (I) of equivalence languages applied to $\mathtt{a}$ and $\mathtt{b}$. There are eight strings of length four in $Z(\Sigma)$: $\mathtt{aaaa}$, $\mathtt{aabb}$, $\mathtt{abba}$, $\mathtt{baab}$, $\mathtt{bbaa}$, $\mathtt{abab}$, $\mathtt{baba}$, and $\mathtt{bbbb}$. Of these, $\mathtt{aaaa}$, $\mathtt{bbbb}$, $\mathtt{abab}$, and $\mathtt{baba}$ can be shown to be in $L$ via property (I) of equivalence languages. $\mathtt{aabb}$ and $\mathtt{bbaa}$ are in $L$ because $\mathtt{aa}$ and $\mathtt{bb}$ are in $L$ and $L$ is closed under concatenation. $\mathtt{baab}$ and $\mathtt{abba}$ can be shown to be in $L$ because $\mathtt{aabb}$ is in $L$ and these two strings are rotations of that string, which by property (II) are in $L$.
For our inductive step suppose that all strings of lengths $k$ and $k+2$ in $Z(\Sigma)$ are in $L$. (We only need to worry about even lengths, so there are no strings of length $k+1$ in $L$.) We'll show that all strings of length $k+4$ are in $L$. Pick any string $w \in Z(\Sigma)$ of where $|w| = k+4$. We consider two cases.
Case 1: $w$ starts or ends with $\mathtt{aa}$ or $\mathtt{bb}$. Assume WLOG that $w = \mathtt{aa}z$ for some string $z$. We know $|w| = k+4$, so this means $|z| = k+2$. We can check that $z$ has an even number of copies of each character ($w$ has an even number of copies of each character and we just dropped $\mathtt{aa}$), so $z \in Z(\Sigma)$. Therefore by our IH we know $z \in L$. We also know $\mathtt{aa} \in L$ from our base case, and since equivalence languages are closed under concatenation we know $\mathtt{aa}z = w \in L\text.$
Case 2: $w$ doesn't start or end with $\mathtt{aa}$ or $\mathtt{bb}$. Then $w$ both starts with either $\mathtt{ab}$ or $\mathtt{ba}$ and ends with either $\mathtt{ab}$ and ends with $\mathtt{ba}$. Assume WLOG that $w = \mathtt{ab}z\mathtt{ab}$ for some string $z$ of length $k$. As above, $z \in Z(\Sigma)$, so by our IH $z \in L$. We also know that $\mathtt{abab} \in L$ from our base case, so $\mathtt{abab}z \in L$ as well. Applying Property (II) of equivalence languages to this string gives $\mathtt{ab}z\mathtt{ab} = w \in L\text.$
This means we always have $w \in L\text,$ as required. $\blacksquare$
Notice that the logic in the inductive step is heavily specific to the fact that we're working with a two-character alphabet, where it's possible to enumerate all possible ways that a string can start or end. But I don't see a nice way to generalize this to work with larger alphabets.
While I'm conjecturing that $\bigcap ER(\Sigma) = Z(\Sigma)$, I'm not fully convinced this is the case. For example, I don't see how to get $\mathtt{abcacb} \in Z(\Sigma)$ using the rules for equivalence languages plus the other properties listed above.
All this is to say that a refined version of my question is as follows:
Question (v2): Is the conjecture that $\bigcap ER(\Sigma) = Z(\Sigma)$ true?
And now the plot thickens. While thinking about how I might prove this, I realized that there's a close connection between equivalence languages, $Z(\Sigma)$, and walks in a hypercube graph. Specifically, given an alphabet $\Sigma$ where $|\Sigma| = n\text,$ think of an $n$-dimensional hypercube and assign each axis a unique character from $\Sigma$. We can interpret a string over $\Sigma$ as a series of instructions about how to walk around the hypercube. Each character means "the next step is to walk on the edge along the axis associated with this character." Every string in $Z(\Sigma)$ therefore corresponds to a walk in a hypercube that ends where it begins (e.g. a closed walk), since if there's an even number of copies of each character we "undo" every step we take. We can also check that the three rules for equivalence languages, applied to strings that are closed walks in a hypercube, preserve this property. Specifically:
- Property (I) says that any series of directions, repeated twice, returns home.
- Property (II) says that cyclically shifting a closed walk leaves a closed walk.
- Property (III) says that if one closed walk ends with the same sequence that a second closed walk starts with, we can "cancel out" the matching parts and glue the remaining steps together to get a closed walk.
It's clear that these rules will give rise to closed walks and only closed walks, but it's not clear that these rules are sufficient to generate all possible closed walks on a hypercube. This connection between equivalence languages, $Z(\Sigma)$, and hypercube walks gives rise to the final version of my question:
Question (v3): What walks on a hypercube do you get if you begin with walks generated by property (I) and then repeatedly apply rules (II) and (III)?
I'm curious for an answer to any version of the question. All of this is to say - I accidentally invented something much more nuanced than I anticipated when writing my final exam, and I'd like some clarity about what exactly I just unleashed on my students. :-)
It's a bit easier to talk about the conjecture if we go back to equivalence relations. Fix an equivalence language $L \subseteq \Sigma^*$; for words $x,y \in \Sigma^*$, define $\sim$ by $x \sim y$ if and only if $xy \in L$. This is an equivalence relation by the definition of an equivalence language!
We can prove three quick lemmas:
Lemma 1. For all $x,y \in \Sigma^*$, $x \sim xyy$.
Proof. By (I), $xx \in L$ and $yy \in L$, which we can interpret as $xx \sim \epsilon$ and $\epsilon \sim yy$. Therefore $xx \sim yy$, or $xxyy \in L$. But this is also exactly what we need to check for $x \sim xyy$.
Lemma 2. For all $x,y \in \Sigma^*$, $xy \sim yx$.
Proof. We have $xy \sim yx \iff xyyx \in L \iff xyy \sim x$, which we know from Lemma 1.
Lemma 3. For all $x,y,z \in \Sigma^*$, if $x \sim y$, then $xz \sim yz$ and $zx \sim zy$.
Proof. By Lemma 1, $x \sim xzz$, so $xzz \sim y$, which means $xzzy \in L$. Therefore $xz \sim zy$, which we can turn into both $xz \sim yz$ and $zx \sim zy$ by Lemma 2.
Together, Lemma 2 and Lemma 3 show that any word is equivalent to any permutation of that word. If we write a word $w$ as $abcd$, where $b,c \in \Sigma$, then $bc \sim cb$ by Lemma 2; by two applications of Lemma 3, $abcd \sim acbd$. This lets us swap $b$ and $c$ within $w$ and get a word equivalent to $w$. Any permutation of $w$ can be obtained by repeatedly swapping adjacent characters.
In particular, if every character appears in $w$ an even number of times, we can permute $w$ into the form $xx$ for some $x \in \Sigma^*$. Therefore $w \sim xx$; since $xx \in L$, $xx \sim \epsilon$, so $w \sim \epsilon$ by transitivity. From this, we can conclude that $w \in L$.