数理解析研究所講究録1093 巻 1999 年 1-41

多値論理代数における semirigidity 問題-自己双対関数について-

宮川正弘 (Masahiro Miyakawa)

筑波技術短期大学 (Tsukuba College of Technology)

概要

通部分を meet 演算としたとき,$A$$:=$$k>1$ の上の 1 つの置換 $s(X):Aarrow A$

に対して,$fb\mathrm{h}s$についての(1 変数) 自己双対関数

ここでは, 置換の任意の集合について, それぞれの置換の自己双対関数の共通部分が trivial な関数すなわち射影関数の集合 $J=\{f(x_{1}, \ldots, X_{n}):=x.\cdot|i=1, \ldots, n, n\in N\}$となる条件 (rigidity 条件と呼ぶ) を調べる。特に が素数の時, orbit-free な任意の 2 つの置換とについ$k$$s_{1}$$s_{2}$とその自己双対関数に共通に含まれる 1 変数関数か\sim (恒等写像) だけであることを示す。これは本て,$S_{1}$

ロンは」A を最小元,をなを最大元とする束す。有限集合 $|A|>2$ のときであり,$L_{A}$$|L_{A}|=2^{\mathrm{N}_{0}}[2]$この束の様子は十分には分かっていない。 しかし,$f(s(x))=S(f(x))$
を満たす関数といわれる。の上の全てのク$O_{A}$

多値論理関数 $\{f : k^{n}arrow k\}$ の集合において,$k=\{0, \ldots, k-1\},$$A$$S_{2}$

文中に述べる 1 変数への帰着の予想により,
互いに rigid であること, すなわち

$S_{1}$と$S_{2}$がこの束の極大元 (dual atoms,) すなわ
ちの直下の元は極大 maximal or precomplete
クロンと呼ばれ, 全て既知であり, 任意のクロンはいずれかの極大元の部分クロンとなっている。
関係を保存する関数. 極大元を記述するには次に述べるの概念が有用である。 を正の整数とすると
き,の部分集合 ( の元の 組の集合) を の上の 項関係と呼ぶ。 変数関数 $f\in O_{A}$ がを保存するとは, 各面を から任意に取って作成した
行 列の任意の行列 $X=[x_{ij}]$ に対して, 常に$=\mathrm{c}\mathrm{o}\mathrm{a}\mathrm{t}_{\mathrm{o}\mathrm{m}}\mathrm{e}\mathrm{S}$$O_{A}$$h$$A^{h}$$\rho$

$A$

$h$

$A$

$h$

$n$

$\rho$$\rho$$h$$S_{1}\cap S_{2}=J$$n$を示唆するものである.

$(f(x_{1}), f(x_{2}),$ $\ldots,$ $f(xh))\in\rho$semirigidity 問題について, 背景と既知の結果についてが (部分) 順序が成り立つことである。例えば,$\text{反対称的},$関係(すなわち反射的,推移的 2 項$\rho$も述べる。

$\leq$.

関係) のとき,$f$が$\leq$を保存するのは,関数, すなわち $x_{11}\leq x_{21},$1. 背景と問題$\ldots,$$f$が単調$x_{1n}\leq x_{2n}$のときとなるときである。与えられた関係を保存する関数の集合をで表す。
極大クロン.の上の極大クロンの全てを与える$f(x_{1})\leq f.(x_{2})$空でない基底集合 A を固定する. 正の整数 $n>0$に対してで $A$ の上の全ての変数演算ある
いは関数 (=写像 $f:A^{n}arrow A$) の集合をあらわし,とする. 例えば $1\leq i\leq n$ について,変数の 番目の射影と呼ばれる 変数演算$\mathit{0}_{A}^{(n)}$

$i$

$n$

は $e_{i}^{n}(a_{1}, \ldots, a_{n}):=a_{i}$ for all$e_{i}^{n}$$a_{1},$$\ldots,$$a_{n}\in A$

