Некоторые элементарные свойства подмножеств множества Z

[Sdy]

Довольно давно не занимался ничем хорошим, поэтому хотелось бы обратиться с вопросом о корректности доказательств некоторых тривиальных утверждений.
Утверждение.
Среди целых чисел четные и нечётные встречаются одинаково часто : если мы возьмём большой интервал подряд идущих чисел, то количество чётных и нечётных чисел в этом интервале будет отличаться максимум на 1.
Доказательство.
Из $\mathbb{Z}$ выделим произвольное подмножество подряд идущих целых чисел $S$, которое в силу упорядоченности будет кортежем. Из $S$ выделим подмножество чётных чисел - $E$ и нечетных - $O$.
Наша задача - доказать, что $\left\lvert card(E) - card(O) \right\rvert \leqslant 1$
Обозначим первый элемент $S$ - $a$, последний - $b$.
Разберём крайние случаи :
1.$S \sim\varnothing \Rightarrow \left\lvert card(E) - card(O) \right\rvert = 0$
2.$a=b \Rightarrow \left\lvert card(E) - card(O) \right\rvert = 1 $
3.$a\mod2=0 \wedge b\mod2=0$
За любым чётным числом в нашем кортеже (кроме $b$) идёт нечётное, значит мы получили биекцию между элементами $E \setminus b$ и $O$.
Следовательно $\left\lvert card(E) - card(O) \right\rvert = 1$
4.$a\mod2=1 \wedge b\mod2=1$
Такое же рассуждение - за каждым, кроме последнего, нечётным числом следует чётное.
5.$a\mod2=0 \wedge b\mod2=1$
За каждым чётным идёт нечетное, получили биекцию, значит $E \sim O$
6.$a\mod2=1 \wedge b\mod2=0$
Такое же рассуждение. $\triangle$
Вопросы :
1.Корректно ли это доказательство и достаточно ли оно строго?
2.Пусть мы рассматриваем теперь $\mathbb{Z}$ и его подмножества чётных и нечётных чисел. Чтобы установить между ними биекцию, достаточно ли просто сказать, что каждому элементу вида $2k$ мы ставим в соответствие элемент вида $2k+1$ ($k \in \mathbb{Z}$)?

[пианист]

"если мы возьмём большой интервал подряд идущих чисел"
Да хоть бы и маленький. Просто на "первый-второй рассчитайсь", и все :))
Зачем так сложно?

[arseniiv]

Sdy в сообщении #1383353 писал(а):

которое в силу упорядоченности будет кортежем

Это точно не нужно.

-- Чт мар 21, 2019 22:55:56 --

Ещё можно много куда прицепиться (то есть конечно пианист уже и так всё сказал, но пускай ещё). Например,

Sdy в сообщении #1383353 писал(а):

Обозначим первый элемент $S$ - $a$, последний - $b$.

В этом месте $S$ может ещё быть пустым и потому у него не будет ни наименьшего, ни наибольшего элемента. Понятно, что случаем ниже эта альтернатива уже отбрасывается, но надо бы с самого начала аккуратно.

Sdy в сообщении #1383353 писал(а):

2.$a=b \Rightarrow \left\lvert card(E) - card(O) \right\rvert = 1 $

Поглощается двумя из следующих случаев.
Кроме того, их вообще слишком много, достаточно рассматривать $(a-b)\bmod2$, а после этого передумать и рассматривать $|S|\bmod2$.

Sdy в сообщении #1383353 писал(а):

2.Пусть мы рассматриваем теперь $\mathbb{Z}$ и его подмножества чётных и нечётных чисел. Чтобы установить между ними биекцию, достаточно ли просто сказать, что каждому элементу вида $2k$ мы ставим в соответствие элемент вида $2k+1$ ($k \in \mathbb{Z}$)?

Почему нет? Если есть сомнения, проверьте явно, что вы задали так биекцию.

[Sdy]

пианист, arseniiv , спасибо за ответы.

пианист в сообщении #1383359 писал(а):

Да хоть бы и маленький.

Просто это авторская формулировка задачи, я решил её не менять. В доказательстве же я проверил утверждение и для множеств $S $ мощности $0,1$. И лишь затем для любых конечных $S$.

пианист в сообщении #1383359 писал(а):

Зачем так сложно?

Ну, чтобы не забыть никакие случаи. Ведь фактически я и делаю то, о чём вы сказали. Рассчитать на $1$ и $2$ - это же все равно построить биекцию.

