研究有限域上连续逻辑的收敛性,发现复杂公式可简化为无聚合函数的形式。
A convergence law for continuous logic and continuous structures with finite domains
- 在有限域上定义连续逻辑与概率分布,用密度函数刻画关系值
- 证明任意公式在极限下等价于无聚合函数的简单形式
- 揭示连续逻辑的收敛规律,适合逻辑与概率交叉研究者
我们研究定义在有限域 $[n] := \{1, \ldots, n\}$ 上的连续关系结构,采用取值于单位区间的多值逻辑 $CLA$,其包含连续连接词和连续聚合函数。该逻辑涵盖经典有限结构上的一阶逻辑。对每个关系符号 $R$ 及与其类型匹配的恒等约束 $ic$,我们关联一个连续概率密度函数 $μ_R^{ic} : [0, 1] \to [0, \infty)$。考虑定义在连续结构集合 $\mathbf{W}_n$ 上的概率分布,使得对任意 $R$、$ic$ 与满足 $ic$ 的元组 $\bar{a}$,$R(\bar{a})$ 的值分布由 $μ_R^{ic}$ 决定,且与其他关系或元组独立。在此设定下,我们证明:$CLA$ 中任一公式在渐近意义下等价于不含任何聚合函数的公式。由此推出 $CLA$ 的收敛律:若 $φ \in CLA$ 无自由变量,$I \subseteq [0, 1]$ 为区间,则存在 $α \in [0, 1]$,当 $n \to \infty$ 时,$φ$ 的值落在 $I$ 中的概率趋于 $α$。
原文摘要 · Abstract (English)
We consider continuous relational structures with finite domain $[n] := \{1, \ldots, n\}$ and a many valued logic, $CLA$, with values in the unit interval and which uses continuous connectives and continuous aggregation functions. $CLA$ subsumes first-order logic on ``conventional'' finite structures. To each relation symbol $R$ and identity constraint $ic$ on a tuple the length of which matches the arity of $R$ we associate a continuous probability density function $μ_R^{ic} : [0, 1] \to [0, \infty)$. We also consider a probability distribution on the set $\mathbf{W}_n$ of continuous structures with domain $[n]$ which is such that for every relation symbol $R$, identity constraint $ic$, and tuple $\bar{a}$ satisfying $ic$, the distribution of the value of $R(\bar{a})$ is given by $μ_R^{ic}$, independently of the values for other relation symbols or other tuples. In this setting we prove that every formula in $CLA$ is asymptotically equivalent to a formula without any aggregation function. This is used to prove a convergence law for $CLA$ which reads as follows for formulas without free variables: If $φ\in CLA$ has no free variable and $I \subseteq [0, 1]$ is an interval, then there is $α\in [0, 1]$ such that, as $n$ tends to infinity, the probability that the value of $φ$ is in $I$ tends to $α$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。