で定義される.の部分集合で, 関数の合成に関して閉じており,を含んだものはクロン clone と呼ばれる。 (クロンの定義や–般代数 (universal algebra)
で表す。

6 個の関係の族
はすべて$\mathcal{R}_{1},$$\mathcal{R}\epsilon$$\ldots,$が既知で,$A$の極大集合と表現でき(cf. [13]). 極大クロンの個数も既知である (cf.

る$\mathrm{P}\mathrm{o}1\rho(\rho\in R:=\mathcal{R}_{1}\cup\ldots \mathcal{R}_{6})$[12] . 全ての極大クロンの共通集合は束の最小元であるに–致する。 このことから, それではどれくらい極大クロンを集めれば共通部分が trivial 関数になるのかという問題 (後述) が生ずる。 $A$ の項関係 は, 全ての $a\in A$ に対して $(a, \ldots, a)\in\rho$$L_{A}$$)$$\text{」_{}A}$

クロン (閉じた集合). 全ての射影関数の集合を$J_{A}$$\mathrm{P}\mathrm{o}1\rho$

$A$

$n$

$O_{A}:= \bigcup_{n=1}^{\infty}o^{(n}A)$$n$$\rho$$O_{A}$$J_{A}$$h$$\rho$

例えば, 集合疏や. はクロンである。全ての定数.
関数 (すなわち $|imf|=1$ である $f\in O_{A}^{(n)}$ の集が成り立つとき反射的と呼ばれる。便宜上反射的な関係とそうでない関係に分けて取り扱う。
関係の集合の中で反射的でない関係はすべての単項関係, すなわち $\phi\neq\rho\neq A$ なる $A$ の部分合) の集合を集合とにおける意味付けについては文献 [6] や [13] にある)。
$O_{A}$で表す。射影関数と定数関数の和集
合 $K_{A:}=J_{A}\cup C_{A}$ を trivial 関数と呼ぶ。 trivial 関数もクロンをなす。包含関係を順序とし, 集合の共$c_{A}$$\mathcal{R}$$s$

