Множества и операции над ними примеры: § 1. Множества и операции над ними

 Множества в реальной жизни

Ма­те­ма­ти­ка от­ра­жа­ет ре­аль­ную жизнь, а в ре­аль­ной жизни мы на­блю­да­ем вы­де­ле­ние от­дель­ных объ­ек­тов, людей в еди­ную со­во­куп­ность. На­при­мер, род­ствен­ни­ков мы вы­де­ля­ем в еди­ную со­во­куп­ность и на­зы­ва­ем се­мьей, груп­пу книг на­зы­ва­ем биб­лио­те­кой и т. д. В ма­те­ма­ти­ке со­от­вет­ству­ю­щим по­ня­ти­ем яв­ля­ет­ся по­ня­тие мно­же­ства.

Мно­же­ства обо­зна­ча­ют­ся боль­ши­ми бук­ва­ми ла­тин­ско­го ал­фа­ви­та (). Мно­же­ства в ма­те­ма­ти­ке со­сто­ят из эле­мен­тов, ко­то­рые обо­зна­ча­ют­ся ма­лы­ми ла­тин­ски­ми бук­ва­ми ().

Тот факт, что эле­мент  при­над­ле­жит мно­же­ству , за­пи­сы­ва­ет­ся как . Тот факт, что эле­мент  не при­над­ле­жит мно­же­ству , за­пи­сы­ва­ет­ся как .

Два мно­же­ства на­зы­ва­ют­ся рав­ны­ми, если они со­дер­жат одни и те же эле­мен­ты. На­при­мер: мно­же­ство  со­дер­жит цифры 1, 2, 3 и мно­же­ство  со­дер­жит эти цифры (), зна­чит, мно­же­ства равны друг другу (.

Спо­со­бы за­да­ния мно­же­ства:

1) Пе­ре­чис­ле­ние всех эле­мен­тов мно­же­ства. На­при­мер: .

2) С по­мо­щью ха­рак­те­ри­сти­че­ско­го свой­ства – свой­ства, ко­то­рым об­ла­да­ют эле­мен­ты мно­же­ства (рис. 1).

Мно­же­ство про­стых чисел – все на­ту­раль­ные числа, ко­то­рые имеют ровно два обыч­ных де­ли­те­ля.

Рас­по­ло­жен­ные на оси x числа, между чис­ла­ми 1 и 2: .

Рис. 1. За­да­ние мно­же­ства с по­мо­щью ха­рак­те­ри­сти­че­ско­го свой­ства

Мно­же­ство всех моск­ви­чей, ко­то­рых зовут Дмит­рий.

При­мер

Рас­смот­рим мно­же­ство кор­ней урав­не­ния. За­да­дим его ха­рак­те­ри­сти­че­ским свой­ством: . До­пу­стим, те­перь сле­ду­ет за­дать то же мно­же­ство, но с по­мо­щью пе­ре­чис­ле­ния его эле­мен­тов. Для этого решим урав­не­ние:

Тогда  и т.д., по­ря­док эле­мен­тов здесь не важен.

Мы видим, что пе­ре­ход к но­во­му виду мно­же­ства может быть со­дер­жа­тель­ной ма­те­ма­ти­че­ской за­да­чей. Здесь – это ре­ше­ние урав­не­ния.

Ана­ло­гич­ный при­мер: опи­сать мно­же­ство кор­ней урав­не­ния: .

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

По ана­ло­гии с нулем пу­стое мно­же­ство – это мно­же­ство в ко­то­ром нет ни од­но­го эле­мен­та.

Ха­рак­те­ри­сти­че­ское мно­же­ство все­гда долж­но быть сфор­му­ли­ро­ва­но четко. Вот при­мер не очень удач­ной ха­рак­те­ри­сти­ки мно­же­ства: окруж­но­стью на­зы­ва­ет­ся мно­же­ство точек плос­ко­сти, рав­но­уда­лен­ных от одной точки. Если пред­ста­вить квад­рат, то можно уви­деть, что все его вер­ши­ны рав­но­уда­ле­ны от одной точки – точки пе­ре­се­че­ния диа­го­на­лей (рис. 2).

Рис. 2. Ил­лю­стра­ция при­ме­ра не очень удач­ной ха­рак­те­ри­сти­ки мно­же­ства

Но мно­же­ство вер­шин квад­ра­та не яв­ля­ет­ся окруж­но­стью, про­пу­ще­но клю­че­вое слово «…всех точек плос­ко­сти…».

Еще один при­мер о спо­со­бах за­да­ния бес­ко­неч­ных мно­жеств. Тео­ре­ма: се­ре­дин­ный пер­пен­ди­ку­ляр к от­рез­ку есть гео­мет­ри­че­ское место точек, рав­но­уда­лен­ных от его кон­цов.

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

Рис. 3. При­мер к тео­ре­ме о се­ре­дин­ном пер­пен­ди­ку­ля­ре к от­рез­ку

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

Имеем угол с вер­ши­ной , бис­сек­три­са , точка  на бис­сек­три­се. Опус­ка­ем пер­пен­ди­ку­ля­ры на сто­ро­ны угла, к точ­кам  и  (рис. 4). Эти пер­пен­ди­ку­ля­ры, а зна­чит, и рас­сто­я­ние от точки  до лучей угла равны между собой. Точка  при­над­ле­жит бис­сек­три­се  () тогда и толь­ко тогда, когда .

Рис. 4. При­мер для тео­ре­мы о бис­сек­три­се угла

Смысл этой тео­ре­мы в том, что есть мно­же­ство с за­дан­ным ха­рак­те­ри­сти­че­ским свой­ством: гео­мет­ри­че­ское место точек, рав­но­уда­лен­ных от сто­рон угла, то есть мно­же­ство за­да­но неяв­но. Тео­ре­ма утвер­жда­ет, что это мно­же­ство может быть за­да­но явно, то есть может быть ука­зан спо­соб его по­стро­е­ния, в дан­ном слу­чае по­стро­е­ние цир­ку­лем и ли­ней­кой. Оно сов­па­да­ет с бис­сек­три­сой. В дан­ном слу­чае мы опять стал­ки­ва­ем­ся с тем, что за­да­ча пе­ре­хо­да от од­но­го опи­са­ния мно­же­ства к дру­го­му, может быть со­дер­жа­тель­ной ма­те­ма­ти­че­ски. Об­ра­тим вни­ма­ние на то, что для бес­ко­неч­ных мно­жеств, за­да­ние мно­же­ства пе­ре­чис­ле­ни­ем невоз­мож­но, а явное по­стро­е­ние слу­жит за­ме­ной этого спо­со­ба.

С по­ня­ти­ем «мно­же­ство» вы уже зна­ко­мы. Под­мно­же­ство, как можно до­га­дать­ся из на­зва­ния, – это опре­де­лен­ная часть мно­же­ства. На­при­мер:

А – это мно­же­ство всех уче­ни­ков в клас­се.

В – это мно­же­ство де­во­чек ука­зан­но­го выше клас­са.

С – мно­же­ство всех маль­чи­ков клас­са.

D – мно­же­ство всех от­лич­ни­ков дан­но­го клас­са.

Е – мно­же­ство всех маль­чи­ков-от­лич­ни­ков этого клас­са.

Таким об­ра­зом, были пе­ре­чис­ле­ны мно­же­ство (А) и его под­мно­же­ства (В, С, D, Е). Те­перь мы можем дать опре­де­ле­ние, что такое «под­мно­же­ство».

Если каж­дый эле­мент мно­же­ства В яв­ля­ет­ся эле­мен­том мно­же­ства А, то мно­же­ство В на­зы­ва­ют под­мно­же­ством мно­же­ства А.

В ⊂ А

Как при­мер, де­воч­ки клас­са из при­ме­ра выше (мно­же­ство В) яв­ля­ют­ся уче­ни­ца­ми клас­са (мно­же­ство А). Зна­чит, В вхо­дит в А.

Маль­чи­ки тоже яв­ля­ют­ся ча­стью клас­са, зна­чит, С ⊂ А.
Все от­лич­ни­ки яв­ля­ют­ся ча­стью клас­са, D ⊂ A.

Как и маль­чи­ки, от­лич­ни­ки – это уче­ни­ки клас­са, то есть Е ⊂ А.

Если у нас а ∈ А, то это зна­чит, что а при­над­ле­жит А.То есть, это один эле­мент a при­над­ле­жит мно­же­ству А.

Если же под­мно­же­ство В вхо­дит в А, то мы пишем В ⊂ А.

То есть между знач­ка­ми есть раз­ни­ца.

N – мно­же­ство на­ту­раль­ных чисел (с их по­мо­щью мы счи­та­ем пред­ме­ты, при­ро­ду и так далее.)

N = 

Z – мно­же­ство целых чисел.

Z = 

Ясно, что на­ту­раль­ные числа – это под­мно­же­ство целых чисел, то есть N ⊂ Z.

Q – мно­же­ство ра­ци­о­наль­ных чисел.

Q = 

Если к мно­же­ству ра­ци­о­наль­ных чисел до­ба­вить мно­же­ство ир­ра­ци­о­наль­ных чисел, то мы по­лу­чим мно­же­ство всех дей­стви­тель­ных чисел.

R – мно­же­ство дей­стви­тель­ных чисел.

R = 

За­пи­шем пра­виль­ные вклю­че­ния:

N ⊂ Z ⊂ Q ⊂ R

Пусть мно­же­ство А – это мно­же­ство всех че­ты­рех­уголь­ни­ков: A, B, C, D (рис. 1).

Рис. 1. Мно­же­ство А

Пусть мно­же­ство В – это мно­же­ство че­ты­рех­уголь­ни­ков с парой рав­ных па­рал­лель­ных сто­рон: A, B, C, D (рис. 2).

BC = AD       BC || AD

Рис. 2. Мно­же­ство В

Мно­же­ство С – это мно­же­ство таких че­ты­рех­уголь­ни­ков, у ко­то­рых диа­го­на­ли, пе­ре­се­ка­ясь, де­лят­ся по­по­лам: AB, CD – диа­го­на­ли, т. О – точка пе­ре­се­че­ния диа­го­на­лей, АО = ОС, BO = OD (рис. 3).

Рис. 3. Мно­же­ство С

Итак, было рас­смот­ре­но 3 мно­же­ства че­ты­рех­уголь­ни­ков: мно­же­ство про­из­воль­ных че­ты­рех­уголь­ни­ков; мно­же­ство че­ты­рех­уголь­ни­ков, у ко­то­рых пар­ные сто­ро­ны равны и па­рал­лель­ны; мно­же­ство че­ты­рех­уголь­ни­ков, у ко­то­рых диа­го­на­ли, пе­ре­се­ка­ясь, точ­кой пе­ре­се­че­ния де­лят­ся по­по­лам.

Рас­смот­рим еще 2 мно­же­ства.

Мно­же­ство D – это мно­же­ство всех па­рал­ле­ло­грам­мов, и мно­же­ство Е – мно­же­ство па­рал­ле­ло­грам­мов с пря­мым углом (рис. 4).

Рис. 4. Мно­же­ства D и Е

Таким об­ра­зом, мы имеем 5 мно­жеств че­ты­рех­уголь­ни­ков.

На­пи­сать вер­ное вклю­че­ние (то есть, какое мно­же­ство яв­ля­ет­ся под­мно­же­ством дру­го­го мно­же­ства) (рис. 5).

Рис. 5. Ил­лю­стра­ция к за­да­че

Наи­бо­лее бо­га­тое – это мно­же­ство всех че­ты­рех­уголь­ни­ков. Зна­чит:

B ⊂ A; C ⊂ A; D ⊂ A; E ⊂ A

Мно­же­ства В, С, D и Е яв­ля­ют­ся под­мно­же­ства­ми мно­же­ства А.

Далее вспом­ним опре­де­ле­ние па­рал­ле­ло­грам­ма:

Па­рал­ле­ло­грам­мом на­зы­ва­ет­ся такой че­ты­рех­уголь­ник, у ко­то­ро­го про­ти­во­по­лож­ные сто­ро­ны по­пар­но па­рал­лель­ны.

Для того чтобы убе­дить­ся, что фи­гу­ра яв­ля­ет­ся па­рал­ле­ло­грам­мом, необ­хо­ди­мо вспом­нить его при­зна­ки:

1. Если 2 сто­ро­ны па­рал­лель­ны и равны, то такой че­ты­рех­уголь­ник яв­ля­ет­ся па­рал­ле­ло­грам­мом.

Зна­чит, В – это мно­же­ство всех па­рал­ле­ло­грам­мов.

2. Если в че­ты­рех­уголь­ни­ке диа­го­на­ли пе­ре­се­ка­ют­ся и точ­кой пе­ре­се­че­ния де­лят­ся по­по­лам, то эта фи­гу­ра – па­рал­ле­ло­грамм.

Зна­чит, С – это мно­же­ство всех па­рал­ле­ло­грам­мов.

Про мно­же­ство D на­пря­мую было ска­за­но, что это мно­же­ство всех па­рал­ле­ло­грам­мов.

Если будет сто­ять во­прос, какие мно­же­ства равны между собой, то можно от­ве­тить, что:

В = С = D – это мно­же­ства всех па­рал­ле­ло­грам­мов.

3. Если в па­рал­ле­ло­грам­ме хотя бы один угол равен 900, то такой па­рал­ле­ло­грамм яв­ля­ет­ся пря­мо­уголь­ни­ком.

Зна­чит, Е – это мно­же­ство всех пря­мо­уголь­ни­ков. Мно­же­ство всех пря­мо­уголь­ни­ков яв­ля­ет­ся под­мно­же­ством (част­ным слу­ча­ем) про­из­воль­но­го че­ты­рех­уголь­ни­ка и под­мно­же­ством па­рал­ле­ло­грам­ма. От­сю­да имеем:

Е ⊂ А; E ⊂ B; E ⊂ C; E ⊂ D

Мы рас­смот­ре­ли мно­же­ства че­ты­рех­уголь­ни­ков, из ко­то­рых самое бо­га­тое мно­же­ство – это мно­же­ство всех че­ты­рех­уголь­ни­ков, далее по-раз­но­му за­да­ны мно­же­ства па­рал­ле­ло­грам­мов и, на­ко­нец, Е – это мно­же­ство всех пря­мо­уголь­ни­ков. Были даны от­ве­ты на во­про­сы, где вер­ные вклю­че­ния, какие мно­же­ства равны между собой.

Мы уже знакомы с понятием множеств. Знаем, что каждое множество состоит из элементов. Сегодня мы рассмотрим примеры пересечения и объединения множеств.

Пе­ре­се­че­ние и объ­еди­не­ние мно­жеств – опе­ра­ции над мно­же­ства­ми.

При­мер: В клас­се 19 уче­ни­ков: 10 де­во­чек, 9 маль­чи­ков.

10 де­во­чек – это мно­же­ство .

9 маль­чи­ков – это мно­же­ство .

Класс из 19 уче­ни­ков – это мно­же­ство С, ко­то­рое объ­еди­ня­ет два мно­же­ства.

Пусть в клас­се 5 от­лич­ни­ков – это мно­же­ство D.

Из них 2 маль­чи­ка – это мно­же­ство E.

Из какие эле­мен­тов со­сто­ит мно­же­ство Е?

Маль­чи­ки вхо­дят в мно­же­ства В, так как 2 маль­чи­ка – от­лич­ни­ки, они вхо­дят в мно­же­ство D.

Рис. 1. Пе­ре­се­че­ние двух мно­жеств

Мно­же­ство Е есть пе­ре­се­че­ние двух мно­жеств В и D(рис. 1).

Опре­де­ле­ние: объ­еди­не­ни­ем мно­жеств А и В на­зы­ва­ет­ся новое мно­же­ство, со­сто­я­щее из тех и толь­ко тех эле­мен­тов, ко­то­рые вхо­дят хотя бы в одно из мно­жеств А или В (рис. 3).

Рис. 2. Мно­же­ства

Рис. 3. Объ­еди­не­ние мно­жеств

 – знак объ­еди­не­ния.

Мно­же­ство  со­сто­ит из всех эле­мен­тов , ко­то­рые вхо­дят или в мно­же­ство , или в мно­же­ство . Это можно за­пи­сать сле­ду­ю­щим об­ра­зом:

Дано мно­же­ство = и .

Найти объ­еди­не­ние мно­жеств .

Ре­ше­ние:

Дано мно­же­ство  и .

Найти объ­еди­не­ние мно­жеств .

Ре­ше­ние:

Имеем со­во­куп­ность нера­венств:

Ре­шить квад­рат­ное нера­вен­ство .

Ре­ше­ние:

Рас­смот­рим функ­цию .

Най­дём корни функ­ции .

По тео­ре­ме Виета: .

Имеем объ­еди­не­ние двух мно­жеств .

Схе­ма­ти­че­ски изоб­ра­зим гра­фик функ­ции:

 при  или .

Ответ:.

Пе­ре­се­че­ние мно­жеств

Пе­ре­се­че­ни­ем мно­жеств Aи B на­зы­ва­ет­ся новое мно­же­ство, со­дер­жа­щее те и толь­ко те эле­мен­ты, ко­то­рые вхо­дят од­но­вре­мен­но и в мно­же­ство А, и в мно­же­ство В.

 – знак пе­ре­се­че­ния

Рис. 4а. Пе­ре­се­че­ние мно­жеств

– пе­ре­се­че­ние мно­жеств на рис. 4а

Рис. 4б. Пе­ре­се­че­ния мно­жеств нет

На рис. 4б мно­же­ства не пе­ре­се­ка­ют­ся, их пе­ре­се­че­ние – пу­стое мно­же­ство 

Даны мно­же­ства  и . Найти пе­ре­се­че­ние мно­жеств .

Ре­ше­ние

По опре­де­ле­нию пе­ре­се­че­ния, ре­ше­ни­ем будут те эле­мен­ты, ко­то­рые од­но­вре­мен­но вхо­дят в оба мно­же­ства:

 – пе­ре­се­че­ние мно­жеств.

Срав­ним с объ­еди­не­ни­ем:

C= – объ­еди­не­ние мно­жеств.

Найти пе­ре­се­че­ние бес­ко­неч­ных мно­жеств

Ре­ше­ние

Нужно найти такие х, ко­то­рые при­над­ле­жат пе­ре­се­че­нию :

Нужно ре­шить си­сте­му нера­венств. На оси изоб­ра­жа­ем мно­же­ства и на­хо­дим их пе­ре­се­че­ние

Ответ:

