6.6.6.6. 述語と集合述語と集合述語と集合述語と集合

(1)

離散数学離散数学離散数学

離散数学University of ElectroUniversity of ElectroUniversity of ElectroUniversity of Electro----CommunicationsCommunicationsCommunicationsCommunications

6. 6. 6.

6. 述語と集合述語と集合述語と集合述語と集合

植野真臣

University of ElectroUniversity of ElectroCommunicationsCommunications

スケジュールスケジュールスケジュールスケジュール

４月１４日：第1回：命題と証明

４月２１日：第2回：集合の基礎、全称記号、存在記号４月２８日：第3回：命題論理

５月１２日：第4回：述語論理５月１９日：第5回：述語と集合５月２６日：第6回：直積と冪集合６月２日：第7回：様々な証明法(1) ６月９日：第8回：様々な証明法(2)

６月１６日：第9回：様々な証明法（再帰的定義と数学的帰納法）

６月2３日：第10回：中間試験６月３０日：第11回：写像（関数）(1) ７月７日：第12回：写像(関数) (2)

７月１４日：第13回：写像と関係：二項関係、関係行列、グラフによる表現７月２１日：第14回：同値関係

７月２８日：第15回：順序関係：半順序集合、ハッセ図、全順序集合、上界と下界８月４日：期末試験（補講があればずれていきます。）

2

離散数学University of ElectroUniversity of Electro----CommunicationsUniversity of ElectroUniversity of ElectroCommunicationsCommunicationsCommunications

１．本日１．本日１．本日１．本日の目標の目標の目標の目標

1

．直積

2

．集合の冪集合

3

．集合系の演算

4

．ラッセルのパラドックス

2.

2. 先週の復習：先週の復習：先週の復習：先週の復習：

内包的記法での条件部での量化子

1. ∀(())}

はすべての

について条件

()

を満たす共通集合

⋂ {| }

という意味

2.

内包的記述での

∃(())}

はすべての

について条件(述語)

()

を満たす和集合

⋃ {| }

という意味

4

2.

例題

1. ∈ ℕ ∀ ∈ ℕ( > )}

2. ∈ ℕ ∃ ∈ ℕ( > )}

2.

例題

1. ∈ ℕ ∀ ∈ ℕ( > )}

= ⋂ _∈ℕ ∈ ℕ > } = ∅ 2. ∈ ℕ ∃ ∈ ℕ( > )}

= ⋃ ∈ℕ ∈ ℕ > } = ∈ ℕ > 1 = ℤ

ℤ :1

以上の整数

(2)

3.

3. 直積直積直積直積

Def.1.

集合の要素

と要素

を順序を考慮して組

にしたものを

と

の「順序対」といい，記号で

(, )

と書く。

Def.2. = , = b

のときのみ

(, )

と

(, )

が等しいという。

Def. 3.

集合

,

に対して，

の要素と

の要素から作られる順序対の全体

{(, )| ∈ , ∈ }

を

と

の直積といい，

×

で表す。

7

注意注意注意注意

= ∅

または

= ∅

のとき

× = × ∅ = ∅ × = ∅ × ∅ = ∅

8

例題１例題１例題１例題１

= 1,2 , ! = {3,4}

とすると，

× !

は？

9

例題１例題１例題１例題１

= 1,2 , ! = {3,4}

とすると，

× !

は？

× ! = { 1,3 , 1,4 , 2,3 , 2,4 }

10

例題例題例題例題2222

ℕ × ℕ

は，自然数の順序対の全体を示す。

= {(, ) ∈ ℕ × ℕ| × = 2}

の要素は？

11

ℕ × ℕ

は，自然数の順序対の全体を示す。

= {(, ) ∈ ℕ × ℕ| × = 2}

の要素は？

= { 1,2 , 2,1 }

12

(3)

× ! ∪ % = ( × !) ∪ ( × %)

を証明せよ。

13

× ! ∪ % = ( × !) ∪ ( × %)

を証明せよ。

[証明]

∀(, ) [ (, ) ∈ × ! ∪ % ⟺ (, ) ∈ ( × !)

∪ ( × %)]

を示せばよい。

