Меню

Мощность подмножества натуральных чисел



Мощность множества

Мощность множества — это обобщение понятия количества (числа элементов множества), которое имеет смысл для всех множеств, включая бесконечные.

Существуют бо́льшие, есть ме́ньшие бесконечные множества, среди них счётное множество является самым маленьким.

Определение

Два множества называются равномощными, если между ними существует биекция. Существование биекции между множествами есть отношение эквивалентности, а мощность множества — это соответствующий ему класс эквивалентности.

Пример

Множество чётных целых чисел имеет такую же мощность, что и множество целых чисел . Определим так: . f — биекция, поэтому

Свойства

  • Два конечныхмножества равномощны тогда и только тогда, когда они состоят из одинакового числа элементов. То есть для конечного множества понятие мощности совпадает с привычным понятием количества.
  • Для бесконечных множеств мощность множества может совпадать с мощностью его собственного подмножества, например .
  • Теорема Кантора гарантирует существование более мощного множества для любого данного: Множество всех подмножеств множества A мощнее A , или | 2 A | > | A | .
  • С помощью канторова квадрата можно также доказать следующее полезное утверждение: Декартово произведение бесконечного множества A с самим собой равномощно A .

Связанные определения

Следуя Кантору, мощность множества называется кардинальным числом, и обозначается мощность такого множества A через | A | (сам Кантор использовал обозначение ). Иногда встречается обозначение .

Мощность множества натуральных чисел обозначается символом («алеф-нуль»). Множество называется бесконечным, если его мощность , таким образом, счётные множества — это «самые маленькие» из бесконечных множеств. Следующие кардинальные числа в порядке возрастания обозначаются .

Про множества, равномощные множеству всех вещественных чисел, говорят, что они имеют мощность континуума, и мощность таких множеств обозначается символом c. Континуум-гипотеза утверждает, что .

Для мощностей, как и в случае конечных множеств, имеются понятия: равенство, больше, меньше. То есть для любых множеств A и B возможно только одно из трёх:

  1. | A | = | B | или A и B равномощны;
  2. | A | > | B | или A мощнее B, т. е. A содержит подмножество, равномощное B, но A и B не равномощны;
  3. | A | B | или B мощнее A, в этом случае B содержит подмножество, равномощное A, но A и B не равномощны.

Ситуация, в которой A и B не равномощны и ни в одном из них нет части, равномощной другому, невозможна. Это следует из теоремы Цермело. Иначе это означало бы существование несравнимых между собой мощностей (что в принципе возможно, если не принимать аксиому выбора).

Ситуация, в которой | A | > | B | и | A | B | , невозможна по теореме Кантора — Бернштейна.

Источник

Мощность множества. Конечные и бесконечные множества

date image2015-05-13
views image12527

facebook icon vkontakte icon twitter icon odnoklasniki icon

Мощность (кардинальное число) множества — такое свойство множества, которое остается после абстрагирования от качества (состава) его элементов (определение мощности по Кантору). Мощность множества А обозначается | А | или gard A.

Любые два множества А и В называются равномощными (эквивалентными), если между их элементами может быть установлено взаимно однозначное соответствие, т.е. существует взаимно однозначная функция f: A → B с областью определения А и множеством (областью) значений В. Таким образом, можно сказать, что мощность – это то общее, что есть у всех эквивалентных множеств. Понятие мощности введено Кантором для количественного сравнения различных множеств. С точки зрения правил сравнения (выявления общего), все множества делятся на конечные и бесконечные. В свою очередь бесконечные множества делятся на счетные и континуальные .

Читайте также:  Снизилась мощность блока питания

Конечное множество – множество, содержащее конечное число элементов; мощность n-элементного множества А равна числу его элементов, т.е. | А | = n; множество, не содержащее ни одного элемента, называется пустым множеством и обозначается Æ; пустое множество является подмножеством любого множества и имеет нулевую мощность (| Æ | = 0). Из определения конечного множества следует – любые два конечные множества с одинаковым (равным) числом элементов эквивалентны (между ними легко установить взаимно однозначное соответствие – для этого достаточно, например, ввести нумерацию элементов).