arseniiv в сообщении #1383390 писал(а):

Это точно не нужно.

Просто очень хотелось назвать то что имеется в $S$ "последовательностью", но в математике ведь это слово обозначает именно бесконечное множеством элементов. Тогда сказал, что это кортеж именно для того чтобы выделить "первый" и "последний" элементы.
Ведь если нам дано просто множество $S$, то для него выделить какие-то позиции элементов не получится ($\left\lbrace 1,2,3\right\rbrace$ и $\left\lbrace 2,1,3\right\rbrace$ - эти множества совпадают, а в случае кортежей - это разные множества), не сказав об упорядоченности. А любое упорядоченное множество - кортеж.

arseniiv в сообщении #1383390 писал(а):

В этом месте $S$ может ещё быть пустым и потому у него не будет ни наименьшего, ни наибольшего элемента. Понятно, что случаем ниже эта альтернатива уже отбрасывается, но надо бы с самого начала аккуратно.

Да, поторопился, так говорить можно было лишь после рассмотрения первого случая.

arseniiv в сообщении #1383390 писал(а):

Поглощается двумя из следующих случаев.

Опять же, хотелось "аккуратности", а получилась избыточность.

arseniiv в сообщении #1383390 писал(а):

и рассматривать $|S|\bmod2$.

Да, это я понимаю. У меня будет еще одна такая задачка (ну, очень похожая, она уже решена, но я ее делал в точности также, как и эту) и я попробую в ней учесть предыдущие замечания и также опубликовать тут решение.

arseniiv в сообщении #1383390 писал(а):

Почему нет? Если есть сомнения, проверьте явно, что вы задали так биекцию.

Я попробую, а вы, пожалуйста, скажите, такая ли в этих случаях подразумевается проверка.
Утверждение.
Необходимо доказать, что отображение $f : E \to O$, определяющееся как $2k \to 2k+1$ задает биекцию между этими множествами.
Доказательство.
1.Проверим однозначность :
По определению, отображение однозначно, если $\forall e_1, e_2 (e_1 \ne e_2) \in E \Rightarrow f(e_1) \ne f(e_2)$.
Возьмём $e_1 = 2k, e_2 = 2l; l,k \in \mathbb{Z}, l \ne k$. $f(e_1) = 2k+1, f(e_2) = 2l+1$. Если бы эти образы совпадали, то были бы равны и $l$ с $k$, что противоречит нашему условию.
2.Проверим взаимность :
По определению, отображение взаимно, если $ \forall o \in O \exists e \in E : f(e) = o$.
Возьмём $o = 2k+1$. Обратное к нашему отображение переведет $o$ в $e = 2k$, значит наше отображение взаимно.
Получаем, что $f$ - взаимно однозначное отображение, то есть, биекция. $\triangle$

[arseniiv]

Sdy в сообщении #1383520 писал(а):

Просто очень хотелось назвать то что имеется в $S$ "последовательностью", но в математике ведь это слово обозначает именно бесконечное множеством элементов.

На «конечную последовательность» вроде не должны ругаться. Но в любом случае $S$ не обязательно превращать в последовательность, это не особо упростит нумерацию его подмножеств.

Sdy в сообщении #1383520 писал(а):

Тогда сказал, что это кортеж именно для того чтобы выделить "первый" и "последний" элементы.

Но ведь вы строите кортеж, руководствуясь порядком на $\mathbb Z$ — так что можно сразу из знания порядка сказать о наименьшем и наибольшем элементах и всё. Кроме того их не нужно выделять, тут вы уже выше согласились.

Кстати можно подоказывать обобщение: если $S = \{n : 0\leqslant n<a, n\in\mathbb Z\}$, $a\geqslant0$, и $S_i = S\cap(N\mathbb Z + i)$, $N>0$, то $\lfloor a/N\rfloor\leqslant|S_i|\leqslant\lceil a/N\rceil$. ($a, N, i$ целые.)

Sdy в сообщении #1383520 писал(а):

Я попробую, а вы, пожалуйста, скажите, такая ли в этих случаях подразумевается проверка.

Да, всё настолько просто.

[Sdy]