(, ) ∈ × ! ∪ % ⟺ ∈ ∧ ∈ (! ∪ %) ⟺ ∈ ∧ [ ∈ ! ∨ ∈ %] ⟺ [ ∈ ∧ ∈ !] ∨ [ ∈ ∧ ∈ %] ⟺ [(, ) ∈ ( × !) ] ∨ [(, ) ∈ ( ×

%)] ⟺ (, ) ∈ ( × !) ∪ ( × %)

■

14

× ! ∩ % = ( × !) ∩ ( × %)

を証明せよ。

15

× ! ∩ % = ( × !) ∩ ( × %)

を証明せよ。

[証明]

∀(, ) [ (, ) ∈ × ! ∩ % ⟺ (, ) ∈ ( ×

!) ∩ ( × %)]

を示せばよい。

(, ) ∈ × ! ∩ % ⟺ ∈ ∧ ∈ (! ∩ %) ⟺ ∈ ∧ [ ∈ ! ∧ ∈ %] ⟺ [ ∈ ∧ ∈ !] ∧ [ ∈ ∧ ∈ %] ⟺ [(, ) ∈ ( × !) ] ∧ [(, ) ∈ ( ×

%)] ⟺ (, ) ∈ ( × !) ∩ ( × %)

■

16

4 44

4．．．．関係関係関係関係 ( ( 本授業の後半で詳しく学習します。( ( 本授業の後半で詳しく学習します。本授業の後半で詳しく学習します。))))本授業の後半で詳しく学習します。

Def 4.

二つの集合

,

の直積集合

×

の部分集合

,

を

から

への「関係」という．

また，

, ∋ (, )

のとき

, :

と

は関係ある

, ∌ (, )

のとき

, ：

と

は関係なしと書く．

関係の例関係の例関係の例関係の例

= 1,2 , ! = {3,4}

× ! = { 1,3 , 1,4 , 2,3 , 2,4 }

このとき，

, = { 1,4 , 2,4 }

もしくは

1,4 , 2,4

は，１が４と関係がある、

2

が

4

と関係があるということを表現している。

(4)

例例例例1111．．．．

ℝ × ℝ

は，実数の順序対の全体を示す。

(, ) ∈ ℝ × ℝ

は、座標軸平面上の点。

19

例例例例2.2.2.2.

ℝ

から

ℝ

への関数

1

に対し，

2 3 = {(, ) ∈ ℝ × ℝ| = 1()}

は，「関数

1

のグラフ」を示す。

例

2 3 = {(, ) ∈ ℝ × ℝ| = _{4567 (89:)} ⁴ }

20

5.

5. 冪冪冪冪集合集合集合集合

Def. 4.

の部分集合の集まりを

の冪（べき）集合

(power )

といい，

ℱ

または

2 ^<

で表す。

21

例例例例

= {, , =}

とすると，

2 ^< = {∅, , , = , , , , = , , = , , , = }

22

Th Th Th Th 1111

集合について

= >

のとき，の冪集合

2 ^?

について

ℱ = 2 ^@ .

23

Th Th Th Th 1111

集合について

= >

のとき，の冪集合

2 ^?

について

ℱ = 2 ^@ .

[

証明

]

= {1,2,3, ⋯ , >}

としても一般性を失わない。このとき，の部分集合の取り方は，

1

を含むかどうか、

2

3 ⋯ >

を含むかどうかで決まるので，その総数は

2 ^@ .

■

24

(5)

6.

6. 集合系集合系集合系集合系

Def. 5. >

個の

の部分集合

₄ ⋯ _@

が与えられているとき，

= { 4 ⋯ @ } = { B }(C = 1, ⋯ , >)

を集集集集合系

合系合系

合系と呼ぶ。集合族と呼ばれることもある。

Th. 2.

普遍集合普遍集合普遍集合

普遍集合

の冪集合

2 ^<

の部分集合の集合

{ | ⊆ 2 ^< }

は集合系である。集合系である。集合系である。集合系である。

25

注意：集合系と集合族注意：集合系と集合族注意：集合系と集合族注意：集合系と集合族

= { ₄ ⋯ _@ } = { _B }(C = 1, ⋯ , >)

のようにインデックスがついている場合と冪集合

2 ^<

の部分集合としてのみ扱われるる場合で、集合系と集合族を区別することがある。

しかし、どちらの場合をどう呼ぶかが様々に異なり決まっていない。

