無料のブール代数

数学において、自由ブール代数とは、生成元と呼ばれる特別な要素の集合を持つブール代数であり、以下の条件を満たすものである。

1. ブール代数の各要素は、ブール演算と、生成元の有限の組み合わせとして表現できます。
2. 生成子は可能な限り独立しており、どの要素を選択しても、すべてのブール代数において成り立たない関係（ブール演算を用いた有限式の観点から）は存在しない。

自由ブール代数の生成子は、独立した命題を表すことができる。例えば、 「ジョンは背が高い」と「メアリーは金持ちだ」という命題を考えてみよう。これらは、次の4つの原子を持つブール代数を生成する。

• ジョンは背が高く、メアリーは金持ちだ。
• ジョンは背が高く、メアリーは裕福ではない。
• ジョンは背が高くなく、メアリーは金持ちだ。
• ジョンは背が高くなく、メアリーは金持ちではない。

ブール代数のその他の要素は、原子の論理和であり、例えば「ジョンは背が高く、メアリーは金持ちではない」または「ジョンは背が高くなく、メアリーは金持ちである」といったものです。さらに、FALSEという要素がもう1つあり、これは空の論理和、つまり原子が存在しない論理和と考えることができます。

この例では、16 個の要素を持つブール代数が得られます。一般に、有限のnの場合、 n 個の生成元を持つ自由ブール代数は 2 ⁿ個の原子を持ち、したがって$2^2^n$要素。

生成元が無限に存在する場合、原子が存在しない点を除けば、同様の状況が成り立ちます。ブール代数の各要素は、有限個の生成命題の組み合わせであり、そのような2つの要素は、論理的に同値であれば同一とみなされます。

n 要素集合上の自由ブール代数がなぜ$2^2^n$要素とは、各要素が n ビットから 1 への関数であることに注意することです。$2n$このような関数には可能な入力があり、関数は各入力に対して0または1を選択して出力します。$2^2^n$可能な機能。

圏論の言葉で言えば、自由ブール代数は、集合と関数の圏Setと、ブール代数とブール代数準同型の圏BAとの間の随伴関係によって簡単に定義できます。実際、このアプローチは、普遍代数の枠組みで定義可能な任意の代数構造に一般化できます（自由オブジェクトを参照）。

上記で述べたように、自由ブール代数とは、ある特定の振る舞いをする生成元を持つブール代数です。あるいは、ある集合から始めて、それがどのような代数を生成するかを問うこともできます。すべての集合X は、自由ブール代数FXを生成します。これは、すべての代数Bと関数f  : X → Bに対して、 fを拡張する一意のブール代数準同型f ′  : FX → Bが存在する代数として定義されます。図式的に、

ここでi _Xは包含関係であり、破線の矢印は一意性を表します。この考え方は、Xの要素をどこへ送るかを一度選択すると、ブール代数の準同型の法則によって、自由代数FX内の他のすべての要素をどこへ送るかが決定されるというものです。FX に X の要素の組み合わせとして表現できない要素が含まれている場合、f ′は一意ではなくなり、 Xの要素が十分に独立でない場合、f ′ は適切に定義されません。FXは（同型を除いて）一意であることが容易に示されるため、この定義は意味を持ちます。また、最初に定義された生成集合 X を持つ自由ブール代数はFXと同型であることが容易に示されるため、2 つの定義は一致します。

上記の定義の欠点の1つは、図がf ′が準同型であることを捉えていないことです。これはSetの図であるため、各矢印は単なる関数を表します。これをBAとSetの2 つの図に分けることで修正できます。この 2 つの図を関連付けるために、代数構造を「忘れる」ファンクターU  : BA → Set を導入し、代数と準同型をその基礎となる集合と関数にマッピングします。

上側の矢印をBAの図、下側の三角形をSetの図と解釈すると、この図は、すべての関数f  : X → UB が一意のブール代数準同型f ′  : FX → Bに拡張されることを適切に表現しています。ファンクターU は、準同型f ′ をSetに引き戻してfと関連付けるための装置と考えることができます。

この注目すべき点は、後者の図が、2 つのファンクターが随伴である場合のさまざまな (同等の) 定義の 1 つであるということです。私たちのF は、ファンクターSet → BAに容易に拡張でき、自由ブール代数FXを生成するXの定義は、まさにUが左随伴Fを持つことなのです。

κ 個の生成子を持つ自由ブール代数(κ は有限または無限の基数)は、 {0,1 } が離散位相を持つと仮定して積位相が与えられた場合、 {0,1} ^κのすべての閉じた部分集合の集合として実現できます。各 α < κ に対して、α番目の生成子は、α番目の座標が 1 である {0,1} ^κのすべての要素の集合です。特に、$\displaystyle \aleph _{0}}$生成元とは、カントール空間のすべての閉じた部分集合の集合であり、カントール代数と呼ばれることもあります。この集合は可算です。実際、n個の生成元を持つ自由ブール代数 ( n は有限)の濃度は です。$2^2^n$、自由ブール代数$\displaystyle \aleph _{0}}$ジェネレーター、自由代数の場合と同様$\displaystyle \aleph _{0}}$生成子と可算個の有限演算は、濃度を持つ$\displaystyle \aleph _{0}}$。

自由ブール代数へのこの位相的アプローチの詳細については、ストーンのブール代数に関する表現定理を参照してください。

• ブール代数（構造）
• 生成セット

• Steve Awodey (2006)カテゴリー理論(Oxford Logic Guides 49). Oxford University Press.
• Paul Halmosと Steven Givant (1998)論理を代数として捉える。アメリカ数学協会。
• Saunders Mac Lane (1998) 『働く数学者のためのカテゴリー』第2版（大学院数学テキスト5）。Springer-Verlag。
• Saunders Mac Lane ( 1999)代数学、第3版、アメリカ数学会。ISBN 0-8218-1646-2。
• ロバート・R・ストール、1963年。『集合論と論理学』第6.7章。ドーバー社復刻版、1979年。