.

Срав­ним с объ­еди­не­ни­ем мно­жеств:

Ре­шить си­сте­му нера­венств 

Ре­ше­ние:

Рас­смот­рим ось х:

Ответ: 

Пе­ре­се­че­ни­ем мно­жеств будет:

Источник конспекта: http://interneturok.ru/ru/school/algebra/9-klass/sistemy-racionalnyh-neravenstv/ponyatie-mnozhestva?konspekt&chapter_id=22

http://interneturok.ru/ru/school/algebra/9-klass/sistemy-racionalnyh-neravenstv/peresechenie-i-ob-edinenie-mnozhestv?konspekt&chapter_id=22

Источник видео: http://www. youtube.com/watch?v=s0As4waawqA

Набор операций

• Объединение двух множеств — это множество, содержащее все элементы из обоих этих множеств.
  • Написано \(A\чашка B\) и определено \[A\cup B = \{x \mid x\in A\vee x\in B\}\,.\]
  • Например, \[\{1,2,3,4\}\чашка\{3,4,5,6\} = \{1,2,3,4,5,6\}\,\\ \mathbf{R} = \mathbf{Q} \cup \overline{\mathbf{Q}}\,.\]
• Пересечение двух множеств — это множество, содержащее элементы, которые входят в оба этих множества.
  • Написано \(A\cap B\) и определено \[A\cap B = \{x \mid x\in A\клин x\in B\}\,\\ \mathbf{Q} \cap \overline{\mathbf{Q}}=\emptyset\,.\]
  • Например, \[\{1,2,3,4\}\cap\{3,4,5,6\} = \{3,4\}\,.\]
• Разница между двумя наборами — это набор значений в одном, но не в другом: \[A-B = \{x \mid x\in A\text{ и } x\notin B\}\,.\]
  • Например, \[\{1,2,3,4\}-\{3,4,5,6\} = \{1,2\}\,\\ \overline{\mathbf{Q}} = \mathbf{R}-\mathbf{Q} \,. \]
  • Также иногда пишут \(A\setminus B\).
• Теорема: Для любых множеств \(|AB|\le|A|\).

  Доказательство: Предположим, что \(|A-B|>|A|\). Тогда должен быть элемент \(x\) с \(x\in(AB)\), но \(x\не в A\). Таким образом, \(AB\not\subseteq A\).

  Но из определения разности множества мы видим, что \[ A-B = \{x \mid x\in A\text{ и } x\notin B\} \subseteq \{x \mid x\in A\} =A\,. \] Это противоречие, поэтому \(|AB|\le|A|\).∎

• С подобными доказательствами мы могли бы доказать следующее:

  Теорема: Для любых множеств \(|A\cap B|\le|A|\) и \(|A\cap B|\le|B|\).

  Теорема: Для любых множеств \(|A\cup B|\ge|A|\) и \(|A\cup B|\ge|B|\).

• При выполнении операций над множествами нам часто нужно определить универсальный набор , \(U\).
  • Как и домен для квантификаторов, это набор всех возможных значений, с которыми мы работаем.
  • Часто не определяется явно, а подразумевается в зависимости от проблемы, которую мы рассматриваем.
  • напр. когда мы работаем с действительными числами, вероятно, \(U=\mathbf{R}\).
• дополнение набора \(S\) записывается как \(\overline{S}\) и представляет собой набор всех значений , а не в \(S\): \[\overline{S} = \{x\mid x\notin S\} = U-S \,.\]
  • Стандартная запись иррациональных чисел теперь должна иметь большой смысл: с универсальным набором \(\mathbf{R}\) иррациональные числа (\(\overline{\mathbf{Q}}\)) являются дополнением рациональные числа (\(\mathbf{Q}\)).
• Теорема: Для любого множества \(S\cap\overline{S}=\emptyset\).

  Доказательство: Предположим противное, что существует элемент \(x\in S\cap\overline{S}\). Тогда по определению операторов \[ х\in S\cap\overline{S}\\ х\in S \клин х\in\overline{S} \\ х\in S \клин х\notin{S}\,. \] Это противоречие, поэтому мы должны иметь \(S\cap\overline{S}=\emptyset\).∎

• Обратите внимание на сходство между соответствующим набором и логическими операторами: \(\vee,\cup\) и \(\wedge,\cap\) и \(\overline{\mbox{S}},\neg\).
  • Это больше, чем похожие символы.
• Вот несколько важных наборов идентификаторов:

  Имя	Идентификатор
  Идентификатор	\(A\cap{U}= A\\A\cup\emptyset= A\)
  Доминирование 9000\cup = {U}\\A\cap\emptyset= \emptyset\)
  Идемпотент	\(A\cap A= A\\A\cup A= A\)
  Двойное отрицание	\ (\overline{(\overline{A})}= А\)
  Коммутативный	\(A\чашка B = B\чашка A\\A\крышка B = B\крышка A\)
  Ассоциативный	\((A\чашка B)\чашка C = A\cup(B\cup C)\\(A\cap B)\cap C = A\cap(B\cap C)\)
  Распределительный	\(A\cup(B\cap C) =(A\чашка B)\крышка(A\чашка C)\\A\крышка(B\чашка C) = (A\крышка B)\чашка(A\крышка B)\)
  Закон де Моргана	\(\overline{A\cap B}=\overline{A} \cup \overline{B}\\\overline{A\cup B}= \overline{A} \cap \overline{B}\)
  Поглощение	\(A\чашка(A\крышка B) = A \\ A\крышка(A\чашка B) = A\)
  Отрицание	\(A\cup\overline{ A} = {U}\\A\cap\overline{A} = \emptyset\)

• Выглядит знакомо? Это таблица логических эквивалентов с некоторым поиском и заменой.
• В качестве примера мы можем доказать один из законов Де Моргана (книга доказывает другой).
  • Мы будем осторожны с этим и будем манипулировать нотацией построителя наборов.

  Теорема: Для любых множеств \(\overline{A\cup B}= \overline{A} \cap \overline{B}\).

  Доказательство: По определению операций множества, \[\начать{выравнивать*} \overline{A\чашка B} &= \{x\mid x\notin (A\cup B)\} \\ &= \{x\mid \neg(x \in (A\cup B))\} \\ &= \{x\mid \neg(x \in A\vee x\in B)\} \\ &= \{x\mid\neg(x\in A)\клин \neg(x\in B)\} \\ &= \{x\mid x \in \overline{A}\wedge x \in \overline{B} )\} \\ &= \{x\mid x \in (\overline{A}\cap\overline{B}))\} \\ &= \overline{A}\cap\overline{B}\,.\quad{}∎ \конец{выравнивание*}\]

  • Можно было бы привести и менее формальное доказательство. (Для этого см. раздел 2.2, пример 10.)
  • Это тот случай, когда, вероятно, проще быть более формальным: писать все детали в предложениях настолько мучительно, что семь шагов в этом доказательстве приятнее читать. (См. также пример 10.)
• Это доказательство может подсказать, почему таблицы эквивалентностей и множественных тождеств так похожи.
  • Для любой из операций над множествами мы можем использовать нотацию построителя множеств, а затем использовать логические эквивалентности для управления условиями.
  • Так как мы проделываем те же манипуляции, то и таблицы у нас получились одинаковые.
  • Будьте осторожны с другими операциями. То, что это сработало для них, не означает, что вы можете считать, что все одинаково. Не существует логической версии установленного различия или установленной версии исключающего или (по крайней мере, насколько мы определили).

• Теорема: Для любых множеств \(AB = A\cap\overline{B}\).

  Менее формальное доказательство: Набор \(A-B\) представляет собой значения из \(A\) с удаленными значениями из \(B\).

  Набор \(\overline{B}\) — это набор всех значений, не входящих в \(B\). Таким образом, пересечение с \(\overline{B}\) приводит к тому, что остаются только значения, не входящие в \(B\). То есть \(A\cap\overline{B}\) — это \(A\) со всеми удаленными значениями из \(B\). Таким образом, мы видим, что эти множества содержат одни и те же элементы. ∎

  Более формальное доказательство: По определению операций над множествами \[\начать{выравнивать*} А-Б &= \{х\середина х\в А \клин х\не в В\} \\ &= \{x\mid x\in A \wedge x\in \overline{B}\} \\ &= \{x\mid x\in (A \cap \overline{B})\} \\ &= A\cap\overline{B}\,.\quad{}∎ \конец{выравнивание*}\]

• Я думаю, что любое из этих доказательств является действительным.
  • «Менее формальная» версия должна быть написана достаточно тщательно, чтобы убедить читателя (или ТА в вашем случае).
  • В «более формальной» версии больше шагов и отсутствует интуитивная причина (она может помочь вам вспомнить почему).
• Мы можем использовать тождества множеств для доказательства других фактов о множествах. Например:

  Теорема: \(A-(B\чашка C)= (A-B)\cap(A-C)\).

  Доказательство: Для множеств \(A,B,C\) из приведенной выше теоремы имеем \[\начать{выравнивать*} А-(В\чашка С) &= A\cap \overline{B\cup C} \\ &= A\cap \overline{B}\cap \overline{C} \\ &= A\cap \overline{B}\cap A\cap \overline{C} \\ &= (A-B)\cap (A-C)\,.\quad{}∎ \конец{выравнивание*}\]