ここでは、同じとして扱う。

26

7.

7. 7.

7. 集合系集合系集合系集合系の演算の演算の演算の演算

Def. 6.

集合系

{ B }(C = 1, ⋯ , >)

について，条件

∀C( ∈ B )

を満たす

全体の集合を「集合系

{ B }(C = 1, ⋯ , >)

の共通部分」といい，

⋂ B

BE4

と書く。すなわち，

F B

BE4

ただし、左辺は添え字の集合が自然数集合

ℕ

のとき，

⋂ G B

BE4

と書く。

27

7.

7. 集合系集合系集合系の演算集合系の演算の演算の演算

Def. 6.

集合系

{ B }(C = 1, ⋯ , >)

∀C( ∈ B )

を満たす

{ B }(C = 1, ⋯ , >)

の共通部分」といい，

⋂ B

BE4

と書く。すなわち，

F B BE4

= {|∀C( ∈

B

)}

ただし、左辺は添え字の集合が自然数集合

ℕ

のとき，

⋂ G B

BE4

と書く。

28

7.

Def. 7.

集合系

{ B }(C = 1, ⋯ , >)

∃C( ∈ B )

を満たす

{ B }(C = 1, ⋯ , >)

の和集合」といい，

⋃ H B

BE4

と書く。

すなわち，

I B H

BE4

ただし，左辺は添え字の集合が自然数集合

ℕ

の

7.

Def. 7.

集合系

{ B }(C = 1, ⋯ , >)

∃C( ∈ B )

を満たす

{ B }(C = 1, ⋯ , >)

の和集合」といい，

⋃ H B

BE4

と書く。

すなわち，

I B H BE4

= {|∃C( ∈

B

)}

ただし，左辺は添え字の集合が自然数集合

ℕ

の

(6)

7.

J = {1, ⋯ , >}

もしくは

J = ℕ

のときを統一的に共通部分を

⋂ K B B∈L

和集合を

I B

K

B∈L

と書くこともある。

31

例例例例

J = {1,2}

のとき，

⋂ K B

B∈L = 4 ∩ M . I B

K

B∈L

= 4 ∪ M . J = {1,2, ⋯ }

のとき，

⋂ K B

B∈L ， ⋃ K B

B∈L

は２個の集合の共通部分，和集合の一般化である。

32

∈ ℕ

に対し，集合

!

を

! = ∈ ℝ| ≥

とし，

集合系

{B }( ∈ ℕ)

の共通部分と和集合は

33

ℕ

の要素

n

に対し，集合

!

を

! = ∈ ℝ| ≥

とし，集合系

{B }( ∈ ℕ)

F !

G E4

= ∀ ≥ = ∅,

⋃ G E4 ! = {|∃( ≥ )} = ≥ 0

34

ℕ

の

1

以上の要素

n

に対し，集合

を

= ∈ ℝ| < ⁴

とし，集合系

{ B }(C ∈ ℕ)

35

ℕ

の

1

以上の要素

n

に対し，集合

を

= ∈ ℝ| < ⁴

とし，集合系

{ B }(C ∈ ℕ)

F

G

E4

= ∀ < 1 = ≤ 0 ,

⋃ G

E4 = {|∃( < ⁴ )} = < 1

36

(7)

ℕ

の

1

以上の要素

n

に対し，集合

を

= ∈ ℝ| < ⁴

とし，集合系

{ B }(C ∈ ℕ)

37

ℕ

の

1

以上の要素

n

に対し，集合

を

= ∈ ℝ| < ⁴

とし，集合系

{ B }(C ∈ ℕ)

F G

E4 = ∀

<

¹_{= {0},}

⋃ G

E4 = {|∃( < ⁴ )} = −1 < < 1

38

分配律分配律分配律分配律

集合と集合系

B ∈ ℕ , J ⊆ ℕ

について以下が成り立つ。

39

∪ F !

B

K

B∈L

= F( ∪ !

B

)

K

B∈L

∩ I !

B

K

B∈L

= I( ∩ !

B

)

K

B∈L

ド・モルガンの法則ド・モルガンの法則ド・モルガンの法則ド・モルガンの法則

普遍集合を

とする集合系

_B C ∈ ℕ , J ⊆ ℕ

について以下が成り立つ。

I B

K

