← A note on language measurability
FirstVersion.tex
\documentclass{amsart}
\usepackage[left=2cm, right=2cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox}
\usepackage{blindtext}
\usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref}
\usepackage{tikz,tikz-cd}
\usepackage{cleveref}
\usepackage{xcolor}
\usepackage{array}
\usepackage[style=alphabetic,sorting=nyt, maxnames=4]{biblatex}
% \usepackage[style=authoryear, maxnames=4]{biblatex}
\renewbibmacro{in:}{}
% \addbibresource{biblio.bib}
\addbibresource{CommonBiblio20240922.bib}
\tikzset{pullback/.style={minimum size=1.2ex,path picture={
\draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);%
}}}
\usetikzlibrary{calc}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[subsection]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{todo}[theorem]{Todo}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}{Claim}[theorem]
\crefname{claim}{Claim}{Claims}
\renewcommand{\theclaim}{\thetheorem.\alph{claim}}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{puzzle}[theorem]{Puzzle}
\newtheorem{idea}[theorem]{Idea}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\dq}[1]{``#1"}
\newcommand{\memo}[1]{\textcolor{red}{memo: #1}}
% \newcommand{\invmemo}[1]{\textcolor{blue}{memo: #1}}
\newcommand{\invmemo}[1]{}
\newcommand{\horamemo}[1]{\textcolor{green!70!black}{hora: #1}}
\newcommand{\para}[1]{\paragraph{\textbf{#1}}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\Clopen}{{\Delta}}
\newcommand{\Open}{{\mathcal{O}}}
\newcommand{\Bcl}{\mathcal{B}_\Clopen}
\newcommand{\N}{\mathbb{\N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathbf{F}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\ob}{\mathrm{ob}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\BoolAlg}{\mathbf{BoolAlg}}
\newcommand{\ProfSp}{\mathbf{ProfSp}}
\newcommand{\sSet}{\mathbf{sSet}}
\newcommand{\FinSet}{\mathbf{FinSet}}
\newcommand{\PSh}{\mathbf{PSh}}
\newcommand{\Sh}{\mathbf{Sh}}
\newcommand{\Cont}{\mathbf{Cont}}
\newcommand{\Func}[2]{[#1,#2]}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\demph}[1]{\textit{#1}}
\font\maljapanese=dmjhira at 2.5ex
\newcommand{\yo}{\textrm{\!\maljapanese\char"48}}
\newcommand{\Pow}{\mathcal{P}}
\newcommand{\St}{\mathrm{St}}
\newcommand{\Ext}{\mathrm{Ext}}
% \newcommand{\Dor}{\mathrm{Cl}_{\perp\perp}}
\newcommand{\Dor}{\mathrm{Dxt}}
\newcommand{\RExt}{\mathrm{RExt}}
\newcommand{\SF}{\mathsf{SF}}
\newcommand{\G}{\mathsf{G}}
\newcommand{\Reg}{\mathsf{Reg}}
\newcommand{\Regu}{\mathsf{Reg}_{>\frac{1}{2}}}
\newcommand{\Regd}{\mathsf{Reg}_{<\frac{1}{2}}}
\newcommand{\MA}{{A^{\ast}}}
\newcommand{\Sp}{\mathrm{Sp}}
\title{A note on language measurability}
\author{Ryuya Hora}
\address{ZEN University, Tokyo, Japan}
\email{ryuya\_hora@zen.ac.jp}
\date{\today}
\subjclass[2020]{}
\keywords{h}
\begin{document}
\begin{abstract}
This is a short note, exclusively for personal conversations with Sin'ya Ryoma.
\end{abstract}
\maketitle
\tableofcontents
Definitions are due to \cite{sin2025measure} and papers cited therein.
\section{Kuratowski closure axioms}
\begin{proposition}
There exist subsets $\C_A, \D_A\subset \Reg$ such that
\[
\RExt(\C_A)\cup \RExt(\D_A)\subsetneq \RExt(\C_A \cup \D_A).
\]
\end{proposition}
\begin{proof}
Let $\C_A$ be the set \[
\C_A\coloneqq \left\{L\in \Reg \;\middle | \;\delta(L)>\frac{1}{2}\right\},
\]
and $\D_A$ be the set
\[
\D_A\coloneqq \left\{L\in \Reg \;\middle | \;\delta(L)<\frac{1}{2}\right\}.
\]
Let $L_n$ be the regular language defined by
\[
L_n=\{w\in \MA\mid \abs{w}\equiv 0 \mod n\}.
\]
We have $L_2\notin \RExt(\C_A)\cup \RExt(\D_A)$ since $\C_A$ does not have a lower-approximation of $L_2$ and $\D_A$ does not have an upper approximation of $L_2$.
% If a regular language $L_1\in \Reg$ is $\C_A$-measurable, there exists a smaller regular language $L_0$ in $\C_A$ This implies $\frac{1}{2}<\delta(L_0)\leq\delta(L_1)$ and hence $L_1 \in \C_A$. So we have $\RExt(\C_A)= \C_A$. Similarly, we have $\RExt(\D_A)=\D_A$.
However, we have $L_2\in \RExt(\C_A\cup \D_A)$ due to the approximation
\[
(L_2\setminus L_{3^n}) \subsetneq L_2 \subsetneq (L_2\cup L_{3^n})
\]
for increasing positive integers $n\to \infty$.
Notice that we can use
\begin{align*}
\delta(L_2\setminus L_{3^n}) &=\frac{1}{2}-\frac{1}{2\cdot 3^n}\\
\delta(L_2\cup L_{3^n})&=\frac{1}{2}+\frac{1}{2\cdot 3^n},
\end{align*}
because $L_n$ and $L_m$ are independent if (and only if) $n,m$ are coprime. This completes the proof.
\end{proof}
\section{Orthogonality and Measurability}
\subsection{Orthogonality}
\begin{notation}
For two languages $L_0, L_1$, we write $L_0 \perp L_1$ for the independency, i.e., $\delta(L_0 \cap L_1)=\delta(L_0)\cdot \delta(L_1)$.
For two language classes $\C_A, \D_A\subset 2^\MA$, we write $\C_A \perp \D_A$ if any element of $\C_A$ and any element of $\D_A$ are independent.
\end{notation}
\begin{example}
Sin'ya and Yuyama proved $\SF\perp \G$ in \cite[Theorem 18]{sin2025measure}.
\end{example}
\begin{example}\label{exmp:SelfOrthogonality}
For any language $L$, the self-orthogonality $L\perp L$ holds if and only if $\delta(L\cap L )= \delta(L)\cdot \delta(L)$, i.e., $\delta(L)=0,1$.
\end{example}
\begin{proposition}
The \demph{double orthogonal} function $\Dor\colon2^{2^\MA}\to 2^{2^\MA}$ is a closure operator.
\end{proposition}
\begin{proof}
This holds for any set instead of $2^\MA$ and any binary relation instead of $\perp$.
\end{proof}
\subsection{Comparison with the measurability}
\begin{definition}
The \demph{orthogonal class} of $\C_A$, denoted by $\C_A^\perp$, is defined by
\[
\C_A^\perp \coloneqq \{L\in 2^{\MA} \mid L\perp \C_A\}.
\]
\end{definition}
\begin{lemma}\label{lem:extOrthogonal}
If $\C_A\perp L$, then $\Ext(\C_0)\perp L$. In other words, we have
\[
\C_A^\perp = \Ext(\C_A)^\perp
\]
\end{lemma}
\begin{proposition}
For any $\C_A\subset 2^\MA$, we have $\Ext(\C_A)\subset \Dor(\C_A)$.
\end{proposition}
\begin{proof}
By the above lemma and $\Dor(\C_A)=\Dor(\Ext(\C_A))\supset \Ext(\C_A)$.
\end{proof}
\memo{How much are $\Ext$ and $\Dor$ different?}
\begin{remark}[The embedding into the Hilbert space]
This is essentially the same as the construction of the closed subspace in Hilbert space. In fact, this should coincide with the corresponding operation on $L^2(\widehat{\MA})$, where $\widehat{\MA}$ is Carathéodory's extension $\mu$ of the regular language density. Then, \Cref{lem:extOrthogonal} follows from the fact that orthogonality is a closed condition.
As long as we consider the measurability of only regular languages, the natural subject to consider is the measurable subsets of $\widehat{\MA}$, not subsets of $2^{\MA}$. The comparison often fails, as exemplified by $\mu(\MA)=0$. Some works so far might be understood as studies on the extent to which the comparison fails.
\end{remark}
\begin{proposition}
$\C_A\perp \D_A$ implies $\Ext(\C_A) \perp \Ext(\D_A)$.
\end{proposition}
\begin{corollary}
For any independent language classes $\C_A\perp \D_A$, if a language $L$ is $\C_A$-measurable and $\D_A$-measurable\footnote{Actually, the upward measurabilities suffice.}, then $\delta(L)=0,1$.
\end{corollary}
\begin{proof}
By the assumptions, we obtain $L\in \Ext(\C_A)\cap \Ext(\D_A)$ and $\Ext(\C_A)\perp \Ext(\D_A)$, and hence $L\perp L$. Then, as we have seen in \Cref{exmp:SelfOrthogonality}, $\delta(L)$ is either $0$ or $1$.
\end{proof}
\begin{example}
If a language $L$ with $0<\delta(L)<1$ is $\G$-measurable, then it is not $\SF$-measurable.
\end{example}
\appendix
\section{A general theory for Boolean algebras with probability}
\subsection{Preliminary: Stone duality}
See Johnstone's textbook \cite{johnstone1982stone} for detailed explanations of Stone duality.
\begin{notation}\label{notation:BorelandVariants}
Let $X$ be a topological space.
\begin{itemize}
\item We write $\Clopen(X)$ for the boolean algebra of all clopen subsets of $X$, and $\Bcl(X)$ for the $\sigma$-algebra generated by $\Clopen(X)$.
\item We write $\Open(X)$ for the set of all open subsets of $X$, and $\B(X)$ for the $\sigma$-algebra generated by $\Open(X)$, i.e., the set of all Borel sets of $X$.
\end{itemize}
\end{notation}
\begin{fact}[Stone duality \cite{stone1936theory, stone1937applications, doctor1964categories}]
The category of Boolean algebras and the category of profinite spaces are contravariantly equivalent via the functor $\Clopen$.
\[
\begin{tikzcd}
\ProfSp^\op \ar[r, "\Clopen", "\simeq"', shift left] & \BoolAlg
\end{tikzcd}
\]
\end{fact}
We write $\Sp$ for the (essentially unique) converse equivalence $\Sp \colon \BoolAlg^\op \to \ProfSp$
\subsection{Boolean algebra with measure}
\begin{definition}
A \demph{Boolean algebra with measure} (in short, \demph{BwM}) is a pair $(B,\mu)$ of a Boolean algebra $B$ and a function $\mu\colon B \to [0,\infty)$ such that
\begin{itemize}
\item for any $x,y \in B$, $x\land y=\bot$ implies $\mu(x\lor y)=\mu(x)+\mu(y)$.
\end{itemize}
\end{definition}
\begin{lemma}[Basic properties]
For any BwM $(B, \mu)$, the following conditions hold.
\begin{enumerate}
\item $\mu: B \to [0, \infty)$ is order-preserving.
\item $\mu(\bot)=0$
\item For any $x,y \in B$, $\mu(x\lor y)\leq \mu(x)+\mu(y)$
\end{enumerate}
\end{lemma}
\begin{proof} We prove them one by one.
\begin{enumerate}
\item Assuming $x\leq y$, we have $y=y\land(x\lor \lnot x)=x\lor (y\land \lnot x)$. Since $x \land (y\land \lnot x)=\bot$, we have $\mu(y) =\mu (x)+\mu (y\land \lnot x)\geq \mu(x)$. This proves that $\mu$ is order-preserving.
\item Since $\bot= \bot \land \bot $, we have $\mu(\bot)= \mu(\bot \land \bot)=\mu(\bot)+\mu(\bot)$, which implies $\mu(\bot)=0$.
\item As $x\lor y =x\lor (\lnot x \land y)$, we have $\mu(x\lor y)=\mu(x)+\mu(\lnot x \land y)\leq \mu(x)+\mu(y)$.
\end{enumerate}
\end{proof}
% \begin{remark}
%
\invmemo{This provides an embedding into the category of topological spaces with finite additive measure?}
% \end{remark}
% \begin{todo}
%
\invmemo{The metric space structure of (\dq{separable} BwM)}
% \end{todo}
For a topological space, we call a finitely additive measure on $\Clopen(X)$ a \demph{$\Clopen$-measure}. A (finitely or $\sigma$-)additive measure is \demph{finite} if the measure of the whole set is finite.
The next proposition immediately follows from the argument above and the isomorphism $\Clopen(\Sp(B))\cong B$ given by the Stone duality.
\begin{proposition}\label{prop:CorrespondenceAtFiniteLevel}
For any BwM $(B,\mu)$, the function $\Clopen(\Sp(B))\cong B \xrightarrow{\mu}[0,\infty)$ defines a finitely additive finite $\Clopen$-measure on $\Sp(B)$. Furthermore, this correspondence provides a bijective correspondence between BwM structures on a Boolean algebra $B$ and finitely additive finite $\Clopen$-measure on its Stone dual $\Sp(B)$.
\[
\begin{tikzcd}
\text{BwMs on a Boolean algebra $B$}\ar[r, leftrightarrow, "1:1"] & \text{(fin.add.) finite $\Clopen$-measures on its Stone dual $\Sp(B)$}
\end{tikzcd}
\]
\end{proposition}
\subsection{Extension via Hopf-Kolmogorov}
Then, we expand our consideration from $\Clopen(X)$ to $\Bcl(X)$ (\Cref{notation:BorelandVariants}).
% \begin{lemma}\label{lem:restriction}
% For any Boolean algebra $B$, and any finite $\Bcl$-measure $\mu\colon \Bcl(\Sp(B)) \to [0, \infty)$ on $\Sp(B)$, the restriction of $\mu$ to $B\cong\Clopen(\Sp(B))\subset \Bcl(\Sp(B))$ provides a BwM structure on $B$.
% \end{lemma}
% \begin{proof}
% This immediately follows from the definition.
% \end{proof}
\begin{proposition}\label{prop:UniqueExtensionToMeasure}\memo{This should be already known}
For any Boolean algebra $B$,
% the construction of \Cref{lem:restriction} provides
there is a natural one-to-one correspondence between BwM structures on $B$ and finite $\Bcl$-measures on its stone dual $\Sp(B)$.
\[
\begin{tikzcd}
\text{BwMs on a Boolean algebra $B$}\ar[r, leftrightarrow, "1:1"] & \text{($\sigma$-add.) finite $\Bcl$-measures on its Stone dual $\Sp(B)$}
\end{tikzcd}
\]
\end{proposition}
\invmemo{On the natrurality of the above correspondence, in terms of category theory}
Our proof requires the following classical fact.
\begin{fact}[Hopf-Kolmogorov extension]\label{fact:HopfKolmogorov}\memo{Possible citations include \cite[Exercise 1.3.5, 1.3.6]{cohn2013measure}}
A finitely additive measure $(X, B, \mu)$ admits an extension to $\sigma$-additive measure on the measureble space $(X, \sigma(B))$ if and only if it satisfies the $\sigma$-additivity in the following sense.
\begin{description}
\item[$\sigma$-additivity] For any mutually disjoint family $\{A_i\}_{i=0}^\infty$ of elements of $B$, if $\bigcup_{i=0}^\infty A_i$ happens to be an element of $B$, then $\mu\left(\bigcup_{i=0}^\infty A_i\right) = \sum_{i=0}^\infty \mu(A_i)$ holds.
\end{description}
Furthermore, the finitely additive measure space $(X, B, \mu)$ is finite, i.e. $\mu(X)<\infty$, then the extension of $(X, B, \mu)$ to $(X, \sigma(B))$ is unique.
\end{fact}
\begin{proof}[Proof of \Cref{prop:UniqueExtensionToMeasure}]
Due to \Cref{prop:CorrespondenceAtFiniteLevel} and \Cref{fact:HopfKolmogorov}, it suffices to prove that any finitely additive $\Clopen$-measure on $\Sp(B)$ is $\sigma$-additive. Let $\{A_i\}_{i=0}^\infty$ be a mutually disjoint family of elements of $B$ such that $A\coloneqq \bigcup_{i=0}^\infty A_i \subset \Sp(B)$ is an element of $\Clopen(\Sp(B))$. Since $\Sp(B)$ is compact, every closed (in particular, clopen) subset is also compact. Therefore, the equation $A\coloneqq \bigcup_{i=0}^\infty A_i$ provides a open cover of a compact subspace $A$, and hence there exists a finite open subcover. As the family $\{A_i\}_{i=0}^\infty$ is mutually disjoint, we conclude that all but finite components are empty subsets. Thus, the required equality $\mu\left(\bigcup_{i=0}^\infty A_i\right) = \sum_{i=0}^\infty \mu(A_i)$ is reduced to the finite additivity of $\mu$.
\end{proof}
\begin{remark}[Completeness in the above proof]
To the question of why $\sigma$-additivity can be proved from purely finite data, the following answer can be given.
For a Boolean algebra, its Stone dual is the space obtained by adjoining all points that exist virtually. In this sense, Stone duality can be regarded as a kind of existence theorem for points (or completeness theorem). What makes the crucial assumption of $\sigma$-additivity in the Hopf–Kolmogorov theorem trivial in our case is precisely an existence theorem asserting that for any equation of the form $A\coloneqq \bigcup_{i=0}^\infty A_i$, there exists a point refuting it. \invmemo{This should be directly related to the completeness theorem of classical propositional logic.}
\end{remark}
\subsection{Comparison with Borel measures}
\begin{corollary}
If a Boolean algebra $B$ is countable,
% then the construction of \Cref{lem:restriction} provides
there is
a one-to-one correspondence between BwM structures on $B$ and Borel measures on its Stone dual $\Sp(B)$.
\[
\begin{tikzcd}
\text{BwMs on a Boolean algebra $B$}\ar[r, leftrightarrow, "1:1"] & \text{($\sigma$-add.) finite Borel-measures on its Stone dual $\Sp(B)$}
\end{tikzcd}
\]
\end{corollary}
\memo{Taking their generating functions should be a continuous map. Is this written by ... some methods in functional analysis?}
\begin{fact}\label{fact:ProfiniteSpacesAreZeroDimensional}
Any profinite space is \textit{zero-dimensional}, i.e., every open subset is a sum of clopen subsets.
\end{fact}
\begin{proof}
\memo{This follows since every profinite space is a flitered limit of finite discrete topological spaces.}
\end{proof}
\begin{lemma}\label{lem:CountableComparisonBorelAndBorelClopen}
If a Boolean algebra $B$ is countable, then the $\Bcl(\Sp(B))$ coincides with the Borel $\sigma$-algebra $\B(\Sp(B))$.
\end{lemma}
\begin{proof}
As the Borel $\sigma$-algebra $\B(\Sp(B))$ is generated by open subsets $\Open(\Sp(B))$, it suffices to prove $\Open(\Sp(b))\subset \Bcl(\Sp(B))$.
The countability of $B$ and \Cref{fact:ProfiniteSpacesAreZeroDimensional} imply that every open subset is a sum of a necessarily countable number of clopen subsets.
\end{proof}
\memo{How about $2^{\omega_1} \cong \Sp(\text{free Boolean algebra generated by $\omega_1$})$?}
\begin{remark}[Countability assumption is necessary]
We cannot remove the countability assumption in \Cref{lem:CountableComparisonBorelAndBorelClopen}.
% Let $\beta$ be an ordinal with cofinality larger than omega (for example, $\beta =\omega_1$), and $B_\beta$ be the free Boolean algebra generated by $\beta$. Then, its Stone dual $\Sp(B_\beta)$ is (homeomorphic) to the product space $2^\beta\coloneqq\{f\colon \beta \to \{0,1\}\text{ function}\}$. Let $\B_b(2^\beta)$ be the set of all subsets $A\subset 2^\beta$ such that
% % $f\colon \beta \to \{0,1\}$ such that
% \[
% \text{There exists $\alpha\in \beta$ such that for any functions $f,g\colon \beta \to \{0,1\}$, $f\restriction_{\alpha}=g\restriction_{\alpha}$ implies $(f\in A \iff g\in A)$.}
% \]
Let $I$ be an uncountable set, and $B_I$ be the free Boolean algebra generated by $I$. Then, its Stone dual $\Sp(B_I)$ is (homeomorphic to) the product space $2^I\coloneqq\{f\colon I \to \{0,1\}\text{ function}\}$. We call a subset $A\subset 2^I$ \textit{$\aleph_0$-bounded} if there exists a countable subset $J\subset I$ such that $A$ is an inverse image of a subset of $2^{J}$ along the restriction function $2^I \twoheadrightarrow 2^{J}$. For any countable family of $\aleph_0$-bounded subsets $\{A_i\}_{i=0}^\infty$ witnessed by $\{J_i\}_{i=0}^\infty$, their countable sum or intersection is also $\aleph_0$-bounded witnessed by $\bigcup_{i=0}^\infty$. With easier observations on finite Boolean operations, we can conclude that the set of all bounded subsets, denoted by $\B_0(2^I)$, is a $\sigma$-additive family. Furthermore, one can check $\Clopen(2^I) \subset \B_0(2^I)$, which implies $\Bcl(2^I)\subset \B_0(2^I)$.
On the other hand, $\B(2^I)$ is not included by $\B_b(2^I)$, since the closed subset $\{\mathrm{const}_0\}$, consisting of the unique element of the constant function at $0$, is not $\aleph_0$-bounded. Therefore, we have proven $\Bcl(2^I) \subset \B_b(2^I) \not \supset \B(2^I)$, in particular, $\Bcl(2^I) \neq \B(2^I)$.
% Let $\B_b(2^I)$ be the set of all subsets $A\subset 2^\beta$ such that
% $f\colon \beta \to \{0,1\}$ such that
% \[
% \text{There exists a countable subset $I_0\subset I$ such that $A$ is an inverse image of a subset of $2^{I_0}$ along the restriction function $2^I \twoheadrightarrow 2^{I_0}$.}
% \]
\end{remark}
% \begin{todo}
% Extend it by the Caratheodory extension. Consider its $L^2$ space and Step functions.
% \end{todo}
\section{sandbox}
\printbibliography
\end{document}