Вот и
Утверждение.
Покажите, что все три типа чисел (кратные трём - $3k$, дающие при целочисленном делении остаток $1$ и $2$ - $3k+1$ и $3k+2$ ($k \in \mathbb{Z}$)) встречаются одинаково часто: в большом отрезке подряд идущих целых чисел их количества отличаются максимум на 1.
Доказательство.
Выделим из $\mathbb{Z}$ произвольное подмножество подряд идущих целых чисел $S$. В $S$ выберем 3 подмножества целых чисел - кратные трём $S_1$, дающие остаток $2$ - $S_2$ и дающие остаток $3$ - $S_3$. Необходимо доказать, что количества элементов в этих трёх множествах отличаются не более, чем на 1.
1.Если $S$ $\sim$ $\varnothing$, то количества элементов в $S_1, S_2, S_3$ совпадают и равны нулю.
Теперь, пусть в нашей конечной последовательности $S$ $a$ - первый элемент, $b$ - последний.
2.Пусть $card(S)\mod3 = 0$.
Тогда, начиная с начала, разобьем элементы в $S$ на подряд идущие тройки. В каждой из троек будет по 1му представителя от каждого из классов $S_1, S_2, S_3$, значит и во всём $S$ будет одинаковое количество представителей каждого класса, то есть $card(S_1) = card(S_2) = card(S_3)$.
3.Пусть $card(S)\mod3 = 1$.
Отбросим элемент $a$, наш случай свёлся к случаю 1. Значит в данном случае представителей одного класса на 1 больше, чем представителей других классов.
4.Пусть $card(S)\mod3 = 2$.
Отбросим элементы $a$ и $b$. Они не могут принадлежать к одному класса, так как тогда бы $card(S) \mod 3$ равнялось бы $1$. Докажем это
$\triangle$ Пусть $a = 3k, b = 3d; d,k \in \mathbb{Z}$. Тогда $card(S) \mod 3 = (3d-3k+1) \mod 3 = 1$. Такая же проверка и для случаев, когда $a$ и $b$ принадлежат к другим двум классам.$\triangle$ Отбросив $a$ и $b$ мы снова перешли к случаю 1. Значит в данном случае элементов лишь одного класса будет на один меньше, чем элементов двух других классов.
Мы рассмотрели все случаи, так как $card(S) \in\mathbb{N}$, а любое натуральное число имеет вид или $3n$ или $3n+1$ или $3n+2$, $n \in \mathbb{N}$. $\triangle$.
Также прошу на него посмотреть.

-- 22.03.2019, 23:38 --

arseniiv в сообщении #1383534 писал(а):

Кстати можно подоказывать обобщение

Попробую взглянуть на него завтра.

arseniiv в сообщении #1383534 писал(а):

На «конечную последовательность» вроде не должны ругаться. Но в любом случае $S$ не обязательно превращать в последовательность, это не особо упростит нумерацию его подмножеств.

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

arseniiv в сообщении #1383534 писал(а):

Да, всё настолько просто.

Спасибо.

[arseniiv]

Sdy в сообщении #1383538 писал(а):

и дающие остаток $3$ - $S_3$

Таких нет.

-- Пт мар 22, 2019 21:31:46 --

Кстати только щас заметил, что вы пишете $S\sim\varnothing$ — это тоже лишнее, любое равномощное пустому множеству им и является, так что можно $S=\varnothing$, что как-то привычнее смотрится.

-- Пт мар 22, 2019 21:41:38 --

Кстати, и опять вы выделяете случай $S=\varnothing$ совершенно зря, он аналогично тому, что было раньше, является частным случаем $|S|\bmod3=0$ — просто выделим ноль троек элементов.

Sdy в сообщении #1383538 писал(а):

Отбросим элементы $a$ и $b$. Они не могут принадлежать к одному класса, так как тогда бы $card(S) \mod 3$ равнялось бы $1$.

Можно проще: отбросить $a$ и $a+1$ (или $b$ и $b-1$) — тут сразу ясно, что классы будут разные.

-- Пт мар 22, 2019 21:47:27 --

Можно ещё рассматривать только множества с наименьшим элементом 0, если он есть, и отдельно доказать, что при прибавлении ко всем элементам множества (вообще любого ${}\subset\mathbb Z$) какого-то числа мощности $S_1,\ldots,S_N$ циклически переставляются, что распространит теорему как надо.

[Sdy]

arseniiv, спасибо за ответ.

arseniiv в сообщении #1383559 писал(а):

Таких нет.

Эх, и ведь несколько раз перечитывал свое сообщение и помарки не заметил. Да, конечно, возможные остатки от целочисленного деления на три - только $0,1,2$.

