Федоров В.Н. - Введение в теорию множеств, страница 5

f(x) = (х – 1) х = х!

описывается рекурсивной вычислительной процедурой, задаваемой следующими правилами:

1) f(0) = 1; 2) f(x + 1) = f(x)(х + 1).

Вот некоторые, наиболее употребляемые, способы представления функций одного аргумента:

• Перечнем всех значений аргумента а и соответствующих им значений функции b, a, b M, представленных строкой

φ = (a₁ → b₁ , а₂ → b₂, ..., а_п → b_п),

а чаще парой строк:

Если предварительно зафиксирован список (последовательность) элементов (a₁, a₂, ..., а_п) множества М, то для задания функции φ достаточно указать вектор значений (b₁, b₂,..., b_n). При этом φ(a_i) = b_i, т.е. результат выполнения функции φ для i–ого аргумента списка равен i–ой компоненте вектора значений.

• Списком всех пар "аргумент–значение" (a, b) φ, a,b М, для всех возможных значений аргументов:

φ = {(a₁, b₁), (а₂, b₂),..., (а_п, b_п)}.

Число таких пар |пр₁ φ| = т |M| .

• Формулой φ(а) = b, например, lga = b.

Для функций двух переменных φ:М х М→ М на конечном множестве М = {a₁, a₂ ,..., а_п} наиболее часто применяют следующие способы задания:

• Таблица Кэли — таблица имеет число строк, равное числу значений аргумента a, и число столбцов, равное числу значений аргумента b. На пересечении строки, соответствующей аргументу а, и столбца, соответствующего аргументу b, записывается результат с выполнения функции φ над а и b.

На рис. 2.4 приведена таблица Кэли для функции, называемой "сложением по модулю 3" на множестве М= {0, 1, 2} и обозначаемой "mod 3", или (результат с выполнения операции равен остатку от деления суммы аргументов (а + b) на 3).

• Списком всех троек (а, b, с), где а, b – соответственно первый и второй аргументы из М, с – результат выполнения функции φ над а и b, a,b,c M.

Для всюду определенной функции число всех троек в списке |М х M|= п². Например, для функции сложения по модулю 3: = ={(0,0,0), (0,1,1), (0,2,2), (1,0,1), (1,1,2), (1,2,0), (2,0,2), (2,1,0), (2,2,1)}.

• Формулой φ(а, b) = с – так называемое префиксное представление; иное – инфиксное представление формулой а φ b = с, например а b = с, где – операция сложения по модулю 3.

Пример 1. Таблица выигрышей лотереи устанавливает соответствие G между парами чисел из N x N = N ² (серия, номер выигравшего билета) и множеством выигрышей М, т.е. . Является ли заданное соответствие функцией, и если – да, то какой?

• Соответствие , задаваемое таблицей выигрышей, является функциональным, так как для каждой указанной пары из N ² (серии, номера билета) определен конкретный (единственный) выигрыш из М. Таким образом, данное соответствие есть двухместная функция f:N х N → М. Функция такого типа, не всюду определена, а значит не является отображением. Более того, как правило, число выигравших билетов (мощность области определения пр₁f) больше перечня наименований выигрышей (мощности области значений пр₂f), поэтому данная функция не обладает единственностью прообраза. В силу сказанного f не является взаимно однозначным соответствием.

Таким образом, таблица выигрышей лотереи определяет функцию

f: N x N → M,

которая не является взаимно однозначным соответствием.

Пример 2. Чему равна композиция функций f(x) = 2х и g(x) = l + x?

• Пусть функции f(x) = 2х и g(x) = l + x имеют тип → . Тогда их композиции возможны в произвольном порядке. Композиция функций f ○ g = h₁ представляет собой подстановку f в g, т.е.

h₁ = f ○ g = f(g(x)) = 1+ f(x) = 1+ 2x.

Композиция g ○ f = h₂ есть функция, полученная подстановкой g в f, т.е.

h₂ = g ○ f = f(g(x)) = 2g(x) = 2(1 + x) = 2 + 2x.

Пример 3. Чему равна композиция функций f(x) = 2^х и g(x) = log₂x?

Каковы области определения функций и их композиций?

• Пусть функции f(x) = 2^х и g(x) = log₂ x имеют тип R→R, т.е. отображают одно и то же множество в себя. Тогда композиция возможна в произвольном порядке и дает функции:

h₁ = f ○ g = g(f(x)) = log₂2^x = x;

