Алгоритмічні проблеми (стр. 2 из 7)
Функція називається ін’єктивною, якщо з х, у 
Dom (f) і х 
у випливає f(х) f (у). Для ін’єктивної функції f через f -1 позначається функція, зворотня до f, тобто така єдина функція g, що Dom (g)=Ran (f) g (f(x))=x для всіх х Dom (f). Функція f з А в В називається сюр’єктивною, якщо Ran(f)=B.
Якщо f: A
В и функція f ин’єктивна (сюр’єктивна), то f називається ін'єкцією (з А в В) (сюр’єкцією (з А в В)). Функція, що є одночасно ін'єкцією і сюръекцией, називається биекцией.Припустимо, що f є функцією, а Х – множина. Обмеженням f на Х називається функція з областю визначення Х
Dom(f), значення якої в кожному х Х Dom (f) дорівнює f(x).Обмеження f на Х позначається через f|X. Ran (f|X) позначається через f(X). Якщо Y – множина, то прообразом Y відносно f називається множина f-1(Y)={x|f(x) Y}. (Помітимо, що прообраз визначений навіть тоді, коли функція не ин’єктивна.)
Якщо f, g-функції, то будемо говорити, що g продовжує f, коли Dom (f)
Dom (g) і f(х) = g (х) для всіх х Dom (f); у коротшому запису: f=g/Dom(f). Це відношення функцій f, g записується як f g.Композиція двох функцій f і g є функція з областю визначення {x/x Dom(g) і g(x) Dom(f)}, значення якої, коли вона визначена, є f (g(x)). Цю функцію позначають через f 
g.
Через f0 позначаємо ніде не визначену функцію; тобто Dom(f0)=Ran(f0)=0. Очевидно, що f0=g|0 для будь-якої функції g.
В обчисленнях нам часто будуть зустрічатися функції чи вирази, що включають функції, що не усюди визначені. У таких випадках дуже зручне наступне позначення. Нехай a(x) і b(х) – вирази, що включають змінні х=(х1,…, хn). Тоді запис а(x)
b(x) означає, що для кожного х вираження а(x) і b(x) або одночасно визначені і рівні, або обидва не визначені. Так, наприклад, для функцій f і g запис f(x) g(x) означає, що f=g; і для довільного числа y запис f(x) y означає, що f(x) визначена і дорівнює y (оскільки y завжди визначене).Функції від натуральних чисел. У більшій частині цієї книги ми будемо мати справу з функціями від натуральних чисел, тобто з функціями з Nn в N для різних п, здебільшого для п = 1 чи 2.
Функція f з Nn в N називається п-місною функцією. Значення f на п-кі (x1,…, хn)
Dom (f) записується як f(x1,…, xn) чи f(x), якщо x представляє (x1,…, xn). У багатьох книгах і статтях термін часткова функція використовується для позначення функції з Nn у N, область визначення якої не обов'язково збігається з Nn. Для нас слово функція означає часткову функцію. Проте при нагоді ми будемо писати «часткова функция», щоб підкреслити її можливу «не усюди визначеність». Тотальною функцією з Nn у N ми називаємо функцію з Nn у N), область визначення якої є всі Nn. lМи затушовуємо розходження між функціями і їхнім значеннями в різних крапках, особливо у випадку теоретико-числових функцій у двох досить стандартних і недвозначних ситуаціях. По-перше, ми допускаємо такі фрази як «Нехай f(x1,…, xn) – функція…», що означає, що f є n-місною функцією. По-друге, ми часто описуємо функцію в термінах її значення, що задається деякою формулою. Наприклад, «функціях2» означає «одномісна функція f, значення якої в кожному х
N є х2»; аналогічно «функція х + у» означає «двомісна функція», значення якої в кожній парі (х, у) N2 є х+ у.Функцію, тотожно рівну 0 на N, ми позначаємо через 0, і взагалі для т
N функцію N N, значення якої усюди дорівнює т, ми позначаємо жирним символом т.3. Відношення і предикати
Якщо А – множина, то властивість М(х1,…, хn), що виконується на деяких n-ках з Аn і не виконується (чи помилкове) на всіх інших n-ках з An, називається п-місним відношенням, чи предикатом на А.
Наприклад, властивість х<у є двомісне відношення (чи предикат) на N; 2 < 3 виконується (чи істинно), тоді як 9 < 5 не виконується (чи хибно). Інший приклад: кожна n-місна функція f з Nn у N приводить до (п + 1) – місцевого предиката М (х, у), що задається умовою:
М (x1,…, хn, у), якщо і тільки якщо f (x1,…,xn)
у.Відношення еквівалентності і порядку. (Читач, не знайомий з цими поняттями, може при бажанні відкласти читання цього параграфа доти, поки він не буде потрібен в гл. 9.) У гл. 9 ми зустрінемося із двома спеціальними видами відносин на множині А.
(a) Бінарне відношення R на множині А називається відношенням еквівалентності, якщо для всіх х, у, z А виконуються три наступні властивості:
(i) (рефлективність) R (х, х);
(іі) (симетрія) R (х, y)
R (у, х);(iii) (транзитивність) якщо R (x, y) і R (у,z), то R (х, z). Говорячи, що х, y еквівалентні (у деякому спеціальному змісті), ми маємо на увазі відношення R (х, у). Потім ми визначаємо клас еквівалентності х як множина {у | R (х, у)}, що складається з всіх елементів, еквівалентних х.
(b) Двомісне відношення R на множині А називається частковим порядком, якщо для всіх х, у, z
A.(i) (іррефлексивность) не R (х, х);
(іі) (транзитивність) якщо R (х, у) і R (y, z), те R (x, z).
Частковий порядок звичайно позначається символом <, і ми віддаємо перевагу запису х < у запису < (х, у). Часто визначають частковий порядок, вводячи спочатку предикат < (позначающий < чи =) із властивостями:
(i) х 
х;
(ii) якщо x y і у х, те х=у;
(iii) відношення транзитивно, а потім визначаючи х < у як х уи х у.
4. Логічні позначення
Ми скрізь вживаємо стандартні логічні позначення. Символ
позначає еквівалентність по визначенню, означає логічне слідування, а 
позначає «випливає з». Символи 
, 
використовуються в значенні «для всіх» і «існує» відповідно.