6.4: Функції «один-на-один»

Починаємо цей розділ з прикладу.

Приклад\(6.4.1\).

1. Припустимо, інспектор Thinkright знає два факти:
   1. Аліса - дружина злодія, і
   2. Аліса - дружина Боба.
      Тоді інспектор може заарештувати Боба за крадіжку, адже жінка не може бути дружиною більше одного чоловіка.
2. З іншого боку, припустимо, інспектор знає:
   1. Аліса - мати підвальника, і
   2. Аліса - мати Чарлі.
      Тоді інспектор не знає достатньо, щоб бути впевненим, хто такий підробник, тому що це може бути інша дитина Аліси, замість того, щоб бути Чарлі.

Цей приклад ілюструє принципову різницю між\(\text{wife}\) функцією та\(\text{mother}\) функцією: дві різні люди можуть мати однакову матір, але лише одна людина може мати будь-яку конкретну людину як їхню дружину. (Наприклад, якщо у Бада і Чарлі однакова дружина, то «Буд» повинен бути прізвиськом для Чарлі.) У математичному плані це важлива властивість функції дружини виражається тим, що\(\text{wife}\) функція «один-на-один».

Поняття формалізується в наступному визначенні:

Визначення\(6.4.2\).

Припустимо\(f: A \rightarrow B\). Ми говоримо, що\(f\) це один-на-один, якщо, для всіх\(a_{1}, a_{2} \in A\), такий, що\(f(a_{1}) = f(a_{2})\), у нас є\(a_{1} = a_{2}\).

Вправа\(6.4.3\).

Припустимо\(f: A \rightarrow B\) і\(g: X \rightarrow Y\). Перекласти кожне твердження в логіку FirstOrder. 1) f - один до одного. 2) g - один до одного. 3) f не один до одного. 4) g не один до одного. (Спростіть свої відповіді в (3) і (4) так, щоб ¬ застосовувався лише до присудків.)

Зауваження\(6.4.4\).

Якщо у вас є діаграма зі стрілками функції, то легко визначити, чи є функція один-на-один. Наприклад:

1. \(f\)Функція Figure не\(6A(a)\) є один-на-один. Це відбувається тому, що стрілка від\(b\) і стрілка від\(d\) йдуть в одне і те ж місце, так\(f(b) = f(d)\). Взагалі, якщо стрілки з двох різних елементів домену йдуть на один і той же елемент діапазону, то функція не один-на-один.
2. \(g\)Функція Figure\(6A(b)\) - один до одного. Це пояснюється тим, що стрілки з двох різних елементів домену ніколи не переходять на один і той же елемент діапазону. Коротше кажучи, є тільки один елемент домену, який переходить до якогось одного елементу діапазону. (Це і є причиною термінології «один-на-один». Функція «два до одного», якщо є два елементи відображення домену до кожного елемента діапазону, як це справедливо для функції на\(h\) малюнку\(6A(c)\), але нам ця термінологія не потрібна.)
3. Попередження. Хоча діаграма стрілок функції один до одного ніколи не має більше однієї стрілки, що вказує на один і той же елемент кодомена, це не означає, що кожен елемент кодомена має рівно одну стрілку в нього. Наприклад, функція\(g\) Figure\(6A(b)\) є один-на-один (тому що в будь-якій точці ніколи не буває більше однієї стрілки), але в кодомені є точка, яка не має до неї ніяких стрілок.

Малюнок\(6A\). Стрілка діаграми трьох функцій\(f\)\(g\), і\(h\).

Приклад\(6.4.5\).

Не даючи офіційних доказів, визначимося, які з перерахованих нижче функцій є один-на-один.

1. \(f: \mathbb{R} \rightarrow \mathbb{R}\), Визначені\(f(x) = x + 1\).
   Це один до одного. Для будь-яких дійсних чисел\(x\) і\(y\),\(f(x) = f(y)\) означає, що\(x + 1 = y + 1\). Віднімаючи 1 з обох сторін рівняння, робимо висновок, що\(x = y\) всякий раз\(f(x) = f(y)\).
2. \(g: \mathbb{R} \rightarrow \mathbb{R}\), Визначені\(g(x) = |x|\). Це не один на один. Ми демонструємо це, знаходячи два різних дійсних числа, зображення яких однакове:\[g(1)=|1|=1=|-1|=g(-1) ,\]
   але\(1 \neq-1\). Це показує, що\(g\) це не один до одного.