• Эти тождества должны убедить вас в том, что порядок объединения и пересечения не имеет значения (точно так же, как сложение, умножение, конъюнкция и дизъюнкция: все они являются коммутативными операциями).
  • Таким образом, мы можем написать их кучу без скобок, как сложение/умножение/соединение/дизъюнкция: \[A\чашка B\чашка C \чашка D\,\\A\крышка B\крышка C \крышка D\,.\]
• Если нам нужно выполнить объединение/пересечение множества вещей, иногда используется такое обозначение, как суммирование.
  • Например, предположим, что в этом семестре ZJU предлагает \(n\) курсов. {n} S_i\,.\] Студенты берут 92\,.\]

Наборы: основное определение и операции

Мы затронем темы:

• Определение наборов

• Операции: Объединение, пересечения, дополнение, множество разностей.

• Диаграммы Венна

• Кардинальность: принцип включения-исключения

Определяющие наборы

Пока удобно предположить, что существует вселенная из элементов .

Понятие множества является настолько базовым в математике, что не поддается простому определение. Большинство определений просто переходят к , набор — это набор :-).

Существует два способа определить набор:

• Явно : Просто перечислите его элементы. напр., .

• Неявно : Напишите описание того, что входит в набор, на английском языке или еще лучше на логике. напр., .

На данный момент, всякий раз, когда мы обсуждаем наборы, необходимо прояснить вселенную.

Наивная теория множеств

Понятие теории множеств, которое мы изучаем в этой лекции, называется наивной теорией множеств .

Причина, которую мы называем наивной, заключается в допущении универсального множества . До 20 века математики и философы представляли набор всех возможных сущностей и назвал его универсальный набор. В этом наборе есть буквально все, что можно представить: козы , муравьи , Бозоны Хиггса , столы , стулья , номера , группы и все такое. Подумайте об этом, и престо !, в универсальном наборе есть. Но работы математиков таких как Кантор и Бертран Рассел в начале 20 века доказали, что универсальное множество не может существовать, так как его существование ведет к парадоксам или противоречиям.

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

Пример 1: Целые числа

Мы предполагаем, что вселенная ограничена множеством всех целых чисел.

Что определяют следующие наборы:

Обратите внимание, что ограничение нашей вселенной набором целых чисел не создает противоречия или парадокса в приведенных выше определениях.

Пример 2: Животные

Пусть вселенная будет всеми видами животных на планете Земля.

Обратите внимание, что ограничение вселенной только всеми видами животных на планете Земля делает наборы выше четко определенными и свободными. противоречий.

Пустые/универсальные наборы

Наивная теория множеств часто добавляет специальное универсальное множество. В качестве отмечалось ранее, универсального набора не существует, и его нужно будет необученный.

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

Союз, Пересечение, Разность и Дополнение.

Позвольте обозначить наборы, взятые из ограниченной вселенной .

Операция дополнения определяется в наивной теории множеств.

• .

Если мы действуем в ограниченной вселенной, то .

Иначе не существует, строго говоря, потому что универсального набора, содержащего все, не существует.

Пример 1

Позвольте быть ограниченной вселенной, заданной набором всех целых чисел.

Позвольте быть набором всех нечетных целых чисел, быть набором всех четных целых чисел, быть набором всех простых целых чисел и быть набором всех составных чисел (не являются ни простыми, ни составными).

Что такое наборы?

Пример-2

То же, что и ? Как насчет ?

То же, что и ? Приведите простой пример.

Конечный Против. Бесконечные наборы

Конечные множества — это те, которые имеют конечное число элементов. Бесконечные наборы, с другой стороны, имеют бесконечно много элементов. Мы определим бесконечные множества, и в ближайшее время подробно рассмотрим бесконечные множества.

Диаграммы Венна

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

С другой стороны, диаграммы Венна — это не так уж и чихать. статья в Википедии о Венне диаграммы или на этом сайте есть много интересной информации.

Диаграммы Венна можно использовать для доказательства некоторых свойств множеств.

Мощность

Мощность множества — это количество элементов в нем. На данный момент это имеет смысл говорить о мощности только для конечных множеств. Мы будем обсудим вопрос о бесконечных множествах и мощности после того, как мы охватывающие отношения и функции. Мощность пустого множества равна конечно ноль. Мощность множества никогда не может быть отрицательной.

Какова мощность следующих множеств:

• (Ответ: 21).

• (Ответ 15).

• (Ответ: 26)

• ? (Ответ: 10)

• ?

• ?

Мощность множества обозначается или иногда . Мы будем использовать .

Обратите внимание на следующий интересный факт: . Почему это правда?

Используя диаграмму Венна, мы можем вывести, что

Приведенное выше отношение называется принципом исключения включения .

Мы можем расширить его до трех наборов:

Обратите внимание на любопытное изменение знака!!

Пример-1

Пусть и .

Проверить принцип включения-исключения для ?

Мы это видим.

Мы также можем увидеть это, используя принцип исключения включения:

Пример-2

Если мы посмотрим на все числа от до . Сколько чисел содержит ?

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

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

Пример -3

Сколько чисел между и делится на или на или на ?

Давайте исправим вселенную, чтобы она была .

Пусть . Аналогично, пусть — числа, которые делятся на и быть числа делятся на .

Мы ищем .

У нас есть

• .

• .

• .

• .

• .

Всего = = .

(могу ошибиться в расчетах, проверьте).

Общий принцип исключения включения

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

Головоломка (Подсчет простых чисел)

Имея список простых чисел от до , покажите, как этот список можно использовать для подсчета количества простых чисел от до с помощью включение исключение.

Давайте рассмотрим более простой случай подсчета простых чисел из . Вместо простых чисел будем считать составные. Как только мы посчитаем композиты, мы можем сразу же сделать вывод, сколько существует простых чисел.

Универсальный набор. Определим множество. Мы опускаем, поскольку оно не является ни простым, ни составным.

Мы принимаем исходный набор простых чисел равным .

Теорема Каждое составное число из делится на или . Другими словами, каждое составное число имеет или в качестве одного из своих простых делителей.

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

Пишем

Заметим, что это просто . Мы знаем, потому что есть числа, которые делятся на .

Следовательно,

Таким образом, количество составных частей равно (почему мы вычли ?) Количество простых чисел будет (почему из? почему не здесь?). Убедитесь, что действительно есть простые числа от до : .

Тот же расчет может быть выполнен для всех простых чисел. За это получаем:

Используя это, число композитов равно . Отсюда делаем вывод, что простые числа существуют. Дополнительные четыре простых числа за .

Существует очень тесная связь между этим способом подсчета и ситом Эратостена для перечисления все простые числа. Следовательно, принцип включения-эксклюзия часто называют принципом сита .

как забавное упражнение: реализуйте счетчик для решения головоломки. Вам обязательно нужно будет написать программу скорее чем пытаться сделать это вручную.

Декартовы произведения и мощности

Теперь рассмотрим две другие операции над множествами:

• Декартовы произведения

• Силовые наборы

Декартово произведение

Возьми наборы и над какой-нибудь вселенной. Декартово произведение определяется как

Другими словами, мы строим набор из всех 2-кортежей , где первый компонент из набора и второй компонент из набора.

Мы можем распространить декартово произведение не только на множества:

Здесь мы берем декартово произведение множеств, и в результате получается множество 3-кортежей .

Пример-1

Если множество всех действительных чисел представлено вещественной линией, то что это за множество?

Ответ: состоит из всех наборов вещественных чисел вида где и — вещественные числа. Другими словами, мы перешли от однозначных чисел к -мерным координатам.

Для простоты произведение множества на себя записывается .

Что такое ?

Пример 2: пустой набор

Чему равно декартово произведение пустого множества на множество?

Ответ: Пустое множество.

Мощность декартовых произведений

Правило декартова произведения состоит в том, что

Мы можем убедиться сами, нарисовав таблицу всех записей. Допустим и .

Порядок декартова произведения имеет значение

Если для множеств, то заметим, что не будет равно. Другими словами, имеет значение в кортеже, который идет первым и идет вторым. Например, если я попрошу вас нарисовать пиксель в точке , это не то же самое, что нарисовать пиксель в , верно?

Если , однако, это тривиально, что все одно и то же.

Пример

Какова величина декартова произведения, если ?

Подмножество

Set является подмножеством написанного тогда и только тогда, когда каждый элемент также является элементом .

Примеры

• ?

• ?

• Верно ли, что для любого набора ?

• Верно ли, что для всех наборов?

• Верно ли, что для всех наборов?

Ответы: да, нет, да, нет, да!

Набор Python (с примерами)

В этом руководстве вы узнаете все о наборах Python; как они создаются, добавляются или удаляются из них элементы, и все операции, выполняемые над множествами в Python.

Набор — это неупорядоченный набор элементов. Каждый элемент набора уникален (без дубликатов) и должен быть неизменным (не может быть изменен).

Однако сам набор может изменяться. Мы можем добавлять или удалять элементы из него.

Множества также можно использовать для выполнения математических операций над множествами, таких как объединение, пересечение, симметричная разность и т. д.

Создание наборов Python

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

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

 # Различные типы наборов в Python
# набор целых чисел
мой_набор = {1, 2, 3}
печать (мой_набор)
# набор смешанных типов данных
my_set = {1.0, "Привет", (1, 2, 3)}
печать (мой_набор) 

Выход

  {1, 2, 3}
{1.0, (1, 2, 3), "Привет"}  

