\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}