3. \(f:\{1,2,3\} \rightarrow\{\mathrm{a}, \mathrm{b}, \mathrm{c}\}\)визначаються\(f=\{(1, b),(2, a),(3, a)\}\).
   Це не один на один. Ми демонструємо це, знаходячи два різних значення, на зображенні\(\{1,2,3\}\) яких однакове: f (2) = a = f (3), але 2 = 3. Це показує, що f не один до одного. 4) h: N → N, визначається h (x) = |x|. Це один до одного. Оскільки всі натуральні числа невід'ємні, ми маємо |x| = x для кожного натурального числа x, тому якщо h (x) = h (y), то x = |x| = h (x) = h (y) = |y| = y.

Зауваження\(6.4.6\).

Ці приклади демонструють загальну закономірність того, як довести, що функція є (або не є) один-на-один:

• Щоб довести, що функція\(f: A \rightarrow B\) один до одного, ми повинні продемонструвати, що для кожного\(a_{1}, a_{2} \in A\), якщо\(f(a_{1}) = f(a_{2})\), то\(a_{1} = a_{2}\).
• Щоб довести,\(f: A \rightarrow B\) що функція не один до одного, нам потрібно знайти лише одну пару значень\(a_{1}, a_{2} \in A\), для якої\(f(a_{1}) = f(a_{2})\), але\(a_{1} \neq a_{2}\).

Вправа\(6.4.7\).

Поясніть, чому ваші відповіді правильні (але вам не потрібно давати офіційні докази).

1. Кожна формула визначає функцію від\(\mathbb{R}\) до\(\mathbb{R}\). Які з функцій є один-на-один?
   1. \(f(x) = 1\).
   2. \(g(x) = x\).
   3. \(h(x) = x^{2}\).
   4. \(i(x) = 3x + 2\).
   5. \(j(x) = 1/ ( |x| + 1)\).
2. Кожен з наступних наборів впорядкованих пар є функцією from\(\{1,2,3,4\}\) to\(\{a, b, c, d, e\}\). Які бувають один-на-один?
   1. \(f = \{(1, a),(2, b),(3, d),(4, e)\}\)
   2. \(g = \{(1, c),(2, d),(3, d),(4, e)\}\)
   3. \(h = \{(1, e),(2, d),(3, c),(4, b)\}\)
   4. \(i = \{(1, e),(2, e),(3, e),(4, e)\}\)
   5. \(j = \{(1, a),(2, c),(3, e),(4, c)\}\)
   6. \(k = \{(1, a),(2, c),(3, e),(4, d)\}\)

Ось приклад формального доказу того, що функція є один до одного.

Приклад\(6.4.8\).

Дозвольте\(f: \mathbb{R} \rightarrow \mathbb{R}\) визначитися з\(f(x) = 2x + 1\). Тоді\(f\) один до одного.

Подряпини. За визначенням, ми хочемо показати\(\forall x_{1}, x_{2} \in \mathbb{R},\left(f\left(x_{1}\right)=f\left(x_{2}\right) \Rightarrow x_{1}=x_{2}\right)\). Таким чином, доказ буде використовувати\(\forall\) -введення: першими словами в доказі буде «дано\(x_{1}, x_{2} \in \mathbb{R}\)» (або іншими словами на цей рахунок). Тоді, тому що ми хочемо показати\(f(x_{1}) = f(x_{2}) \Rightarrow x_{1} = x_{2}\), ми будемо вважати\(f(x_{1}) = f(x_{2})\), і доказ буде повним, як тільки ми зможемо довести\(x_{1} = x_{2}\).

За визначенням\(f\), припущення\(f(x_{1}) = f(x_{2})\) означає, що\[2 x_{1}+1=2 x_{2}+1 .\]
Віднімаючи 1 з обох сторін, ми бачимо, що\[2 x_{1}=2 x_{2}.\]
Розділивши обидві сторони на 2, ми робимо висновок\(x_{1} = x_{2}\), що за бажанням.

Оскільки читачі цього підручника, як очікується, добре володіють логікою та алгеброю середньої школи, наше офіційне доказ може опустити коментарі, непотрібні для такого добре освіченого читача. Наприклад, можна очікувати, що читач зможе легко перевірити, що рівняння\(2x + 1 = 2x2 + 1\) можна спростити до рівняння\(2x_{1} = 2x_{2}\), не сказавши, що вони повинні відняти 1 з обох сторін.

Рішення

