[ Japanese | English ]
Norikazu Takahashi Personal Web Page

その他の話題

自然数の集合は非可算?

昨年度から「工学安全教育」という講義の一部を担当しています.私の担当部分の主要テーマは「ソフトウェアの万能性と自動化の限界」であり,ソフトウェアは万能でないということを停止性判定問題を通して説明します.その中で対角線論法を用いるのですが,本日の講義終了後に受講生のA君(情報系学科1年生)から「対角線論法を用いると自然数の集合が非可算であるということが証明されてしまいます.この証明のどこが間違っているのでしょうか?」という質問を受けました.A君の証明は以下の通りです.

【A君の証明】各自然数の最上位桁の左には見えない0が無限個並んでいると考え,各自然数を0,1,...,9の無限列に変換します.例えば231は...0000231に変換されます.いま,自然数の集合は可算であると仮定すると,これらの無限列には1,2,3...と番号をつけることができます.そこで
...000001 : 1
...000002 : 2
...000003 : 3
...
と番号をつけることにします.このとき,右端の数字が2でその他の数字がすべて1である無限列...111112を考えます.この無限列と上の表の1行目の無限列を比べると右端の数字が異なるので両者は等しくありません.また,この無限列と上の表の2行目の無限列を比べると右から2番目の数字が異なるので両者は等しくありません.以下同様に,無限列...111112は上の表のどの無限列とも等しくありません.これは番号のつかない自然数が存在することを意味しています.したがって自然数の集合は非可算です.(証明終)

自然数の集合が可算であることは自明です.しかし,A君の証明も正しいように思えます.実際,私はその場で証明の間違い指摘することができず,「面白いことを考えますねぇ」,「不思議ですねぇ」,「どうしてでしょうねぇ」,「後でじっくり考えてみましょう」などとお茶を濁し,そのまま講義室を後にしました.

講義から4時間ほど経った午後8時過ぎ.ある会合の懇親会に出席した私は,大学周辺を千鳥足で歩きながら,もう一度A君の証明を考えました.適度にお酒を飲んでリラックスしていたのがよかったのでしょう.自宅に着く前に証明の間違いに気がつきました.

【私の回答】A君の方法で各自然数を無限列に変換すると,どの無限列にもある有限の数kが存在して,右からk番目の数字は0でなく,それより左の数字はすべて0となります.一方,無限列...111112においては右端を除いてすべて1ですので,そのような有限の数kは存在しません.このことは無限列...111112がどの自然数にも対応しないことを意味します.したがって,この無限列が上の表に存在しなくても矛盾は導かれません.(回答終)

A君いかがでしょうか?

(2014/12/19)

エルデシュ数

ハンガリー出身の数学者ポール・エルデシュ(Paul Erdős, 1913-1996)は生涯に約1500本もの論文を発表しました.そのうち507本が共著論文であり,彼の共著者は511人に上るそうです.その共著者の多さに着目して考案されたのがエルデシュ数です.これは次のように定義されます.まず,エルデシュ自身のエルデシュ数を0とします.次にエルデシュの共著者511人のエルデシュ数を1とします.あとはnを1以上の整数として,エルデシュ数nの人との共著論文があり,エルデシュ数n未満の人との共著論文がない人のエルデシュ数をn+1とします.例えば,エルデシュとの共著論文はないがエルデシュの共著者との共著論文がある人のエルデシュ数は2となります.

エルデシュ数のことは以前から知っていたのですが,私には関係ないとずっと思っていました.ところがある日,エルデシュ数が2以下の科学者の一覧(Erdős Number Project で公開されています)を何気なく眺めていたところ,私につながりそうな人の名前を見つけました.うれしくなって更に調べてみると,確かに下記4本の論文で Erdős から私につながっていることがわかりました.

  1. P. Diaconis and P. Erdős, “On the distribution of the greatest common divisor,” Technical Report, Stanford University, 1997.
    この論文は Lecture Notes-Monograph Series (2004) に再掲載されているようです.
  2. S. Boyd, P. Diaconis and L. Xiao, “Fastest mixing Markov chain on a graph,” SIAM Review, vol.46, no.4, pp.667-689, 2004.
    DOI: 10.1137/S0036144503423264
  3. S. Boyd and L.O. Chua, “Uniqueness of a basic nonlinear structure,” IEEE Transaction on Circuits and Systems, vol.30, no.9, pp.648-651, 1983.
    DOI: 10.1109/TCS.1983.1085403
  4. N. Takahashi and L.O. Chua, “A New Sufficient Condition for Nonsymmetric CNNs to Have a Stable Equilibrium Point,” IEEE Transactions on Circuits and Systems-I, vol.44, no.11, pp.1092-1095, November 1997.
    DOI: 10.1109/81.641777
つまり,私のエルデシュ数は4ということになります.共著関係のネットワークはやはり小さな世界のようです.

(2014/11/8)

3D画像

2010年が3D元年と呼ばれていることに象徴されるように,3D映像技術がこの数年で急激に普及しました.そこで平成23年度の電気情報工学入門では,3D画像をテーマに掲げ,配属された学生さん達にアナグリフ(赤青メガネ)方式の3D画像を制作してもらいました.使用する機材はデジタルカメラ1台(3D機能はついていません)とノートパソコン1台のみです.1台のデジタルカメラで対象物の写真を2枚(右目用と左目用)撮り,ノートパソコンに取り込んで画像処理ソフトGimpで色と位置の調整をする,という簡単な方法でしたが,予想以上にいい作品ができました.学生さん達の作品の一部を以下に載せておきますので,赤青メガネをお持ちの方はお楽しみ下さい.

anaglyph image 1 anaglyph image 2

(2011/8/12)