2019-07-21

関数の初等な連続性の距離空間への一般化

数学距離空間

距離空間

距離空間とは、次の公理を満たす距離関数(distance function) $d: X \times X \to \mathbb{R}$ を持つ集合 $X$ のことをいう。

$d(a, b) \geq 0$
$d(a, b) = 0 \iff a = b$
$d(a, b) = d(b, a)$
$d(a, c) \leq d(a, b) + d(b, c)$

つまり、

2点 $a, b$ 間の距離は $0$ 以上
2点 $a, b$ 間の距離が $0$ であることは、 $a$ と $b$ は同じ点
距離関数の引数を入れ替えても、2点間の距離は変わらない
$b$ を経由すると、2点 $a, c$ をまっすぐ進むよりも距離は大きいか、等しくなる

という自然な距離の性質を満たす関数 $d: X \times X \to \mathbb{R}$ が定義されている集合のことを距離空間という。
距離空間は、考える集合 $X$ とその上の距離関数 $d: X \times X \to \mathbb{R}$ の2つを組みにしたもの $(X, d)$ として表される。
例えば、実数 $\mathbb{R}$ の上に、 $a \in \mathbb{R}$ と $\mathbb{R}$ の差の絶対値 $|a - bl|$ を距離関数として入れれば、その $[tex: (\mathbb{R}, | \cdot |)$ は距離空間になるし、2次元ユークリッド平面 $\mathbb{R}^2$ 上に $\|a - b\| = \sqrt{a^2 + b^2}$ を入れたもの $(\mathbb{R}^2, \| \cdot \|)$ も距離空間になる。

注意して欲しいのは、上の定義を満たすような集合と距離関数が与えられれば、それは距離空間と言われる、ということである。
つまり、自然に感じられないような定義、例えば、集合 $X$ 上に、

$d(x, y) = \begin{cases} 0 & \text{if} \enspace x = y \\ 1 & \text{otherwise} \end{cases}$

というような関数を定義してやると、これは距離関数となり、 $(X, d)$ は距離空間となる(確かめるのは簡単なので、試してみて欲しい)。

関数の連続性

実数空間 $\mathbb{R}$ 上の関数の連続性とは、理系の大学1年生ならならうかもしれないが、 $\epsilon$ - $\delta$ 論法という形で表される( $\epsilon$ - $N$ もあるけど、ここでは割愛)。

つまり、関数 $f: \mathbb{R} \to \mathbb{R}$ が点 $a \in \mathbb{R}$ で連続(continuous)であるとは、任意の正の実数 $\epsilon > 0$ を考えたとき、ある

$\forall x \in \mathbb{R}; |x - a| < \delta \implies |f(x) - f(a)| < \epsilon$

を満たすような正の実数 $\delta > 0$ が存在することをいう。
すなわち、どんな距離 $\epsilon$ をとっても、 $a \in \mathbb{R}$ との距離が $\delta$ となるような全ての点 $x$ に対して $f(x)$ と $f(a)$ との距離が $\epsilon$ より小さくような $\delta$ が存在すれば、関数は連続であると主張している。

連続性の一般化

$(\mathbb{R}, |\cdot|)$ と、 $f: \mathbb{R} \to \mathbb{R}$ によって写像された $(\mathbb{R}, |\cdot|)$ はどちらも距離空間となっている。
これは、関数の連続性はその2つの距離空間によって定義されていると考えることができる。
つまり、この考え方を用いて、一般の距離空間 $(X, d)$ とその写像先 $(Y, d')$ における連続性を定義しようというわけだ。
すなわち、距離空間 $(X, d)$ に対して、 $(Y, d')$ へ写像する関数 $f: X \to Y$ が点 $a \in X$ で連続であるとは、任意の正の実数 $\epsilon > 0$ に対し、

$\forall x \in X; d(x, a) < \delta \implies d'(f(x), f(a)) < \epsilon$

となるような正の実数 $\delta > 0$ が存在することをいう、というように定義するのである。
このようにすれば、関数の連続性をより一般の距離空間へと拡張できる。

2019-07-13

wpa_cliに渡せるアクションスクリプト

wpa_cliはwpa_supplicantからのイベントを待ち受けて実行されるアクションスクリプトというものを設定できる。このアクションスクリプトは第二引数にwpa_supplicantからのイベントが渡される。

イベント	意味
CONNECTED	APへの接続時に発行される
DISCONNECTED	APから接続解除されたときに発行される

これを使って、次のようなスクリプト(ここではhoge.sh)を作ってやり、

case "$2" in
  "CONNECTED") echo "APへ接続されたときの処理。DHCPとかを連続して呼びたいときとか";;
  "DISCONNECTED") echo "APから接続解除されたときの処理、クリーンアップとか";;
esac

wpa_cliの-aオプションの引数として指定してやると、wpa_supplicantからイベントが呼ばれるたびに、登録したスクリプトが発行される。

wpa_cli -B -i wlan0 -a hoge.sh

みたいにしてやると、バックグラウンドで動作しつつ、wlan0インターフェースを監視して、wpa_supplicantからイベントが来たら、hoge.shが呼ばれる。

オプション	意味
`-B`	wpa_cliをバックグランドで起動するようにする
`-i wlan0`	操作対象のWi-Fiインターフェースを指定する。`wlan0`に好きなインターフェース名を入れる

問題は、アクションスクリプトに実行権限が付いているかどうかという部分。気付かないと時間が溶ける(溶けた)。この手のスクリプト名を指定しておいて実行させるようなコマンドは気を効かせて、bashコマンドとかでスクリプト名指定して確実に走らせるようにしたりすることが多い(気がする)、のだけど、このwpa_cliはそんなことはしてくれない。実行権限を適切に付けてやらねばならない。

chmod +x hoge.sh

原因

理由はわかりきっているが、きちんと書いておく。なお、適宜いらない部分は削除している。

まず、main関数のオプション解析部で、-aに渡されたオプション引数をaction_fileという変数に収めている。

/* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n54 */
static const char *action_file = NULL;

int main(int argc, char *argv[])
{
    /* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n4641 */
    for (;;) {
        c = getopt(argc, argv, "a:Bg:G:hi:p:P:s:v");
        if (c < 0)
            break;
        switch (c) {
        case 'a':
            action_file = optarg;
            break;
        }
    }
}

main関数内の前処理が終了したら、action_file変数を見て、スクリプトが指定されていたらwpa_cli_action関数へ処理を移す。

int main(int argc, char *argv[])
{
    /* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n4724 */
    if (action_file)
            wpa_cli_action(ctrl_conn);
}

このwpa_cli_actionが、wpa_cli_action_receiveをAP接続イベントが発生したときのハンドラとして登録しておく。

/* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n4533 */
static void wpa_cli_action(struct wpa_ctrl *ctrl)
{
    /* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n4544 */
    eloop_register_read_sock(fd, wpa_cli_action_receive, ctrl, NULL);
}

APへ接続できたら、wpa_cli_action_receiveが呼ばれる。 wpa_cli_action_receiveはwpa_cli_recv_pendingを単に呼びだすだけ。

/* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n4525 */
static void wpa_cli_action_receive(int sock, void *eloop_ctx, void *sock_ctx)
{
    /* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n4529 */
    wpa_cli_recv_pending(ctrl, 1);
}

このwpa_cli_action_reciveがwpa_cli_action_processを呼ぶ。

/* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n4185 */
static void wpa_cli_recv_pending(struct wpa_ctrl *ctrl, int action_monitor)
{
    /* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n4191 */
    while (wpa_ctrl_pending(ctrl) > 0) {
        if (wpa_ctrl_recv(ctrl, buf, &len) == 0) {
            if (action_monitor)
                wpa_cli_action_process(buf);
}

wpa_cli_action_processが内部でwpa_cli_execを呼ぶ。

/* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n3907 */
static void wpa_cli_action_process(const char *msg)
{
    /* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n3939 */
    if (str_starts(pos, WPA_EVENT_CONNECTED)) {
        if (wpa_cli_connected <= 0 || new_id != wpa_cli_last_id) {
            wpa_cli_connected = 1;
            wpa_cli_last_id = new_id;
            wpa_cli_exec(action_file, ifname, "CONNECTED");
        }
    }
}

wpa_cli_execは、os_execを呼び出してプログラムの実行を行っている。

/* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n3884 */
static int wpa_cli_exec(const char *program, const char *arg1,
            const char *arg2)
{
    /* https://w1.fi/cgit/hostap/tree/wpa_supplicant/wpa_cli.c#n3900 */
    res = os_exec(program, arg, 1);
}

このos_exec関数はutils/os.h内で定義されていて、wpa_cli.cはutils/common.hをインクルードしているため、この関数が利用できる。関数本体はutils/os_internal.cに定義されていて、この関数が子プロセスを生成してexecvを実行している。

/* https://w1.fi/cgit/hostap/tree/src/utils/os_internal.c#n503 */
int os_exec(const char *program, const char *arg, int wait_completion)
{
    /* https://w1.fi/cgit/hostap/tree/src/utils/os_internal.c#n508 */
    pid = fork();
    if (pid == 0) {
        execv(program, argv);
    }
}

ここまで見るとわかるけど、bashやshを引数に渡していない。当然、実行権限が付与されていないと駄目になるという話だった。

2019-06-28

bashスクリプトの位置を取得する

bash

bash スクリプトをプロジェクトルートを起点として走らせたいことがある。そこで、bash スクリプトが格納されている絶対パスをとりたくなるが、これは次のようすると取れる。

SCRIPT_PATH="$( cd "$( dirname "$( readlink -f  "$BASH_SOURCE" )" )" >/dev/null 2>&1 && pwd )"

解説

$BASH_SOURCEでbash スクリプトの実体へのパスがとれる。

しかし、$BASH_SOURCEはシンボリックリンクの解決が行われていない状態のパスが入っているので、readlinkコマンドで解決させている。ただ、これでも不十分で、パスの間に挟まっているシンボリックリンクも解決する必要がある。そこで、readlinkに-fを指定して、階層の途中にあるシンボリックリンクも全部解決してもらっている。これはGNU Core Utilitiesで利用できるがMacでは利用できない。 readlinkを再帰的にするような関数を自前で実装するか、GNU Core utilitiesをインストールするなどしなければならない。

最後に、直したパスからdirnameコマンドでbash スクリプト名を剥がし、そのディレクトリへ移動してpwdすると絶対パスが得られる。

2019-05-13

JREのスリム化

java

Dockerなどで、Javaの実行環境を小さくしたいというのはある。そいうときに使えるのがjlinkとjdeps (リンク先はJava 10のもの)。

精確にはjdepsはライブラリの依存関係を調べるためのツールで、jlinkは実行環境を作るためのツール。これらは$JAVA_HOME/binにある。 Arch Linuxであれば、/usr/lib/jvm/default/binの下にある。

この2つを使って小さなJava実行環境を作っていく。なお、記事執筆時点でのバージョンはJava 11.0.3。環境はArch Linuxでやってるので、当然なが他の環境では$JAVA_HOMEは違うので、 find / -iname jdepsをシェルに実行させるなりして探して欲しい。

Javaプログラムの依存関係を調査

まず、プログラムを動かすのに必要な標準ライブラリをjdepsで調べる。

$ jdeps --list-deps *.jar

--list-depsはプログラムが参照しているモジュール(java.baseなど)を表示するためのオプション。

得られたモジュールリスト(たとえば、プログラムがjava.baseとjava.desktopに依存していたとする)を元に、jlinkでJavaの実行環境をminjre下に作成する。

$ jlink --compress=2 --module-path $JAVA_HOME/jmods --add-modules java.base,java.desktop --output minjre

モジュールの情報は.jmod拡張子がついたファイルに収められていて、基本的なモジュールについての情報を収めたファイルは$JAVA_HOME/jmods/の下にある。

絶対に必要なオプションが--module-pathと--add-modulesの2つで、

--module-path modulepath: モジュールの情報が収められたファイルのあるディレクトリmodulepathを使用するモジュールパスとして設定
--add-modules module[,module..]: JREに追加したいモジュールmoduleを設定。複数個指定する場合はmodule1,module2のようにカンマ(,)区切り

を指定しなければならない。また、

--output output_dir: 出力先output_dirを設定。指定したディレクトリの下にJRE環境ができる
--compress=n: 圧縮するかどうかを設定する
- 0: 圧縮なし
- 1: 定数文字列を共有させる
- 2: ZIPによる圧縮

は必要あれば設定して欲しい。

以上で、最小限のJRE環境を作ることができる。

自分で試したときはjava.baseとjava.xml、それにjava.namingをcompress=2でバージョンがJava 11で作成したが、JREの環境自体は52MB程になった。標準だと245MBくらいなので、大分小さい環境ができた。

2019-04-30

CrystalのIndexableの実装

Crystal

本家のAPIドキュメントに Indexable(T) の詳しい実装方法がなくて苦戦した。

crystal-lang.org

最初は #unsafe_fetch だけを実装すればよいのかと思ったが、どうも、#unsafe_fetch を実装しただけだとスタックオーバーフローを起こしてプログラムが死ぬ。不思議に思ってドキュメントを見直したところ、単純に#unsafe_fetchと #size の2つのメソッドを実装する必要があった(ドキュメント内でabstraft defを検索すればよかった)。他の Hogeable 系は「#foo メソッドを実装してね」とかちゃんと書いてあるのに、これだけ書いてない...

以下、いらないかもだけど、実装例

class Klass(T)
  include Indexable(T)

  def initialize(n : Int)
    @n = n
    @buffer = Pointer(T).malloc(n)
  end

  def size
    @n
  end

  def unsafe_fetch(index : Int)
    @buffer[index]
  end
end

2019-04-25

集合の濃度について

数学集合

2つの有限集合 $A$ と $B$ が同じ数の元を持つとは、 $A$ に含まれる元の個数と $B$ に含まれる元の個数を数えればわかる。
また、有限集合 $A$ が有限集合 $B$ 以上の元を持つことは、集合の元の個数を $|A|$ と表すことで $|A| \leq |B|$ と表すことができるし、 $|A| \lt |B|$ は有限集合 $B$ が有限集合 $A$ よりも元を多くもっていると言える。
この関係は集合の要素の個数を一般化したときにどうなるのだろうか？
また、どのようにこの個数の一般化はなしとげられるのだろうか？

今回はここについて記しておく。

準備

まず、集合の元の個数の一般化にあたって必要な全単射と逆関数、それに合成関数について記す。

集合 $A$ から $B$ への関数 $f: A \to B$ が全単射であるとは、一言で言えば、 $f$ が $A$ と $B$ の要素を一対一で対応付けているということを意味している。
厳密に言えば、関数 $f: A \to B$ が

全射性: $\forall b \in B, \exists a \in A; b = f(a)$
単射性: $\forall a_1, a_2 \in A; f(a_1) = f(a_2) \implies a_1 = a_2$

を満たすことをいう。
$f: A \to B$ が全射であるとは、どの $b \in B$ に対しても、必ず対応する $a$ があることを言っている。
すなわち、写される先 $B$ のどの元も、関数 $f: A \to B$ によって写されるもとが存在することを意味している。
また、 $f: A \to B$ が単射であるとは、どの $a_1, a_2 \in A$ に対しても、必ず、写された先が等しい( $f(a_1) = f(a_1)$ )ならば、 $a_1 = a_2$ でなければならないことを意味している。
これは、関数 $f: A \to B$ によって写される先は重ならないということを意味する。
以上から、全単射はどの写される先の元も写されるもとが存在し、しかも写された先は重ならないという良い性質を持っている。

全射な関数 $f$ によって写される先の集合には $f$ によって写されないものはないし、写されるものには写されるもとがある。ただし、写す元には写されないものがあってもよいし、写されるもとは複数あってよい

単射な関数 $f$ は写すもとの集合の要素を全て重複なく写すが、写される先の集合には、写されないものがあってもよい

全単射な関数 $f$ は写すもとの集合の要素を全て重複なく写し、また写される先の集合には写されないものは存在しない

この全単射な関数 $f: A \to B$ の写す先 $b = f(a) \in B$ と写されるもと $a \in A$ を対応づける関数 $f^{-1}(b) =a$ を逆関数という。
この関数が $f^{-1}(f(a)) = a, f(f^{-1}(b)) = b$ という性質を持つことは明らかであると思う。

また、関数 $f: A \to B$ で写したものを $g: B \to C$ で写すということが考えられる。
これによって、 $A$ の元は $C$ へ写されることとなる。
つまり、 $g(f(x))$ というものが考える。
これは関数の合成と呼ばれ、合成された関数を合成関数と呼び、 $g \circ f(x)$ と表される。
実は、 $f: A \to B$ と $B \to C$ が全単射ならば、合成関数 $g \circ f: A \to C$ は全単射となることが知られている。

以上の定義をもちいて、濃度について調べていく。

濃度

先程の全単射な関数を考えることで、集合が同じだけの元を持つということを定義できる。
全単射な関数が1つでもあれば、集合同士は過不足なく、しかも重複もなく元を対応づけることができる。
これによって、集合どうしが同じだけの元を持つということが言える。
つまり、 $A$ と $B$ に全単射な関数が少なくとも1つでもあれば、 $A$ と $B$ は対等であるという。
対等であることは記号 $\sim$ を使って、 $A \sim B$ と表される。
この関係には次の性質が存在することは簡単に確認できる。

$A \sim A$
$A \sim B \implies B \sim A$
$A \sim B \land B \sim C \implies A \sim C$

簡単に言えば:

$A \sim A$ : $f(x) = x$ という関数を考えると、これは全単射
$A \sim B \implies B \sim A$ : $A$ から $B$ へは全単射な関数が少なくとも1つ存在するので、その逆関数を考える
$A \sim B \land B \sim C \implies A \sim C$ : $A$ から $B$ へ全単射な関数 $A \to B$ が存在し、 $B$ から $C$ への全単射な関数 $g: B \to C$ が存在するので、その合成関数 $g \circ f$ は全単射となる

ということになる。

この関係によって、集合は対等なものと対等でないものにわけることができる。
つまり、集合 $A, B$ が $A \sim B$ であって、さらに集合 $D$ が $B \sim D$ であれば、 $A \sim D$ になるし、集合 $E$ と $F$ が対等でなければ、それは同じだけの要素を持っていないので別のものであるとみなせる。
これをさまざまな集合に対して行えば、対等なものどうしのグループにわけることができる。

分類したグループに対して、

同じグループの集合には同じしるしをつける
異なるグループの集合には異なるしるしをつける

という規則のもと付けたしるしのことを濃度といい、Aの濃度は $|A|$ と書かれる。
$A$ と $B$ が同じグループに入る、つまり、 $A \sim B$ ならば $|A| = |B|$ であるし、逆に $|A| = |B|$ であれば、同じグループに入っているので、 $A \sim B$ となる。
しるしとしては、例えば $A = \{1, \cdots, n\}$ 、つまり $A$ が $n$ 個の元を持つ元であれば $|A| = n$ というしるしをつければよい。

可算集合

有限集合にはしるしとして自然数を割り当てた。
しかし、自然数全体の集合 $\mathbb{N}$ や実数全体の集合 $\mathbb{R}$ などの要素が無限にある集合の濃度には自然数というしるしをつけることはできない。

一般に $\mathbb{N}$ の濃度には $\aleph_0$ という記号がわりあてられる。
$\aleph_0$ は"アレフゼロ"と読む。
つまり、 $\aleph_0$ の濃度を持つ集合は $\mathbb{N}$ と対等だし、 $\mathbb{N}$ と対等な集合の濃度は $\aleph_0$ となる。

この $\mathbb{N}$ と対等な集合のことを可算集合あるいは可付番集合という。
なお、有限集合と可算集合を、合わせて高々可算な集合という

可付番な集合としては

整数全体の集合 $\mathbb{Z}$
有理数全体の集合 $\mathbb{Q}$
整数係数のみをもつ代数方程式 $a_n x^n + a_{n - 1} + x^{n - 1} + \cdots a_1 + x + a_0 = 0 \enspace (a_i \in \mathbb{Z})$ の解となる数(これを代数的数という)の集合

がある。

$\mathbb{Z}$ : $0, -1, 1, -2, 2, \cdots$ と並べて前から順々に自然数を割り当てていく
$\mathbb{Q}$ : まず、正の有理数だけを考え、下図の矢印の順番に自然数を割り当てればよい。従って、正の有理数全体の集合と自然数全体の集合は対等となる。あとは負の有理数と正の有理数を、整数と同じように自然数を割り振り直す
代数的数の集合: $a_0 > 0$ と仮定しても一般性を失しなわないので $a_0 > 0$ とする。一般に方程式 $a_n x^n + a_{n - 1} + x^{n - 1} + \cdots a_1 + x + a_0 = 0$ において、 $n + a_0 + |a_1| + |a_2| + \cdots |a_n|$ なる自然数をその方程式の高さという。高さはあきらかに2以上であるし、高さが同じ方程式の数は有限個となる。なぜならば、高さ $h$ を1つ決めれば、 $n < h, a_0 < h, |a_1| < h, \cdots, |a_n| < h$ とならなければならないからである。さらに、方程式の解の個数は最大でも $n$ なので、代数的数も有限個しかないことがわかる。

意外なことに、 $\mathbb{N}$ と $\mathbb{Z}$ 、 $\mathbb{N}$ と $\mathbb{Q}$ の濃度は同じとなる。

また、可算集合 $A$ の無限部分集合 $B \subseteq A$ は可算となる。
これは $A$ の中から、 $B$ にはいっていないものを除いて、残ったものに小さい順に自然数を割り当てればよいことからわかる。

さらに、高々可算な集合の和集合もまた高々可算な集合となる。

$A$ も $B$ も有限集合とするこのとき、あきらかに $A \cup B$ も有限個しか元を持たない
$A$ か $B$ のどちらか一方が有限集合で、もう一方が可算集合とする。なお、ここでは $A$ を有限集合、すなわち $A = \{a_1, a_2, \cdots, a_n\}$ 、他方、 $B$ を可算集合、すなわち $B = \{b_1, b_2, \cdots\}$ とする。 $A \cup B$ の元を $a_1, a_2, \cdots, a_n, b_1, b_2, \cdots$ と並べて、前から自然数を割り当てればよい
$A$ もl $B$ も可算集合とする。すなわち、 $A = \{a_1, a_2, \cdots\}, B = \{b_1, b_2, \cdots\}$ とする。このとき、 $a_1, b_1, a_2, b_2, \cdots$ というように並べて、前から自然数を割り当てればよい

どの場合も重なるものは飛ばして考えればよい。

非可算集合

$\mathbb{N}$ や $\mathbb{Q}$ は同じ濃度であったが、実数全体の集合 $\mathbb{R}$ の濃度は同じとなるのだろうか？
実は同じとはならないことがカントールによって証明されている。
この $\mathbb{R}$ の濃度は $\aleph_1$ と書かれるが、これが $\aleph_0$ と等しくないことを簡単に証明してみる。
それには、 $\mathbb{R}$ の部分集合に可算でないものがあることを証明すればよい。
そこで、 $(0, 1] = \{x : 0 \lt x \leq 1\}$ が可算でないこと示す。

まず、 $(0, 1]$ が可算であると仮定する。
$(0, 1]$ の元 $x$ は $0$ から $9$ までの自然数を用いて、 $x = 0.a_1 a_2 \cdots a_n \cdots$ と表せるので、

$\begin{array}{c} a_1 = 0.a_{1 1} a_{1 2} a_{1 3} \cdots a_{1 n} \cdots \\ a_2 = 0.a_{2 1} a_{2 2} a_{2 3} \cdots a_{2 n} \cdots \\ a_3 = 0.a_{3 1} a_{3 2} a_{3 3} \cdots a_{3 n} \cdots \\ \vdots \\ a_n = 0.a_{n 1} a_{n 2} a_{n 3} \cdots a_{n n} \cdots \\ \vdots \end{array}$

とならべる。
このうち、 $a_{i i}$ の部分に対し、

$b_n = \begin{cases} 1 & \text{if} \enspace (a_{n n} \neq 1) \\ 2 & \text{if} \enspace (a_{n n} = 1) \end{cases}$

として、数 $b = 0.b_1 b_2 \cdots b_n \cdots$ を定義する。
明らかに $0 \lt b \leq 1$ なので、 $b$ はある $a_i$ と等しくなる。しかし、 $b$ の定義からどの $a_i$ に対しても $b$ は等しくない数を $i$ 桁目に含んでいる。
よって、 $b \neq a_i$ 。
しかし、これは矛盾となるので、 $(0, 1]$ は可算集合とはならない。

さらに、 $\mathbb{R}$ から $\mathbb{R}$ への関数全体 $F$ の濃度は $\aleph_0$ でも $\aleph_1$ でもない。
ここではこのことについて考えてみる。

まず、どんな $x \in \mathbb{R}$ に対しても定数 $a \in \mathbb{R}$ を割り当てる関数 $f_a$ を考えると、 $f_a \in F$ 。
このような関数 $f_a$ 全体の集合を $C$ とすれば明らかに任意の $f_a \in C$ は $f_a \in F$ なので、 $C$ は $F$ の部分集合となる。
$f_a$ はある $a \in \mathbb{R}$ に対して定義されており、それが全ての実数に対して定義されているので、 $C$ と $\mathbb{R}$ は一対一対応している。
すなわち、 $C \sim \mathbb{R}$ 。
ここから、 $F$ は高々可算な集合でないことがわかる。
高々可算な集合であれば、その全ての部分集合もまた高々可算となるが、 $C$ は高々可算な集合ではないからである。
次に、 $F$ と $\mathbb{R}$ が対等でないことを示す。
今、 $\mathbb{R}$ から $F$ への全単射の関数 $g$ があると仮定する。
すると、任意の $F$ の元はある $a \in \mathbb{R}$ から $g$ で写されたものとなる。
これを $g_a$ とする。
ここで、任意の $a \in \mathbb{R}$ に対し、 $h(a) = g_a(a) + 1$ を考える。
これは実数を受けとって、実数を返しているので、 $h \in F$ 。
よって、これはある $g_b$ と等しい。
つまり、 $h(x) = g_b(x)$ 。
とくに、 $h(b) = g_b(b)$ 。
しかし、これは $h(b) = g_b(b) + 1$ であることに矛盾。
よって、 $F$ と $\mathbb{R}$ の濃度は等しくない。

以上から、 $F$ の濃度は $\aleph_0$ でも $\aleph_1$ でもない。

濃度の大小

有限集合においては、 $A$ の濃度が $B$ の濃度よりも小さいということは、 $B$ の中に、 $A$ と対等な真部分集合 $B_1 \subset B$ (つまり、 $B \neq B_1$ かつ $B_1$ は $B$ の部分集合)があるといことになる。
このときに限って $|A| < |B|$ が成立することとなる。

しかし、この定義を無限集合にそのまま適用することはできない。
たとえば、 $\mathbb{N} \subset \mathbb{Q}$ ではあるものの、先程示したように $\mathbb{N}$ も $\mathbb{Q}$ も濃度は $\aleph_0$ である。
よってそのままこの定義を無限集合へと延長して利用することはできない。

そこで、濃度 ${\frak a}$ 、及び ${\frak b}$ を持つどんな集合 $A, B$ ( $|A| = {\frak a}, |B| = {\frak b}$ )にたいしても、 $A \sim B_1, B_1 \subseteq B$ なる $B_1$ があれば、 ${\frak a}$ は ${\frak b}$ よりも大きくない、あるいは ${\frak b}$ は ${\frak a}$ よりも小さくないといい、 ${\frak a} \leq {\frak b}$ あるいは ${\frak b} \geq {\frak a}$ と書かれる。
とくに、 ${\frak a} \leq {\frak b}$ かつ ${\frak a} \neq {\frak b}$ のとき、 ${\frak a}$ は ${\frak b}$ よりも小さい、あるいは ${\frak b}$ は ${\frak a}$ よりも大きいといい、 ${\frak a} < {\frak b}$ と書く。

これは有限集合でも無限集合でも濃度を上手く比較することができる。
しかし、これは ${\frak a}$ と ${\frak b}$ を持つ任意の集合について成立しなければ、 ${\frak a} \leq {\frak b}$ が成立しないということには注意しなければならない。

ここで、 $|A| = |C|, |B| = |D|$ とし、 $A \sim B_1, B \subseteq B_1$ なる $B_1$ があるとすれば、 $C \sim D_1, D_1 \subseteq D$ となる $D_1$ が存在する、という性質について言及しておく。
まず、 $B \sim D$ から $B$ から $D$ への一対一対応する $f$ がある。
$B_1$ の元を $f$ によって写した先の全体を $B_1^f$ とすると、 $B_1^f \subseteq D$ で、 $B_1 \sim B_1^f$ 。
この $B_1^f$ を $D_1$ とおくと、 $D_1 \subseteq D$ で、しかも、 $|A| = |C|$ と $A \sim B_1$ から $C \sim A \sim B_1 \sim B_1^f = D_1$ 。
よって、 $C \sim D_1$ 。

また、 ${\frak a} \leq {\frak b}, {\frak b} \leq {\frak c} \implies {\frak a} \leq {\frak c}$ ということが示せる。
まず、 $|A| = {\frak a}, |B| = {\frak b}, |C| = {\frak c}$ となる集合 $A, B, C$ を考える。
${\frak a} \leq {\frak b}, {\frak b} \leq {\frak c}$ から、 $A \sim B_1, B_1 \subseteq B$ かつ $B \sim C_1, C_1 \subseteq C$ となる $B_1, C_1$ がある。
$B$ から $C_1$ への一対一対応を $f$ 、 $B_1$ の元を $f$ で写したもの全体を $B_1^f$ とする。
すると、 $A \sim B_1 \sim B_1^f$ かつ、 $B_1^f \subseteq C_1 \subseteq C$ 。
ゆえに、 $A \sim B_1^f, B_1^f \subseteq C$ 。
これは ${\frak a} \leq {\frak c}$ ということを示してる。

以上から、まとめると、 $\mathbb{R}$ から $\mathbb{R}$ への関数全体の集合の濃度を ${\frak f}$ とすると、
$\aleph_1 \neq \aleph_0, \aleph_1 \neq {\frak f}, \aleph_0 \neq {\frak f}$ であって、

$\mathbb{N}$ は $\mathbb{R}$ の部分集合
$\mathbb{R}$ から $\mathbb{R}$ への関数全体の集合 $F$ 証明の中で利用した、任意の $x \in \mathbb{R}$ をある $a \in \mathbb{R}$ に対応づける関数の集合 $C$ と $\mathbb{R}$ は対等( $\mathbb{R} \sim C, C \subseteq F$ )