arseniiv в сообщении #1383559 писал(а):

Кстати только щас заметил, что вы пишете $S\sim\varnothing$ — это тоже лишнее, любое равномощное пустому множеству им и является, так что можно $S=\varnothing$, что как-то привычнее смотрится.

Я так пишу по привычке. Просто если абстрагироваться от этого конкретного случая (в котором вы, конечно, правы) и взять, например за множество $S_1$ отрезок $[0;1]$, а за множество $S_2$ отрезок $[0;1000]$, то у меня рука не повернется написать $S_1 = S_2$, а вот запись $S_1 \sim S_2$ у меня в голове вполне укладывается. Или же в случае конечных совпадающих множеств всё-таки принято писать вместо $\sim$ символ $=$?

arseniiv в сообщении #1383559 писал(а):

Кстати, и опять вы выделяете случай $S=\varnothing$ совершенно зря, он аналогично тому, что было раньше, является частным случаем $|S|\bmod3=0$ — просто выделим ноль троек элементов.

Да, я об этом подумал, но просто тогда запись

Sdy в сообщении #1383538 писал(а):

Теперь, пусть в нашей конечной последовательности $S$ $a$ - первый элемент, $b$ - последний.

пришлось бы всё равно оговаривать, о чём вы мне выше уже писали.

arseniiv в сообщении #1383559 писал(а):

Можно проще

Понял, тогда действительно и дополнительно доказывать ничего не нужно.

[arseniiv]

Sdy в сообщении #1383604 писал(а):

Просто если абстрагироваться от этого конкретного случая (в котором вы, конечно, правы) и взять, например за множество $S_1$ отрезок $[0;1]$, а за множество $S_2$ отрезок $[0;1000]$, то у меня рука не повернется написать $S_1 = S_2$

Ну правильно, они не совпадают. Но пустое множество-то всего одно.

Sdy в сообщении #1383604 писал(а):

пришлось бы всё равно оговаривать

Можно в принципе, как я выше предлагал, ограничиться только множествами $[0..a) := \{ n : 0\leqslant n<a \}$, $a\geqslant0$, тогда для непустых наибольшим элементом будет $a-1$ и наименьшим $0$, но пустое в таком виде тоже представимо как $[0..0)$. После этого можно например получить подотрезок из кратного $N$ числа элементов как $[0..\lfloor a/N\rfloor)$ и т. д..

[Sdy]

arseniiv, спасибо за ответ.

arseniiv в сообщении #1383622 писал(а):

ограничиться только множествами $[0..a) := \{ n : 0\leqslant n<a \}$, $a\geqslant0$,

Просто в таком случае мне нужно доказать, что любой отрезок из целых чисел $[a...b]$ я могу отразить взаимно однозначно на $[0...c-1]$.
$\triangle$
Я могу это сделать так :
1. $a>0 \wedge b > 0 \Rightarrow s\to s-\left\lvert a \right\rvert$
2.$ a < 0 \wedge (b \geqslant 0 \vee b \leqslant 0) \Rightarrow s\to s+\left\lvert a \right\rvert$
То что в обеих случаях - биекция - я проверил.
$\triangle$.
Но мне не нравится, что в таком случае, например $[-7;-6;-5]\to[0;1;2]$, то есть, что у нас изменилось количество четных/нечётных чисел. Теоритически, это никак не влияет на доказательство, по крайне мере, я пока не понял, как это может помешать, ведь мы играем в любом случае от $S \mod 2$, и вроде бы дальше уже можно рассуждать таким же образом, как это делал я.

[Sdy]

Хотел бы уточнить, так как для меня это не совсем очевидно.

arseniiv в сообщении #1383534 писал(а):

Кстати можно подоказывать обобщение: если $S = \{n : 0\leqslant n<a, n\in\mathbb Z\}$, $a\geqslant0$, и $S_i = S\cap(N\mathbb Z + i)$, $N>0$, то $\lfloor a/N\rfloor\leqslant|S_i|\leqslant\lceil a/N\rceil$. ($a, N, i$ целые.)

Правильно ли я понимаю, что ещё есть ограничение $0 \leqslant i < N$, а также, что мы доказываем $\forall N, a$?
То есть словами данное утверждение можно озвучить как
"Какой бы отрезок целых чисел мы не взяли, количество чисел, принадлежащих к разным классам по остаткам от деления на $0 < N < \infty$ отличается максимум на 1"? (У меня довольно коряво получается, но я пока только начинаю знакомство с теорий чисел и не знаю, как более правильно назвать эти "классы по остаткам").

