В выкладках по комбинаторике можно часто встретить фразу: "каждому элементу слева соответствует ровно 1 элемент справа и наоборот => мощности множеств одинаковые". Кажется, что того, что из каждого элемента обоих множеств выходит ровно 1 стрелка в элемент противоположного множества недостаточно для биекции и упускается одна очевидная вещь.
Пример: пусть есть множество строк S и множество графов G. Через элементы S кодируем какие-то графы и хотим их насчитать. Далее какими-то рассуждениями приходим к выводу, что каждому s из S соответствует ровно 1 g из G и наоборот(то есть из каждого элемента обоих множеств выходит ровно 1 стрелка в элемент противоположного множества). Но ведь этого недостаточно, пример:
s1<->g1
s2<->g2
s3<->g3
s2<-g4
Вот если бы помимо условия на стрелки было бы ещё утверждение, что из S нету недостижимых (по стрелкам) вершин в G и наоборот, тогда легко получить противоречие: если мощности неравномощны, тогда в большем по количеству элементов множестве хотя бы одна вершина окажется без входящий стрелки(а это противоречие с тем что все вершины достижимы), значит множества не могут иметь разные мощности.
Вопрос: правильно ли я понимаю, что авторы обычно пропускают утверждение о "достижимости" (видимо считая это очевидным), то есть о том, что, на примере графов, нет графов, которые нельзя сконструировать по строке из S и нет строк, которые нельзя сконструировать по графу из G ?
shurshur, просто в комбинаторных "наоборот" это тоже какая-то цепочка рассуждений, только в другую сторону, но смысл одинаковый - из обоих рассуждений следует, что слева из каждого элемента выходит ровно одна стрелка и справа из каждого элемента выходит ровно одна стрелка, а также то что авторы обычно скипают - что отображение сюрьективно
Пример:
Сколькими способами можно разложить пять одинаковых шаров по трём различным ящикам? На число шаров в ящике ограничений нет.
Представим себе, что ящики стоят вплотную друг к другу. Три таких ящика — это фактически две перегородки между ними. Обозначим шар нулём, а перегородку — единицей. Тогда любому способу раскладывания пяти шаров по трём ящикам однозначно соответствует последовательность из пяти нулей и двух единиц; и наоборот, каждая такая последовательность однозначно определяет некоторый способ раскладывания. Например, 0010010 означает, что в первом ящике лежат два шара, во втором — два шара, в третьем — один шар; последовательность 0000011 соответствует случаю, когда все пять шаров лежат в первом ящике.
floppa322, это не вызывает вообще никаких проблем, потому что если |A|⩽|B| и |B|⩽|A|, как написано в утверждении. то |A|=|B|. Это прям на первой же лекции по понятию мощности множества объясняют.
shurshur, тут к сожалению из того что написано не следует, что |A|⩽|B|, если убрать сюрьективность, которая у автора неявно фигурирует, то возможно такое:
Элементы множества A можно отобразить в подмножество (различные элементы) множества B. Это и есть |A|⩽|B| по определению. После "и наоборот" мы получаем |B|⩽|A| и как следствие |A|=|B|.
Кажется, что то, что оно отображается именно в различные элементы (то есть нет элемента ни в S ни в G, в который входит 2 и более стрелок) следует из утверждений, что из S выходит из каждого элемента ровно по одной стрелке в G и из G из каждого элемента выходит ровно по одной стрелке в S, и то что f и h сюрьекции, но не напрямую из наличия f: "Тогда любому способу раскладывания пяти шаров по трём ящикам однозначно соответствует последовательность из пяти нулей и двух единиц"
Если брать два независимых отображения (f: S→G и h: G→S) — ты прав, этого недостаточно, и пример рабочий.
Но в комбинаторике имеют в виду одно f: S→G, у которого "ровно 1 g на каждый s" (функция) + "ровно 1 s на каждый g" — это про прообразы того же f, т.е. инъективность + сюръективность. Никакой второй независимой h нет. "Достижимость" и есть сюръективность, она прямо зашита в "каждый g покрыт ровно 1 стрелкой".
Пример из одного учебника, похожим которому можно найти много:
Сколькими способами можно разложить пять одинаковых шаров по трём различным ящикам? На число шаров в ящике ограничений нет.
Представим себе, что ящики стоят вплотную друг к другу. Три таких ящика — это фактически две перегородки между ними. Обозначим шар нулём, а перегородку — единицей. Тогда любому способу раскладывания пяти шаров по трём ящикам однозначно соответствует последовательность из пяти нулей и двух единиц; и наоборот, каждая такая последовательность однозначно определяет некоторый способ раскладывания. Например, 0010010 означает, что в первом ящике лежат два шара, во втором — два шара, в третьем — один шар; последовательность 0000011 соответствует случаю, когда все пять шаров лежат в первом ящике.
Здесь же как раз упоминается про f и h? Или может быть я что-то не понимаю
да, именно — когда пишут «каждому g соответствует ровно 1 s», это и есть сюръективность без слова «сюръективность». Авторы не называют, но де-факто утверждают.
Простой
