プ意味論基礎1.2
1.2.1
部分集合: $ X \subseteq Y \Leftrightarrow \forall x \in X .x \in Y
集合の等しさ: $ X = Y \Leftrightarrow X \subseteq Y \land Y \subseteq X
和集合: $ X \cup Y = \{x | x \in X \lor x \in Y\}
共通集合: $ X \cap Y = \{x | x \in X \land x \in Y\}
冪集合: $ 2^X = \{Y | Y \subseteq X\}
$ 2^Xと書くのは、Xの要素の数をnとするとXの冪集合の要素の数が$ 2^nになるからだと思われ
これは部分集合が、Xの各要素がそこに含まれるかを0, 1のビットで表現できることからも直感的にわかる。例えば$ X = \{a, b, c\}の場合、$ \emptysetは$ 000、$ \{a, b\}は$ 110と表せる。ただしビットは左からa, b, cに対応。
直積: $ X \times Y = \{(x, y) | x \in X \land y \in Y\}
1.2.2
$ (x, y) \in Rと$ xRyは同じ意味
同値関係
反射律: 自然数上の関係で言えば$ =は満たすけど$ <は満たさない
対称律: 同上
推移律: $ <も満たす
演習1.2
$ x \equiv y(mod \, n)とか。nは0以外の自然数ならなんでもいい
半順序関係
同値関係から対称律out, 反対称律in
例: 自然数上の$ \leq, $ 2^X上の部分集合関係
半順序関係$ Rが$ \forall x, y.\,xRy \lor yRxを満たすとき全順序関係と呼ぶ
$ \leqは全順序だが$ 2^X上の部分集合関係は違う
整礎関係
無限に列をつなげることはできなくて絶対どっかで止まるよってこと
整数上の$ <は無限に小さいのを作れるので整礎ではない
反射推移的閉包
2項関係Rを反射性と推移性を持つように膨らませたやつの中で最小のやつ
$ R^*が定義を満たしているか証明しよう
演習1.3
$ \{(0, 2), (2, 3)\}を$ \{0, 2, 3\}上の2項関係と見るか、$ \mathbb{N}上の2項関係で見るかで答え変わるやんけ
前者だとすると$ \{(0, 2), (2, 3), (0, 0), (2, 2), (3, 3), (0, 3)\}
演習1.4
有向グラフの辺集合は頂点集合の直積で表される。$ (x, y) \in Eのとき、頂点xから頂点yへの辺がある
$ (x, y) \in E^*のとき、n (>=0) 個の頂点を経て頂点xから頂点yへ到達できる
1.2.3
部分関数
定義域の中に未定義要素があってもよい関数
$ f: X \rightharpoonup Yと書くとfはXからYの部分関数とみなす。矢が上半分だけの矢印なので注意
合成
関係の合成と同じだけど順番が逆になっているので注意
関数
いわゆる普通の意味での関数
全射
https://upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Surjection.svg/200px-Surjection.svg.png
単射
https://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Injection.svg/200px-Injection.svg.png
全単射
https://upload.wikimedia.org/wikipedia/commons/thumb/a/a5/Bijection.svg/200px-Bijection.svg.png
逆射
なぜ全射だけではダメか。上の全射の図だと3, 4が両方Cに写されるので、Cから戻す先が一意でない(関数にならない)から
演習1.5
1. $ \{(0, 0), (1, 1)\}, \{(0, 1), (1, 0)\}
2. $ \{0, 1, 2\}から$ \{0, 1\}への関数は$ 2^3個あり、そのうち全射でないのは全部0に写すやつと全部1に写すやつの2つなので6個
3. $ \{(2, 0), (1, 1)\}
1.2.4
集合の濃度
集合間に全単射が存在すれば、要素間の一対一対応が作れるということなので濃度は等しい
可算集合、非可算集合
無限集合の濃度は自然数と同じ(可算)か実数と同じ、とするのが連続体仮説。これは証明も反証もできないっぽいが、前提としても普通にうまく行くらしい
演習1.6
3. ASCIIだけ使えるとすると(C言語でASCII以外を使えるのか知らん。使えたとしても方針は同じ)、文法的に正しいC言語のプログラムの各文字を8ビット列に変換してつなげて最後に1ビット足せばおk。これは自然数の部分集合への写像で、任意の自然数の部分集合は可算。