B∈L U

= F K B U B∈L

F B

K

B∈L U

= I B U

K

B∈L

40

集合の集合の集合の集合の集合の集合の集合の集合の問題問題問題問題

我々は本日、集合の集合について考えてきた。しかし、集合の集合を数学的に体系づけるときに重要な問題が発見されている。

ラッセルは集合の集合は次の二つのものしかないと考えた。

Ａ：自分自身を要素とする集合の集合Ｂ：自分自身を要素としない集合の集合 8

88

8．．．．ラッセルのラッセルのラッセルのラッセルのパラドックスパラドックスパラドックスパラドックス

(8)

集合Ａ：自分自身を要素とする集合の集合集合Ｂ：自分自身を要素としない集合の集合Ａの例：要素の個数が無限の集合の集合

→

要素の個数が無限の集合は無限に存在するのでそれ自身もＡに属する。

Bの例：遊びの集合の集合を考える。遊びの集合

は遊びではないので自分自身を要素としない集合の集合Ｂに入る。

43

ラッセルは集合は次の二つのものしかないと考えた。

44

8 88

8．．．ラッセルのパラドックス．ラッセルのパラドックスラッセルのパラドックスラッセルのパラドックス

自分自身を含まない集合全体の集合

, = {| ∉ }

は存在しない。

45

888

8．．．ラッセルのパラドックス．ラッセルのパラドックスラッセルのパラドックスラッセルのパラドックス

自分自身を含まない集合全体の集合

, = {| ∉ }

は存在しない。

証明

１．

, ∈ ,

の場合

, = {| ∉ }

より，

, ∉ ,

となり矛盾２．

, ∉ ,

の場合

, = {| ∉ }

より，

, ∈ ,

となり矛盾例：すべての集合を含む集合

集合論で，

,

が集合の定義としては許容されないような体系が構築されてきた。

46

8 88

8．．．．ラッセルのラッセルのラッセルのラッセルのパラドックスパラドックスパラドックスパラドックス

床屋の深刻な問題床屋の深刻な問題床屋の深刻な問題床屋の深刻な問題

以下のようなルールを課せられた町に一人だけ存在する床屋がいる。

・自分でひげをそらない町の人全員のひげをそる。

・自分でひげをそる町の人のひげはそらない。

このとき、床屋自身は自分のひげはそるのか？

8.

8. ラッセルのパラドックスラッセルのパラドックスラッセルのパラドックス解決法ラッセルのパラドックス解決法解決法解決法

A = {| ∈ }

も

B = {| ∉ }

も集合ではないと考える。

→

自分自身が要素となる概念を使って集合を定義してはならない

→

集合理論：

ZFC

公理系

47

１１１

１００００．まとめ．まとめ．まとめ．まとめ

48

1

．直積

2

．集合の冪集合

3．集合系の演算

4

．ラッセルのパラドックス

(9)

演習問題演習問題演習問題演習問題

49

問題問題問題問題1111

= 1,2,3,4 , = {1,2,3,4,5,6,7,8,9,10}

とし，それぞれの部分集合を

] = ∈ | ≤ 3 , ^ = { ∈

| ≤ 6}

とする。直積

×

を普遍集合とし，次に示す集合を外延的記法で表せ。

(1) (, ) + < 5}

(2) (, ) = 2 +1}

(3) {1,3} × (4) (] × ^) Û (5) ] Û × ^ Û

50

= ! ∩ % → × = (! × !) ∩ (% × %)

を証明せよ。

51

= 1,2,3,4

の冪集合

ℱ()

を外延的記法で示せ。

52

次の集合系について，共通部分と和集合を求めよ。

(1) | ∈ ℕ = ∈ ℝ| ^M ≤ ⁴

(2) ! | ∈ ℕ ! = ∈ ℝ| ≥ − a < ⁴ (3) % | ∈ ℕ % = ∈ ℝ| > 0 a ≤ ⁴ (4) b | ∈ ℕ b = { ∈ ℝ| ≥ a <

+ 1}

問題問題問題問題5555．．．．

次の述語の演算法則を用いて，集合系の分配律を証明せよ。

「

を含まない命題

c

と自由変数

についての述語

d

について，以下が成り立つ。

c ∨ ∀ d ≡ ∀ c ∨ d

