Музыка: | Eric B. and Rakim – Don't Sweat The Technique |
конечные множества
Эквивалентные (в ZFC) определения конечного множества
у A есть биекция с [1..n];
по Дедекинду: любая инъекция A в себя - биекция (+ то же утверждение для 2^{2^A}, если хотим избежать аксиому выбора);
любая сюръекция A в себя - биекция (+то же утверждение для 2^{2^A}, выбор не нужен);
А может быть вполне упорядочена < так, что <* (обратное отношение) тоже вполне упорядочение;
все вполне-упорядочения A изоморфны;
при любом вполне-упорядочении имеет максимальный элемент;
по Тарскому: любой непустой набор подмножеств A имеет минимальный элемент;
по Куратовскому: если A представляется как конечное объединение одноточечных множеств (или пустое). В терминах теории решеток: A принадлежит подполурешетке полурешетки 2^A (с объединением как джойном), порожденной пустым множетсвом и всеми одноточенчными подмножествами.
(без аксиомы выбора определение Куратовского слабее)
Существование бесконечного множества эквивалентно существованию натуральных чисел (то есть паре (N, '), удвлетворяющей аксиомам Пеано).
Натуральные числа, очевидно, бесконечно по Дедекинду (функция ' инъективна, но не биекция).
Обратно, пусть есть бесконечное множество А. То есть есть инъекция f: A -> A и точка 0 из А, не лежащая в f(A). Она будет нулем. Пересечение N всех подмножеств A, содержащих 0 и отображаемых f в себя с ограничением f, взятым в качестве ' даст нам натуральные числа.