6.6: Уперечення
- Page ID
- 65229
Кращі функції є як один до одного, так і на. Вони називаються «двоїння».
Функція - це біекція, якщо вона є як один до одного, так і на.
Розглянемо гіпотетичну країну\(\text {Married}\), в якій
- кожен одружений (тільки на одну людину — немає полігамії!) , і
- кожен шлюб між чоловіком і жінкою (одностатевих шлюбів немає).
Нехай
- \(\text {Men}\)бути набором чоловіків на дачі, і
- \(\text {Women}\)бути безліччю жінок в країні.
Тоді\(\text {wife}: \text { Men } \rightarrow \text { Women}\) йде біекція:
- Двоє різних чоловіків не можуть мати однакову дружину, тому ми знаємо, що\(\text {wife}\) це один до одного.
- Кожна жінка є дружиною якогось чоловіка (тому що всі одружені),\(\text {wife}\) так само і на.
Аналогічно функція\(\text {husband}: \text { Women } \rightarrow \text { Men}\) - це і біекція.
У країні,\(\text {Married}\) описаній вище, зрозуміло, що кількість чоловіків точно дорівнює числу жінок. (Якби чоловіків було більше, ніж жінок, то не у кожного чоловіка могла бути дружина; якби жінок було більше, ніж чоловіків, то не кожна жінка могла б мати чоловіка.) Це приклад наступного важливого принципу, про який піде мова в наступному розділі, присвяченому «кардинальності»:
Якщо є біекція від\(A\) до\(B\), то
два множини\(A\) і\(B\) повинні мати рівно однакову кількість елементів.
Пошук біекції є найпоширенішим способом показати, що дві множини мають однакову кількість елементів.
- Ви можете згадати, що функцію один до одного можна назвати «ін'єкцією», а функцію onto можна назвати «surjection». Термін «біекція» походить від того, що мають обидві ці дві властивості.
- Деякі підручники використовують термін «листування один до одного» для біекції, але ми уникнемо цієї термінології, оскільки її занадто легко сплутати з «функцією один до одного», що не означає одне і те ж.
Показуючи, що функція є біекцією, вимагає двох речей: показати, що функція є один до одного, і показувати, що функція знаходиться на. Отже, доказ того, що функція є біекцією, буде (зазвичай) мати дві частини:
- Показати, що функція один до одного.
- Показати, що функція включена.
Дві частини можуть прийти в будь-якому порядку: цілком прийнятно спочатку довести, що функція знаходиться на, а потім довести, що це один до одного.
Визначте\(f: \mathbb{R} \rightarrow \mathbb{R}\) по\(f(x) = 5x − 7\). Потім\(f\) йде біекція.
Рішення
Досить показати, що\(f\) є як один до одного, так і на.
(один-на-один) З огляду\(x_{1}, x_{2} \in \mathbb{R}\) на\(f\left(x_{1}\right)=f\left(x_{2}\right)\), що, ми маємо\[5 x_{1}+7=5 x_{2}+7 ,\]
\[5 x_{1}=5 x_{2} ,\]
так\[x_{1}=x_{2} .\]
Тому\(f\) один до одного.
(на) Дано\(y \in \mathbb{R}\), нехай\(x=(y+7) / 5\). Тоді\[f(x)=5 x-7=5\left(\frac{y+7}{5}\right)-7=(y+7)-7=y .\]
Тому\(f\) йде на.
Оскільки\(f\) це як один до одного, так і на, це біекція.
Кожна формула визначає функцію від\(\mathbb{R}\) до\(\mathbb{R}\). Показати, що функція є bijection.
- \(a(x) = 5x + 2\)
- \(b(x) = 2x − 5\)
- \(c(x) = 12x − 15\)
- \(d(x) = −15x − 12\)
- \(e(x) = x^{3}\)
- \(f(x)=\sqrt[3]{x-4}\)
Для будь-якого набору\(A\) визначте карту\(I_{A}: A \rightarrow A\) ідентичності\(I_{A}(a) = a\) для кожного\(a \in A\).
Нехай\(A\) буде набір. Показати, що карта ідентичності\(I_{A}\) є біекцією від\(A\) до\(A\).
Кожна формула визначає функцію від\(\mathbb{R}\) до\(\mathbb{R}\). Які з функцій є двосторонніми? Покажіть, що ваші відповіді правильні.
- \(a(x) = 7.\)
- \(b(x) = 4x − 7.\)
- \(c(x) = x^{2}.\)
- \(d(r) = 3r + 2.\)
- \(e(s) = 3|s| + 2.\)
- \(f(t)=\sqrt{t^{2}+1}\)
- \(g(u)=\sqrt[3]{u}-5 .\)
Визначте\(f : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) по\(f(m, n) = m^{2} + n\).
- Покажіть, що\(f\) знаходиться на.
- Покажіть, що\(f\) це не один на один.
Рішення
- Дано\(k \in \mathbb{N}\), нехай\(x = (0, k) \in \mathbb{N} \times \mathbb{N}\). Тоді\[f(x)=f(0, k)=0^{2}+k=k.\]
Оскільки\(k\) є довільним елементом\(\mathbb{N}\), ми робимо висновок, що\(f\) є на. - Нехай\(x_{1} = (1, 0)\) і\(x_{2} = (0, 1)\). Тоді\(x_{1} \neq x_{2}\), але\[f\left(x_{1}\right)=f(1,0)=1^{2}+0=1=0^{2}+1=f(0,1)=f\left(x_{2}\right) ,\]
так\(f\) не один-на-один.
Визначте\(g: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z} \times \mathbb{Z}\) по\(g(m, n) = (m + n, m − n)\).
- Покажіть, що\(g\) це не на. [Підказка:\((m + n) + (m − n) = 2m\). Чи може це бути дивним?]
- Покажіть,\(g\) що один до одного.
Припустимо\(f: A \rightarrow B\). Шоу\(f\) - це bijection iff, для кожного\(b \in B\), є своє унікальне\(a \in A\), таке, що\(f(a) = b\). Іншими словами,\(f\) це біекція тоді і тільки тоді, коли\[\forall b \in B, \exists ! a \in A,(f(a)=b) .\]
- Доказ
-
(\(\Rightarrow\))\(b\) Дозволяти бути довільним елементом\(B\). Оскільки\(f\) це біекція, вона знаходиться на, так існує\(a \in A\), така, що\(f(a) = b\). Залишається лише показати, що\(a\) є унікальним. З цією метою нехай\(a^{\prime} \in A\), такий, що\(f(a^{\prime}) = b\). Тоді\[f\left(a^{\prime}\right)=b=f(a) .\]
Оскільки\(f\) це біекція, це один до одного, тому ми робимо висновок, що\(a^{\prime} = a\). Таким чином,\(a\) є унікальним.(\(\Leftarrow\)) Досить показати, що\(f\) є як на, так і один до одного.
(На) Враховуючи\(b \in B\), ми припускаємо, що існує (унікальний) елемент\(a\)\(A\), такий, що\(f(a) = b\). Тому\(f\) є на.(один-до-одному) дано\(a_{1}, a_{2} \in A\), такий що\(f(a_{1}) = f(a_{2})\), нехай\(b = f(a_{1})\). Потім\(f(a_{1}) = b\) і\(f(a_{2}) = b\). З унікальності\(a\) елемента\(A\), такого, робимо висновок\(f(a) = b\), що\(a_{1} = a_{2}\). Так як\(a_{1}\) і\(a_{2}\) є довільними елементами\(A\), такі\(f(a_{1}) = f(a_{2})\), що, це означає, що\(f\) один до одного.
Офіційно не\(\times\) є асоціативним, тому що\[(A \times B) \times C=\{((a, b), c) \mid a \in A, b \in B, c \in C\}\]
і\[A \times(B \times C)=\{(a,(b, c)) \mid a \in A, b \in B, c \in C\} .\]
є (зазвичай) не однаковими множинами: елемент\((A \times B) \times C\) повинен мати впорядковану пару\((a, b)\) як свою першу координату, тоді як елемент\(A \times(B \times C)\) може мати будь-який елемент \(A\)як його перша координата.
Припустимо\(A\),\(B\), і\(C\) є множинами. Визначте\[f:(A \times B) \times C \rightarrow A \times(B \times C) \quad \text { by } \quad f((a, b), c)=(a,(b, c)) .\]
Покажіть, що\(f\) це біекція.
Можна визначити декартовий добуток більше двох множин. Наприклад,\[A \times B \times C=\{(a, b, c) \mid a \in A, b \in B, c \in C\} .\]
Хоча\(A \times B \times C\) це не те ж саме, що\((A \times B) \times C\) або\(A \times(B \times C)\), різницю між ними часто можна ігнорувати на практиці.