偶奇の交替性
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/03/27 07:26 UTC 版)
ゼロが偶数であるという事実と、偶数と奇数の交替性という事実があれば、すべての他の自然数の偶奇性を決定するためには十分である。この考え方は、「すべての偶数の自然数の集合」を次のように帰納的に定義することで定式化できる。 0は偶数。 (n + 1) が偶数であることとnが偶数でないことは同値。 この定義は0と後者関数の存在という、自然数の最小の基礎のみ利用しているという概念的な有利さを持つ。そのため、それはen:Logical frameworkやIsabelle theorem proverのような計算機による論理システムに役に立つ。 この定義においては、ゼロの偶数性は、定理ではなく公理であり、従って、「0は偶数である」は、偶数の自然数が一つのモデルになるようなペアノ公理系における公理の一つとして解釈される。 計算幾何学における古典的なポリゴンの点テストは上の考えの応用である。ある点があるポリゴンの中にあるかどうかを判定するためには、無限遠からその点に直線を引き、ポリゴンの境界とその直線が交わる回数を数える。その交差数が偶数であることと、その点がポリゴンの外側にあることは同値である。このアルゴリズムが有効なのは、直線が決してポリゴンと交わらないならばその交差数はゼロ、すなわち偶数であり、その点は外側にあるという事実による。その直線がポリゴンと交わるたびに、交差数は偶数と奇数を交代し、その点も内部と外部の間を交代する。 グラフ理論において、2部グラフとは、それぞれの頂点が2種類に色分けされ、隣接する頂点は異なる色を持つようなグラフである。ある連結グラフが奇数の閉路を持たなければ、基点vを選び、各頂点をvからの距離が偶数か奇数かによって白と黒に塗分けることにより、2部グラフを構成できる。ここで、vからそれ自身への距離は0であり、0は偶数だから、基点自身は距離1であるような隣接点とは異なる色になる。
※この「偶奇の交替性」の解説は、「ゼロの偶奇性」の解説の一部です。
「偶奇の交替性」を含む「ゼロの偶奇性」の記事については、「ゼロの偶奇性」の概要を参照ください。
- 偶奇の交替性のページへのリンク