Ми маємоf: {1,2,3} -> {1,2} і g: {1,2,3} -> {1,2,3,4}. Як існує багато ін'єкційних функцій f і g?

Відповідь:

# f # не може бути ін'єкційним.

# g # може бути ін'єкційним в #24# способи.

Пояснення:

Функція ін'єкційна, якщо два входи не забезпечують однаковий вихід. Іншими словами, щось подібне

#f (x) = f (y), quad x t

не може статися.

Це означає, що у випадку кінцевого домену і кодомена функція може бути ін'єкційною тоді і тільки тоді, коли область менша, ніж кодомен (або, щонайбільше, однакова) в термінах потужності.

Ось чому # f # ніколи не може бути ін'єкційним. Насправді, можна виправити #f (1) # як тобі до вподоби. Сказати #f (1) = 1 #, наприклад. При виборі #f (2) #, ми не можемо ще раз сказати #f (2) = 1 #або # f # не буде ін'єкційним. Але коли справа доходить до #f (3) # у нас немає вибору, якщо ми скажемо #f (3) = 1 # ми маємо #f (1) = f (3) #, і якщо скажемо #f (3) = 2 # ми маємо #f (2) = f (3) #.

Іншими словами, ми повинні оцінювати один з двох можливих виходів до кожного з трьох входів. Має бути очевидним, що входи не можуть забезпечити різні виходи.

З іншого боку # g # може бути ін'єкційним, оскільки є "достатньо місця": кожен з трьох входів може вибрати один з чотирьох виходів таким чином, що ніякі різні входи не забезпечують однаковий вихід.

Але на скільки способів? Ну, припустимо, ми знову почнемо з #f (1) #. Ми можемо вибрати будь-який з чотирьох вихідних для цього входу, щоб ми могли вибрати #f (1) # чотирма способами.

Коли справа доходить до #f (2) #, ми втрачаємо деяку свободу: ми можемо призначити будь-яке значення #f (2) #, за винятком тієї, яку ми призначили #f (1) #, так що нам залишилося два варіанти. Наприклад, якщо ми виправили #f (1) = 2 #, потім #f (2) # може бути #1#, #3# або #4#.

За тією ж логікою ми маємо два варіанти вибору #f (3) #: з чотирьох можливих варіантів виключаємо тих, які вже призначені #f (1) # і #f (3) #.

Отже, ми можемо визначити # g # в #4*3*2 = 24# способи такі # g # ін'єкційно.