「JSの配列で集合算を考えてみた - IIJIMASの日記」の続きです。 配列が2つ与えられたとき、重複を省きつつ、和集合、共通部分、差集合などを表す配列を計算するアルゴリズムで、ループ回数をなるべく少なくしたものを考えます。 以前のエントリのやり方だと…

どんなプログラミングでも基本的な配列の操作において、集合算を実装したいということはあるかと思います。言語仕様やライブラリに実装されていればそれを使えばよいですが、そうでない場合に自分で実装せざるをえないなくなったり、興味や頭の体操で実装し…

直前のエントリで「写像と単射と全射と全単射について - IIJIMASの日記」写像と特別な写像について説明しました。 特に、全単射（1対1対応）の存在は強力な性質で、AとBの間に1つでも全単射が存在すると有限集合の場合要素数が同じということがわかってしま…

以前にも「集合と基数の説明 - IIJIMASの日記」 に書いたのですが、再び説明を考えてみました。 数学の集合論で写像というのは、ある集合Aの要素aに対して、集合Bの要素bを1つ定める対応とのことです。特に写像をfで表して、bのことをfによるaの像といいf(a)…

以前のエントリベルンシュタインの定理がわからないといわれたので、わかってもらうべく図をつけて説明しようとエントリ集合と基数の説明を作成した。そこでは、集合論の「写像」「単射」「全射」「全単射」「基数」などの用語の定義した。 それを踏まえて本…

前のエントリ（ベルンシュタインの定理）がわからないと不評だったのでまず集合論の基礎から図をつけて説明しようと思いたった。それぞれの図はVisio 2010で作成して、PNGに変換した。このエントリの内容は前エントリの諸定義の部分である。 fが集合Aから集…

集合論にベルンシュタインの定理という定理がある。 カントールの対角線論法と並んで集合論の基本的な定理である。 AからBへの単射 f と、BからAへの単射 g が存在するとき、AとBには1対１対応h が存在する。すなわち、AとBの基数（濃度）が等しい。 諸定義:…