Множество возможных пределов для сюръекции N -> N ...

[resevus]

Найти все значения $\lim\limits_{n \to \infty} \frac{f(n)}{n}$, если $f:\mathbb{N} \to \mathbb{N}$, сюръекция.

[Sonic86]

По-моему, только 1.
Думаю, надо рассматривать нижний и верхний и предел и исходить из того, что они равны.
upd: Ой! Это я для $f$ биекции сказал.

[gris]

Я в таких случаях пытаюсь построить разные примеры, а там вдруг и озарит

$$\begin{matrix} 1 & 2 & 3 &4&5&6&7\\ 1 & 2 & 3 &4&5&6&7\\ \end{matrix}$$

$$\begin{array}{cccccccccccccccc} 1 & 2 & 1 &1&3&1&1&1&4&1&1&1&1&5&1&1\\ 1 & 2 & 3 &4&5&6&7&8&9&10&11&12&13&14&15&16\\ \end{array}$$

$$\begin{array}{cccccccccccccccc} 1 & 1 & 2 &2&3&3&4&4&5&5&6&6&7&7&8&8\\ 1 & 2 & 3 &4&5&6&7&8&9&10&11&12&13&14&15&16\\ \end{array}$$

А вот попробую наоборот. И проблема: куда девать маленькие числа

[ewert]

$[0;\;1]$.

Если $x\in(0;\;1]$, то $x=\lim\limits_{n\to\infty}\dfrac{[nx]}{n}\,.$

Если $x=0$, то $x=\lim\limits_{n\to\infty} \dfrac{\left[\sqrt{n}\,\right]}{n}\,.$

Если $x=\lim\limits_{n\to\infty}\dfrac{f(n)}{n}>1\,,$ то на достаточно далёких участках найдётся бесконечно много пропущенных чисел, которые не могут быть поглощены начальным участком, т.е. это не будет сюръекцией.

[Dan B-Yallay]

resevus в сообщении #445299 писал(а):

Найти все значения $\lim\limits_{n \to \infty} \frac{f(n)}{n}$, если $f:\mathbb{N} \to \mathbb{N}$, сюръекция.

А этого предела может и не существовать. Например берем

$$f(n):\begin{cases} f(p)=p^2, \quad p-\text{prime}\\ f(p^2)=p, \quad p-\text{prime}\\ f(n)=n, \quad else \end{cases}$$

[vlad_light]

Помоему только $\mathbb N$.
Т.е. $f:\mathbb N \to \mathbb N; n\mapsto nx, x\in \mathbb N$
$lim\frac{nx}{n}=x \in \mathbb N$

[Kallikanzarid]

Для биекции предел всегда равен $1$ (связано с теоремой кого-то там об инвариантности предела последовательности при перестановках), так что вопрос в том, будет ли существенной проблемой отсутствие инъективности. ИМХО, поскольку для любой биективной подпоследовательности $f$ предел будет одним и тем же, предел должен быть равен $1$, но это только hunch :) Будет, рассмотрим в качестве примера последовательность

$$1\ 2\ 1\ 3\ 1\ 4\ 1\ 5\ 1\ 6\ldots$$

Но если рассматривать последовательности, имеющие предел, то ИМХО (не проверял) можно показать, что пределом $f(n)/n$ может быть любое число из $[0, 1]$. ИМХО, стратегия доказательства тут - сначала сконструировать в явном виде $f$ для каждого числа из этого множества, а затем доказать, что никакое другое вещественное число не может быть пределом последовательности $f(n)/n$.

[ewert]

Kallikanzarid в сообщении #445633 писал(а):

сконструировать в явном виде $f$ для каждого числа из этого множества

ewert в сообщении #445314 писал(а):

Если $x\in(0;\;1]$, то $x=\lim\limits_{n\to\infty}\dfrac{[nx]}{n}\,.$

Если $x=0$, то $x=\lim\limits_{n\to\infty} \dfrac{\left[\sqrt{n}\,\right]}{n}\,.$

[gris]

А я ещё раньше предложил решения, но молчу об этом, молчу, хотя молчать невыносимо, ибо вот мой первый пример для 1, второй для нуля, третий для любого промежуточного числа. И всё так изящно намекнуто, а не вульгарно вывалено. И на то, что больше 1 лимитов нет. А в черновиках ещё примеры, когда предел не существует. И пример для иррационального числа. И всё так аккуратно сделано, но вот поди ж ты... Нет, пора в леса. Рассказывать про тензоры клещам.

[ewert]

Что больше единицы быть не может -- достаточно очевидно. Лень наводить марафет, а идея проста: на каждом из участков от $n=2^{k}$ до $n=2^{k+1}-1$ при всех достаточно больших $k$ будет потеряно хоть одно число из предполагаемой области значений функции $f(n)$ (а фактически много чисел). Просто потому, что точек на этом участке $2^{k}$, а значения растянуты по промежутку существенно большей длины (порядка $(x-\varepsilon)2^{k}$).

[gris]

Вот и сравните Ваше длинное и непонятное объяснение с моим: "При сюрьекции некуда девать маленькие числа."
То есть неизбежно будут постоянно появляться дроби не большие единицы. Вот.

[ewert]

(Оффтоп)

gris в сообщении #445696 писал(а):

"При сюрьекции некуда девать маленькие числа."

Сравнил -- и ничего не понял. Даже сейчас, при повторном прочтении, не говоря уж о тогда.

[Kallikanzarid]

gris в сообщении #445694 писал(а):

Нет, пора в леса. Рассказывать про тензоры клещам.

Только в современном изложении!

[gris]

Я под большими числами разумею те, которые в конкретной последовательности больше своих номеров. И допустим, что мы хотим построить последовательность, для которой функция $f(n)/n$ сходится к пределу, большему 1. Тогда начиная с некоторого Номера все члены последовательности будут большими и уж подавно большими этого самого Номера. И где мы разместим числа, которые не больше этого Номера? Не Дирихле ли возопит, что их некуда девать?