☆集合と論理
◎集合
◆集合
set
※ものの集まり。特定のものが特定の集合に属しているか否か、数学的に厳密に判断できなければならない。
※すべての要素を列挙したリストがあればそれを集合Ｗとして、ある概念は、集合Ｗの要素のことである、と定義できる。
※要素が無限にある場合は、条件式により集合Ｇを定義し、そこである概念は、集合Ｇの要素のことである、と定義する。
＿◇集合の要素もしくは元
element
ｘ∈A
＿ ものxが集合Aの要素であることを表す
＿◇外延 denotoation
ある概念にあてはまるものの集合を、その概念の外延という。
＿◇内包 connotation
ある概念にあてはまるものがみたすべき性質を内包という
※内包を既定して概念を定義するのを内包的定義、外延を既定して概念を定義するのを外延的定義（集合論的定義）という
※集合(set)とは、ものの集まりのことである。ただし、特定のものが特定の集合に属しているかどうかは、数学的に厳密に判定できなければならない。
＿◇有限集合 finite set
要素の数が有限であるような集合。要素を網羅することにより記述できる。
※n個の要素x1,…,x2からなる有限集合を
{x_1,…,x_n}
とかく。
＿◇無限集合 infinite set
要素の数が無限であるような集合。
※一般に
{ x | … }
によって「…」を満たすようなｘの全体からなる集合を現す。この記法は無限集合に対しても用いることができる。
※無限集合には「濃度」の異なる集合が無限にある
＿◇集合の等しさ
集合Ａと集合Ｂが等しい、すなわち
Ａ＝Ｂ
であるとは、ＡとＢが同じ要素からなる集合であることを意味する。
⇒外延的な等しさ
extensional equality
＿◇空集合 empty set
要素が一つもない集合を空集合という。
要素が一つもない集合は互いに等しいから、空集合は一つだけ存在する。
空集合をΦで表す。
＿◇濃度
※無限集合を扱う場合、集合を比べるのに使われる概念
２つの集合の要素を１対１のペアとできれば、２つの集合の濃度は等しい
＿◇部分集合
subset
集合Ａの要素が集合Ｂの要素にもなっているとき、ＡをＢの部分集合という。
Ａ⊂Ｂ
とかく
※Ａ＝ＢのときもＡ⊂Ｂはなりたつ
※Ａ＝Ｂが成り立つことと、Ａ⊂ＢかつＢ⊂Ａは同値
{a∈A| … }
によって、…を満たすようなaからなるＡの部分集合を表す
※空集合は任意の集合に含まれる
※Ａ＼Ｂで、集合Ａに入っているが集合Ｂには入っていないような要素の集合を表す。特にＢ⊂ＡのときＡ＼ＢをＡ－Ｂと書く
＿◇集合の大きさ
集合Ｙが集合Ｘよりおおきいとは、Ｘの要素にＹの要素を対応させるどんな関数でも、Ｙのすべての要素をおれなく対応させることはできない
◆結びと交わり
＿◇結び union
ＡとＢの結びとは、ＡとＢの両方の要素からなる集合のことである。
＿ Ａ∪Ｂ
＿ Ａ∪Ｂ={x|x∈Ａ または x∈Ｂ}
＿◇交わり intersection
ＡとＢの交わりとは、ＡとＢの両方に共通の要素から成る集合のことである。
＿ Ａ∩Ｂ
＿ Ａ∩Ｂ={x|x∈Ａ かつ x∈Ｂ}
＿◇集合における「互いに素」
2つの集合が交わりを持たない (disjoint) あるいは互いに素（ mutually disjoint）とは、それらが共通の元を持たないことを言う。
※Ａ∩Ｂ＝Φのとき
◆直和と直積
＿◇直積
direct product
二つの集合 A, B に対し、
A × B = {(a,b) | a ∈ A, b ∈ B}.
で定義される集合を A と B の直積集合とよぶ。ここで (a,b) は、順序対を表す。つまり一般には (a, b) ≠ (b, a) である。これらは、たとえ a, b (a ≠ b) がともに A にも B にも属していたとしても異なるものとして区別される。したがって、A × B と B × A は集合として相異なる。
※Ａ×Ｂ＝｛<x,y>|x ∈ Ｘ, y ∈ Ｙ}.
※<x,y,z> = <x,<y, z>>
Ａ×Ｂ×Ｃ＝Ａ×（Ｂ×Ｃ）
直積演算を 2 つの集合だけでなく、複数個の集合に対しても拡張することが出来る。n 個の集合 A1, …, An に対する直積集合を、
Π(i=1;n) ai = {(a1,…,an)|a1 ∈ A1,…,an ∈ An}
と定義する。Π(i=1;n)Ai を A1 × … × An とも表す。
※Ａ＾ｎ
＿◇直和
direct sum
集合の直和（disjoint union, 非交和）とは、共通部分が空集合であるような二つの集合の和集合。（互いに交わらない）
※直和 direct sum
※Ａ＋Ｂ＝｛<0,x>|x ∈ Ａ}∪｛<1,y>|y ∈ Ｂ}
0,1は要素がどちらの集合から来たかを区別するためのものである。
◆関数空間とベキ
集合Ａと集合Ｂに対して、ＡからＢへの関数の全体から成る集合をＢ＾ＡもしくはＡ→Ｂとかく
Ａ→Ｂを関数空間(function space)という
※Ａ→Ｂに属する関数fとgはＡの任意の要素aに対して
f(a)=g(a)
となるとき、そして、そのときに限り等しいものとする。
※外延的等しさ extensional equality
※集合Ａに対して、Ａの部分集合の全体から成る集合をＡのべき集合(power set)といい
２＾ＡもしくはＰ（Ａ）
と書く。
＿◇特性関数 (characteristic function)
集合”２”を２={0,1}と定義する。Ｓを２＾Ａの要素、すなわちＳをＡの部分集合としたとき、Ａから２への関数
＿χs(a)= 1 … a ∈ Ｓ
＿ 0 … a ∈／ Ｓ
※1,0は逆であってもよい。部分集合Ｓの特性関数
◆集合族、Π、Σ
＿◇集合族
family of sets
Iを集合とする。Iの各要素iに集合Aiが対応しているものとする。
i→Ai
はIの要素に集合を対応させる対応。このような対応を集合族という。
{Ai}_i∈I
と書く
※集合I
添数集合(index set)
※集合族に対してその結び∪（Aiの要素を集めてできる集合）、交わり∩（どのAiにも属している要素の集合）を定義できる
※集合Π
集合族
＿ {Ai}_i∈I
の結び
＿ U=∪[i∈I]Ai
とおき、fをIからUへの関数とする。
＿ i∈Iに対してf(i)∈Uが成り立つ
関数f∈U~Iの内でi∈Iに対して必ずf(i)∈Aiがなりたつようなもののみを考え、
そのような関数全体からなる集合を
＿ Π[i∈I]Ai
I={0,1,2}とするとΠ[i∈I]Aiの要素は
＿ f(0)∈A0,f(1)∈A1,f(2)∈A2
を満たす。逆にf(0)∈A0, f(1)∈A1, f(2)∈A2を定めればΠ[i∈I]Aiに属する関数f
が定まるので、関数fと三組<f(0), f(1), f(2)>を同一視することにより
＿ Π[i∈{0,1,2}Ai = A0 x A1 x A2
※集合Σ
Σ[i∈I]Ai = {<i,x> | i∈I, x∈Ai }
I={0,1,2}とすると
Σ[i∈I]Ai = A0 + A1 + A2
◆有界な集合の上限(sup)と下限(inf)
定義：集合Mに対し、ある数Kが存在して、Mに属する点ｘに対し、つねにｘ＜Kが成り立つとき、Mは上に有界な集合であるという。またある数Lが存在して、Mに属する点ｘに対し、常にL＜ｘが成り立つとき、Mは下に有界な集合であるという。
定理：Mを上に有界な集合とする。このとき次の性質をみたす実数αが存在する。
(i)x∈Mならば、x≦α
(ii)どんなに小さい正数εをとっても
α-ε<x~
をみたすx~∈Mが存在する
※αをMの上限という
※上に有界な集合Mに対し、その上限を
supM
と表す。 (supremum)
※下に有界な集合Nに対しては、その下限を
infN
と表す。(infimum)
◎形式論理、記号論理
数学の証明の中で使われている推論規則を形式化し、定理や推論規則に関する一般てきな性質を調べるのが形式論理もしくは記号論理である。
◆命題論理
propositional logic
命題を単位とした推論を形式化した論理。それぞれの命題の内部構造にまでは立ち入らない。
＿◇命題
proposition
正しいか間違っているかのどちらかであるはずの主張もしくは文
※真偽値 truth value
真(true)または偽(false)
真Ｔ
偽⊥
命題Ｐが正しい Ｐ＝Ｔ
命題Ｐが間違っている Ｐ＝⊥
＿◇論理記号
logical symbol
※連言 conjunction
命題「ＰかつＱ」
Ｐ∧Ｑ
命題Ｐ∧Ｑは、どちらも正しいとき、そのときに限り正しい。
※論理記号∧は、真偽値に対する２項演算として可換的かつ結合的である
※選言 disjunction
命題「ＰまたはＱ」
Ｐ∨Ｑ
命題Ｐ∨Ｑは、どちらかが正しいとき、そのときに限り正しい。
※論理記号∨は、真偽値に対する２項演算として可換的かつ結合的である
※∨は∧よりも結合力が小さいとする
※否定 negation
￢Ｐ
※￢は∨や∧よりも結合力が強いとする。
※含意 implication
「ＰならばＱである」という命題を
Ｐ⊃Ｑ
とかく
Ｐ＝ＴかつＱ＝ＴならばＰ⊃Ｑ＝Ｔである
Ｐ＝Ｔ、Ｑ＝⊥ならばＰ⊃Ｑ＝⊥である
※Ｐ＝⊥の場合、Ｑの真偽に関わらず
Ｐ⊃Ｑ＝Ｔ
「ＰならばＱである」という形の論理は定理の前提であるＰが成り立たなければ常に正しい
Ｐ⊃Ｑ＝￢Ｐ∨Ｑ
が成り立つ
※⊃は∨や∧よりも結合力が弱いとする
※同値命題 equivalence
「ＰならばＱであり、ＱならばＰである」
Ｐ←→Ｑ
Ｐ←→Ｑ＝（Ｐ⊃Ｑ）∧（Ｑ⊃Ｐ）
※←→は⊃より結合力が弱い
※命題変数 propositional variable
※命題変数、真偽値、論理記号を組み合わせて命題論理式が作られる。
propositional formula
＿◇トートロジ
tautology
※命題変数にどのような真偽値の組み合わせを代入しても必ず真となるような命題論理式
※排中律 (excluded middle)
ＰまたはＰでない
Ｐ∨￢Ｐ
⇒典型的なトートロジ
※ＡとＢを命題論理式としたとき Ａ⇔Ｂがトートロジであるとき、ＡとＢは同値であるという equivalent
※Ａ⇔Ｂがトートロジであるならば、ＡとＢの中の命題変数にどのような真偽値の組み合わせを代入してもＡとＢの真偽値は等しい
※どのような真偽値の組み合わせを代入してもＡとＢの真偽値は等しいならばＡ⇔Ｂはトートロジである。
※Wangのアルゴリズム
トートロジの判定
＿◇シークエント
sequent
A1,…,AmとB1,…,Bnを命題論理式の並びとしたとき
A1,…,Am→B1,…,Bn
をシークエント、矢式、連鎖、式という
A1,…,Am 前提部 antecedent
B1,…,Bn 結論部 succedent
m=0, n=0でもよい。とくにm=n=0の場合は→のみかかれる
m=0の場合は前提部は真
n=0の場合は結論部は偽
→は Ｔ⊃⊥ を意味するがこれは、⊥と同値
※シークエントの意味
A1∧…∧Am ⊃ B1∨…∨Bn
→シークエントがトートロジであるばあい、どのような真偽の組み合わせを代入してもＡのどれかが偽となり、Ｂのどれかが真となることを意味する
→トートロジでなければ、適当な真偽の組み合わせの代入により、Ａの全てが真、Ｂの全てが偽となることを意味する
※イニシャル・シークエント
initial sequent
初式
⇒命題変数のみからなるシークエントで、前提部と結論部の両方に同じ命題変数が現れるもの
⇒イニシャル・シークエントはトートロジ
※任意のシークエントは
Γ→Δ
と書くことができる
※「、」をつかってΓの後ろに命題論理式Ａを追加した並びを表す
Γ、Ａ
＿◇推論規則
inference rule
既にトートロジと分かっているシークエントから、新たなトートロジであるシークエントを得る規則
※推論規則の形
＿ 前提１。。。前提ｎ
＿ ――――――――― （規則の名前）
＿ 結論
※前提(premise)
シークエント
※結論(conclusion)
シークエント
※すべての前提がトートロジであるとき、結論もトートロジとなる
※イニシャルシークエントから始めて推論規則を有限回的用して得られるシークエントはすべてトートロジである
⇒イニシャルシークエントから始めて推論規則を有限回的用して得られるシークエントを証明可能(probable)であるという
⇒証明可能なシークエントはトートロジである
⇒そのようなとき推論規則の全体は健全(sound)であるという
＿◇完全性
任意のトートロジであるシークエントが証明可能であるとき、
推論規則の全体は完全(complete)であるという。
◆述語論理
＿◇ストラクチャ
＿◇モデル
＿◇Herbrand領域
◎証明、論法
◆∀と∃
「∀」は数学的には「任意」という。この記号は単独で使うことはなく「∀ｘ」といったように使う。意味は「すべてのｘが」。
「∃」は「特定の・・・」といった意味になる。「∃ｘ」といったように書くと意味は「あるｘが」となる。
ｆ（∀ｘ）＝０だとｘがなんであれ、ｆ（ｘ）＝０ということになり、ｆ（∃ｘ）＝０だとｘがある特定の値を持つとｆ（ｘ）＝０になる。
●∴と∵
∴は「よって」，「したがって」という意味がある。
∵は「なぜならば」という意味がある。
◆数学的帰納法
Mathematical Induction
「数学的帰納法は自然数の性質というよりも、数学的帰納法が使えるシステムが自然数そのものなのである」
—芹沢正三
やってみればわかるように
「n=k-1のときを仮定してn=kの場合を証明する」方式にしておいた方が、結論の式がそのまま現れてずっと計算しやすい
—芹沢正三
◆無限降下法
※数学的帰納法の一種
証明する対象が無数にある場合、ひとつについてだけ証明して、他の数に対してもその証明法で証明できることをあきらかにする。
◆ε-δ論法
関数f(x)の極限値が存在するときに、関数f(x)が極限に近づく過程において、f(x)の値が極限値に近づいたり、遠ざかったりすることもありえる。そのふらつきがどんどん小さくなることを正確に記述するもの。
どんな正数εを指定されても、適当に正数δを選ぶと、次の条件が成り立つ。
0 < | x – a | < δを満たすどんな x についても
| f(x) – b | < ε
◆背理法
例）√２が無理数であることの証明
①√２が有理数であると仮定する
②√２=p/q （p,qは互いに素）とおける
③両辺にqをかけて分母を払う
√２×q=p
④両辺を二乗する。
2q^2=p^2
上の式からp^2は２の倍数であることが分かるので、pも２の倍数である。
⑤上からp=2k（kは整数）と書ける
⑥4k^2=2q^2とおけるので、両辺を２で割ると
2k^2=q^2となる
⑦上からq^2は２の倍数であることがわかり、qも２の倍数となる。
⑧しかし、pとqは互いに素なので、これはありえない。よって、√２が有理数であるという仮定が誤っていたことになる。
よって、√２は無理数である。（証明終了）
◆対角線論法
例）
すべての自然数にすべての実数を対応させることはできない
[証明]
自然数に実数を対応させる任意の関数をhとして、関数値h(n)を十進小数で表し、nの小さい順にならべる。（実際の右辺はどのように数字が並んでいてもよい）
右辺の小数の、小数点より左は無視して、小数点以下の桁数字、特にh(n)の小数点以下n桁目に注目する。この対角線状にならぶ桁数字を並べて先頭に0と小数点をつけると、また一つの実数を作ることができるが、そこで、先頭の0を除き、4以下は7に、5以上は2に書き換える。
この新たに生成した実数は、h(n)のどれとも異なるので、実数側に対応もれがある。
※公理で証明しているのか直感で当たり前と思っているのか
点の代わりにビールジョッキ、直線の代わりに椅子、という言葉を使って見る
公理「２つの相異なるビールジョッキＰ，Ｑに対して、その２つのビールジョッキを通る椅子ＰＱがただ一脚だけ存在する」
命題「相異なる３つのビールジョッキＰ，Ｑ，Ｒがあって、椅子ＰＱはビールジョッキＲを通らないとする。すると、椅子ＱＲはビールジョッキＰを通らない」を証明する
証明：
◆コンピュータによる証明
①証明すべきことがらを、反例となりうる有限個のケースからなるリストに還元する
②それをひとつずつ消去していく
◎パラドックス
◆パラドックス
悪しき循環(vicious circle)
病的な文(pathological sentence)
①数学の中で使う分は、その文の中の全ての語句が、その意味を確定できるものでなければならない
②数学の中で使われる分は、自分自身を直接または間接に指示する語句を含んではならない
※
①集合Ｘを確定するためには、その全ての要素が確定していなければならない
②集合Ｘの要素の中に、集合Ｘが確定しないと決まらないものがあってはならない
＿◇ラッセルの階型理論(type theory)
①基本的な対象の集合をＤとする（１階の対象）
Ｄの上で次のような集合だけを公認する
②Ｄの要素の集合（２階の対象）
③２階の集合を要素とする集合（３階の対象）
。。。以下ｎ階の対象というが、ｎは有限でなければならない。
＿◇超言語、メタ言語、metalanguage
２階以上の言葉の体系。もとの言語を対象言語という。
◆カントルのパラドックス
カントルの証明
Ｘの全ての部分集合の集合をＹとすると、ＹはＸより大きい。
よって、全てのものの集合Ｓを考えると、これより大きなものは存在しない筈なのに、それより大きい集合Ｙが存在してしまう筈だが、そんな集合はありえない。
◆ラッセルのパラドックス
「自分自身を要素として含まないような集合」を全部集めた集合をＲとする。この定義から当然、任意の集合Ｘについて
＿ ＸがＲの要素である。※１
＿ とは
＿ ＸがＸの要素でない。※２
＿ のと同じことである。
では、Ｒ自身は、この集合Ｒの要素だろうか、※１と※２のＸのところにＲをあてはめると
＿ ＲがＲの要素である
＿ とは
＿ ＲがＲの要素でない
のと同じことである、となってしまい矛盾が発生する。
◆ウソつきパラドックス（エピメニデスのパラドックス）
クレタ人のうちのある預言者が
「クレタ人はいつもウソつき」
といっているが、この非難はあたっている
（新約聖書「テトスへの手紙」第１章）
◆視覚的パラドックス
＿◇ペンローズの三角形
◆パラドックスではないがそう呼ばれるもの
＿◇バースデーパラドックス
Birthday paradox
あるクラスで誕生日が一致する組が一組以上ある確率
数学的にはパラドックスではないが、以外な結果であるためにパラドックスと呼ばれる。
異なるｍ個の数から、重複を許してｋ（≦ｍ）個の数を選んだとき、その中に同一の数が２回以上現れる確率Ｐとx=k/√(m)の関係
P(%) xの近似値
10 0.459044√(m)
20 0.668047√(m)
30 0.844600√(m)
40 1.010768√(m)
50 1.177410√(m)
60 1.353729√(m)
70 1.551756√(m)
80 1.794123√(m)
90 2.145966√(m)
◎論理学
logic
◆fallacy
＿◇量化子交換の虚偽
∀∃のつく前件と∃∀のつく後件を持っているが、∀∃は∃∀を含意しない。
量化子変換の誤り（a quantifier-shift fallacy）
英語での別名: illicit quantifier shift
前提：すべてのPがあるQに対してRという関係を持っている。
結論：あるQはすべてのPに対してRという関係を持っている。
例）
前提：すべての学生はある教師を尊敬している。
結論：ある教師はすべての学生から尊敬されている。
この例の前提の意味は、すべての学生がそれぞれ少なくとも1人の教師を尊敬しているということである。このことから、少なくとも1人の教師がすべての学生から尊敬されているという結論は出せない。