千葉大学融合理工学府数学情報科学専攻数学・情報数理学コース 2020年8月実施専門 B11

标签：

Author

祭音Myyura (co-authored with GPT 6 Astra)

自然数は $0$ を含む。零関数、後者関数、射影、切り捨て減算 $\operatorname{sub}(x,y)=\max(x-y,0)$ を含み、合成と有界和・有界積

\Sigma f(x,\mathbf a)=\sum_{y<x}f(y,\mathbf a),\qquad \Pi f(x,\mathbf a)=\prod_{y<x}f(y,\mathbf a)

で閉じた関数を初等関数という。特徴関数が初等関数である述語を初等述語という。

\mu_{<}p(x,\mathbf a)=\min(\{y<x:p(y,\mathbf a)\}\cup\{x\})

が初等関数であることを示せ。

从零函数、后继函数、投影和截断减法出发，经复合、有界求和与有界求积得到初等函数。特征函数为初等函数的谓词称初等谓词。(1) 证明加法是初等函数；(2) 证明有界最小化 $\mu_<p$ 是初等函数，其中搜索不到时返回上界 $x$ 。

(1) 定数 $1$ は後者関数と零関数の合成で得られる。まず

\operatorname{mul}(x,y)=\sum_{u<x}y

は初等関数であり、

x+y=\operatorname{sub}\bigl(\operatorname{sub}((x+1)(y+1),xy),1\bigr)

なので加算も初等関数である。ここで $x+1,y+1$ は後者関数による。

(2) $\chi_p$ を $p$ の特徴関数とする。次の式が成り立つ。

\boxed{\mu_<p(x,\mathbf a)=\sum_{y<x}\prod_{z<y+1}\bigl(1-\chi_p(z,\mathbf a)\bigr)}.

最初に $p$ が真となる添字が $k<x$ なら、積は $y<k$ で $1$ 、 $y\ge k$ で $0$ となり、和は $k$ 。真となる添字がなければ全 $x$ 項が $1$ となる。右辺は切り捨て減算、有界積、有界和、合成で構成されるので初等関数である。