デデキント無限

数学において、集合"A" がデデキント無限（Dedekind-infinite）である、またはデデキント無限集合であるとは、"A" と同数（equinumerous）であるような"A" の真部分集合"B" が存在することである。つまり、"A" と"A" の真部分集合"B" の間に全単射が存在するということである。集合 "A" がデデキント無限でないとき、デデキント有限であるいう。
デデキント無限は、自然数を用いないような最初の無限の定義である。選択公理を除いたツェルメロ・フレンケルの公理系は、任意のデデキント有限集合は有限個の元を持つという意味での有限である、ということを証明するだけの強さを持たない。デデキント無限以外にも、選択公理を用いない有限集合や無限集合の定義が存在する。
通常の無限集合の定義との比較.
デデキントの意味での“無限集合”は、普通の意味での無限集合と比較されるべきであろう:
無限とは、全単射が存在しないという意味で文字通り有限でないという集合である。
19世紀後半、多くの数学者はデデキント無限であることと通常の意味の無限は同値であると単純に考えていた。しかし実際は、選択公理（“AC”）を除いたツェルメロ・フレンケルの公理系（通常、“ZF”と表記される）からは、その同値性は証明されえない。弱いACを使うことで証明でき、フルの強さは要求されない。その同値性は、可算選択公理（“CC”）より真に弱い形で証明できる。
ZFにおけるデデキント無限.
次の4条件は、ZF上同値である。特に、これらの同値性はACを用いないで証明できることに注意せよ。
どのようなデデキント無限集合"A" も以下の条件を満たす。
このことを、“"A" は双対デデキント無限である”という。"A" が双対デデキント無限であるならば"A" がデデキント無限であるということは（ACを除いたZF上で）証明可能でない。
どのような双対デデキント無限集合も次の（同値な）条件を満たす、ということがZF上で証明できる。
（この条件を満たすことを、弱デデキント無限(weakly Dedekind infinite)であるということがある。）
弱デデキント無限であるならば無限であることはZFにおいて証明されている。
また、整列無限集合はデデキント無限であることもZFにおいて示されている。
歴史.
デデキント無限という語は、この定義を初めて明確に示したドイツ人のリヒャルト・デデキントにちなんでつけられた。自然数の定義に依存しない最初の“無限”の定義であったことは明記すべきであろう。
選択公理との関係.
整列可能な任意の無限集合はデデキント無限である。ACは任意の集合が整列可能であることを述べた整列可能定理と同値であるから、ACから無限集合はデデキント無限集合であるということが簡単に導かれる。しかしながら、無限とデデキント無限の同値性はACよりもっと弱いものである。すなわちこの同値性を仮定してもACは導かれない。
とくに可算無限な部分集合を持たない無限集合の存在するようなZFのモデルが存在する。このモデルでは無限だがデデキント有限である集合が存在する。以上よりそのような集合はこのモデルにおいて整列不可能である。
可算選択公理CC（ACω）を仮定すればいかなる無限集合もデデキント無限であることが証明される。しかしながら、この同値性は、実際にはCCより真に弱い。（ZFの無矛盾性の仮定のもとで）CCは成立しないが2つの無限集合の定義の同値性が成り立つZFのモデルが存在する。すなわちこの同値性を仮定してもCCは導かれない。
可算選択公理を仮定した無限との同値性の証明.
デデキント無限集合が無限であることはZFで容易に証明される。実際、任意の有限集合はある有限順序数と等濃であって、有限順序数がデデキント有限であることは帰納法により証明できる。
可算選択公理を用いることによって、その逆が証明できる。つまり、無限集合はデデキント無限であることを以下のように証明できる。
まず無限集合 formula_1 は可算無限な部分集合を持つことを示す。相異なる formula_1 の元からなる長さ formula_3 の列の成す集合を formula_4 とする。 formula_1 は有限でないから formula_4 は空でない。したがって可算選択公理により選択関数 formula_7 が存在する。そこで
と表す。いま formula_9 とおけば、 formula_10 は可算無限集合である。実際 formula_10 の元は formula_12 と（重複は飛ばして）枚挙できる。したがって formula_10 は formula_1 の可算無限部分集合である。そこで可算無限部分集合 formula_10 を潰すことで全射でない単射 formula_16 が得られる。したがって formula_1 はデデキント無限である。
一般化.
圏論的な言葉で表現すれば、集合 は集合の圏においてすべてのモノ射 が同型射であるときにデデキント有限である。フォン・ノイマン正則環 が（左あるいは右）-加群の圏において同様の性質を持つことと、 において ならば が成り立つことは同値である。より一般に、デデキント有限環 (Dedekind-finite ring) は、この条件（ ならば ）を満たす環のことである。台集合がデデキント無限であっても環はデデキント有限となりうることに注意。例えば整数環。正則加群 "RR" がホップ的（すなわち任意の全射自己準同型が同型）であることと "R" がデデキント有限であることは同値である。