Одна из особенностей конечного множества заключается в том, что его всегда можно задать путем перечисления элементов. Ясно, что это не всегда удобно (когда число элементов велико), но довольно часто другие способы просто неприемлемы. Последнее относится, например, к ситуации, когда нужно описать подмножество студентов, объединенных в определенную группу (поток). Очевидно, в этом случае придумать какое-то свойство или порождающую функцию, позволяющие однозначно выделить группу студентов из всего множества студентов вуза (факультета), практически невозможно (да в этом и нет необходимости – достаточно составить список студентов).

Бесконечное множество — всякое множество А, имеющееправильную часть В, равномощную всему ( целому ) множеству А , т. е. В Ì А и |В| = |А|. Так, например, множество М квадратов натуральных чисел является правильной частью всего множества N натуральных чисел (взаимно однозначное соответствие между этими множествами очевидно); следовательно, оба эти множества обладают одинаковой мощностью и подпадают под определение бесконечных множеств. В то же время это определение не подходит к конечным множествам, так как мощность (число элементов) правильной части любого конечного множества всегда меньше мощности полного множества.

Счетное множество — любое бесконечное множество, равномощное множеству N натуральных чисел. Мощность счетного множества принято обозначать (алеф — нуль). Отличительная особенность счетного множества – все его элементы могут быть пронумерованы. И хотя любое конечное множество также обладает этой особенностью, оно, по определению, к счетным множествам не относится. Примеры часто встречающихся счетных множеств: любые бесконечные подмножества множества N натуральных чисел; множества целых и рациональных чисел и их бесконечные подмножества (одним из таких подмножеств является, в частности, множество N );

множества, составленные из элементов бесконечных числовых последовательностей как функций натурального аргумента (если эти множества после исключения одинаковых элементов не трансформируются в конечные ).

Читайте также:  Мощность котельной гкал сзз

Замечание. С возможностью нумерации элементов счетного множества связан тот факт, что довольно часто такого рода множества описываются посредством перечисления элементов. Это характерно, например, при задании (описании) бесконечных числовых последовательностей и рядов, когда по записанным нескольким первым членам последовательности (ряда) видна закономерность их изменения и, как следствие, запись последующих членов с помощью выявленной закономерности не вызывает затруднений. Простейшей иллюстрацией к вышесказанному могут служить применяемые на практике описания множеств натуральных и целых чисел, а именно:

Континуальное множество — любое бесконечное множество, равномощное множеству R действительных чисел. Говорят, что всякое континуальное множество имеет мощность континуума. Такой мощностью обладают, например:

множество всех подмножеств всякого счетного множества;

множество точек, принадлежащих некоторой прямой или поверхности;

множество всех действительных чисел некоторого интервала ( a,b ) или отрезка [ a,b ] (см. пример1.2).

В отличие от счетного множества,элементы континуального множества не могут быть пронумерованы, т.е. множество-континуум несчетно. Справедливость данного утверждения подтверждается теоремой Кантора, одно из доказательств которой представлено ниже.

Теорема Кантора. Множество действительных чисел отрезка [0,1] несчетно.

→ Докажем теорему методом от противного. Для этого предположим, что множество счетно, т.е. может быть пронумеровано. Расположим все числа, изображенные бесконечными десятичными дробями, в порядке их нумерации:

Рассмотрим любую бесконечную дробь , у которой . Эта дробь не может войти в указанную последовательность, так как от первого числа она отличается первой цифрой, от второго — второй цифрой и т.д.

Геометрическая интерпретация множеств. Для геометрического (графического) изображения множеств и их свойств (связей между ними) довольно часто используются так называемые диаграммы Эйлера-Венна, представляющие собой в общем случае некоторый прямоугольник на плоскости и вложенные в него круги.

Так, если в рамках конкретно решаемой задачи рассматривается некая система S = <A,B,C,…,G>частных множеств, то кругами (круги Эйлера), находящимися внутри прямоугольника, изображаются любые множества из S, а прямоугольником — некоторое фиксированное универсальное множество (множество-универсум) U, включающее в себя в качестве подмножеств всю систему S частных множеств, т.е.