c ∧ ∃ d ≡ ∃ c ∧ d

6.6.6.6. 述語と集合 述語と集合 述語と集合 述語と集合

6. 6. 6.

6. 述語と集合 述語と集合 述語と集合 述語と集合

1

2

3

4

1. ∀(())}

()

⋂ {| }

2.

∃(())}

()

⋃ {| }

1. ∈ ℕ ∀ ∈ ℕ( > )}

2. ∈ ℕ ∃ ∈ ℕ( > )}

1. ∈ ℕ ∀ ∈ ℕ( > )}

= ⋂ ∈ℕ ∈ ℕ > } = ∅ 2. ∈ ℕ ∃ ∈ ℕ( > )}

= ⋃ ∈ℕ ∈ ℕ > } = ∈ ℕ > 1 = ℤ

ℤ :1

Def.1.

(, )

Def.2. = , = b

(, )

(, )

Def. 3.

,

{(, )| ∈ , ∈ }

×

= ∅

= ∅

× = × ∅ = ∅ × = ∅ × ∅ = ∅

= 1,2 , ! = {3,4}

× !

= 1,2 , ! = {3,4}

× !

× ! = { 1,3 , 1,4 , 2,3 , 2,4 }

ℕ × ℕ

= {(, ) ∈ ℕ × ℕ| × = 2}

ℕ × ℕ

= {(, ) ∈ ℕ × ℕ| × = 2}

= { 1,2 , 2,1 }

× ! ∪ % = ( × !) ∪ ( × %)

× ! ∪ % = ( × !) ∪ ( × %)

∀(, ) [ (, ) ∈ × ! ∪ % ⟺ (, ) ∈ ( × !)

∪ ( × %)]

(, ) ∈ × ! ∪ % ⟺ ∈ ∧ ∈ (! ∪ %) ⟺ ∈ ∧ [ ∈ ! ∨ ∈ %] ⟺ [ ∈ ∧ ∈ !] ∨ [ ∈ ∧ ∈ %] ⟺ [(, ) ∈ ( × !) ] ∨ [(, ) ∈ ( ×

%)] ⟺ (, ) ∈ ( × !) ∪ ( × %)

× ! ∩ % = ( × !) ∩ ( × %)

× ! ∩ % = ( × !) ∩ ( × %)

∀(, ) [ (, ) ∈ × ! ∩ % ⟺ (, ) ∈ ( ×

!) ∩ ( × %)]

(, ) ∈ × ! ∩ % ⟺ ∈ ∧ ∈ (! ∩ %) ⟺ ∈ ∧ [ ∈ ! ∧ ∈ %] ⟺ [ ∈ ∧ ∈ !] ∧ [ ∈ ∧ ∈ %] ⟺ [(, ) ∈ ( × !) ] ∧ [(, ) ∈ ( ×

%)] ⟺ (, ) ∈ ( × !) ∩ ( × %)

Def 4.

,

×

,

, ∋ (, )

, :

, ∌ (, )

, ：

= 1,2 , ! = {3,4}

× ! = { 1,3 , 1,4 , 2,3 , 2,4 }

, = { 1,4 , 2,4 }

1,4 , 2,4

2

4

ℝ × ℝ

(, ) ∈ ℝ × ℝ

ℝ

ℝ

1

2 3 = {(, ) ∈ ℝ × ℝ| = 1()}

1

2 3 = {(, ) ∈ ℝ × ℝ| = 4567 (89:) 4 }

Def. 4.

(power )

ℱ

2 <

6.6.6.6. 述語と集合述語と集合述語と集合述語と集合

6. 述語と集合述語と集合述語と集合述語と集合

= ⋂ _∈ℕ ∈ ℕ > } = ∅ 2. ∈ ℕ ∃ ∈ ℕ( > )}

2 3 = {(, ) ∈ ℝ × ℝ| = _{4567 (89:)} ⁴ }

2 ^<

2 ^< = {∅, , , = , , , , = , , = , , , = }

2 ^?

ℱ = 2 ^@ .

2 ^?

ℱ = 2 ^@ .

2 ^@ .

₄ ⋯ _@

2 ^<

{ | ⊆ 2 ^< }

= { ₄ ⋯ _@ } = { _B }(C = 1, ⋯ , >)

2 ^<