を $A$ の上のある特殊な置換とするとき,: $a\in A$ } の形の 2 項関係の 2 種類だけである。最後の 2 項関係が本稿で扱う自己双対$s^{\mathrm{O}}:=\acute{\{}(a, s(a))$

2semirigid である。 が大きくなるとき$k$$k!$の全ての線形順序の中に占めるこのような線形順序の割合は $1/e$ (約 13%) に収束する [8]。

2. 1 変数 (unary) への帰着の問題$C$を universe $A$ の上のクロンとする。 $C$ の 1 変数関数の集合$C^{(1)}:=C\mathrm{n}o^{(\mathrm{i})}$をクロン $C$ の foun-dation と呼ぶ。以後 universe を示すインデクス
はを省略する (例えば,を示す).
次の補題は, 多値論理の semirigidity 問題はそのfoundation で, すなわち次数 (arity) を 1 変数に制限して考えて良いことを示している ([3], Prop 2-2$A$$\mathit{0}^{(1)}$

図 1: semirigid な 2 項関係 $G(|A|=6)$

および [10]関数に対応する。

semirigidity 問題.
に対して $K_{A}\subseteq Pol$$\rho$$A$の上の全ての反射的関係$\rho$が成り立つことは自明である。

そこで $A$ の上の反射的関係の集合 $\{\rho_{i} : i\in I\}$ につ

Pol が成り立つとき, その関係の集合を semirigid と呼ぶ。 が反射的でないとき

いて,$K_{A}= \bigcap_{i\in I}$$\mathrm{P}\mathrm{o}1\rho i$

同様に (は$J_{A}$を含むが定数関数$c_{A}$を」A で置き換えた)が成り立つとき, その関係の集合$\prime \mathcal{R}$。

が $A$ の上のクロン$C$の$K^{(1)}$foundation となるのは,$C=K$ のときであり, このときに限る.

$\rho_{i}$$K_{A}$

ぶ。 問題は$)$

Proposition 1. $|A|>2$ とする。 このとき$\rho_{*}$

は$O_{A}^{(1)}$は含まないので,$J_{A}= \bigcap_{i\in I}$

Pol

この補題巳|$2$のときは成立しない。 クロンは共通集合演算について閉じているので, 関係の集合$\rho_{i}$$R$を吻掘と呼の semirigid あるいは rigid な部分集$=$が semirigid になるための必要十分条件は $R$ の中$\{\rho_{i}\}$合を決定することである。
簡単のため, $R$ がただ –つの関係 からなる特別な場合についても, 関係 を保存する関数が trivial関数だけである場合に関係 を semirigid と呼ぶこ$\rho$$\rho$の全ての関係を保存する 1 変数関数の集合の共通部分が, 1 変数の trivial 関数, すなわち 1 変数定数関数と射影関数 (項等写像) となることである。この補題は $K$ を $K_{h-1}$ (高々 $h-1$ 値しか取らない関数のなすクロン) で置き換えて強化することができる$\rho$$[7]_{\text{。}ここに}$とにする。

semirigid な関係の例. $A:=6=\{0, \ldots, 5\}$の上の反射的な 2 項関係 (グラフ)$G$を図 1 に示す。 ここに $\iota_{A}:=\{(a, a)|a\in A\}$ (反射関係) である。 $G$ は semirigid である。
関係 $G$ は高さが 1 の次の二つの部分順序関係$=$$\{(\mathrm{o}, 1), (2,3), (4,5)\}\cup\iota A$$\leq’$$=$$\{(1,2), (1,4), (3,0), (5,0)\}\cup\iota_{A}$$G=\leq\cup\leq^{J}$の部分順序集合の組

も semirigid であるこされている。

例えば, $k>3$ のとき, 自然な線形順序関係 $0<$$\ldots<k-1$

線形順序$\preceq$.

Proposition 1$l^{}$rigidity についても同様に 1 変数に還元できるであろうか? $K$ の代わりに」と置き換え
それでは,たとき, この命題は –般には成立しない。すなわち,

Proposition 2. 有限集合 $A(|A|\geq 2)$ の上の clone$C$について次は成立しない$C^{(1)}=J^{(1}$:)( $=\{e\}$ :恒等写像) then.

$C=\text{」}$と分解される。これより, 2 つ$\{\leq, \leq^{J}\}$とが導かれる。
高さが 1, 線形, ダイアモンド形の順序関係についての semirigidity 問題はそれぞれ [ $1|,[51,[81$ で研究$1,$’$h=2\delta^{\backslash }$帰着する。

ifにより,$K_{h-1}:=\{f\in O:|imf|\leq h-1\}\cup\text{」}$$=$$\{(0,1), (1,2), (2,3), (3,0), (1,4), (4,5), (5,2)\}\cap\iota_{A}$$\leq$

for,$1<h\leq k:=|A|\text{で},$と対になったとき semirigid になるが必ず存在する。例えば, $k=4$ の場

合 $1\prec 3\prec 0\prec 2$ だけが$0$.

$<1<2<3$ との対で証明。例えば, 自然な順序関係 $0<1\ldots<k-1$$(|A|=k)$ を用いて定義される演算$\wedge$で生成されるクロンは上の命題の反例になっている。 ここに,とする。口

$x \wedge y:=\min(x, y)$

しかしながら, 一般には成立しない上記命題は,本稿でで考える自己双対関数のなすクロンについては成立しているものと予想される (本稿の作成時点では証明は得ていない) 。本稿の最後にこの問題を未解決問題として定式化する。

33. 自己双対極大クロンで表す。

ここでは semirigidity 問題は rigdity 問題に帰着する。亀を $A:=k:=\{0, \ldots , k-1\}$ の上の置換の集合 (対称群) とする。置換 $s\in S_{k}$ について二項関係$s^{\mathrm{O}}=\{(x, s(x))|_{X\in}k\}$と置く。 Pol

1 変数自己双対関数$s$Lemma 4. 1 変数関数,’ .

$s$のような置換$[a_{j\dot{.},\prime:}a_{i,0}$’$.\cdot$$.,$$a_{j_{*},r:+p}.a_{i,p-1}-1(\mathrm{m}\mathrm{o}\mathrm{d} p)]$.

$k=p\cdot\ell$$p$$\{s, s^{2}, \ldots, s^{k}\}$$s$$i$についての自己双対関数と$s^{\square }$$s$がについて自己双対になるのは, 各 $i\in\{1, \ldots,\ell\}$ について 成分が$f$.

が極大クロンとなるのは,,素数とするとき, 置換 が長さ の 個のサイクルの積となることが必要十分である。本稿では, こ呼ばれる。Polは成分ごとに次のように表現できる。

$.$

は置換

$s^{\mathrm{O}}$$f$を固定する。置換を$s$$\ell$$P$$s$の orbit と呼ぶ,について, 集合
ここにと表現できることが必要十分である。 ここに,
$j_{1},$$\ldots,$$j_{l}\in\{1, \ldots, l\},$とする。

$r_{1},$.

$\ldots,$$r_{l}\in\{0, \ldots, p-1\}$$s^{k}=e$(恒等写像) である。 2 つの置換はその orbit か$e$のみを共有するとき orbit-free と呼ぶ。次の補題は既すなわち $f$ は各サイクルをサイクルの上に$s$を保存しながら写像する.
これより, 以下の系を得る。

知である。

Lemma 3. (cf. [4]) $s’\in S^{k}$ について, PolPolとなる必要十分条件は$s,$$s^{\square }=$$s^{:}=s’$

Corollary 5. について自己双対な 1 変数関数の個数は次式で与えられる。
$s$$s^{\mathrm{O}’}$for some $i\in\{1, \ldots, k-1\}$$|(^{\mathrm{p}_{\circ]}}s^{\mathrm{o}})^{(}1)|=k^{\ell}$.

(3)

である。

Corollary 6. について自己双対な 1 変数全射関数の個数は次式で与えられる。
$s$すなわち, 2 つの置換は orbit-free のとき, かつそのときのみ異なる極大クロンを誘起する。
$k$

$=$

$l\cdot P$(素数,$p$$\ell$$\geq$1) とし,$\{a_{1,0}, \ldots, a_{1,p1}-, \ldots.’.a\ell,0, \ldots, a_{t,p-1}\}$に置換$s(a_{i,r})$

$s$

$k$

$|(\mathrm{P}\mathrm{o}1s^{\mathrm{o}})(1,\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{o})|=\ell!p^{t}$$=$と置いたとき

Theorem 7.

が素数のとき, 自己双対極大クロンの任意の対, すなわち orbii-free な置換で誘起さ$a_{i,r+1(p)}.\mathrm{m}\mathrm{o}\mathrm{d}$$(i=1, \ldots,\ell;r=0, \ldots,p-1)$.

$(\mathrm{m}\mathrm{o}\mathrm{d} p))$for $j=0,1,$$e$$\ldots$.

$\ldots,$ $a_{1}.,-$

$i$

$s$

$\min\{a_{i},0, \ldots, a_{i,p-1}\}$

1 変数関数$f$

定義から全ての $x\in k$ について$s$$\{s^{\square \mathrm{O}}, s^{J}\}$

次の例は, 上の条件が十分条件ではないことを示している。

$s(f(x))=f(s(_{X}))$ .

(1)

例. 置換 8and $s’$ がそれぞれ次で与えられるものとする。

が成り立つことと同値である。 これより
$f(a:,r)=S^{\gamma}(f(ai,0))(r=0, \ldots,p-1;i=1, \ldots,\ell)$$s=bs’=$ .

.

(2)

.
$i$

Corollary 8. 二つの置換 と I が成分を共有すれは rigid ではない。

ば,と正規化して良い。

か s について自己双対であるとは,を得る。 関数 $f$ ののみを共有する。

次の結果も同じ補題から得られる。

が成り立つ。集合$p1(s$} の サイクル) の各元は により巡回置換されるので, $a_{i,0}=$$\mathrm{t}a_{i,0},$$k$れる任意のクロンの対の 1 変数部分集合は恒等写像をみたしているとする。 このとき$\theta^{\dot{\prime}}(a_{i},r)=a_{i,t+j}$(4)

補題 4 から次の結果が得られる。

が$=$.

サイクルへの制限 ( $=i$ サイク

このとき 置換

ルから $k$ の写像) を $f$ の$i$成分と呼び,$\cdot$.

で与えられる関数$f=$の両方に属する。

$f$はPol
次の例は長さが異なる 2 つの置換の間でも恒等写像以外の置換を共通に含むことがあることを示して$s^{\mathrm{O}}$いる。と Pol$s^{l}\mathrm{o}$4\"uber
Funktionenalgebren[4] D.Lau.
1,Monoendlichen Mengen Bandgraph, Universit\"at Rostock, pp. 592,

例. 2 つのクロン

Pol

1998.
は trivial 関数でない 1 変数関数

A.Nozaki,
M.Miyakawa,[5] V.Laskia,
Semi.Rosenberg.
G.Pogosyan,
rigid sets of diamond orders, Discrete
Mathematics 156:277-283, 1996.
$\mathrm{I}.\mathrm{G}$でいる。の乏個のサイクルからなる全ての置換からなる集合とする (k=p\sim )。このとき次が未$\Sigma$を素数長$P$解決である。,

未解決問題 1(1 変数帰着の予想). 81,$s\gamma n\in\Sigma$$\ldots,$.Maltsev. Post’s Iterative Algebras(Russian), Monograph, Novosibirsk StateUniversity, 1976.
[ M.Miyakawa, A.Nozaki, G.Pogosyan,.Rosenberg. Semirigid sets of central
relations over a finite domain, Proc. 22thInternational Symposium on MultipleValued Logic, 300-307, May, 1992.
[8] A.Nozaki, M.Miyakawa, G.Pogosyan,.Rosenberg. The number of orthogonal permutations, Europ. J. Combinatorics 16:71-85, 1995.

[6]$\mathrm{A}.\mathrm{I}$$\eta$について$\mathrm{I}.\mathrm{G}$$(\mathrm{n}^{m}\mathrm{P}\dot{\mathrm{a}}=1i\mathrm{o}1_{S}0)^{()}1=\{e\}$(恒等写像)

が成り立つとき$\bigcap_{i=1}^{m}\mathrm{P}\circ 1S^{\square }i=J$(射影関数)$\mathrm{I}.\mathrm{G}$が成り立つ。

未解決問題 2.
$s_{1)}\ldots,$$S_{m}\in\Sigma$

が$\{s_{1}^{\mathrm{O}..\mathrm{O}},., s_{m}\}$を特徴づける。

rigid になる.

G.Pogosyan, M.Miyakawa,.Rosenberg. Semirigid sets of quasiInternational
linear clones, Proc.
Symp. on Multiple-Valued Logic, Sacramento, 1993, 105-110.

[9] A.Nozaki,$\mathrm{I}.\mathrm{G}$$\mathit{2}\mathit{3}rd$

4. おわりに多値論理関数における semirigidity 問題を概観し,自己双対関数の rigidity 問題に新しい結果を与えた。
また, 未解決問題を示した。

[10]$\mathrm{P}.\mathrm{P}$.P\’alfy. Unary polynomials in algebra

I. Algebra Universalis 18:162-273, 1984.
.Kalu\v{z}nin. Funktionen[11] R.P\"oschel,und Relationen Algebren, Ein Kapitel der$\mathrm{L}.\mathrm{A}$

謝辞. Prof IG. Rosenberg には有益な助言をいただきました。

Diskreten Mathematik (German), Math.
Monographien B. 15, VEB Deutscher,1979.
Verlag . Wissen., Berlin,
Also Math R. B. 67, Birkh\"auser Verlag,Basel&Stuttgart, 1979.
$\mathrm{p}\mathrm{p}.2_{\acute{0}9}$$\mathrm{d}$参考文献
M.Miyakawa,[1] J.Demetrovics,
D.Simovici,.Rosenberg,
I.Stojmenovi\v{c}. Intersections of isotone clones on a finite set, Proc. 20thInternational Symp. on Multiple- Valued
Logic; Charlotte, 248-253, 1990.

[12]$\mathrm{I}.\mathrm{G}$.Mu\v{c}nik. Existence of k[2] Iu.I.Ianov,valued closed classes without a finite basis (Russian), Dokl. Akad. Nauk. SSSR
$127(1):44-46$ , 1959.
$\mathrm{A}.\mathrm{A}$[3] F.L\"anger, R.P\"oschel. Relational systems
with trivial endomorphisms and polymorphisms. J. Pure Appl. Algebra $32(2):129-$142, 1984.

.Rosenberg. The number of maximal
closed classes in the set of functions over afinite domain, J. Combinat. Theory, Ser.
14:1-7, 1973.

$\mathrm{I}.\mathrm{G}$$A$[13].Rosenberg. Completeness propertiesof multiple-valued logic algebra, in Computer Science and Multiple-valued logic,. Rine ed.),Theory and Applications (North-Holland, 2-nd revised ed., 144-$\mathrm{I}.\mathrm{G}$$\Delta$$\mathrm{D}.\mathrm{C}$$\mathrm{s}$186, 1984.
[14] G.Tard\’os. A maximal clone of monotone
operations which is not finitely generated,
Order 3:211-218, 1986.