Попробуйте также следующие примеры.

 # набор не может иметь дубликатов
# Вывод: {1, 2, 3, 4}
my_set = {1, 2, 3, 4, 3, 2}
печать (мой_набор)
# мы можем сделать множество из списка
# Вывод: {1, 2, 3}
my_set = установить ([1, 2, 3, 2])
печать (мой_набор)
# в наборе не может быть изменяемых элементов
# здесь [3, 4] — изменяемый список
# это вызовет ошибку. 
my_set = {1, 2, [3, 4]} 

Вывод

  {1, 2, 3, 4}
{1, 2, 3}
Traceback (последний последний вызов):
  Файл "", строка 15, в 
    my_set = {1, 2, [3, 4]}
TypeError: unhashable type: 'list'  

Создать пустой набор немного сложно.

Пустые фигурные скобки {} создаст пустой словарь в Python. Чтобы создать набор без каких-либо элементов, мы используем функцию set() без каких-либо аргументов.

 # Различать набор и словарь при создании пустого набора
# инициализируем {}
а = {}
# проверить тип данных a
печать (тип (а))
# инициализируем с помощью set()
а = установить ()
# проверить тип данных a
печать (тип (а)) 

Выход

  <класс 'словарь'>
  

Изменение набора в Python

Наборы изменяемы. Однако, поскольку они неупорядочены, индексация не имеет смысла.

Мы не можем получить доступ к элементу набора или изменить его с помощью индексации или нарезки. Установить тип данных не поддерживает его.

Мы можем добавить один элемент, используя метод add() , и несколько элементов, используя метод update() . 9Метод 0701 update() может принимать в качестве аргумента кортежи, списки, строки или другие множества. Во всех случаях дубликаты избегаются.

 # инициализировать my_set
мой_набор = {1, 3}
печать (мой_набор)
# мой_набор[0]
# если вы раскомментируете строку выше
# вы получите сообщение об ошибке
# TypeError: объект 'set' не поддерживает индексацию
# добавить элемент
# Вывод: {1, 2, 3}
my_set.add(2)
печать (мой_набор)
# добавить несколько элементов
# Вывод: {1, 2, 3, 4}
my_set.update([2, 3, 4])
печать (мой_набор)
# добавить список и установить
# Вывод: {1, 2, 3, 4, 5, 6, 8}
my_set.update([4, 5], {1, 6, 8})
печать (мой_набор) 

Выход

  {1, 3}
{1, 2, 3}
{1, 2, 3, 4}
{1, 2, 3, 4, 5, 6, 8}  

Удаление элементов из набора

Конкретный элемент можно удалить из набора с помощью методов discard() и remove() .

Единственная разница между ними состоит в том, что функция discard() оставляет набор без изменений, если элемент отсутствует в наборе. С другой стороны, функция remove() вызовет ошибку в таком состоянии (если элемент отсутствует в наборе).

Следующий пример иллюстрирует это.

 # Разница между discard() и remove()
# инициализировать my_set
my_set = {1, 3, 4, 5, 6}
печать (мой_набор)
# отбросить элемент
# Вывод: {1, 3, 5, 6}
my_set.discard(4)
печать (мой_набор)
# удалить элемент
# Вывод: {1, 3, 5}
my_set.remove(6)
печать (мой_набор)
# отбросить элемент
# отсутствует в my_set
# Вывод: {1, 3, 5}
my_set.discard(2)
печать (мой_набор)
# удалить элемент
# отсутствует в my_set
# вы получите сообщение об ошибке.
# Вывод: KeyError
my_set.remove(2) 

Выход

  {1, 3, 4, 5, 6}
{1, 3, 5, 6}
{1, 3, 5}
{1, 3, 5}
Traceback (последний последний вызов):
  Файл "", строка 28, в 
KeyError: 2  

Точно так же мы можем удалить и вернуть элемент, используя метод pop() .

Поскольку набор является неупорядоченным типом данных, невозможно определить, какой элемент будет извлечен. Это совершенно произвольно.

Мы также можем удалить все предметы из набора, используя метод очистки() .

 # инициализировать my_set
# Вывод: набор уникальных элементов
my_set = установить ("HelloWorld")
печать (мой_набор)
# извлекаем элемент
# Вывод: случайный элемент
печать (my_set.pop())
# извлечь другой элемент
my_set.pop()
печать (мой_набор)
# очистить my_set
# Вывод: установить()
my_set.clear()
print(my_set) 

Вывод

  {'H', 'l', 'r', 'W', 'o', 'd', 'e'}
ЧАС
{'г', 'В', 'о', 'д', 'е'}
set()  

Python Операции над множествами

Наборы можно использовать для выполнения математических операций над множествами, таких как объединение, пересечение, разность и симметричная разность. Мы можем сделать это с помощью операторов или методов.

Рассмотрим следующие два набора для следующих операций.

 >>> А = {1, 2, 3, 4, 5}
>>> B = {4, 5, 6, 7, 8} 

Set Union

Union of A и B представляет собой набор всех элементов из обоих наборов.

Объединение выполняется с помощью | оператор. То же самое можно сделать с помощью метода union() .

 # Установить метод объединения
# инициализируем А и Б
А = {1, 2, 3, 4, 5}
В = {4, 5, 6, 7, 8}
# использовать | оператор
# Вывод: {1, 2, 3, 4, 5, 6, 7, 8}
напечатать (А | В) 

Выход

  {1, 2, 3, 4, 5, 6, 7, 8}  

Попробуйте выполнить следующие примеры в оболочке Python.

 # использовать функцию объединения
>>> А.союз(Б)
{1, 2, 3, 4, 5, 6, 7, 8}
# используем функцию объединения на B
>>> Б.союз(А)
{1, 2, 3, 4, 5, 6, 7, 8} 

Пересечение множества

Пересечение A и B — это набор элементов, общих для обоих наборов.

Пересечение выполняется с помощью 9Оператор 0701 и . То же самое можно сделать, используя метод пересечения() .

 # Пересечение множеств
# инициализируем А и Б
А = {1, 2, 3, 4, 5}
В = {4, 5, 6, 7, 8}
# использование и оператор
# Вывод: {4, 5}
печать(A и B) 

Вывод

  {4, 5}  

Попробуйте выполнить следующие примеры в оболочке Python.

 # использовать функцию пересечения на A
>>> А.пересечение(Б)
{4, 5}
# используем функцию пересечения на B
>>> Б.пересечение(А)
{4, 5} 

Set Difference

Отличие набора B от набора A ( A — B ) это набор элементов, которые есть только в 3 B 83 B но не . Точно так же B — A является набором элементов в B , но не в A .

Различие выполняется с помощью оператора - . То же самое можно сделать с помощью метода разницы().

 # Разница двух наборов
# инициализируем А и Б
А = {1, 2, 3, 4, 5}
В = {4, 5, 6, 7, 8}
# use - оператор на A
# Вывод: {1, 2, 3}
печать(A - B) 

Вывод

  {1, 2, 3}  

Попробуйте выполнить следующие примеры в оболочке Python.

 # использовать функцию разницы на A
>>> А.разница(Б)
{1, 2, 3}
# use - оператор на B
>>> Б - А
{8, 6, 7}
# используем функцию разности на B
>>> Б.разница(А)
{8, 6, 7} 

Выход

  {1, 2, 3, 6, 7, 8}  

Попробуйте выполнить следующие примеры в оболочке Python.

 # использовать функцию symmetric_difference на A
>>> А.симметричная_разница(Б)
{1, 2, 3, 6, 7, 8}
# использовать функцию symmetric_difference на B
>>> Б. симметричная_разница (А)
{1, 2, 3, 6, 7, 8} 

Другие методы установки Python

Существует множество методов установки, некоторые из которых мы уже использовали выше. Вот список всех методов, которые доступны с установленными объектами:

Метод	Описание
добавить()	Добавляет элемент в набор
очистить()	Удаляет все элементы из набора
копировать()	Возвращает копию набора
разница()	Возвращает разницу двух или более наборов в виде нового набора
разность_обновление()	Удаляет все элементы другого набора из этого набора
отбросить()	Удаляет элемент из набора, если он является членом. (Ничего не делать, если элемента нет в наборе)
пересечение()	Возвращает пересечение двух наборов как новый набор
cross_update()	Обновляет набор пересечением себя и другого
непересекающийся()	Возвращает Истинно , если два набора имеют нулевое пересечение
issubset()	Возвращает True , если другой набор содержит этот набор
issuperset ()	Возвращает True , если этот набор содержит другой набор
поп()	Удаляет и возвращает произвольный элемент множества. Вызывает KeyError , если набор пуст
удалить()	Удаляет элемент из набора. Если элемент не является членом, вызывает ошибку KeyError
симметричная_разность()	Возвращает симметричную разность двух наборов в виде нового набора
симметричная_разница_обновление()	Обновляет набор с симметричной разностью себя и другого
объединение()	Возвращает объединение наборов в новый набор
обновление()	Обновляет набор объединением себя и других

Другие операции над множествами

Проверка принадлежности множества

Мы можем проверить, существует ли элемент в множестве, используя ключевое слово в .

 # в ключевом слове в наборе
# инициализировать my_set
my_set = установить ("яблоко")
# проверяем, присутствует ли 'a'
# Вывод: Истина
print('a' в my_set)
# проверить, присутствует ли 'p'
# Вывод: Ложь
print('p' нет в my_set) 