» МÎ S : M Ì U. При этом каждое множество мыслится как множество точек, принадлежащих изображающему его кругу Эйлера.

Замечание. Ясно, что множество-универсум U должно быть либо задано, либо очевидно из контекста задачи. Так, для S = <A, B, С >, где

в качестве универсального множества можно использовать как весь латинский алфавит, так и множество U = <a,b,c,d,e,f,g>. Круги, иллюстрирующие множества А и В на рисунке, пересекаются, так как эти множества имеют общие элементы.

Источник

Мощность множества натуральных чисел

Amicus Plato

Мой вопрос: каких же чисел больше: четных или нечетных — не вызвал большого ажиотажа )))
Отвечаю на него сама.
Начну с теории.
И этот вопрос подведет нас к понятию самой «простой» бесконечности.
Истоки того, о чем сейчас пойдет речь, лежат в теории множеств, но в нее я сейчас углубляться не буду.
Расскажу только, что любое множество состоит из некоторых элементов. Количество элементов может быть конечным или бесконечным. Множество яблок в корзинке, множество квартир в доме, множество книг на полке… — всё это примеры конечных множеств. Если в корзинке 10 яблок, — число элементов множества яблок в корзинке равно десяти.
Как же определяется число элементов в бесконечном множестве?
Обобщенным понятием количества элементов на произвольные множества является понятие мощности.
Т.е. в примере с корзинкой речь идет о мощности множества яблок. И эта мощность равна 10.
Мощность множества на самом деле — это абстракция. Она определяется как то общее, что есть у всех множеств, (количественно) эквивалентных данному.
И вот тут самое главное:

Читайте также:  Мощность рассеивания для выключателей

Два множества называются эквивалентными, если между ними можно установить взаимнооднозначное соответствие.

Помните пример с овцами?

Первая вышедшая овца — 1
Вторая вышедшая овца — 2
Третья вышедшая овца — 3
Четвертая вышедшая овца — 4
Пятая вышедшая овца — 5
Шестая вышедшая овца — 6

Это и есть пример взаимнооднозначного соответствия между множеством, состоящим из шести овец и множеством чисел: <1, 2, 3, 4, 5, 6>.
*Это нам пригодится чуть ниже, как только мы закончим с теорией.

Мощности часто называются кардинальными числами.

Наименьшей бесконечной мощностью является мощность НАТУРАЛЬНЫХ чисел. Обозначается она алеф-нуль.

Так вот, теперь посмотрим, что мы можем сказать о четных, нечетных и других числах.
Согласно очень красивой теории бесконечных чисел, автором которой является отец-основатель теории множеств Георг Кантор, мощности множеств четных чисел, нечетных чисел, чисел делящихся на три, пять, десять, сто, миллион, и т.д., СОВПАДАЮТ и равны алеф-нуль!
То есть, «количество» всех этих чисел одинаково!
Невероятно?
Это еще не всё.
Может создаться впечатление, что, скажем, целых чисел больше, чем натуральных, потому что целые числа могут быть как положительными, так и отрицательными, а натуральные только положительны! А еще более «очевидным» кажется тот «факт», что ДРОБЕЙ больше, чем натуральных чисел!
НЕТ!

Общее количество всех целых чисел, натуральных чисел и дробей равны одному и тому же бесконечному кардинальному числу алеф-нуль!

Чтобы доказать любое из этих утверждений достаточно установить взаимнооднозначное соответствие между множеством натуральных чисел и конкретным множеством, мощность которого мы хотим найти. Если такое соответствие есть, множества эквивалентны по данному выше определению.

Построим соответствие, предположим, для четных чисел.
Получим (Ч — четные числа; Ц — целые):

Заметим, что каждое число в левом и правом столбцах встречаются один и только один раз. Соответствие взаимнооднозначно.
Это и доказывает ОДИНАКОВОСТЬ количества элементов множества четных и всех натуральных чисел.
Со всеми остальными множествами (кроме дробей) разобраться столь же легко.
С дробями (рациональными числами) разбираться будем потом. Но их количество, как это ни парадоксально, — тоже равно алеф-нуль.

Источник