Теорема 3. Любое подмножество конечного множества само конечно. Любое надмножество бесконечного множества само бесконечно.

     Доказательство. Каждое из двух утверждений теоремы следует из другого. Так, если первое утверждение верно, то верно и второе, так как если A бесконечно и , то и B бесконечно, т. к. если бы B было конечно, то по первой половине теоремы и A было бы конечно. Достаточно поэтому доказать первое утверждение. Итак, пусть A конечно и . Если A = 0, то и B = 0, теорема справедлива. Пусть . Тогда A ~ |1, n| для некоторого натурального числа n. Применим индукцию относительно n. При n = 1 теорема верна, так как A содержит один элемент, и либо B = 0, либо B = A. Пусть утверждение верно для некоторого n. Докажем его для числа n + 1. Итак, пусть f - взаимно однозначное отображение A на отрезок |1, n+1|. Если B = A, то B конечно. Пусть . Существует элемент . Можно считать, что f(a) = n + 1. Иначе f(a') = n + 1, где . Если тогда f(a) = i, то строим новое отображение f₁, полагая f₁(a) = n + 1, f₁(a') = i и f₁ = f для остальных элементов множества A. Итак, пусть f(a) = n + 1. Положим A' = A\{a}. Тогда f определяет взаимно однозначное отображение множества A' на отрезок |1, n|, и . Следовательно, по предположению индукции B конечно. Теорема доказана.

     Согласно теореме 3 понятие о числе элементов имеет смысл для любого подмножества данного конечного множества. При этом имеет место

     Теорема 4. Число элементов конечного множества A всегда больше числа элементов его собственного подмножества B.

     Доказательство. Пусть m - число элементов A и n - число элементов B. Предположим, что . Так как , то и A ~ |1, m|. Также и , следовательно,

B ~ |1, n|.     (1)

При взаимно однозначном отображении A на отрезок |1, m| множество B отображается также взаимно однозначно на некоторое собственное подмножество B' отрезка |1, m, таким образом,|

B ~ B'.     (2)

-1-2-3-4-5-6-7-8-