論理和と論理積の冪等律

暇つぶしに見て

2023.06.03

同値関係についてもう少し掘り下げてやろうと思います。

冪等律
1. 冪等律
2. 代入元理

冪等律

【冪等律】
数学において、冪等性（べきとうせい、英: idempotence、「巾等性」とも書くが読み方は同じ）は、大雑把に言って、ある操作を1回行っても複数回行っても結果が同じであることをいう概念である。

二項演算 “” を備えた集合 S について、S の元 s は $\displaystyle ss=s$
を満たすとき（”” に関して）冪等（べきとう、idempotent）であるという。特に、任意の中立元は冪等である。S の全ての元が冪等である場合には、その二項演算 “” は冪等（演算）であるという。例えば、集合の結びと交わりはどちらも冪等演算である。

【単項演算】
単項演算、つまり集合 X から X への写像 f が、X のいかなる元 x についても

$\displaystyle f(f(x))=f(x)$
を満たすとき、f は冪等であるという。これを写像の合成 ∘ で表すと

$\displaystyle f\circ f=f$
となる。つまり、X 上の冪等単項演算とは、X からそれ自身への写像全体のなす集合 XX における、合成 ∘ に関して（上記、二項演算に対する意味で）冪等な元のことである。
Wikipedia

A⇔A∧A⇔A∧A∧A…
1=1×1×1×…
という風にいくつAと∧があっても真理値は変化しないのが冪等性です。

自然演繹だと
1.A∧A(仮定)
2.A(除去)

1.A(仮定)
2.A∧A(結論)
こんな感じですかね。

A∧A⇔A

A∧A⇔Aなので

A∧A∧A⇔(A∧A)∧A⇔A∧A⇔A

またA∧A∧A∧A⇔Aなので

A∧A∧A∧A⇔(A∧A∧A)∧A⇔A∧A⇔A

前者が後者をA∧Aに変形する定義になっているので、数学的帰納法により
A⇔A∧A⇔A∧A∧A…
となります。

A∨A⇔A
も同じように
1.A∨A,A→A(仮定)
2.A(∨除去)

1.A(仮定)
2.A∨A(∨導入)

A∨A⇔A
なので

(A∨A)∨A⇔A∨A⇔A
となり、これも前者が後者を再帰的に定義しているので、無限回の証明を省けます。

代入元理

【代入元理】
代入原理はもう少し一般に、対象 ai, bj が、

$a_{1}=b_{1},\ a_{2}=b_{2},\ \ldots ,\ a_{l}=b_{l}$
であるならば、l 個の自由変数 x1, x2, …, xl を持ついかなる命題関数 P(x1, x2, …, xl) に対しても

$\displaystyle P(a_{1},a_{2},\ldots ,a_{l})\Leftrightarrow P(b_{1},b_{2},\ldots ,b_{l})$
が成り立つ、という形に述べることもある。これは命題関数 P(x) において自由変数 x が複数回現れるとき、命題 P(a) に現れる a の一部をそれと等しいもので置き換えてもよいことを含意している。なんとなれば、全ての i について ai = a で、いくつかの j について bj = b かつそれ以外の j について bj = a と置いてみるとよい。
Wikipedia

$a_1=b_1,a_2=b_2,a_3=b_3$
なら
$a_1+a_2+a_3=a_1+a_2+b_3$
と論理的な同値関係同士なら入れ替えることを認めている（推移律）ので、

A⇔A∨AとA⇔A∧Aから

A∧A⇔A∨A

が導出されます。