集合論勉強会 (20141202)のフィードバック(1)

集合論勉強会で投稿されたノートについてのコメント(内輪用なのでノートがないと意味不明です)。・「\(A-B\)が可能」を正確に表現すると:空集合も一種の集合であると認めることにすれば、\(A,B\)がどのような集合であっても「\(A-B\)という集合が存在する…

赤攝也『集合論入門』p121注意2(p122問7)

【問】二つの集合系\(A_i(i\in I),B_i(i\in I)\)において、\(I\)の元\(i\)のいかんにかかわらず\(|A_i|=|B_i|\)が成立するならば、\(|\prod_{i\in I}A_i|=|\prod_{i\in I}B_i|\)であることを示せ。【解答】各\(i\in I\)に対し全単射\(\varphi_i:A_i\to B_i\)…

赤攝也『集合論入門』p117~p118定理2の証明

【定理】\(a,b\)を二つの濃度とし、\(a > 0\)とする。このとき、\(|I|=a\)なる集合\(I\)を添え字の集合とする濃度系\(b_i\)(\(i\in I\))が、\(i\)のいかんにかかわらず\(b_i=b\)を満足するならば、その濃度系の和は\(ab\)に等しい:\[\sum_{i\in I}b_i=ab.…

赤攝也『集合論入門』p111問4

以下、テキストに合わせて\(0\notin\mathbb{N}\)としておく。【問】自然数の任意の列:\(m_1,m_2,\cdots,m_n,\cdots\)に対して\(m_1+m_2+\cdots+m_n+\cdots=\aleph_0\)が成り立つことを示せ。【解答】\(|A_k|=m_k\)を満たす素な集合系\(A_k\ (k\in\mathbb{N}…

赤攝也『集合論入門』p87問5

【問】集合\(A,R\)に対し、\(R\)から\(R\)への写像全体の集合を\(F\)、\(A\)から\(R\)への写像全体の集合を\(F_1\)とする。\(A\sim R\)ならば\(F_1\sim F\)であることを示せ。【解答】\(A\)から\(R\)への全単射の一つを\(\varphi\)とする。任意の\(f\in F\)…

部分集合への単射に関する性質

【演習】\(f\)は集合\(A\)からその部分集合\(B\)への単射であるとする。このとき、任意の自然数\(m,n\)(ただし\(m\neq n\))について\(f^m[A\backslash B]\cap f^n[A\backslash B]=\varnothing\)となることを示せ。【解答】\(m > n\)としても一般性を失わな…

Bernsteinの定理(改)

前エントリの証明を、\(A\rightarrow B\)でなく\(A\rightarrow g[B]\)の全単射を構成する方法に変えただけの証明。\(g^{-1}\)が登場しないのでちょっとだけ簡明かもしれない。【定理】(Bernsteinの定理) 集合\(A,B\)について、単射\(f:A\rightarrow B\)と…

Bernsteinの定理

【定理】(Bernsteinの定理) 集合\(A,B\)について、単射\(f:A\rightarrow B\)と単射\(g:B\rightarrow A\)が存在するとき、全単射\(h:A\rightarrow B\)が存在する。(証明)以下、自然数全体の集合\(\mathbb{N}\)には\(0\)も属すとする。 \(\displaystyle C=…

Heine-Borelの被覆定理

\(\bf R\)についてのHeine-Borelの被覆定理、すなわち「閉区間の任意の開被覆は有限部分被覆を持つ」を、Weierstrassの上限公理から導く。(証明)\(\mathcal U\)を閉区間\([a,b]\)の開被覆とする。\([a,b]\)の要素であって、しかも\([a,x]\)が\(\mathcal U\…

Rにおける「コンパクト」と「有界閉」の同値性

\(\bf R\)において、「コンパクト集合であること」と「有界な閉集合であること」とは同値であることを示す。ここではあえて、一般的な定理をできるだけ使わずに証明する。(コンパクト⇒有界かつ閉) \(C\)を\(\bf R\)におけるコンパクト集合とする。まず有界…

順序として/位相としての稠密性

【定義】(順序としての稠密性)全順序集合\(Y\)とその部分集合\(X\)について、\(a 【定義】(位相としての稠密性)位相空間\(Y\)の部分集合\(X\)が、任意の空でない\(Y\)の開集合と交わるとき、「\(X\)は\(Y\)において稠密である」という。この条件は下のい…

近傍系による位相の定義

\(S\)の各要素\(x\)に対し、\(S\)の部分集合のひとつ以上からなる集合族\(V(x)\)が対応づけられており、以下をすべて満たすとする。ただし\(A\triangleright x\)は\(A\in V(x)\)を意味する。(V1)\(A\triangleright x\rightarrow x\in A\) (V2)\(\exists U[A\…

分離集合による連結性の定義(2)

前エントリに引き続き、今度は位相空間の部分集合が「連結でない」ことを定義しよう。 【定義】位相空間\(Y\)とその部分集合\(X\)について、\(X\)を\(Y\)の部分空間と見たときに\(X\)が連結でないことを、「\(X\)は\(Y\)において連結でない」という。この定…

分離集合による連結性の定義(1)

位相空間\(X\)における、\(A\subset X\)の閉包を\({\rm Cl}_X(A)\)で表す。「位相空間\(X\)が連結でない」とは、「\(X\)が2つの非空なる\(X\)の開集合の直和で表される」、すなわち「 (0)\(A\neq\varnothing,B\neq\varnothing\) (1)\(A\cup B=X\) (2)\(A\cap…

順序体の定義

順序体の定義のいくつかの流儀が互いに同値であることを示す。§1.正錐による定義「体\(F\)は順序体をなす」とは、以下の条件をすべて満たすような\(P\subset F\)が存在することを言う。(1)\(\forall x,y\in P[x+y\in P]\) (2)\(\forall x,y\in P[xy\in P]\) …

アルキメデス的順序体は可換である

【定理】順序体\(F\)がアルキメデス的であるとき、\(F\)は可換である。(証明)\(F\)の任意の要素\(a,b\)をとる。\(F\)のアルキメデス性から、任意の\(\epsilon > 0\)に対して正の整数\(M, N\)が存在して、\(|a| *1 \(|ab|\)も\(|ba|\)も\((m -1)(n-1)\epsil…

区間縮小法の原理/Cantorの共通部分定理

順序体\(K\)の要素からなる数列\(\langle a_n\rangle,\langle a_n\rangle\)が、すべての\(n\in{\bf N}\)について\(a_n (1)\(\displaystyle \lim_{n\to\infty}(b_n-a_n)=0\):\(X\)の要素が1個以下であること(一意性)を示す。\(\alpha\in X,\beta\in X\)と…

Taylorの定理の直感的理解

注意:\(0^0=1\)と定めておく。 【定理】(Taylorの定理) \(n\)を正の整数とし、関数\(f:{\bf R}\rightarrow{\bf R}\)は\([a,b]\)で連続、\((a,b)\)で\(n\)回微分可能であるとき、\[f(b)=\left(\sum_{k=0}^{n-1}\frac{f^{(k)}(a)}{k!}(b-a)^k\right)+\frac{…

閉区間における連続関数は一様連続

【定理】閉区間\([a,b]\)において連続な関数\(f(x)\)は、\([a,b]\)において一様連続である。 (証明)\(\epsilon > 0\)と仮定する。\(f(x)\)の連続性と\(\epsilon/2 > 0\)により、任意の\(c\in[a,b]\)に対し、各々\(\delta_c > 0\)を、\(|x-c| 開区間\( (c-(…

中間値の定理の証明

【注意】この記事は古くなっており、意義を失っています。 y-bonten.hatenablog.com に移動してください。高木『解析概論』の中間値の定理の証明が理解しづらかったため、書き直した。【定理】(中間値の定理)区間\([a,b]\)において連続な関数\(F(x)\)につ…

最大値・最小値の定理からRolleの定理を導く

【定理】(Rolleの定理)関数\(f:{\bf R}\rightarrow{\bf R}\)が\([a,b]\)で連続、\((a,b)\)で微分可能であり、\(f(a)=f(b)=0\)が成り立つとき、\(f'(c)=0\)を満たす\(c\in(a,b)\)が存在する。(証明)最大値・最小値の定理により、\(f(x)\)は\([a,b]\)にお…

ε近傍の境界点

\({\bf R}^n\)において\(d(a,b)=\epsilon > 0\)のとき、任意の\(\epsilon' > 0\)に対して\(U(a,\epsilon)\)と\(U(b,\epsilon')\)は交わることを示せ。 (証明) \(\epsilon' > \epsilon\)のとき、\(d(b,a)=\epsilon \(\epsilon'\leq\epsilon\)のとき、\(a=(a…

開核は開集合である

距離空間\((X,d)\)において、「点\(a\in X\)は集合\(M\subset X\)の内点である」とは「\(U(a,\epsilon)=\{x\in X|d(a,x) 0\)が存在する」ことと定義し、自己の内点のみからなる集合を「開集合」と呼ぶことにする。集合\(M\)の内点全体の集合(\(M\)の開核)…

距離空間から位相空間への橋渡し

距離空間\((X,d)\)を考える。 【定義】(\(\epsilon\)-近傍) 点\(a\in X\)と正の実数\(\epsilon\)に対し、\(a\)から距離\(\epsilon\)未満の点の集合、すなわち\(\{x\in X|d(a,x)【定理1】(点は自身の近傍の要素) 任意の\(x\in X\)と\(\epsilon > 0\)につ…

デデキントの切断公理からワイエルシュトラスの公理を導く

【注意】より一般的な議論を http://y-bonten.hatenablog.com/entry/2015/05/19/030805 で行っているため、このエントリは意義が薄くなっています。稠密全順序集合に対して、デデキントの切断公理 「任意の切断に対して、その補集合が最小元を持つ」 から、…

f(x)=x^2が連続関数であること

『はじめよう位相空間』(大田春外著、日本評論社)p53例題4.7 関数\(f:{\bf E}^1\rightarrow{\bf E}^1;x\mapsto x^2\)は連続関数であることを証明せよ. の証明を書き直した。直してみたかった点は2つ。 (1)教科書の証明では\(\delta\)を「この範囲にとれば…

限定された閉曲線に対する、ガウスの発散定理(平面版)の証明の概略

\(xy\)平面上のベクトル場\(\vec{v}(x,y)=(v_x(x,y),v_y(x,y))\)と、閉曲線\(\partial D\)に囲まれた領域\(D\)を考える。\(\partial D\)の微小線素の法線ベクトルで、\(D\)の外側を向き、線素の長さに等しい大きさを持つものを\(d\vec{L}\)と書く。\(\partia…

IE10+FOXITでPDFをタッチパネル操作で縦スクロールする方法

Win8タブレットPC上のPDFビューアとしてFOXITを使っている。 ブラウザ(IE10)ウィンドウ内でPDFを表示させ、「手のひらツール」で縦にスクロールさせようとタッチパネルで上下にドラッグしても動作しない場合の(本質的でない)解決法。表示を充分に拡大し…

ガウスの発散定理(平面版)

線積分は進行方向を逆にすると符号も反転する。いっぽうで、ガウスの発散定理の平面版を考えると、積分の方向は気にしなくてよいように見える。この疑問を解決するためのメモ。 平面上のベクトル場\(\vec{A}(x,y)=(A_x(x,y),A_y(x,y))\)と、閉曲線\(C\)およ…

『よくわかる初等力学』章末演習11-5

初めに、\(a,b\)はそれぞれ\(r_0/(1-\epsilon^2),r_0/\sqrt{1-\epsilon^2}\)の略記であるのので、(11.42)を\(a,b\)を用いない形に書き直しておく。\[\frac{\cos\phi}{1+\epsilon\cos\phi}=\frac{\cos\alpha-\epsilon}{1-\epsilon^2}\tag{1}\]\[\frac{\sin\ph…

『数学ガールの秘密ノート/丸い三角関数』第4章について

『数学ガールの秘密ノート/丸い三角関数』(結城浩著、SBクリエイティブ)の第4章の後半、アルキメデスの方法の議論の流れを整理したメモ。4.9節の終盤(p188)で「僕」は 《辺の数を2倍にしたときに、辺の長さを計算する方法》を見つければいい と言ってい…

ワイエルシュトラスの公理

実数の完備性を定義する流儀のひとつであるワイエルシュトラスの公理は、「上界を持ち空でない任意の集合が上限を持つ」と書かれるが、これは上下を入れ替えて「下界を持ち空でない任意の集合が下限を持つ」と書いても同値である。この同値性を証明する過程…

デデキント『連続性と無理数』§4末尾の疑問

デデキント「連続性と無理数」(英訳: http://www.gutenberg.org/files/21016/21016-pdf.pdf )についての疑問メモ。(議論の前提)有理数全体の集合に対し、その切断\((X_1, X_2)\)がひとつ定まるごとに、それに対応する実数\(x\)がひとつ定まる、とする。…

確率統計入門ゼミ(03/19/2014)の補足

2項分布\(B(n,p)\)に従う確率変数の期待値。\(1-p\)を\(q\)と書くことにする。 \(n=3\)のとき \(3\cdot{_3C_3}\cdot p^3+2\cdot{_3C_2}\cdot p^2q+1\cdot{_3C_1}\cdot pq^2+0\cdot{_3C_0}\cdot q^3\) \(=3\cdot 1\cdot p^3+2\cdot 3\cdot p^2q+1\cdot 3\cdot…

デデキント『連続性と実数』

デデキント『連続性と実数』( http://books.google.co.jp/books?id=n-43AAAAMAAJ )の序文の末尾の一文の意味がよく理解できないのでメモ。「このカントールの論文における公理は、私が連続性の本質として説いているものと、見かけ上の違いを除いては一致し…

確率統計入門の自主ゼミの予習

確率・統計入門の自主ゼミに参加させてもらうことになったので、補充問題をいくつか。テキストは『プログラミングのための確率統計』(平岡和幸・堀玄 共著、オーム社)。・2個のサイコロA,Bを投げる。「Aの目が1である」という事象と「AとBの目の和が[__]…

自主ゼミ復習課題

前回の数理論理学ゼミで扱われた累積帰納法に関連する復習課題。\(p_x\)は\(x\)番目の素数、すなわち\(p_0=2, p_1=3, p_2=5, \cdots\)である。 \( (z)_x\)は\(z\)を素因数分解したときの\(p_x\)の指数部の値。例えば\( (750)_2=(2^13^15^3)_2=3\)である。\(F…

素数判定アルゴリズム

The Haskell Road to Logic, Maths, and Programming( http://fldit-www.cs.uni-dortmund.de/~peter/PS07/HR.pdf )のp3~p8にある、素数判定プログラムの解説に対して感じた疑問を書き留めておく。以下、\(n\)は常に2以上の整数、すなわち素数か合成数かの…

キーワードリンク抑止の挙動について

以下、[]は全角で書いているので、文章の内容とこの記事そのものの出力は一致しない。[]かくかくしかじか (空行) (はてなキーワード)だと([]が閉じていないために)記事中の文字として[]が出力されるのに対し、[]かくかくしかじか (空行) …

一意に存在する

「\(F(x)\)を満たす\(x\)は一意に存在する」ことを\(\exists!x[F(x)]\)といった論理式で表すが、その定義にはいくつもの流儀があり、互いに同値であることを納得しておきたい。そもそも「一意」という語は「1個以下」という意味なのか「ちょうど1個」という…

「項が関数を表現する」ということ

n変数関数の表現可能性は、(n+1)変数の論理式によって定義する流儀のほかに、n変数の項によって定義する流儀もあることを知った。 以下、何変数関数でも同様であるので、1変数関数で考える。 従来から知っていたのは 「すべての自然数m,nに対して、以下の(α)…

1の目が出るまでサイコロを振る回数の期待値

サイコロを6回振って1の目が出る回数の期待値が1回であることはよく知られている。では、1の目が出るまでサイコロを振り続けたとき、その回数の期待値はいくらか?一般に、1回試行において確率p(≠0)で起こる事象が初めて起こるまで反復試行を行なったとき、…

ゲーデルの第1不完全性定理の証明のスタイル

ゲーデルの第1不完全性定理を証明する際、多くの教科書では「かくかくしかじかな体系がω無矛盾である(したがって無矛盾でもある)」ということを仮定して、「そのとき、こういう文Gについて、\(\vdash G\)でも\(\vdash \neg G\)でもない」ということを導い…

ω矛盾

矛盾とω矛盾、無矛盾とω無矛盾、初めて聞いたときはどちらが強い条件なのか分からなくてずいぶん苦労した。 体系が矛盾することを「何かヨロシクナイ事態」だと勝手に想定するならば、「ω矛盾は軽傷」と憶えておくと便利だ。 そして「ガッツリ矛盾する/ω矛…

『数学ガール・乱択アルゴリズム』リニアサーチの議論

『数学ガール・乱択アルゴリズム』第2章p43、「見つかった場合」と「見つからなかった場合」を統合する議論において、見つからなかった場合のMをnとするのは唯一の方法ではないことに注意。ここでは他の考え方を試してみる。 「見つかったときのνの位置」と…

置き換えの定理

『論理学をつくる』p52定理6は、より強い定理7を経由して証明されているが、直接証明するとどうなるだろう。 AとBが論理的同値であると仮定する。すると、AとBの真理値は常に同じである。このとき、C[A]とC[B]は前者がAを部分論理式として含んでいる何カ所か…

正項等比数列a_nのn乗根は公比に収束する

正項等比数列\(\{a_n\}\)に対して\(\sqrt[n]{a_n}\)を考えると、これは\(n\to\infty\)で公比に収束する。そのイメージ。 \[3,6,12,24,48,96,192,\cdots\] 初項がいくらであっても、\(a_n\)から公比のn乗を引っ張り出して来ることができる。 \[\frac{3}{2}\ti…

関数の表現可能性の定義

「論理式\(F(x_1,x_2)\)が関数\(f(x)\)を表現する」 の定義は 任意の自然数\(\rm q_1,q_2\)に対して、次の(α)(β)がともに成り立つ。 (α)\(\rm f(q_1) = q_2\)であるとき\(\vdash F(\bar{\rm q_1},\bar{\rm q_2})\) (β)\(\vdash\exists!x_2[F(\bar{\rm q_1},x…