論理と集合から始める数学の基礎 読書会
テキスト
方針
第二部終わりまで読めたら最高
途中で止まっても気にしない。そのうち再開できるかも
じっくり足固めして行きつ戻りつする
読めるかな
極限までハードルを低くしろの法則に従い2日3日に数分読んでみよ
まだまだハードルが高い
一週間で14ページ進んだぞ！(2022/12/9)
二ヶ月で35ページまで来たぞ！(2023/02/01)
目次を貼り付けておこう
第１部 論理と集合の基礎
第1章 集合(その1)
1.1 集合とは
空集合はある集合の部分集合になるか？←あとから再度取り組む
1.2 集合の書き表し方
集合の内包的記法における普遍集合の明示
この本においては、普遍集合は文脈中で宣言するとのこと
\{x\in U |P(x)\}じゃなくて\{x|P(x)\}の形をとる
第3章で論じる述語の真理集合との対応を明確にするために、あえて普遍集合は文脈中で宣言するらしい(p.6)
実際は前を使うのが一般的であるとは言ってる
この段階だと、まだ意図がわからない
1.3 集合の基本的な演算
1.4 演習問題
第2章 命題計算
これ初耳
なんのことだか気になる
真理値の話について書いてる
論理演算子や恒真命題、矛盾命題など
true falseを計算しているだけですね。理解
2.1 命題と真理値
2.3 命題代数
代数ってなんだろう？
>数字と文字を使って数の性質や相互関係を研究する学問 (角川新類語辞典)
ふーむ
未知数を文字でおいて式展開するやつ、ってくらいの認識でいいと思う
2.4 含意と同値の論理演算子
2.5 演習問題
3.1 述語(数学)
3.2 真理集合
3.3 述語の演算と真理集合
3.4 全称命題と存在命題
真理集合で表すと
全称命題は\forall xP(x)、すなわち「Uのすべての要素xは条件P(x)をみたす」
つまり「述語P(x)の真理集合はUである」
存在命題は\exist xP(x)、「Uのなかのある要素xは条件P(x)をみたす」
真理集合を使って表すなら、「述語P(x)の真理集合は空集合ではない」ということ
3.5 述語に関する「ならば」の使われ方
書いてあることよくわかんねぇ～
ので一回整理
これは「条件文の命題」を表す時に使う
今回新しい話
1. 述語でも\toを使うことができる！
例:P(x) \to Q(x)
どの論理記号\lor,\land,\lnotも使える
ってどこかでやったか
2. でも、条件文の命題「P(x)ならばQ(x)」と述語「P(x) \to Q(x)」には意味のズレがある
前者は命題なので「真偽」が決定できる
後者は述語なので自由変数xに値が入らないと「真偽」を決定できない
………？？？？
[" 条件文の命題「P(x)ならばQ(x)」]にも自由変数xが入っているが……
どゆこと？
言葉足らずすまぬ
あんまり良くわかってないのがまるわかり！
言及箇所を引いてきた
>ところが，数学の文脈で P(x)ならば Q(x)といえば，多くの場合，「Uの要素が条件 P(x)をみたせば，それは条件 Q(x)をみたす」という主張を意味します.そして，この主張は命題であって，真か偽かが定まっています.(p.36)
このあと真理集合の話になるがの理解が追っついてない()
これなら真偽が定まるので確かに命題である
たぶんこれ
暗黙的に全称の…その…あれがついているということ
言語化の難〜
こうなるので数学に自然言語を混ぜたくないと日頃から思っている
図書館で確認してきました。これであってます
というかこの次の文章に書いてあった
ありがとうございます！
総括するとなんと表現できるか……
述語(数学)ってなんだったかな
過去の俺がメモを書いていた
なるほど、変数の値が定まっているかどうかなんだな
言い方は正しくないかも
数学ではなく日本語の問題であった
>この行まで読んでる
第4章 集合(その2)
第5章 2変数以上の述語
第6章 述語と数学的論証
第２部 集合で表される構造
>ここから問題だけ拾い食いする
第7章 写像
第8章 2項関係とその表現
8.3 二項関係の図による表現
有向グラフとの関係が初見で新鮮だった
思えばグラフってtoとfromで一つの辺を指定できるから、順序対の集合で捉えることもできるのか
グラフを扱うアルゴリズムを書いてるとこの辺は肌感覚として感じる
コラム19 有向グラフと2項関係
任意の有限集合VとE\subseteq V^2を満たすEについて、(V,E)を有向グラフと呼ぶ
Eの元が、グラフの矢印を表している
直積集合(の部分集合)と二項関係は一対一対応が成り立つので、どっちで表現しても同じこと
8.4 演習問題
8.1 X=\{a,b,c,d\}とし、X上の二項関係Rを以下の行列で定める
\begin{array}{c|cccc}&a&b&c&d\\\hline a&1&0&0&1\\b&1&1&1&1\\c&1&0&1&0\\d&0&0&1&1\end{array}
1. Rを集合とみなし、要素を全て書き並べて表せ
\{(x,y)\in X^2|R(x,y)\}=\{(a,a),(a,d),(b,a),(b,b),(b,c),(b,d),(c,a),(c,c),(d,c),(d,d)\}
2. Rを2項関係の座標図で表せ
8.1.2.tikz(tex)\begin{document}
\begin{tikzpicture}[domain=0:4]
\tikzset{
col/.style={above,font=\Large},
row/.style={left,font=\Large},
point/.style={circle,fill,inner sep=2pt},
}
\draw[help lines] (0,0) grid (4,4);
\draw[thick] (0,4) -- ++(4+0.5,0);
\draw[thick] (0,4) -- ++(0,-4-0.5);
\path[col] (0,4)--++(1,0)node{$a$}--++(1,0)node{$b$}--++(1,0)node{$c$}--++(1,0)node{$d$};
\node [row] at (0,3) {$a$};
\node [row] at (0,2) {$b$};
\node [row] at (0,1) {$c$};
\node [row] at (0,0) {$d$};
\path (0,3) -- ++(1,0)node[point]{} -- ++(3,0)node[point]{};
\path (0,2) -- ++(1,0)node[point]{} -- ++(1,0)node[point]{} -- ++(1,0)node[point]{} -- ++(1,0)node[point]{};
\path (0,1) -- ++(1,0)node[point]{} -- ++(2,0)node[point]{};
\path (0,0) -- ++(3,0)node[point]{} -- ++(1,0)node[point]{};
\end{tikzpicture}
\end{document}3. Rを有向グラフで表せ
8.1.3.tikz(tex)\begin{document}
\begin{tikzpicture}[domain=0:4]
\tikzset{
recursive/.style={in=60,out=120,looseness=6},
recursive flip/.style={out=-60,in=-120,looseness=6},
every node/.style={font=\Large},
}
\def\l{4}
\node (a) at (0,\l) {$a$};
\node (b) at (\l,\l) {$b$};
\node (c) at (\l,0) {$c$};
\node (d) at (0,0) {$d$};
\draw[->,very thick]
(a) edge[recursive] (a)
edge (d)
(b) edge (a)
edge[recursive] (b)
edge (c)
edge (d)
(c) edge (a)
edge[recursive flip] (c)
(d) edge (c)
edge[recursive flip] (d);
\end{tikzpicture}
\end{document}8.2 以下に示す\R上の2項関係のグラフの概形を示せ
1. R_1(x,y):\iff x\le 2y
直線で区切られた領域
2. R_2(x,y):\iff x^2-y=0
横に寝た放物線
3. R_3(x,y):\iff x^2-y^2=0
2直線
4. R_4(x,y):\iff\exist t\in\R.x=2\cos t\land y=\sin t
x方向に長径2, y方向に短径1の楕円
図を書くのめんどいのでパス
9.1 順序関係
線形順序とも呼ぶらしい
どうして線形がつくのだろうか
線形代数の意味の線形ではなく「一列に並んでる」のニュアンス
なるほど～めっちゃ納得
全順序 - Wikipediaにも書いてあった(出典つき)
9.2 順序集合
1. 反射律\forall x\in A.x\le x
2. 推移律\forall x,y,z\in A. x\le y\land y\le z\implies x\le z
このとき\leを前順序と呼ぶ
3. 反対称律\forall x,y\in A.x\le y\land y\le x\implies x=y
このとき\leを半順序と呼ぶ
4. 完全律\forall x,y\in A.x\le y\lor y\le x
これで全ての元を一列に並べられることが保証される
典型例が数直線
前順序 - Wikipediaでは全順序律と呼んでいる
完全関係 - Wikipediaでは完全律と呼んでいる
このとき\leを全順序と呼ぶ
コラム20 辞書式順序
辞書順のこと
9.3 Hasse図
9.4 順序同型
1. \varphiは全単射
2. \forall u,u'\in U_1.(u\le_1 u'\iff\varphi(u)\le_2\varphi(u'))
これが順序「構造を維持する」条件に該当する
順序同型写像が存在するとき、両者は順序同型であるという
Hasse図にするとわかりやすい
同じ形になる
例9.6 S:=\{a,b,c\},D_{70}:=\{x\in\Z|70\backslash x\}として、(2^S,\subseteq),(D_{70},\backslash)のHasse図を比較する
右が(2^S,\subseteq), 左が(D_{70},\backslash)
要素が違うだけで、つながり方は全く同じだとわかる
同型の図的理解
実際に順序同型であることを示す
\phi:S\to\{2,5,7\};a\mapsto2,b\mapsto5,c\mapsto7
\varphi:2^S\ni A\mapsto\prod_{x\in A}\phi(x)\in D_{70}
とすれば、\varphiが順序同型写像の一つになるので、2^S,D_{70}が順序同型だとわかる
証明
一対一対応なのは列挙すればわかる(略)
なお、\forall P.\prod_{x\in\varnothing} P(x)=1とした
同型を証明する
\forall A,B\in 2^S.
A\subseteq B
\iff\forall x\in A.x\in B
\iff\forall x\in\phi[A].x\in\phi[B]
\iff \varphi(A)\backslash\varphi(B)
展開はちょい端折った
\phi[B]が\phi[A]を包んでいるので、\phi[B]の総積は\phi[A]の総積で割り切れる
また総積を分解すれば元に戻るので、逆も成り立つ
厳密に解くには、素因数分解の一意性を持ちこむ必要があるかも
9.6.1.tikz(tex)\usepackage{amssymb}
\begin{document}
\begin{tikzpicture}[domain=0:4]
\tikzset{
every node/.style={circle,draw,inner sep=2pt,fill=white},
every path/.style={very thick},
}
\coordinate (left) at ({-sqrt(3)},1);
\coordinate (right) at ({sqrt(3)},1);
\draw (0,0) node[label={below:$\varnothing$}](o){}
-- ++(right) node[label={right:$\{c\}$}](c){}
-- ++(left) node[label={right:$\{a,c\}$}](ac){}
-- ++(0,1) node[label={right:$\{a,b,c\}$}](abc){};
\draw (o)
-- ++(0,1) node[label={right:$\{b\}$}](b){}
-- ++(right) node[label={right:$\{b,c\}$}](bc){}
edge (c)
-- (abc);
\draw (o)
-- ++(left) node[label={left:$\{a\}$}](a){}
edge (ac)
-- ++(0,1) node[label={left:$\{a,b\}$}](ab){}
edge (b)
-- (abc);
\end{tikzpicture}
\end{document}9.6.2.tikz(tex)\usepackage{amssymb}
\begin{document}
\begin{tikzpicture}[domain=0:4]
\tikzset{
every node/.style={circle,draw,inner sep=2pt,fill=white},
every path/.style={very thick},
}
\coordinate (left) at ({-sqrt(3)},1);
\coordinate (right) at ({sqrt(3)},1);
\draw (0,0) node[label={below:$1$}](o){}
-- ++(right) node[label={right:$7$}](c){}
-- ++(left) node[label={right:$14$}](ac){}
-- ++(0,1) node[label={right:$70$}](abc){};
\draw (o)
-- ++(0,1) node[label={right:$5$}](b){}
-- ++(right) node[label={right:$35$}](bc){}
edge (c)
-- (abc);
\draw (o)
-- ++(left) node[label={left:$2$}](a){}
edge (ac)
-- ++(0,1) node[label={left:$10$}](ab){}
edge (b)
-- (abc);
\end{tikzpicture}
\end{document}コラム21 構造と同型
ここでそこそこまあまあ精密に読む『ベーシック圏論 普遍性からの速習コース』とつながった
全単射があるだけではなくて構造を維持する写像であることが必要。この写像を同型写像と呼ぶ
9.5 順序に関する諸概念
9.6 束
>ここまで解いてる
TODO：解き残しがあるので、そっちを先に片付ける
図書館に返却してしまったので、しばらく進まない予定
問題を書き写しているのはやっておこうと思う
有限な束には必ず最大元と最小元が存在する
例9.10
9.7 演習問題
9.1 8.4 演習問題の8.1のRがX上の順序関係でないことを証明せよ
\begin{array}{c|cccc}&a&b&c&d\\\hline a&1&0&0&1\\b&1&1&1&1\\c&1&0&1&0\\d&0&0&1&1\end{array}
反射律は成り立つ
対角線上に1が並んでいる
推移律が成り立たない
a,d,cがcyclicになっていて、推移律が成立していない
よって、8.1のRは順序関係でない
9.1.tikz(tex)\begin{document}
\begin{tikzpicture}[domain=0:4]
\tikzset{
recursive/.style={in=60,out=120,looseness=6},
recursive flip/.style={out=-60,in=-120,looseness=6},
every node/.style={font=\Large},
}
\def\l{4}
\node (a) at (0,\l) {$\bf a$};
\node[gray] (b) at (\l,\l) {$b$};
\node (c) at (\l,0) {$\bf c$};
\node (d) at (0,0) {$\bf d$};
\draw[->,very thick,gray]
(a) edge[recursive] (a)
edge[black] (d)
(b) edge (a)
edge[recursive] (b)
edge (c)
edge (d)
(c) edge[black] (a)
edge[recursive flip] (c)
(d) edge[black] (c)
edge[recursive flip] (d);
\end{tikzpicture}
\end{document}9.2 狭義の順序の性質
9.3 辞書式順序は全順序をなすことを示せ
9.4
9.5
9.6
9.7
9.8 一致数え上げ
第11章 集合の要素の個数
第12章 可算集合
9~11はグラフ理論の前段階
これ以降は飛ばしていいと思う
目次だけ頭にいれて、必要な時に学び始めればいい
2022-12-06 11:56:04 第16章はやったほうがよさそう
13~15を飛ばしてもやれると思う
第13章 命題計算の応用
第14章 ブール代数
練習問題スタック
これをクリアできると、空集合はある集合の部分集合になるか？への道(の一つ)が解放される
うわあああああ▂▅▇█▓▒░░▒▓█▇▅▂
取り組んでない問題がたまるのって、こわい！
スマホだと改行されちゃうのでうわああああ感が減る
それはそれとして自分のアイコンが四角いのでただの階段のような何かになってる
図書館で見てきた
410.12||Ka 13
予想より内容が豊富だった
例や問題演習もたくさんついている
ちょくちょく問題を勝手に作っていたが、最初からこれだけあるなら変に作らなくてもいいかな