Враховуючи\(x_{1}, x_{2} \in \mathbb{R}\), таке\(f(x_{1}) = f(x_{2})\), що, у нас\[2 x_{1}+1=2 x_{2}+1 ,\]
\[2 x_{1}=2 x_{2} ,\]
так і є\(x_{1} = x_{2}\).

Дуже схожий аргумент застосовується і до інших лінійних функцій.

Приклад\(6.4.9\).

Визначте\(p: \mathbb{R} \rightarrow \mathbb{R}\) по\(p(z) = 6z − 100\). Покажіть,\(p\) що один до одного.

Рішення

ДОКАЗ.

Враховуючи\(z_{1}, z_{2} \in \mathbb{R}\), таке\(p(z_{1}) = p(z_{2})\), що, у нас\[6 z_{1}-100=6 z_{2}-100\]
\[6 z_{1}=6 z_{2} ,\]
так і є\(z_{1} = z_{2}\).

Вправа\(6.4.10\).

Доведіть, що кожна функція один до одного.

1. \(f: \mathbb{R} \rightarrow \mathbb{R}\)визначаються\(f(x) = 3x + 5\).
2. \(f: \mathbb{R} \rightarrow \mathbb{R}\)визначаються\(f(x) = 7x − 2\).
3. \(g: \mathbb{R} \rightarrow \mathbb{R}\)визначаються\(g(t) = 4t + 9\).
4. \(h: \mathbb{R} \rightarrow \mathbb{R}\)визначаються\(h(s) = 7 − 8s\).
5. \(i: \mathbb{R} \rightarrow \mathbb{R}\)визначаються\(i(r) = (5r − 2)/7\).
6. \(j : \mathbb{Z} \rightarrow \mathbb{Z}\)визначаються\(j(n) = 2n + 11\).

Той факт, що\(\text{wife}\) функція один-на-один, можна переоцінити як той факт, що дві різні люди не можуть мати однакову дружину. Загалом, функція є один до одного, якщо два різних елементи області завжди відображаються на два різних елементи діапазону:

Функція\(f: A \rightarrow B\) один до одного, якщо і тільки якщо
\(\forall a_{1}, a_{2} \in A,\left(a_{1} \neq a_{2} \Rightarrow f\left(a_{1}\right) \neq f\left(a_{2}\right)\right).\)

(Позначення «\(\forall a_{1}, a_{2} \in A\)» скорочено від «\(\forall a_{1} \in A, \forall a_{2} \in A\).»)

Ми повинні обґрунтувати твердження в цій коробці доказом. \(\Rightarrow\)Імплікація доведена в наступній теоремі; інший напрямок - вправа.

Теорема\(6.4.12\).

Якщо функція\(f: A \rightarrow B\) один-на-один, то\[\forall a_{1}, a_{2} \in A,\left(a_{1} \neq a_{2} \Rightarrow f\left(a_{1}\right) \neq f\left(a_{2}\right)\right).\]

Доказ

\(f: A \rightarrow B\)Дозволяти бути один-на-один. З огляду на\(a_{1}, a_{2} \in A\), ми знаємо, з визначення один-на-один, що\[f\left(a_{1}\right)=f\left(a_{2}\right) \Rightarrow a_{1}=a_{2} .\]

Таким чином, контрапозитив цього підтексту також вірний. Тобто, a1 = a2 ⇒ f (a1) = f (a2).

Вправа\(6.4.13\).

1. Доведіть зворотне теореми\(6.4.12\). Точніше\(f: A \rightarrow B\), припустимо, і показати, що якщо\[\forall a_{1}, a_{2} \in A,\left(a_{1} \neq a_{2} \Rightarrow f\left(a_{1}\right) \neq f\left(a_{2}\right)\right) ,\]
   тоді f один до одного.
2. Припустимо:
   1. \(f: A \rightarrow B\),
   2. \(f\)один до одного,
   3. \(a_{1}, a_{2} \in A\),
   4. \(g: B \rightarrow C\),
   5. \(g\)один до одного,
   6. \(b_{1}, b_{2} \in B\),
   7. \(f(a_{1}) = b_{1}\),
   8. \(f(a_{2}) = b_{2}\), і
   9. \(g(b_{1}) = g(b_{2})\).

Показати\(a_{1} = a_{2}\). [Підказка: Спочатку використовуйте той факт,\(g\) що один до одного, потім той факт,\(f\) що один до одного.]

Зауваження\(6.4.14\).

(альтернативна термінологія). Багато математиків використовують слово «ін'єкційний», а не «один до одного». (Це походить від французької.) Також функцію, яка є один-на-один, можна назвати ін'єкцією.