[arseniiv]

Sdy в сообщении #1383700 писал(а):

Но мне не нравится, что в таком случае, например $[-7;-6;-5]\to[0;1;2]$, то есть, что у нас изменилось количество четных/нечётных чисел.

Да, они поменяются, но как я уже писал выше, просто переставятся как-нибудь друг с другом. А именно, $|(S+k)\cap(N\mathbb Z+i)| = |S\cap(N\mathbb Z+i-k)|$.

Sdy в сообщении #1383711 писал(а):

Правильно ли я понимаю, что ещё есть ограничение $0 \leqslant i < N$, а также, что мы доказываем $\forall N, a$?

Второе да, потому что они произвольные, и первое тоже да, потому что $N\mathbb Z + i = N\mathbb Z + i\bmod N$.

-- Вс мар 24, 2019 17:19:47 --

Sdy в сообщении #1383711 писал(а):

То есть словами данное утверждение можно озвучить как
"Какой бы отрезок целых чисел мы не взяли, количество чисел, принадлежащих к разным классам по остаткам от деления на $0 < N < \infty$ отличается максимум на 1"?

Да, хотя отсюда может быть не очень просто получить, например, что если $a$ делится на $N$, $\lfloor a/N\rfloor = \lceil a/N\rceil = a/N$, то есть в таком случае мы точно знаем, что все те классы будут иметь одинаковое число элементов.

Sdy в сообщении #1383711 писал(а):

У меня довольно коряво получается, но я пока только начинаю знакомство с теорий чисел и не знаю, как более правильно назвать эти "классы по остаткам"

Сами $N\mathbb Z + i$ целиком называются, например, классами вычетов по модулю $N$, но название для их пересечения с произвольным $S$, даже отрезком, я лично не встречал (но я теории чисел не знаю — то, что тут у нас, это ещё цветочки по сравнению с тем, что там творится!).

[Sdy]

arseniiv, спасибо за ответ.
Утверждение.
Если $S = \{n : 0\leqslant n<a, n\in\mathbb Z\}$, $a\geqslant0$, и $S_i = S\cap(N\mathbb Z + i)$, $N>0$, то $\lfloor a/N\rfloor\leqslant|S_i|\leqslant\lceil a/N\rceil$. ($a, N, i$ целые.)
То есть, необходимо доказать, что какой бы отрезок целых чисел мы не взяли, количество элементов классов по различным остаткам от деления на $0 < N < \infty$ отличается максимум на 1.
Доказательство.
Пусть мы имеем произвольное $S = \left\lbrace0,...,a-1\right\rbrace$ (если мы имеем отрезок из целых чисел,имеющий другой вид - построим биекцию), докажем утверждение для любого $N$.
0.Если $N > a$, то каждое из наших множеств будет состоять из одного элемента, значит утверждение верно. С размерностью - ясно, что мы получаем потолок от $a/N$, так как $a < N$.
Пусть $ 1 \leqslant N \leqslant a$
1.$card(S) \mod N = 0$
Тогда просто разобьём наше множество на $N$-ки элементов, в каждой $N$-ке одинаковое количество представителей каждого класса, значит утверждение верно. При этом $card(S_i) = a/N, \forall i$.
2.Если $card(S) \mod N \ne 0$, то оно равно $1 \vee 2 ... \vee N-1$. Опять же, пока представителей $S$ хватает - делим на $N$-ки, в них равное количество элементов из разных классов. Останется одна "недо"-$N$-ка, в которой $1 \vee 2 ... \vee N-1$ представитель. Тогда либо представителей первого класса больше на 1, чем представителей других классов, либо представителей первого и второго класса больше, чем остальных,...,либо только представителей последнего класса на 1 меньше, чем других. Значит и тут утверждение верно. С размерностью тоже ясно - количество представителей тех классов, что встречаются в "недо"-$N$-ке будет равно потолку от $a/N$, а тех что не встречаются - полу.
Больше случаев нет $\Rightarrow$ утверждение доказано.$\triangle$
Прошу вас проверить это доказательство,хотя идейно я просто обобщил доказательство для $N = 3$.

[arseniiv]

Если никто не захочет раньше, чуть позже.

[Sdy]

(Оффтоп)

arseniiv, в любом случае - спасибо за помощь.