Дискретная математика. Множества. Отображения. Отношения

89 Примерами счетных множеств являются : – множество целых чисел {... 2, 1, 0, 1, 2, ...} = − − N ; – множество всех четных положительных чисел {2,4,6,...,2 ,...} n ; – множество степеней двойки {2,4,8,...,2 ,...} n ; – множество всех рациональных чисел Q ; – множество всех полиномов с рациональными коэффициен - тами . Приведем без доказательства ряд утверждений об общих свойствах счетных множеств . 1. Любое подмножество счетного множества конечно или счетно . 2. Объединение конечного или счетного множества счетных множеств является счетным множеством . 3. Любое бесконечное множество содержит счетное под - множество . 4. Декартово произведение двух счетных множеств счетно . 5. Если множество A счетно , то множество всех конечных последовательностей его элементов также счетно . Утверждение 3 показывает , что счетные множества « самые маленькие » из бесконечных множеств . Характерная особенность бесконечных множеств проявляет - ся в свойстве : любое бесконечное множество эквивалентно ( рав - номощно ) некоторому своему собственному подмножеству . Это свойство является определяющим свойством бесконечного множе - ства : множество A – бесконечное : ( ) & ( ~ ) B A B A B A ↔ ∃ ⊂ ≠ . Например , множество натуральных чисел {1, 2, ...} = N рав - номощно со своим собственным подмножеством четных чисел { : ( 2 )} x n x n ∈ ∃ ∈ = N N . Закон взаимно - однозначного соответствия элементов этих множеств выражается формулой 2 , n n n ↔ ∈ N ;