Выход

  Верно
False  

Перебор набора

Мы можем перебирать каждый элемент набора с помощью цикла for .

 >>> для письма в наборе ("яблоко"):
... печать (письмо)
...
а
п
е
l 

Встроенные функции с набором

Встроенные функции, такие как all() , any() , enumerate() , len() , max()

Функция	Описание
все()	Возвращает True , если все элементы набора истинны (или если набор пуст).
любой()	Возвращает True , если любой элемент набора истинен. Если набор пуст, возвращает False .
перечислить()	Возвращает перечисляемый объект. Он содержит индекс и значение для всех элементов набора в виде пары.
лен()	Возвращает длину (количество элементов) в наборе.
макс()	Возвращает самый большой элемент в наборе.
мин()	Возвращает наименьший элемент в наборе.
отсортировано()	Возвращает новый отсортированный список из элементов набора (сам набор не сортируется).
сумма()	Возвращает сумму всех элементов набора.

Python Frozenset

Frozenset — это новый класс, обладающий характеристиками набора, но его элементы нельзя изменить после назначения. В то время как кортежи — это неизменяемые списки, замороженные наборы — неизменные наборы.

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

Frozensets можно создавать с помощью функции Frozenset().

Этот тип данных поддерживает следующие методы: союз() . Будучи неизменным, он не имеет методов, которые добавляют или удаляют элементы.

 # Фрозенсеты
# инициализируем А и Б
A = замороженный набор ([1, 2, 3, 4])
B = замороженный набор ([3, 4, 5, 6]) 

Попробуйте эти примеры в оболочке Python.

 >>> A.isdisjoint(B)
ЛОЖЬ
>>> А.разница(Б)
замороженный набор ({1, 2})
>>> А | Б
замороженный набор ({1, 2, 3, 4, 5, 6})
>>> А.добавить(3)
...
AttributeError: объект 'frozenset' не имеет атрибута 'add' 

Логические и математические рассуждения, введение в корректуру

\(\require{mathrsfs}\newcommand{\abs}[1]{\left| #1 \right|} \renewcommand{\emptyset}{\varnothing} \DeclareMathOperator{\dom}{dom} \DeclareMathOperator{\range}{rng} \DeclareMathOperator{\пермь}{пермь} \новая команда{\lt}{<} \новая команда{\gt}{>} \newcommand{\amp}{&} \)

Теперь, когда мы определили множества, давайте напомним себе, что мы уже знаем о некоторых: \(\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}\text{,}\) натуральные числа, целые числа, рациональные числа, действительные числа и комплексные числа. Определив наборы, мы также хотим знать, как их можно комбинировать для формирования новых наборов, что и является целью этого раздела.

Определение 2.2.1 Объединение, пересечение, различие

Имея два множества \(A,B\), мы можем выполнить три основные бинарные операции.

штуцер

\(A \cup B = \{ x \mid x \in A \vee x \in B \}\)

перекресток

\(A \cap B = \{ x \mid x \in A \wedge x \in B \}\)

разница

\(A \setminus B = \{ x \mid x \in A \wedge x \notin B \}\)

Легко видеть, что объединение и пересечение коммутативны и ассоциативны, поскольку дизъюнкция (\(\vee\)) и конъюнкция (\(\клин\)) таковы. Более того, они распределяются друг над другом по той же причине. Кроме того, вы можете думать о разнице множеств как об аналоге отрицания (\(\neg\)), момент, который будет прояснен позже. Эти факты заключены в следующей теореме, которую я предлагаю вам доказать для себя, используя доказательства равенства множеств по принципу «тогда и только тогда».

Теорема 2.2.2

Бинарные операции объединение и пересечение коммутативны, ассоциативны и распределяются друг над другом. То есть

Более того, с той разницей, что они удовлетворяют своего рода законам Де Моргана:

Кроме того, разность множеств удовлетворяет своего рода исключению двойного отрицания, а именно,

Определение 2.2.3 Непересекающиеся

Множества \(A,B\) называются непересекающимися , если их пересечение пусто, т. е. \(A \cap B = \emptyset\text{.}\) 9с = U\)

Еще один способ создания новых наборов — создание упорядоченных кортежей . Помните, множества неупорядочены, но очень полезно иметь объекты с упорядоченным расположением. Например, когда мы рассматривали точки на плоскости в алгебре и исчислении, мы обычно представляли их парами действительных чисел, например \((a,b)\), где \(a\) — горизонтальное смещение от начало координат, а \(b\) — вертикальное смещение. Ясно, что \((0,1) \not= (1,0)\text{,}\) поэтому порядка имеют значение .

Определение 2.2.6 Декартово произведение

Для множеств \(A,B\) мы можем составить их декартово произведение (или просто произведение ), которое состоит из всех упорядоченных пар, где первая компонента является элементом \(A\), а вторая компонента является элемент \(B\text{.}\) Символически,

Обратите внимание, что в вашей книге декартово произведение называется «перекрестным произведением». Это просто неверно; никто не относится к этому так. Взаимные произведения — это либо операции с трехмерными (или семи) мерными векторами, которые вы изучили в исчислении, либо гораздо более сложные объекты, включающие групповые действия (вы не должны знать, что такое групповое действие). Только никогда не используйте термин перекрестное произведение вместо декартова произведения. 92\text{,}\), то есть он лежит в плоскости, поэтому мы можем его визуализировать! В частности, \(A \times B\) — это (открытый) прямоугольник на плоскости, \(x\)-значения которого находятся между \(2\) и \(3\), а \(y\)-значения находятся между \(6\) и \(7\text{.}\). Итак, когда у вас есть какое-то свойство о декартовых произведениях и вы хотите узнать, верно ли оно и/или почему оно верно, сначала представьте, что ваши декартовы произведения являются прямоугольниками в плоскости. Надеюсь, это поможет вашей интуиции для следующей теоремы.

Теорема 2.2.7

Предположим, что \(A,B,C,D\) — множества. Затем

• \(A \times (B \times C) = (A \times B) \cup (A \times C)\)
• \(A \times (B \cap C) = (A \times B) \cap (A \times C)\)
• \(A \times\emptyset = \emptyset\)
• \((A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)\)
• \((A \times B) \cup (C \times D) \subseteq (A \cup C) \times (B \cup D)\)

Набор операций и диаграмм Венна

Наборы рассматриваются как математические объекты. Подобно числам, мы можем выполнять определенные математические операции над множествами. Ниже мы рассмотрим основные операции, связанные с пересечением, объединением, разностью, симметрической разностью и дополнением множеств.

Для визуализации операций над множествами мы будем использовать диаграммы Венна. На диаграмме Венна прямоугольник показывает универсальное множество, а все остальные множества обычно представляются кружками внутри прямоугольника. Заштрихованная область представляет собой результат операции.

Пересечение наборов

Пересечение двух множеств \(A\) и \(B\) — это множество элементов, которые входят в оба множества \(A\) и \(B.\). Пересечение двух множеств записывается как \( А \крышка Б.\)

Два множества называются непересекающимися, если они не имеют общих элементов.

Примеры:

1. \(A = \left\{ {a,b,c} \right\},\) \(B = \left\{ {k,\ell,m} \right\}.\) Эти два множества не пересекаются, так как не имеют общих элементов. Их пересечение — пустое множество.

   \[A \cap B = \left\{ {a,b,c} \right\} \cap \left\{ {k,l,m} \right\} = \varnothing.\]

2. \(C = \left\{ {1,2,3,4} \right\},\) \(D = \left\{ {2,4,6,7} \right\}.\) пересечение этих множеств есть

   \[C \cap D = \left\{ {1,2,3,4} \right\} \cap \left\{ {2,4,6,7} \right\} = \left\{ { 2,4} \право\}.\]

Союз наборов

Объединение двух множеств \(A\) и \(B\) определяется как множество элементов, которые находятся либо в множестве \(A\), либо в множестве \(B\), либо в обоих \(A\) и \(B. \) Эта операция обозначается символом \(\cup\).

Примеры:

1. \(A = \left\{ {a,b,c} \right\},\) \(B = \left\{ {k,\ell,m} \right\}.\) Объединение два набора задаются

   \[A \cup B = \left\{ {a,b,c} \right\} \cup \left\{ {k,l,m} \right\} = \left\{ {a,b, в,к,л,м} \право\}.\]

2. \(C = \left\{ {1,2,3,4} \right\},\) \(D = \left\{ {2,4,6,7} \right\}.\) объединение множеств задается выражением

   \[C \cup D = \left\{ {1,2,3,4} \right\} \cup \left\{ {2,4,6,7} \right\} = \left\{ { 1,2,3,4,6,7} \право\}.\]

Принцип включения-исключения

Мощность конечного множества \(A,\), обозначаемого через \(\left| A \right|,\), равна количеству элементов в нем. Мощность объединения двух конечных множеств \(A\) и \(B\) определяется следующим соотношением:

\[\слева| {А \чашка Б} \право| = \ влево | А \право| + \влево| Б \ справа | — \влево| {A \cap B} \right|,\]

где \(\left| {A \cap B} \right|\) — мощность пересечения \(A\) и \(B. \)

Аналогичная формула существует для объединения \(3\) конечных множеств:

