パリティ関数

無限パリティ関数は関数${\displaystyle f\colon \{0,1\}^{\omega }\to \{0,1\}}$で、無限二進列を0か1に対応させるもので、次の条件を満たすものである: ${\displaystyle w}$ と ${\displaystyle v}$ が無限二進列で有限個の座標でしか違いが無いものであるときに、${\displaystyle f(w)=f(v)}$ であることが ${\displaystyle w}$ と ${\displaystyle v}$ の違いが偶数個の座標であることと同値である。

選択公理を仮定すると、パリティ関数の存在とそれが${\displaystyle 2^{\mathfrak {c}}}$個あることが容易に示せる。これは${\displaystyle \{0,1\}^{\omega }}$ から ${\displaystyle \{0,1\}}$ への関数全体の濃度と同じである。これには次の同値関係 ${\displaystyle \approx }$ の代表系を一つ取ればよい: ${\displaystyle w\approx v}$ は ${\displaystyle w}$ と ${\displaystyle v}$ の違いが有限個の座標に留まることである。このような代表系がとれたとき、代表元は全て0に写すとすれば、残りの関数に対する ${\displaystyle f}$ による値は自動的に一意的に定められる。

無限パリティ関数の別の構成法として、${\displaystyle \omega }$ 上の非単項超フィルター ${\displaystyle U}$ を使うものがある。${\displaystyle \omega }$ 上の非単項超フィルターの存在性は選択公理より真に弱い。超フィルター ${\displaystyle U}$ が取れているとして、全ての関数 ${\displaystyle w:\omega \to \{0,1\}}$ に対して、${\displaystyle A_{w}=\{n\in \omega \mid \{k\leq n\mid w(k)=0\}}$ のサイズが偶数である ${\displaystyle \}}$ を考える。このとき、無限パリティ関数 ${\displaystyle f}$ は ${\displaystyle w}$ のパリティが ${\displaystyle 0}$ であることと、${\displaystyle A_{w}}$ が超フィルター ${\displaystyle U}$ の元であることと同値であるように定義することで得られる。

無限パリティ関数は、その簡単な定義と、一方でその記述論的複雑さから、理論的な計算科学や集合論でよく使われる。例えば、逆像${\displaystyle f^{-1}[0]}$が非ボレル集合であることを示すことができる。${\displaystyle f^{-1}[0]}$はルベーグ不可測であり、ベールの性質も持たない。選択公理を仮定せず、また無限パリティ関数が一切存在しないという状況もソロヴェイモデル（このモデルでは実数の集合が全てルベーグ可測でありベールの性質を持つ）では成り立つ。

• Walsh function
• パリティビット
• Piling-up lemma
• Multiway switching
• 誤り検出訂正