Свойства и классификации инъективных отображений N > N

Всякое отображение f.N^>N определяет некоторую последовательность {й"}"₌₁ = (в) = (^ап) натуральных чисел а_п (натуральную последовательность), где a"=f (n), neN, называется общим членом последовательности. В общем случае множество значений функции f. N —> N может быть и конечным.

Ниже, по умолчанию, рассматриваются инъективные отображения (р: N—>N. Пусть ?,= (1,и, п₂,…,",…) с N есть строго монотонная последовательность, N (^) = {/: и jV, = {1, 2,. Пусть далее А,₊₁ = N_M1N/. Последовательность ?, разбивает множество N на нспсрссскающиеся отрезки: N-uA_t, это разбиение мы будем также называть разбиением. Последовательность ?, и отображение (р: N->N определяют две последовательности (</,.) и (8,), /е Щ), целых неотрицательных чисел, где Vie N (Q при.

Здесь символ м обозначает количество элементов множества М.

Если D~ =ф (N_j)N_j и d~ = D~ > 0, тогда d~ =г/, <5,. Действительно, d~ = б, тогда и только тогда, когда пусто множество { р: «. < р < 8, л < л₍ р* ср (л)}. В иных случаях dj < 8,.

Рис. 6.2.1 иллюстрирует отображение (р: N —> N, где (р (л?) = /?.

Рис. 6.2.1.

Здесь р₂ е D~, s₂, s₃ е D_i, 5, — = р₂ — и,-.

Подчеркнем, что V/eiV (%), число d_t = |D₍| = d~ определяет количество «дыр» во множестве (V, — ={1,2,при отображении <�Р|_Л., т. е. количество тех элементов подмножества N, каждый их которых не имеет прообраза в (У,-.

Отображение ф: iV —" TV определяет также последовательность (ф") целых чисел (р" = ф (я) — п. Справедливо почти очевидное Утверждение 6.2.1. Если 5_<�р =зир{ф (и) — п) и для некоторого

пе,

^-разбиения существует б, = sup {5,}, то Ъ, <8_ф.

/еЛЦ!;).

• Если ?, = N, то б_? =8_ф, что очевидно. В общем случае, Зи такое, что 5_ф = ф,_т и 3 i € N (^): nj <�п < л_?+!. Если п = п-_г+[, то вновь б_? = б_ф. При п_Т <�п < n_J+l б₇₊, = ф (л) -п_т+1 < ф (л) -п = ф_г, т. е. 5^ < 8_ф. Однако всегда можно выбрать такое^{-разбиением} множества N, при котором Яг₊₁ =п, и следовательно, будет справедливо равенство.

Ниже мы формулируем и доказываем непосредственное и почти очевидное следствие определения в (6.2.1) множества ?>, и определения сюръективности отображения ф: ф(N) = N (ср. Утверждение 6.1.1).

Утверждение 6.2.2. Необходимое условие сюръективности каждого инъективного отображения ср: N —> IV имеет следующие две эквивалентные формы:

• Пусть ср(N) = N. Тогда условие j € TV: У, с ф (Д₊ ?) следует из включения Л^г, сф (Л^г) и конечности множества У,. Далее мы докажем импликацию (Д п Д_+у =0)=>(Д с ф (Д₊Д). Действительно, из Д пД₊. = 0 и определения Д.. следует включение ф'¹ (Д) с Д. ., тогда Д сф (Д ?). Кроме того, по определению Д имеем включение Д Д с ф (Д) с ф (Д_+у). Следовательно, Д с ф (N_i+j). Обратная импликация (Д с ф (Д₊))=>(Д о Д₊ — =0) доказывается аналогично. ?

Ниже фраза «для почти всех г» обозначает «за исключения конечного множества индексов /» и по определению мы пишем «V /».

Достаточные признаки сюръективности (а) и антисюръективности (6) отображения ф, являющиеся следствием Утверждения 6.2.2 и определения в (6.2.1) последовательности (dj), даны в терминах d_t ниже.

Утверждение 6.2.3. Достаточные условия сюръективности (а) и антисюръективности (6) инъективного отображения ф/ N —> N имеют, соответственно, вид:

• Условие (6.2.4с/) гарантирует существование числа /₀ такого, что для отображения ф справедлива следующая цепь импликаций:

Условие (6.2.46) утверждает неограниченность последовательности (dj), i €У (^), что противоречит сюръективности инъективного отображения ф: N —> N, т. к. каждое число d_j равно по определению количеству элементов и множества Д, каждый из которых не имеет прообраза ф '(л) в Д. ?

Замечание 6.2.1. Из неограниченной натуральной последовательности, например, (с/,), i е /V (с,), всегда можно выделить монотонную подпоследовательность (</,), !? / с /V (?,), для которой lime/, =оо .

Как показывают примеры, условия (6.2.4а) и (6.2.46) не являются необходимыми, соответственно, для сюръективности и антисюръекгивности отображения ф.

Про антисюръективное инъективное отображение мы говорим, что оно потенциально не осуществимо на всем множестве N (ср. с Утверждением 6.1.2).

Теорема 6.2.1. Последовательности (б,) и (d_i), ieN (Q, определяемые парой (Z, ф), удовлетворяют одному и только одному из трех следующих условий:

• Если /ieN (fy б,=0, тогда ф(N_j) = N_l и, по определению, d_t =0, и наоборот, из чего следует (6.2.5а). Предположим далее, что 0 < 8, < С, тогда с/, = d~ < б, < С,. В силу последнего условия очевидно, что неограниченность последовательности (б,) является следствием неограниченности последовательности (</,.). В частности, при isN (?,) справедлива в силу Замечания 6.2.1 следующая импликация:

Пусть далее ЭС₂ е 7V и V/ е 7V (%) с/, < С₂. Теперь мы покажем, что совмещение двух условий: dj = d_t < С₂ и неограниченность последовательности (5,) приводит к противоречию. Не нарушая общности рассуждений, мы будем считать, что 6, —" оо. Из 6, —" оо также следует, что б₍— —> оо при всех конечных q и, в том числе, при q = С₂. Если /г, =б, — л,.

тогда Эи* такое, что V/>и*, k_t >и,. Из этого следует, что для всех j таких, что i — q < j < i, k D_t, и т. к. ф (N_t) = (N₍ D_t)u D~, to.

{k_t, k_{j +l}, c Dj, t. e. все k_f € D_t. Это означает, что число d_t удовлетворяет следующему условию:

Вместе с предположением, что С₂ > d~, мы имеем противоречие С₂>С₂+1, которое подтверждает (6.2.56) и вместе с ним (6.2.5с). ?

Следствие Утверждений 6.2.2−6.2.3 и Теоремы 6.2.1 записано ниже.

Утверждение 6.2.4. Необходимый признак сюръективности инъективного отображения (р: N —> N в терминах последовательности (8,) имеет следующую форму:

Еще один необходимый и более эффективный признак сюръективности инъективного отображения (р: N —> N с учетом равенства (6.2.2) дает следующее предложение.

Теорема 6.2.2. Ограниченность последовательности (ф") целых чисел Ф" -ф («) — п, п е N является необходимым условием для сюръективности инъективного отображения ф: /V —> /V, т. е. из ф (/У) = N следует, что

Существование этого предела следует из необходимого условия.

(6.2.3) сюръективности отображения ф: N —> N .

Равенство (6.2.7) доказано в монографии [2, р. 8] другим способом.

Как показывают примеры, необходимые условия (6.2.3) и (6.2.6) или.

(6.2.3) и (6.2.7) сюръективности инъекции ф: N —> IV являются независимыми, и следовательно, ни одно из этих условий не может быть достаточным.

Последовательность? = (1 , n_l, n₂,…, n_i,…) назовем последовательностью с ограниченным шагом, если ЗС > 0 такое, что / € ЛД%) справедливо неравенство п_м -n_j < С. Доказанная ниже Теорема 6.2.3 является, как и Теорема 6.2.2, далеко не очевидной.

Теорема 6.2.3. Инъективное отображение (р*: N —> N, определяющее некоторую последовательность = (1, т_х, т₂,…), где m_j+i >/", с неограниченным шагом является антисюръективным или, другими словами, будет неосуществимо на всем множестве N.

• Пусть, будет последовательностью с неограниченным шагом, т. с. для отображения ф*, определяющего, при любом^{-разбиением} множества N справедливо следующее условие:

Теперь при ?, = N, и следовательно, N (QN имеем и, = i +1. Значит, для V/eM{l} ф*(/) = т,_, и в этом случае (см. (6.2.1)) VieN S'* =m_i — i. Поэтому VieN S*₊₁ -8* =(/и,₊₁ — (/ + 1)) — (/и, — /) = /и,₊₁ -т_: — 1. Таким образом, в силу условия (6.2.8) неравенство 8*_(С)+1 — 8*_(С) > С — 1 справедливо для i (C)eN. Значит, 8*_(С)+, > 8*_(С)-1 + С. Из этого неравенства неограниченность последовательности (8*), соответствующей парс (N, ф'), следует из произвольности в (6.2.8) числа С. Следовательно, инъективное отображение ф*, определяющее последовательность из условия теоремы, является в силу (6.2.6) антисюръективным. и

Следствие Теоремы 6.2.3. Если последовательность (8,), i € /V (q), соответствующая паре (%, ф), является ограниченной, тогда для любогоразбиения множества N последовательность (8*,), определяемая парой (?,*, ф), также будет ограниченной последовательностью.

Теорема 6.2.3 имплицирует следующее утверждение.

Теорема 6.2.4. Пусть, А = {n}}с N являются бесконечными подмножества множества N. Тогда существует число С е N такое, что пара (п, т) переменных п и т является С-точной парой переменных (6.1.2).

• В силу Теоремы 6.2.3 разность между соседними элементами каждого из множеств А и В ограничена. Поэтому естественно упорядоченная последовательность E=AkjB будет также последовательностью с ограниченным шагом, г. е. разность между любой парой ее соседних членов ограничена, в том числе, и между соседними в Е элементами подмножеств А и В. Следовательно, по Определению 6.1.1 пара (т, к), (т, к)

е (c)© <= (А, В), является С-точной парой переменных. ?

Следующее ниже утверждение, впервые появившееся в [103, р. 91] и [104, р. 9], является следствием условий (6.2.3), (6.2.6) и (6.2.7) для бесконечных подмножеств множества N (ср. Утверждения 6.1.2 и 6.1.4 для конечных множеств).

Теорема 6.2.5. Не существует биекции между множеством N натуральных чисел и его собственным подмножеством А, а N.

Элементарное доказательство этой теоремы дает условие (6.1.1) и тождественные отображения id: N —" N и id : А —> А, или применение метода математической индукции к Утверждению 6.1.4.

Теорема 6.2.5 является следствием Теоремы 3.8 и может быть доказана также методом математической индукции, а именно индукцией по количеству элементов конечного подмножества А с У.

Легко показать, что содержание доказанных выше предложений сохраняется для инъективных отображений (р: А —> А, где А с N.

Доказанные выше предложения позволяют разбить все инъективные отображения (инъекции) (р: N —> N на шесть непересекающихся классов следующим образом.

Определение 6.2.1. Инъекция <�р: N —> N называется точно сюръективной, если существует такое разбиения множества N, что для VieN (?,) б,. =0.

Определение 6.2.2. Инъекция (р: N —> N называется потенциально сюръективной, если выполняются следующие два условия:

a) для некоторой последовательности? = (1, nl, п2,.

1, И], п₂,…, «,…) существует число С > 0 такое, что для V/ 6 А'(^) 0< 6,.<�С_?;

b) V/ е Зуб N{%): D, n D_i+J = 0.

Определение 6.2.3. Инъекция ф: N —> N называется потенциально антисюръективной, если выполняются следующие условия:

a) для некоторого Ъ,-разбиения множества N последовательность (б,), / е /V (c,), определяемая парой (?, ф), является неограниченной;

b) V/ € N&) 3 у б N&): D, п D_l+J = 0.

Определение 6.2.4. Инъекция ф: N —> N называется С-конечно антисюръективной, если а) последовательность (б,), /б N(?,), определяемая парой (?, ф), является ограниченной и Ь) справедливо следующее условие: з (С, «о, У_ф), С> 0, /₀ б N?), У_ф с У: V/ > i₀ У_ф с D, и N_V = С. (6.2.9).

Очевидно, что подмножество (V не пересекается с образом ф (А^г) отображения ф: N —> N: N_v п (p (N) = 0.

Определение 6.2.5. Инъекция ф: N —> N называется tw-

антисюръективной, если а) соответствующая последовательность (8,), i е N (Q, является неограниченной последовательностью и Ь) для этого отображения справедливо условие (6.2.9).

Определение 6.2.6. Инъекция ф: N —> N называется тотально антисюръективной, если при этом отображении подмножество N множества N, -Y_(p п ф (/V) = 0, является бесконечным.

Инъективные отображения ф: А —" А допускают аналогичную классификацию для каждого бесконечного собственного подмножества A

Замечание 6.2.2. Для каждого антисюръективного инъективного отображения ф: N —> N, т. е. для отображения ф, неосуществимого на всем множестве N, существует пара (Р_Х, Р₂) таких бесконечных собственных подмножеств Р_х и Р₂ множества N, что при Ф=Ф|_Р| Ц>(Р_Х) = Р₂ и

Г¹0Р₂) = />.

Например, множество Е четных натуральных чисел можно определить так: Е={е_х: е, =2, Vi еР, <= N е_м = е, + 2}. Здесь множество Р_х является собственным подмножеством множества N, т. к. инъективное отображение ф: N—>N, определяемое формулой ф (я)=е" =2п, является тотально антисюръективным, что очевидно. Поэтому данное отображение неосуществимо на всем множестве N .

На основании введенной выше классификации и Теорем 6.2.1−6.2.3 эффективный критерий конечной или потенциальной сюръективности инъекции ф: N —> N можно сформулировать в следующей форме (ср. [67, с. 198]):

Теорема 6.2.6. Инъекция ц>: N —>N является биекцией, другими словами, точно или потенциально сюръективным отображением, тогда и только тогда, когда для этого отображения выполняются два условия'. (6.2.3) и (6.2.7), т. е.

Отметим, с другой стороны, что или одно, или оба условия (6.2.10) не выполняются для всех антисюръективных отображений ф: N —> N .

Теорема 6.2.6 не совсем очевидным образом обобщает Утверждение 6.1.1 для конечных множеств.