6.5: Теорія множин

Template:MathJaxZach

Практично вся математика може розвиватися в теорії множин. Розвиток математики в цій теорії передбачає ряд речей. По-перше, він вимагає набору аксіом для відношення\(\in\). Розроблено низку різних аксіомних систем, іноді з суперечливими властивостями\(\in\). Виділяється система аксіом\(\Log{ZFC}\), відома як теорія множин Цермело-Френкеля з аксіомою вибору: вона на сьогоднішній день є найбільш широко використовуваною та вивченою, оскільки виявляється, що її аксіом достатньо, щоб довести майже все те, що математики очікують довести. Але перш ніж це можна встановити, спочатку необхідно чітко пояснити, як ми можемо навіть висловити все те, що хотіли б висловити математики. Для початку мова не містить постійних символів або символів функцій, тому здається на перший погляд незрозумілим, що ми можемо говорити про конкретні множини (наприклад,\(\emptyset\) або\(\Nat\)), може говорити про операції над множинами (наприклад,\(X \cup Y\) і\(\Pow{X}\) ), не кажучи вже про інші конструкції, які включають речі, відмінні від множин, таких як відносини та функції.

Почнемо з того, що «є елементом» не єдине відношення, яке нас цікавить: «є підмножиною» здається майже таким же важливим. Але ми можемо визначити «є підмножиною» з точки зору «є елементом». Для цього нам потрібно знайти\(A(x, y)\) формулу мовою теорії множин, яка задовольняється парою множин\(\tuple{X, Y}\) iff\(X \subseteq Y\). Але\(X\) є підмножиною\(Y\) на всякий випадок, всі\(X\) елементи також є елементами\(Y\). Таким чином, ми можемо визначити\(\subseteq\) за формулою\[\lforall{z}{(z \in x \lif z \in y)}\nonumber\] Тепер, всякий раз, коли ми хочемо використовувати відношення\(\subseteq\) у формулі, ми могли б замість цього використовувати цю формулу (з\(x\) і\(y\) відповідним чином замінені, і пов'язана змінна \(z\)перейменований при необхідності). Наприклад, розширеність множин означає, що якщо будь-які\(x\) множини і\(y\) містяться один в одному, то\(x\) і\(y\) повинні бути однаковими множинами. Це може бути виражено\(\lforall{x}{\lforall{y}{((x \subseteq y \land y \subseteq x) \lif x = y)}}\), або, якщо замінити\(\subseteq\) вищевказаним визначенням, на\[\lforall{x}{\lforall{y}{((\lforall{z}{(z \in x \lif z \in y)} \land \lforall{z}{(z \in y \lif z \in x)}) \lif x = y)}}.\nonumber\] Це насправді одна з аксіом\(\Log{ZFC}\), «аксіома розширення».

Немає постійного символу для\(\emptyset\), але ми можемо висловити «\(x\)порожній» шляхом\(\lnot \lexists{y}{y \in x}\). Тоді «\(\emptyset\)існує» стає реченням\(\lexists{x}{\lnot \lexists{y}{y \in x}}\). Це ще одна аксіома\(\Log{ZFC}\). (Зверніть увагу, що аксіома розширеності передбачає, що існує лише один порожній набір.) Всякий раз, коли ми хочемо поговорити про\(\emptyset\) мовою теорії множин, ми б писали це як «є набір, який порожній і...» Як приклад, щоб висловити той факт, що\(\emptyset\) є підмножиною кожного набору, ми могли б написати,\[\lexists{x}{(\lnot\lexists{y}{y \in x} \land \lforall{z}{x \subseteq z})}\nonumber\] де, звичайно, \(x \subseteq z\)в свою чергу доведеться замінити його визначенням.

Щоб говорити про операції над множинами, такі має\(X \cup Y\) і\(\Pow{X}\), доводиться використовувати подібний трюк. У мові теорії множин немає символів функцій, але ми можемо виразити функціональні відносини\(X \cup Y = Z\) і\(\Pow{X} = Y\),\[\begin{aligned} & \lforall{u}{((u \in x \lor u \in y) \liff u \in z)}\\ & \lforall{u}{(u \subseteq x \liff u \in y )}\end{aligned}\nonumber\] оскільки елементи\(X \cup Y\) є саме множинами, які є або елементами\(X\) або елементи\(Y\), а елементи\(\Pow{X}\) є саме підмножинами\(X\). Однак це не дозволяє нам використовувати\(x \cup y\) або\(\Pow{x}\) як ніби вони були термінами: ми можемо використовувати лише цілі формули, які визначають відносини\(X \cup Y = Z\) і\(\Pow{X} = Y\). Насправді ми не знаємо, що ці відносини коли-небудь задовольняються, тобто ми не знаємо, що союзи і набори влади існують завжди. Наприклад, речення\(\lforall{x}{\lexists{y}{\Pow{x} = y}}\) є ще однією аксіомою\(\Log{ZFC}\) (аксіома набору влади).

А як щодо розмов про впорядковані пари або функції? Тут ми повинні пояснити, як ми можемо думати про впорядковані пари та функції як спеціальні види множин. Один із способів визначення впорядкованої пари\(\tuple{x, y}\) - це набір\(\{\{x\}, \{x, y\}\}\). Але, як і раніше, ми не можемо ввести символ функції, який називає цей набір; ми можемо лише визначити відношення\(\tuple{x, y} = z\), тобто\(\{\{x\}, \{x, y\}\} = z\):\[\lforall{u}{(u \in z \liff (\lforall{v}{(v \in u \liff v = x)} \lor \lforall{v}{(v \in u \liff (v = x \lor v = y))}))}\nonumber\] Це говорить про те, що елементи\(u\)\(z\) є саме тими множинами, які або мають \(x\)як єдиний його елемент або мають\(x\) і\(y\) як його єдині елементи (іншими словами, ті набори, які або ідентичні\(\{x\}\) або ідентичні\(\{x, y\}\)). Як тільки ми отримаємо це, ми можемо сказати далі речі, наприклад, що\(X \times Y = Z\):\[\lforall{z}{(z \in Z \liff \lexists{x}{\lexists{y}{(x \in X \land y \in Y \land \tuple{x, y} = z)}})}\nonumber\]

Функція\(f \colon X \to Y\) може розглядатися як відношення\(f(x) = y\), тобто як набір пар\(\Setabs{\tuple{x,y}}{f(x) = y}\). Потім ми можемо сказати, що множина\(f\) - це функція від\(X\) до\(Y\) якщо (а) це відношення\(\subseteq X \times Y\), (б) це загальна, тобто для всіх\(x \in X\) є деякі\(y \in Y\) такі, що\(\tuple{x, y} \in f\) і (c ) вона функціональна, тобто всякий раз\(\tuple{x, y}, \tuple{x, y'} \in f\),\(y = y'\) (тому що значення функцій повинні бути унікальними). Так що «\(f\)є функція від\(X\) до\(Y\)» може бути записана так:\[\begin{aligned} \lforall{u}{(u \in f \lif {}} & \lexists{x}{\lexists{y}{(x \in X \land y \in Y \land \tuple{x, y} = u)}}) \land {}\\ \lforall{x}{(x \in X \lif {}} & (\lexists{y}{(y \in Y \land \mathrm{maps}(f, x, y))} \land {}\\ & (\lforall{y}{\lforall{y'}{((\mathrm{maps}(f, x, y) \land \mathrm{maps}(f, x, y')) \lif y = y')}}))\end{aligned}\nonumber\] де\(\mathrm{maps}(f, x, y)\) скорочується\(\lexists{v}{(v \in f \land \tuple{x, y} = v)}\) (ця формула виражає «\(f(x) = y\)»).

Зараз також не важко висловити, що\(f\colon X \to Y\) є ін'єкційним, наприклад: Функція\[\begin{gathered} f \colon X \to Y \land \lforall{x}{\lforall{x'}{((x \in X \land x' \in X \land {}}} \\ \lexists{y}{(\mathrm{maps}(f, x, y) \land \mathrm{maps}(f, x', y))}) \lif x = x')\end{gathered}\nonumber\]\(f\colon X \to Y\) є ін'єкційною iff, коли\(f\)\(x, x' \in X\) відображає одну\(y\),\(x = x'\). Якщо ми скорочуємо цю формулу як\(\mathrm{inj}(f, X, Y)\), ми вже в змозі констатувати мовою теорії множин щось таке нетривіальне, як теорема Кантора: немає ін'єкційної функції від\(\Pow{X}\) до\(X\):\[\lforall{X}{\lforall{Y}{(\Pow{X} = Y \lif \lnot\lexists{f}{\mathrm{inj}(f, Y, X)})}}\nonumber\]

Можна подумати, що теорія множин вимагає іншої аксіоми, яка гарантує існування множини для кожної визначальної властивості. Якщо\(A(x)\) є формулою теорії множин зі змінною\(x\) вільною, ми можемо розглянути речення.\[\lexists{y}{\lforall{x}{(x \in y \liff A(x))}}.\nonumber\] Це речення стверджує, що існує безліч, елементи\(y\) якого всі і тільки ті\(x\), які задовольняють \(A(x)\). Ця схема називається «принципом розуміння». Це виглядає дуже корисно; на жаль, це непослідовно. Візьміть\(A(x) \ident \lnot x \in x\), тоді принцип розуміння стверджує,\[\lexists{y}{\lforall{x}{(x \in y \liff x \notin x)}},\nonumber\] тобто він стверджує існування сукупності всіх множин, які не є елементами самих себе. Такого набору не може існувати - це Парадокс Рассела. \(\Log{ZFC}\), насправді, містить обмежену і послідовну версію цього принципу, принцип поділу:\[\lforall{z}{\lexists{y}{\lforall{x}{(x \in y \liff (x \in z \land A(x))}}}.\nonumber\]

Проблема\(\PageIndex{1}\)

Покажіть, що принцип розуміння непослідовний, даючи похідну, яка показує\[\lexists{y}{\lforall{x}{(x \in y \liff x \notin x)}} \Proves \lfalse.\nonumber\] Це може допомогти спочатку показати\((A \lif \lnot A) \land (\lnot A \lif A) \Proves \lfalse\).