Представление множеств целых чисел

[Sonic86]

Обозначим $Q(n,R_n) = \bigcup\limits_{r \in R_n} \{ r+kn, k \in \mathbb{Z}\}$.
Пусть $X \subseteq \mathbb{Z}$. Обозначим $I(X) = \bigcap\limits_{n=1}^{+ \infty}Q(n, R_n)$, где $R_n = \{ y: y=x \mod n\}$.
Пусть $f$ - функция, определенная на $\mathbb{Z}$, такая, что $f(x) \equiv f(x \mod n) (\mod n)$ (то есть переводит классы вычетов по модулю $n$, в классы вычетов по модулю $n$). $X = E(f)$.
Докажите или опроверните, что $I(X) = X$.

[Хорхе]

Sonic86 в сообщении #235990 писал(а):

Обозначим $Q(n,R_n) = \bigcup\limits_{r \in R_n} \{ r+kn, k \in \mathbb{Z}\}$.
Пусть $X \subseteq \mathbb{Z}$. Обозначим $I(X) = \bigcap\limits_{n=1}^{+ \infty}Q(n, R_n)$, где $R_n = \{ y: y=x \mod n\}$.

Что-то я условие не понимаю. Может, $I(X) = \bigcap\limits_{n=1}^{+ \infty}Q(n, X)$?

[Sonic86]

Хорхе писал(а):

Что-то я условие не понимаю. Может, $I(X) = \bigcap\limits_{n=1}^{+ \infty}Q(n,X)$?

Да, можно и так писать, если охота, хотя это другое определение.
Например, если $K$ - множество квадратов целых чисел, то

$$K = Q(1,\{ 0\}) \cap Q(2, \{ 0,1\}) \cap Q(3, \{ 0,1\}) \cap Q(4, \{ 0,1\}) \cap Q(5, \{ 0,1, 4\}) \cap ...$$

Тут вот видно сразу, что $R_n$ - множество квадратичных вычетов по модулю $n$, а если Ваше определение брать - будет тоже самое, но в $Q(n,X)$ будет входить бесконечно много совпадающих классов, а с другой стороны, не надо $R_n$ вводить.

[maxal]

А что есть $x$ в определении $R_n$ ? И что такое $E(f)$ ?

[Хорхе]

Я так понимаю, что $E(f) = f(\mathbb Z)$.

-- Вт авг 18, 2009 14:48:46 --

maxal в сообщении #236093 писал(а):

А что есть $x$ в определении $R_n$ ?

Уже вроде разобрались, там вместо $y=x\pmod n$ должно быть $y\in X\pmod n$.

[maxal]

То есть:

$$I(X) = \{ r\in\mathbb{Z} \mid \forall n\geq 1\ \exists k\in\mathbb{Z} : r + nk \in X \}$$

Понятно, что $X\subset I(X)$ (достаточно взять $k=0$). Наоборот, для $X=f(\mathbb{Z}),$ где $f(x)$ определена на классах вычетов по модулю $n'$, если $r\in I(X)$, то, беря $n=n'$, получим $r+n'k\in X$ для некоторого $k$, а значит и $r\in X$. Отсюда следует, что $I(X)\subset X$, а значит $X=I(X)$.

-- Tue Aug 18, 2009 06:23:46 --

Хотя нет. В общем случае $X$ не замкнуто относительно вычитания/прибавления кратных $n'$.

[Sonic86]

maxal писал(а):

А что есть $x$ в определении $R_n$ ?

Блин, опять я не дописал!
$R_n = \{ y: y = x \mod n, x \in X \}$!
Вы меня правильно поняли
И $E(f) = f(\mathbb{Z})$.

-- Вт авг 18, 2009 15:36:15 --

У меня получилось доказать $I(X)=X$ для множества всех квадратов, но я использовал символ Лежандра и теорему Дирихле о бесконечности числа простых вида $at+b, gcd(a,b)=1$ (а если честно, вообще боюсь, что наврал )

[maxal]

Sonic86 в сообщении #235990 писал(а):

Пусть $f$ - функция, определенная на $\mathbb{Z}$, такая, что $f(x) \equiv f(x \mod n) (\mod n)$ (то есть переводит классы вычетов по модулю $n$, в классы вычетов по модулю $n$). $X = E(f)$.

Похоже, что любое непустое подмножество целых чисел $X$ можно представить в таком виде (то есть, подобрать подходящую функцию $f$).
А для произвольного множества $X$ исходное утверждение кажется сомнительным.

[Sonic86]

maxal писал(а):

Похоже, что любое непустое подмножество целых чисел $X$ можно представить в таком виде (то есть, подобрать подходящую функцию $f$).
А для произвольного множества $X$ исходное утверждение кажется сомнительным.

Насчет подбора функции $f$ я не знаю. Хотя бы доказать для случая, когда $f$ - многочлен...
Пока нашел такой пример: если $X$ - множество чисел, не являющихся степенями числа $a, a>1$ (ну или вообще множество плотности нуль), то для него $I(X) \neq X$. То же самое будет и для $X \cap Y, Y \neq \empty$ - любое.