\[\слева| {A \чашка B \чашка C} \right| = \ влево | А \право| + \влево| Б \ справа | + \влево| С \ справа | — \влево| {А \заглавная Б} \право| — \влево| {A \cap C} \right| — \влево| {B \cap C} \право| + \влево| {A \cap B \cap C} \right|.\]

Разница двух наборов

Разность двух множеств \(A\) и \(B\) — это множество, которое содержит ровно все элементы из \(A\), но не из \(B.\) Разность двух множеств \(A\) а \(B\) обозначается \(A \обратная косая черта B\) или \(A — B.\)

Примеры:

1. \(A = \left\{ {a,b,c} \right\},\) \(B = \left\{ {k,\ell,m} \right\}.\) Разница между два непересекающихся множества равно исходному множеству. Итак, у нас есть

   \[A \backslash B = A \backslash \left( {A \cap B} \right) = A \backslash \varnothing = A = \left\{ {a,b,c} \right\}.\]

2. \(C = \left\{ {1,2,3,4} \right\},\) \(D = \left\{ {2,4,6,7} \right\}. \) разность двух множеств \(C\) и \(D\) определяется выражением

   \[C \обратная косая черта D = \left\{ {1,2,3,4} \right\} — \left\{ {2,4,6,7} \right\} = \left\{ {1 ,3} \право\}.\]

Симметричная разность

Симметричная разность двух множеств \(A\) и \(B\) — это множество всех элементов, принадлежащих ровно одному из двух исходных множеств. Эта операция записывается как \(A \,\triangle\, B\) или \(A \oplus B.\)

В терминах объединений и пересечений симметричная разность двух множеств \(A\) и \(B\) может быть выражена как

\[A \,\треугольник\, B = \left( {A \cup B} \right) \backslash \left( {A \cap B} \right).\]

Примеры:

1. \(A = \left\{ {a,b,c} \right\},\) \(B = \left\{ {k,\ell,m} \right\}.\) Симметричная разность двух непересекающихся множеств равно их объединению:

   \[A \,\треугольник\, B = \left( {A \cup B} \right) \backslash \left( {A \cap B} \right) = \left( {A \cup B} \right ) \обратная косая черта \varnothing = A \cup B = \left\{ {a,b,c,k,\ell,m} \right\}. \]

2. \(C = \left\{ {1,2,3,4} \right\},\) \(D = \left\{ {2,4,6,7} \right\}.\) симметричная разность множеств \(C\) и \(D\) определяется выражением 9с} = \{- 4,3,4\} .\]

См. решенные проблемы на стр. 2.

Страница 1 Страница 2

Теория множеств > Базовая теория множеств (Стэнфордская энциклопедия философии)

Множества — это хорошо определенные наборы, полностью характеризуется своими элементами. Таким образом, два множества равны тогда и только тогда, когда если они имеют точно такие же элементы. Основное отношение в множестве Теория есть теория элементальности или членства. Мы пишем \(a\in A\) в указать, что объект \(a\) является элемент или элемент множества \(A\). Мы также говорим, что \(a\) принадлежит до \(А\). Таким образом, множество \(А\) равно множеству \(В\) тогда и только тогда, когда для каждое \(а\), \(а\в А\) тогда и только тогда, когда \(а\в В\). В частности, есть только один набор без каких-либо элементов. Это множество называется, естественно, пустой набор и представлен символом \({\varничего}\).

Мы говорим, что \(A\) есть подмножество множества \(B\), записанное как \(A\subseteq B\), если каждый элемент \(A\) является элементом \(B\). Таким образом, \(A=B\), если и только если \(A\subseteq B\) и \(B\subseteq A\). Заметь \({\varnothing}\subseteq A\), для каждого набора \(A\).

Имея наборы \(A\) и \(B\), можно выполнить некоторые основные операции с из них получаются следующие множества:

• Множество \(A\cup B\), называемое объединением \(A\) и \(B\), чьи элементами являются элементы \(A\) и элементы \(B\).

• Множество \(A\cap B\), называемое пересечением точек \(A\) и \(B\), элементами которого являются элементы, общие для \(A\) и \(B\).

• Множество \(A-B\), называемое разность \(A\) и \(B\), чьи элементами являются те элементы \(A\), которые не являются членами \(В\).

Проверка того, что эти операции удовлетворяют следующим свойства:

• Ассоциативность:

• Коммутативность:

• Распределение:

• Идемпотентность:

  • \(А \чашка А=А\)

  • \(А \крышка А=А\)

• • \(A \cup {\varnothing}=A\)

  • \(A\cap {\varnothing}={\varnothing}\)

  • \(A — A={\varnothing}\)

• Если \(A\subseteq B\), то

Имея объект \(a\), мы можем сформировать множество, в котором \(a\) является единственным элемент. Это множество обозначается через \(\{ a \}\). В более общем плане, учитывая \(a,b,c,\ldots\), мы можем сформировать множество, имеющее \(a,b,c,\ldots\) в качестве элементы, которые мы обозначаем через \(\{ a,b,c, \ldots\}\). Конечно можем на самом деле запишите все элементы множества, когда их не слишком много. многие из них. В случае бесконечных множеств это явно не так. возможный.

Если \(a=b\), то \(\{ a,b\}=\{ a\}\). Кроме того, для любых \(a\) и \(b\) пара \(\{ a,b\}\) совпадает с парой \(\{ b,a\}\). Итак, если мы хотим принять во внимание порядок, в котором два элемента пары Учитывая, нам нужно найти другой способ представления пары. Таким образом, мы определить упорядоченную пару \((a,b)\) как набор \(\{ \{ a\},\{ а, б\}\}\). Легко проверить, что две упорядоченные пары \((a,b)\) и \((c,d)\) равны тогда и только тогда, когда \(a=c\) и \(b=d\). Заказ сейчас важно, ибо если \(a\ne b\), то \((a,b)\ne (b,a)\).

Декартово произведение \(A\times B\) двух множеств, \(A\) и \(B\), определяется как множество всех упорядоченных пар \((a,b)\) таких, что \(а\в А\) и \(б\в В\).

Определив упорядоченные пары, теперь можно определить упорядоченных тройки \((a,b,c)\) как \((a,(b,c))\), или вообще заказано \(n\)-кортежи \((a_1,\ldots ,a_n)\) как \((a_1, (a_2,\ldots ,a_n))\). n\).

Бинарное отношение \(R\) на множестве \(A\) называется рефлексивным , если \((a,a)\in R\) для каждого \(a\in A\). Он называется симметричным , если \((b,a)\in R\) всякий раз, когда \((a,b)\in R\). И это называется транзитивным , если \((a,c)\in R\) всякий раз, когда \((a,b)\in R\) и \((b,c)\в R\). Отношение, которое является рефлексивным, симметричным и транзитивным называется отношением эквивалентности . Отношение тождества на любое множество \(A\) является парадигматическим примером эквивалентности связь. Другим примером является отношение на множестве всех конечных множества натуральных чисел, состоящие из всех пар \((a,b)\) таких, что \(a\) и \(b\) имеют одинаковое количество элементов.

Если \(R\) является отношением эквивалентности на множестве \(A\) и \((a,b)\в R\), тогда мы говорим, что \(a\) и \(b\) \(R\)-эквивалентны . За каждый \(a\in A\), класса эквивалентности \(a\), обычно обозначаемый через \([a]_R\), это множество всех элементов \(A\), которые являются \(R\)-эквивалентными к \(а\). Множество всех классов \(R\)-эквивалентности называется фактор-множество и обозначается \(A/R\). Можно легко проверьте, что \(A/R\) является разделом \(A\), то есть ни один элемент из \(A/R\) пусто, любые два элемента из \(A/R\) не пересекаются, и каждый \(a\in A\) принадлежит (ровно) одному элементу \(A/R\), а именно классу \([а]_Р\).

Если \(R\) является бинарным отношением, то вместо него обычно пишут \(aRb\) из \((a,b)\in R\).

Бинарное отношение \(R\) на множестве \(A\) называется антисимметричным если \(a=b\), когда \(aRb\) и \(bRa\). Отношение \(R\) на множестве \(A\), т.е. рефлексивной, антисимметричной и транзитивной, называется (возвратный) частичный заказ . Если удалить из \(R\) все пары \((a,a)\), для каждого \(a\in A\), мы получаем строгих частичных заказ. Отношение \(\subseteq\) на любом множестве множеств является примером частичный заказ. Частичный порядок на заданном множестве \(A\) обычно представленный символом \(\leq\), и соответствующий строгий частичный упорядочение по \(<\). Частичный порядок \(\leq\) на множестве \(A\) с дополнительное свойство, состоящее в том, что либо \(a\leq b\), либо \(b\leq a\) для всех элементы \(a\) и \(b\) из \(A\), называется 92\) также является линейным порядком на \(В\). Если \(\leq\) — линейный порядок на множестве \(A\), то говорят, что \(a\in A\) является \(\leq\)-наименьшим элементом \(A\), если нет \(b\in A\) различных из \(a\) такое, что \(b\leq a\). Число \(0\) является наименьшим элементом \(\mathbb{N}\), но \(\mathbb{Z}\) не имеет наименьшего элемента.

Линейный порядок \(\leq\) на множестве \(A\) является хорошим порядком, если каждое непустое подмножество \(A\) имеет \(\leq\)-наименьший элемент. Эквивалентно, если нет бесконечного строго убывающего последовательность \[\ldots < a_2< a_1< a_0\] элементов \(A\). Таким образом, обычный порядок \(\mathbb{N}\) является правильным порядком. Но обычное порядок на \(\mathbb{Z}\) не такой, потому что в нем нет наименьшего элемента.

