記事一覧

単射と順列、全射とスターリング数

第192話
全射と単射の不思議



$X, Y$を集合とする。
\begin{align*}
Y^X \equiv \{ f \;|\; \; f \mbox{は集合$X$から集合$Y$への写像}\}
\tag{1}
\end{align*}
とする。 
ここで、


  なぜ、変な記号「$Y^X$」を使うのか?  

と問うかもしれない。
もちろん、このような記法を用いるのは、集合$X,Y$が有限集合の場合、すなわち、$X=\{1,2., \cdots, m \}$, $Y=\{1,2, \cdots , n \}$の場合は、
\begin{align*}
&
\mbox{集合}\{ f \;|\; f \mbox{は集合$X$から集合$Y$への写像}\} 
\\
&
\mbox{の元の個数は、}n^m
\end{align*}
だからである。

この記法は、結構便利で、
$Y=\{0,1\}$の場合は、
\begin{align*}
&
\{0,1\}^X
\\
\equiv
&
\{ f \;|\; \; f \mbox{は集合$X$から集合$\{0,1\}$への写像}\}
\\
\approx
&
\{ A \;|\; A \subseteq X \}
\\
=
&
\mbox{集合$X$のベキ集合}
\\
&
(=\mbox{集合$X$の部分集合全体のなす集合})
\tag{2}
\end{align*}
なので、
\begin{align*}
2^X \equiv
\mbox{集合$X$のベキ集合}
\tag{3}
\end{align*}
と書くのも、常識化されている。

