4.8: Рівноправність

Template:MathJaxZach

Ми маємо інтуїтивне поняття «розмір» множин, яке чудово працює для скінченних множин. Але як щодо нескінченних множин? Якщо ми хочемо придумати формальний спосіб порівняння розмірів двох наборів будь-якого розміру, непогано почати з визначення того, коли набори мають однаковий розмір. Ось Фреге:

Якщо офіціант хоче бути впевненим, що поклав рівно стільки ножів, скільки тарілок на столі, йому не потрібно вважати жодного з них, якщо він просто кладе ніж праворуч від кожної тарілки, щоб кожен ніж на столі лежав праворуч від якоїсь тарілки. Тарілки та ножі, таким чином, унікально співвідносяться один з одним, і справді через ту саму просторову залежність. (Фреге, 1884, §70)

Проникливість цього уривка може бути виведена через формальне визначення:

Визначення\(\PageIndex{1}\)

\(A\)рівноцінний з\(B\), написаний\(\cardeq{A}{B}\), якщо є біекція\(f \colon A \to B\).

Пропозиція\(\PageIndex{1}\)

Рівноцінність - це відношення еквівалентності.

Доказ. Ми повинні показати, що рівноправність є рефлексивною, симетричною та перехідною. Нехай\(A, B\), і\(C\) бути набори.

Рефлексивність. Карта ідентичності\(\Id{A} \colon A \to A\), де\(\Id{A} (x) = x\) для всіх\(x \in A\), є біекцією. Отже\(\cardeq{A}{A}\).

Симетрія. Припустимо\(\cardeq{A}{B}\), тобто є біекція\(f\colon A \to B\). Оскільки\(f\) є двооб'єктивним, то його зворотний\(f^{-1}\) існує, а також є двооб'єктивним. Значить,\(f^{-1}\colon B \to A\) є біекція, так\(\cardeq{B}{A}\).

Транзитивність. Припустимо\(\cardeq{B}{C}\), що\(\cardeq{A}{B}\) і, т\(g\colon B \to C\).\(f\colon A \to B\) Е. Тоді\(\comp{f}{g}\colon A \to C\) композиція двооб'єктивна, так що\(\cardeq{A}{C}\). ◻

Пропозиція\(\PageIndex{2}\)

Якщо\(\cardeq{A}{B}\), то\(A\) підраховується, якщо і тільки якщо\(B\) є.

Доказ. Припустимо\(\cardeq{A}{B}\), так що є деяке біекція\(f \colon A \to B\), і припустимо, що\(A\) підраховується. Тоді або\(A = \emptyset\) or there is a surjective function \(g\colon \PosInt \to A\). If \(A = \emptyset\), then \(B = \emptyset\) also (otherwise there would be an element \(y \in B\) but no \(x \in A\) with \(g(x) = y\)). If, on the other hand, \(g\colon \PosInt \to A\) is surjective, then \(\comp{f}{g} \colon \PosInt \to B\) is surjective. To see this, let \(y \in B\). Since \(g\) is surjective, there is an \(x \in A\) such that \(g(x) = y\). Since \(f\) is surjective, there is an \(n \in \PosInt\) such that \(f(n) = x\). Hence, \[(\comp{f}{g})(n) = g(f(n)) = g(x) = y\nonumber\] and thus \(\comp{f}{g}\) is surjective. We have that \(\comp{f}{g}\) is an enumeration of \(B\), and so \(B\) is  підраховується.

Якщо\(B\) підраховується, ми отримуємо, що\(A\) підраховується, повторюючи аргумент з bijection\(f^{-1}\colon B \to A\) замість\(f\). ◻

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

Покажіть, що якщо\(\cardeq{A}{C}\) і\(\cardeq{B}{D}\), і\(A \cap B = C \cap D = \emptyset\), то\(\cardeq{A \cup B}{C \cup D}\).

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

Покажіть, що якщо\(A\) нескінченно і підраховується, то\(\cardeq{A}{\Nat}\).