2. Функции

A (\(1\)-арные) функция на множестве \(A\) является бинарным отношением \(F\) на \(A\) такие, что для каждого \(a\in A\) существует ровно одна пара \((а,б)\в F\). Элемент \(b\) называется значением элемента \(F\) на \(a\) и обозначается через \(F(a)\). А множество \(A\) называется домен из \(F\). Обозначение \(F:A\to B\) указывает, что \(F\) есть функция с областью определения \(A\) и значениями в множестве \(B\). Для \(n\geq 2\), \(n\)-арная функция 9п\к Б\), для некоторого \(B\).

Функция \(F:A\to B\) является однозначной , если для всех элементов \(a\) и \(b\) из \(A\), если \(a\ne b\), то \(F(a)\ne F(b)\). А также есть на , если для каждого \(b\in B\) существует некоторое \(a\in A\) такое что \(F(a)=b\). Наконец, \(F\) является биективным , если оно является взаимно однозначным. и на. Таким образом, биекция \(F:A\to B\) устанавливает взаимно-однозначное соответствие между элементами \(A\) и элементами \(B\), а \(A\) является биективным с \(B\), если существует такой биекция. тождественная функция на множестве \(A\), обозначаемая \(Id:A\to A\) и состоит из всех пар \((a,a)\), где \(a\in A\) тривиально является биекцией.

Даны функции \(F:A\to B\) и \(G:B\to C\), композиция \(F\) и \(G\) , записанные \(G\circ F\), есть функция \(G\circ F:A\to C\), элементами которого являются все пары \((a,G(F(a)))\), где \(a\in A\). Если \(F\) и \(G\) биекции, то и \(G\circ F\).

3. Наборы и формулы

Формальные язык теории множеств является языком первого порядка язык, единственным нелогическим символом которого является символ бинарного отношения \(\в\).

Дана любая формула \(\varphi(x,y_1,\ldots ,y_n)\) языка теории множеств и множеств \(A,B_1,\ldots ,B_n\), можно сформировать множество всех те элементы \(A\), которые удовлетворяют формуле \(\varphi(x,B_1,\ldots ,В_п)\). Это множество обозначается \(\{ a\in A: \varphi(a,B_1,\ldots ,В_п)\}\). Ниже приведены некоторые примеры

• \({\varnothing}=\{ a\in A: a\ne a\}\)

• \(А=\{а\в А: а=а\}\)

• \(A-B=\{ a\in A: a\not \in B\}\).

• \(A\cap B=\{ a\in A: a\in B\}\).

И если \(B\) и \(C\) являются подмножествами \(A\), то

Учитывая подмножество \(C\subseteq A\times B\), проекция \(C\) (по первой координате) есть множество

\(\{ a\in A: \существует b\in B ((a,b)\in C)\}\).

Однако это не тот случай, когда при любой формуле \(\varphi(x,y_1,\ldots,y_n)\) и множеств \(B_1,\ldots,B_n\), можно сформировать множество всех тех множеств, которые удовлетворяют формуле \(\varphi(x,B_1,\ldots,B_n)\). Пусть \(\varphi(x)\) будет формулой \(х\не \в х\). Если бы \(A\) было множеством всех множеств, удовлетворяющих формулы, то \(А\в А\) тогда и только тогда, когда \(А\не \в А\). Противоречие! Это противоречие известно как Парадокс Рассела , после Бертран Рассел, открывший его в 1901 г. (см. парадокс Рассела).

4. Порядковые номера

Первый порядковый номер — \({\varnothing}\). Учитывая порядковый номер \(\alpha\), следующий больший порядковый номер, называемый (немедленно) преемник \(\alpha\), это набор \(\alpha \cup \{ \альфа\}\). Таким образом, преемником \(\alpha\) является просто набор \(\alpha\) вместе с еще одним элементом, а именно \(\alpha\) сам. конечных порядковых числа получены начиная с \({\varnothing}\) и многократно беря преемника.

В теории множеств натуральных числа определяются как конечные ординалы. Таким образом,

• \(0= {\varnothing}\)

• \(1= {\varnothing}\cup \{ {\varnothing}\}=\{ {\varnothing}\}\)

• \(2= \{ {\varnothing}\} \cup \{\{{\varnothing}\}\}=\{ {\varnothing}, \{ {\varnothing}\}\}\)

• \(3= \{ {\varnothing}, \{ {\varnothing}\}\}\cup \{ \{ {\varnothing}, \{ {\varnothing}\}\}\} =\{ {\varnothing}, \{ {\varnothing}\}, \{ {\varnothing}, \{ {\varnothing}\}\}\}\)

• \(\вдоц\)

Обратите внимание, что \(1=\{ 0\}\), \(2=\{ 0,1\}\), \(3=\{ 0,1,2\}\) и в вообще имеем \(n=\{ 0,1,2,\ldots ,n-1\}\). Итак, каждое натуральное число \(n\) — это просто набор своих предшественников.

Множество \(A\) является конечным , если существует однозначное соответствие между некоторым натуральным числом \(n\) и элементами \(A\), т. е. биекция \(F:n\to A\), и в этом случае мы говорим, что \(A\) имеет \(n\) элементов. Набор бесконечен , если он не конечен.

Множество всех конечных ординалов обозначается греческой буквой омега (\(\омега\)). Таким образом, \(\omega\) — это просто набор \(\mathbb{N}\) натуральных числа. \(\omega\) также является порядковым номером, первым бесконечным порядковый. Обратите внимание, что \(\omega\) не является преемником какого-либо порядкового номера, и поэтому он называется предельным порядковым номером . Когда у нас есть \(\omega\), мы можем продолжайте генерировать больше порядковых номеров, взяв его преемника \(\omega \cup \{ \omega \}\), затем его преемник \((\omega \cup \{\omega\}) \cup \{\omega \cup \{\omega \}\}\) и так далее. Все порядковые числительные больше чем \(0\) производятся таким образом, а именно, либо путем взятия преемник последнего произведенного порядкового номера, или, если такого последнего нет порядковый номер, взяв набор всех произведенных до сих пор ординалов, как в случай \(\omega\), который дает новый предельный порядковый номер. Обратите внимание, однако, что нельзя взять набор из все порядковые номера, для этого множество было бы новым предельным ординалом, что невозможно, так как мы уже все были.

Как и в случае с конечными ординалами, каждый бесконечный ординал — это просто набор его предшественники. Одним из следствий этого является то, что отношение \(\in\) является строгим порядком на любом множестве ординалов. Таким образом, для любых ординалов \(\alpha\) и \(\beta\) мы определяем \(\alpha <\beta\) тогда и только тогда, когда \(\альфа\в\бета\). Тогда соответствующий рефлексивный порядок равен определяется как \(\alpha \leq \beta\) тогда и только тогда, когда \(\alpha <\beta\) или \(\альфа=\бета\). Заметим теперь, что \(\alpha \subseteq \beta\), если и только если \(\alpha \leq \beta\).

5. Счетные и несчетные множества

Если \(A\) конечное множество, то существует биекция \(F:n\to A\) между натуральные числа \(n\) и \(A\). Любая такая биекция дает a , считая элементов \(A\), а именно \(F(0)\) есть первый элемент \(A\), \(F(1)\) — второй и так далее. Таким образом, все конечные множества счетны. Бесконечное множество \(A\) есть называется счетным , если существует биекция \(F:\omega \to A\) между множеством натуральных чисел и \(A\). Набор \(\mathbb{N}\) из натуральные числа (тривиально) счетны. Если \(A\) бесконечное подмножество \(\omega\), то \(A\) также счетно: ибо пусть \(F:\omega \to A\) будет такой, что \(F(n)\) является наименьшим элементом \(A\), не входящим в множество \(\{ F(m)\in A: m

Каждое бесконечное подмножество счетного множества также счетно: для предположим, что \(F:\omega \to A\) является биекцией, а \(B\subseteq A\) является бесконечный. Тогда множество \(\{ n\in \omega: F(n)\in B\}\) является бесконечным подмножество \(\omega\), следовательно, счетно, и поэтому существует биекция \(G:\omega \to \{n\in \omega : F(n)\in B\}\). Тогда состав функция \(F\circ G:\omega \to B\) является биекцией.

Объединение счетного множества и конечного множества также исчисляемый. Для заданных множеств \(A\) и \(B\), которые без потери общности, мы можем предположить, что они не пересекаются, и при заданных биекциях \(F:\omega \to A\) и \(G:n\to B\), для некоторого \(n<\omega\) пусть \(H:\omega \to A\cup B\) — биекция, заданная формулой: \(H(m)=G(m)\), для каждого \(m

Более того, объединение двух счетных множеств тоже счетно: поскольку мы уже показали, что объединение счетного множества и конечного множество также счетно, достаточно убедиться, что объединение двух непересекающиеся счетные множества также счетны. Итак, предположим, что \(A\) и \(B\) равны счетные множества и \(F:\omega \to A\) и \(G:\omega \to B\) биекций, то функция \(H:\omega \to A\cup B\), состоящая из всех пар \((2n,F(n))\), плюс все пары \((2n+1, G(n))\) — биекция.