レポートの解答例 (2006年度後藤担当） • 以下に解答例を示します。 • なお今回のレポートの問題は過去の定期試験問題から出題しています。問１： 2004年度定期試験問題１(a) 問２： 2004年度定期試験問題２(b) 問３： 2005年度定期試験問題 G2 関連 (2004年度定期試験問題２関連あり) 問４： 2004年度定期試験問題4 1 問１集合の要素 • 次の集合に属するすべての要素を列挙せよ。例： {0,1}{a}   0, a ,  1, a  [1-1] 2 2{} (または P (P (f g )) ) {a, {a}, {a, {a}}}  {a, {a}} [1-2] ヒント： [1-2]では＋の左と右の集合の要素の数を、まず数えてみる。これは有限集合である。 2 ［１－１］集合の要素（解答） • まず空集合の冪集合を求める 2{ } この冪集合は一つの要素を持つ {{ }} . 次に空集合の冪集合の冪集合を求める 2{{ }} この集合は二つの要素を持つ {{ }, {{ }} }. よって解答は、 { }, {{ }}. • 確認：空集合は有限集合である。 |{ }|=0. | 2{ } |=20=1 が成立つ。 {} {} 2 同様に、 2 2  2  21  2 となる。解答が二つの要素から成るのは当然である。 3 ［１－２］集合の要素（解答） • [1-2] 直和を表現するタグとして {0, 1}を用いる。 <0,a>, <0,{a}>, <0,{a,{a}}>, <1,a>, <1,{a}> • 確認：左側の { a, {a}, {a,{a}} } という集合が少し複雑に見えるが、要素の数は 3である。右側の集合 {a, {a} }の要素の数は 2である。いずれも有限集合であるから直和の要素の数は 5となる。 {a, {a}, {a, {a}}}  {a, {a}}  {a, {a}, {a, {a}}}  {a, {a}} 4 問2 関数 • 次の集合に属する要素を具体的に一つ挙げよ。 N{0,1}×{2,3｝ヒント：まず集合 {0, 1}×{2, 3} の要素を具体的に書いてみる。 5 問２関数（解答） • まず直積 {0,1}×{2,3}の要素を求める {0,1}×{2,3}＝{<0,2>,<0,3>,<1,2>,<1,3>} N{0,1}×{2,3} という集合は、{0,1}×{2,3} から自然数の集合 N への関数（写像）の集合のことである。ここでは関数の値を具体的に定めて関数を一つ定めればよい。関数の一例のグラフを挙げる。 {<<0,2>,0>, <<0,3>,1>, <<1,2>,2>, <<1,3>,3>} これが N{0,1}×{2,3｝の要素の一つである。 6 問３集合の濃度（可算集合） • 自然数の集合 N={0,1,2,…}の直積 N2=N×N から N への関数 f(x,y)={(x+y)2+3x+y}÷2 を考える。 (３-１) f(0,0), f(0,1), f(1,0) ,f(0,2), f(1,1), f(2,0) の値を計算せよ。 (３-２) N2は可算集合であることを説明せよ。 7 （３－１）解答 f(0,0), f(0,1), f(1,0) ,f(0,2), f(1,1), f(2,0)の値 f (0,0)  {( 0  0 ) 2  30  0} f (0,1)  {( 0 1) 2  30 1} f (1,0)  {(1 0 ) 2  31 0} 2 f (0,2)  f (1,1)  2 1 2 2 {( 0  2 ) 2  30  2} 2 {(11) 2  311} f (2,0)  0 2 3 4 {( 2  0 ) 2  32  0} 2 5 8 （３－２）解答 N  N  N は自然数の集合の直積である。 2 N  N の要素<x,y>に自然数 {( x  y)  3x  y} 2 を対応づける関数は全単射である。よって N と 2 N  N  N とは対等で同じ濃度をもつ。集合 N が可算無限集合であるから N 2 も可算無限集合である。 2 9 問４二項関係の反射推移的閉包 • 集合A = {p, q, r, s} 上の二項関係 R = {<p, q>, <q, r>, <r, s>, <r,r>} の反射推移閉包（すなわち R * ）を求めよ．ヒント p s R0 R1 R2 R3 R4 p p q r r,s r,s q q r r,s r,s r,s r r r,s r,s r,s r,s s s q r 10 問４二項関係の反射推移的閉包（解答） • グラフの上で各点から長さ n の道（経路）で到達できる点を求めれば良い。 p s q r {<p,p>, <q,q>, <r,r>, <s,s>, <p,q>, <q,r>, <r,s>, <p,r>, <q,s>, <p,s>} 11 問４反射推移的閉包（別解） • 解答： R = {<p, q>, <q, r>, <r, s>, <r,r>} の隣接行列を考える。 1  0 0 R  0  0  0  0 2 R  0  0  0 0 0 0   1 0 0 0 ,R  0 1 0 0   0 0 0 1   0 1 0 0   0 1 1 3 0 ,R   0 1 1 0   0 0 0 0   1 0 0  0 1 0 ,  0 1 1  0 0 0  0 1 1 0 0   0 1 1 4 0 0 R   0 1 1 0 0   0 0 0 0 0   p s q r 1 1  1 1 ,  1 1  0 0  (R0+R1+R2+R3+R4+‥)の０でない成分＝ {<p,p>, <q,q>, <r,r>, <s,s>, <p,q>, <q,r>, <r,s>, <p,r>, <q,s>, <p,s>} 12