ここまでは、準備であるが、もうひとつ準備として、単射(一対一の写像)、全射(上への写像)の定義を再度復習[第190話「単射・全射」しておく。
(A):「単射」と全射の定義


$(A_1)$;$f: X \to Y$が単射とは、


「$x_1, x_2 \in X$ で $x_1 \not= x_2$」ならば、「$f(x_1)\not= f(x_2)$」

を満たすことである。


$(A_2)$$g: X \to Y$が全射とは、

「任意の$y \in Y$に対して、「$g(x)=y$」を
満たすような$x \in X$が存在することである。

となる。


そして、第190話「全射・単射」で述べたように、
ここで、

  定義(A)からは、想像できないほど、
「全射・単射」は真逆な関係にある
 
 

であった。

しかし、次の問題を考えると、「真逆」とも言えないかもしれないかもしれない。
問題(B):「単射」と「全射」の個数


$X=\{1,2., \cdots, m \}$, $Y=\{1,2, \cdots , n \}$とする。


(B1):  $m \le n $としたとき、
\begin{align*}&
\mbox{集合}\{ f \;|\; f \mbox{は集合$X$から集合$Y$への単射}\} 
\\
&
\mbox{の元の個数を求めよ、}
\end{align*}
(B2):  $m \ge n $としたとき、

\begin{align*}&
\mbox{集合}\{ f \;|\; f \mbox{は集合$X$から集合$Y$への全射}\} 
\\
&
\mbox{の元の個数を求めよ、}
\end{align*}



を考えよう。

$(B_1)$は簡単。 
高校数学の「順列${}_mP_n$」すなわち、
\begin{align*}
{}_nP_m = n(n-1)(n-2) \cdots (n -(m-1))
\end{align*}

である。 というよりも、「順列${}_nP_m$」の定義を$(B_1)$と考えたい。 普通の

「m 個の元から n-個を選んで得られる順列の総数」

のような「『選んで』などの動作を含む定義」よりは、「${}_nP_m$」の定義を$(B_1)$と考えるほうが、一番スッキリする。

$(B_2)$は簡単でない。
とは言っても、計算だけの問題で、結論は、スターリング数$S(n,m)$(高校数学の組み合わせ${}_nC_m$を含む)を使って、
\begin{align*}&
m!\times S(n,m) \\
=
&
m! \times \frac{1}{m!}\sum_{j=0}^m {}_(-1)^j (m-j)^n {}_rC_j
\end{align*}

となる。


---------------
「単射・全射」は「真逆」のはずなのに、 (B1)と(B2)のあまりにもの違いが気になります。 折角

「$(B_1)$までは美しかったのに,(B2)は残念」

数学がこちらの都合の良いようにはできていないということでしょか? または、もっと深く理解すれば、このギャップも素直に受け入れることが出来るようになるのかも、

科学哲学(二元論的観念論)

量子言語(=測定理論)は、統計学と量子論を合わせた程度の強力な記述力を有する言語である。 量子言語の習得には、いろいろなアプローチの方法があっていい。 このブログでは、数物には関わらず、哲学【二元論的観念論】をメインに量子言語を紹介して、西洋哲学史の本流は常に量子言語に向かって進歩してきたことを確認する。ブログとは、一旦書いてしまうと、訂正するのが億劫になるものである。 したがって、本ブログと大幅な変更があるわけではないが、現時点での正式バージョンは【Western philosophy(PDF)】を見よ。

目次

  • 0:【Home】リンク付き目次(スマホ利用者用)
  • 1:量子力学の観測・解釈問題の解決
  • 2(上):科学哲学とは? (形而上学;統計学;量子力学)
  • 2(下):世界記述(至上)主義
  • 3(上):1+1=2:発明王エジソン;形而上学
  • 3(中):論理実証主義と形而上学
  • 3(下):ケルヴィン卿の形而上学
  • 4(上): 測定理論(=量子言語); 世界記述法の分類
  • 4(中):ソーカル事件の「脱構築」
  • 4(下)論考、知の欺瞞、量子言語
  • 5:古典力学的世界観;量子力学的世界観
  • 6:科学と統計学;量子言語;
  • 7:赤い糸 : 量子力学の観測と因果関係
  • 8:運命の量子的出会い(観測と因果律)
  • 9:コペンハーゲン解釈は虚構;因果と測定
  • 10: $[$一元論、二元論$]$×$[$実在論、観念論$]$
  • 11:離別の予感(測定と因果)
  • 12:ピタゴラス(万物は数)
  • 13:パルメニデスとヘラクレイトス;運動・変化
  • 14: 科学とは何か? 運動;因果律;確率;測定
  • 15:パルメニデスの理屈っぽさ: ゼノンのパラドックス
  • 16(上):ゼノンのパラドックスは未解決問題
  • 16(補): ハジキの公式:形而上学的命題
  • 16(中):「アキレスと亀」は未解決問題
  • 16(下): ゼノンのパラドックスの必然性
  • 17(上):存在論(パルメニデス)
  • 17(下):存在とは何か?(パルメニデス)
  • 18(上):[人気No.3]哲学は進歩したか?
  • 18:無知の知:ソクラテスの詭弁
  • 19:人間は万物の尺度:プロタゴラス×ソクラテス;倫理哲学
  • 20:イデア論:プラトンの詭弁
  • 21(上):プラトンのイデアは絶対基準・測定器のこと
  • 21(下): 西洋哲学はプラトンの脚注
  • 22(上):万学の祖アリストテレス;形相,質料
  • 22(下): プラトンとアリストテレスの融合;スコラ哲学
  • 23(上):アリストテレスの目的因
  • 23(下):三段論法を信じますか? アリストテレス
  • 23(補):必要条件と十分条件
  • 24(上):アリスタルコス(古代の地動説);アルキメデス
  • 24(下):アリスタルコス:古代の地動説
  • 25(上):ユークリッド幾何学--平行線の公準
  • 25(下):言語と数学;公理主義
  • 26:エラトステネス:古代最大の測定者
  • 27:総括〈ギリシャ vs.アレクサンドリア〉
  • 28:天動説(プトレマイオス)
  • 29:古代科学の三つの集大成
  • 30:アウグスティヌスとプラトン哲学
  • 31:アウグスティヌスと時間論;告白
  • 32:十字軍:イスラム文化(アリストテレス)の流入
  • 32.5: 位取り記数法(アラビア数字;ゼロの発見)
  • 33:神の存在証明(アンセルムス);スコラ哲学
  • 34:普遍論争と「存在・実在」;スコラ哲学
  • 36:[人気No.5]オッカムの剃刀(節約の原理)
  • 37:パラダイムシフト;コペルニクスとニュートン
  • 37(中):プラトンとアリストテレス;アテナイの学堂
  • 37(下):帰納主義;イドラ;ベーコン;経験論の祖
  • 38:天動説から地動説へ
  • 39:地動説・天動説とは、何か?
  • 40:ガリレオと地動説;ピサの斜塔;裁判
  • 41:ガリレオからニュートンへ
  • 42:プリンキピアと地動説
  • 43:因果関係とは何か?
  • 44:実在的因果関係(物理学)
  • 45:認識的因果関係(ヒューム・カント)
  • 46:数学的因果関係(ピタゴラス教団)
  • 47:言語的因果関係
  • 48:我思う、 ゆえに我在り(方法序説:デカルト)
  • 49:コギト命題からデカルト図式へ
  • 49下:物心二元論・心身二元論
  • 50:オカルト図式?
  • 52:中二病(デカルトの懐疑)
  • 53:世界記述と非ユークリッド的転回
  • 54:二元論・観念論に対する誤解
  • 56:ジョン・ロック$[$人間知性論$]$タブラ・ラーサ
  • 57:イギリス経験論の祖:ジョン・ロック;第ニ次性質
  • 58:大陸合理主義:ライプニッツ; 生得説
  • 59(上):日常言語はイギリス経験論的
  • 59(下):量子言語はカント哲学的
  • 60:唯心論:バークリー;存在するとは知覚されること
  • 61:懐疑主義:ヒューム
  • 62:実在的世界記述法と言語的世界記述法
  • 63:量子力学の道具主義化
  • 64:ライプニッツ・クラーク論争; 時空とは何か?
  • 65:コペンハーゲン解釈
  • 66:原点回帰:再びパルメニデスへ
  • 67:マクタガートのパラドックス:時間論:時制
  • 68:アウグスティヌスの時間論:主観的時間
  • 70:カント:二律背反(アンチノミー)
  • 71:「我思う、ゆえに我あり」を疑う
  • 72:カントの物自体; 模写説から構成説
  • 73:コペルニクス的転回;純粋理性批判
  • 74:純粋理性批判; アプリオリな総合判断;超越論的観念論
  • 78:カント登場の必然性
  • 78(補): 功利主義;ベンサム;最大多数の最大幸福
  • 79(上): ラプラスの魔:ゼノンのパラドックス
  • 79(下): ホーキング博士の哲学批判
  • 80:カントール:集合論
  • 80(下):空集合と選択公理
  • 81:数理論理学:数学のような、哲学のような
  • 82:弁証法という諺:ヘーゲル
  • 825: プラグマティズム(実用主義)のジレンマ
  • 83:論理哲学論考;ウィトゲンシュタイン
  • 84:言語論的転回;言語哲学
  • 86: 量子力学の解釈とは何か?
  • 88:量子言語の記述力;言語ゲーム;語りえぬもの;ウィトゲンシュタイン
  • 88.5:[人気No.1]心身問題の解決
  • 89: ボーア × アインシュタインの量子力学論争
  • 90: 二つの量子力学
  • 91: 数学の三大発見
  • 92: フォン・ノイマン;量子力学
  • 93: アリストテレス、ライプニッツ、フォン・ノイマン
  • 94: 確率の歴史
  • 95:確率の哲学: 確率とは何か?
  • 96: 確率論 vs. 量子言語
  • 97: 確率論: 二元論の消去
  • 98: 主観的時間; 科学哲学論争
  • 99: フィッシャーの最尤法
  • 100: 科学哲学の大きな物語の終焉
  • 補101:測定・推定・制御の科学哲学
  • 補102:ベイズ統計・ベイズの定理
  • 補103: 確率論と統計学
  • 150:量子力学再入門: ヒルベルト空間法
  • 152:エルミート行列のスペクトラル分解:量子力学再入門
  • 154:スピン:量子力学再入門
  • 156:ハミルトニアンの量子化:量子力学速習
  • 158:同時測定と可換条件:量子力学再入門
  • 160:ド・ブロイのパラドックス:量子力学再入門
  • 162:EPRパラドックス:量子力学再考
  • 164ベルの不等式:量子力学再考
  • 166:[人気No.4]ハイゼンベルグの不確定性原理はキャッチコピー
  • 168:EPRパラドックスの結末
  • 170:ハイゼンベルグの不確定性原理とEPRパラドックスは矛盾?
  • 174:[人気No.2]射影仮説:波束の収縮
  • 176:量子デコヒーレンス
  • 178:ハイゼンベルグ描像
  • 180:正準交換関係の不確定性関係
  • 182:行列のトレース
  • 184:ベルトランの逆説
  • 190:全射・単射・全単射
  • 192:」単射(順列)・全単射(スターリング数)
  • 500:量子言語入門(大学院講義ノート)