h₂ = g ○ f = f(g(x) = .

Области определения исходных функций и их композиций:

пр₁f = R, пр₂ g = R₊, пр₁h₁ = R, пр₁h₂ = R₊.

Пример 4. Дана функция f(x₁, х₂, х₃) = х₁ – 2х₂ + 5х₃.

Определить функции, образованные переименованием:

а) х₃ в x₂; 6) х₁ и х₃ в х₂.

• а) Переименование х₃ в х₂ приводит функцию f(x₁, х₂, х₃) к функции

f = х₁ – 2х₂ + 5х₂, которая равна функции двух аргументов:

f(x₁, x₂) = х₁ + 3х₂.

б). Переименование х₁ и х₃ в х₂ приводит к одноместной функции

f(х₂) = 4х₂.

2.3. Отображения

Отображением А в В называется всюду определенное соответствие

g: А→В (область определения равна множеству A, т.е. Пр₁G = A).

Отображением А на В называется всюду определенное и при этом сюръективное соответствие g: А→В (область определения равна множеству A, а область значений рана множеству B, т.е. Пр₁G = A и Пр₂G = B).

Будем обозначать отображение множества A в B или A на B так

.

Отображение типа А → А часто называют преобразованием множества А. Функция типа А→А, являющаяся отображением А на А, называется перестановкой на А.

Отображение может быть и неоднозначным. Тогда совокупность элементов b для одного a обозначается как Ga . Множество Ga – это образ элемента a в множестве B. Элемент a называется прообразом множества Ga.

Пусть имеется отображение G:А→В, где для любого a образом является Ga , и пусть имеется множество A₁ . Совокупность всех , являющихся образами всех a , называется образом множества A₁ и обозначается GA₁ = .

Если A₁ и A₂ подмножества A, то образ объединения этих подмножеств равен объединению их образов в любом однозначном или неоднозначном отображении

.

Действительно

.

Однако соотношение

(образ пересечения подмножеств равен пересечению их образов) справедливо только при однозначном отображении.

Пусть ,

где – область неоднозначности.

Если (область неоднозначности пуста), то

.

Довольно часто рассматриваются отображения на одном множестве

,

которое представляется парой

(A, G), где G = A x A = A².

Пусть G и D отображения A в A.

Композиция этих отображений будет G(D). Если D = G, то G(G) = G², G(G²) = G³ и т.д.

Если принять G⁰ = a, то это правило можно распространить и на отрицательные степени

G⁰ = G (G^–1) = G G^–1 = a.

Это означает, что G^–1 является обратным отображением.

Продолжая, находим

G^–1(G^–1) = G^–2 и т.д.

Для отображений множеств определены прямое и обратное транзитивные замыкания – многократное отображение G или G ^–1 множества A самого на себя.

Прямое транзитивное замыкание определяется по выражению

для всех .

Обратное транзитивное замыкание определяется по выражению

для всех .

Пример 1. Является ли функция f(x) = 2x, имеющая тип N→N, отображением, и если – да, то каким? Имеет ли функция f обратную функцию f ^–1, и если – да, то является ли f ^–1 отображением?

• Функция f(x) = 2x, f: N→N, всюду определена на N, однако не сюръективна, так как область значений функции f равна пр₂f = М_2п N (область значений содержит не все натуральные числа из N, а только четные). Поэтому f является отображением N в N или преобразованием множества N.

Между областью определения пр₁f = N и областью значений пр₂f = М_2п имеет место взаимно однозначное соответствие: любому элементу п из N соответствует один и только один элемент 2n из М_2п и наоборот.

Поэтому функция f(х) = 2х, f:N→N, имеет обратную функцию f ^–1. Однако обратная функция f ^–1: N→N не всюду определена: ее областью определения является множество четных чисел М_2п N. Поэтому обратная функция f ^–1 в отличие от исходной f не является отображением.

Пример 2. Задать несколько возможных типов для функции f(х) = 2ⁿ. Для каждого типа определить:

• свойства функции f;

• является ли f отображением и, если является, то каким?

• 1) Пусть тип функции f:N→N. Тогда f(х) = 2ⁿ всюду определена, так как пр₁f = N, но не сюръективна, поскольку пр₂f = N ( – множество натуральных чисел, являющихся степенями двойки). Следовательно, функция f является отображением N в N.

2) f:N→ . Тогда функция f всюду определена и сюръективна, следовательно, является отображением N нa .