История изменений

верно то, что 1 бит теряется при любой бинарной операции.

Это не верно.

Для множества D бинарная операция (по определению) это функция f : D * D -> D. Их всего |D| ^ (|D| ^ 2) разных. Ты утверждаешь, что для любого множества D и любой такой функции... Что?

Под D нужно n = log(|D|) бит (тоже по определению). Под первый _или_ второй аргумент — n бит. Под первый _и_ второй — 2 n (log(|D * D|) = log(|D| ^ 2) = 2 log(|D|)). Под результат — 0 <= log(|Im(f)|) <= n бит, то есть столько же или на сколько угодно меньше, не на 1.

Дальше, если 1 < |D| < aleph_0, то бинарная операция не может быть вложением/биекцией, то есть аргументы не восстанавливаются однозначно из результата. Это всегда так — тут не о чем говорить (и вообще — коммутативная операция по определению не вложение/биекция, в случае любого D, так как забывает эти самые ярлычки). Между отрезком и его квадратом есть соответствие только в случае если их нет, они точки или дискретные или непрерывные линия и плоскость.

Ещё у тебя может быть идеальное M с операциями (пусть натуральные числа) и модельное D (регистр), тогда из f : M * M -> M делаем f' : D * D -> M и видим, что log(|Im(f')|) может быть относительно n чем угодно — никаких потерь единиц.

это если ты ярлычки к аргументам приклеишь: «первый» и «второй». Без ярлычков не взлетит.

Это называется декартово произведение.

В случае min : D * D -> D образ это ровно D, под результат нужно ровно n бит.

n != n + 1.

операция возвращающая константу выдаёт _всегда_ 0 бит

Я не стал этого говорить, но да — log(1) = 0.

0 != n + 1.

не удваивает.

Строго говоря не удваивает (есть эквивалентные разбиения на множители, так что часть информации теряется), но и не увеличивает на единицу:

> let n = 64
> logBase 2 n
6.0
> logBase 2 $ fromIntegral $ length $ nub [x * y | x <- [1 .. n], y <- [1 .. n]]
10.302638923787553

11 != 6 + 1.

Я больше про то, что крайний случай это вложение D * D в M (D < M) — Im(f) ~ D * D. То есть правильное утверждение — при сужении любой бинарной операции с M на D всегда _достаточно_ вдвое большего количества бит под результат по отношению к битности (одного из) аргумента (D).

2 n != n + 1.

Заметь, никаких систем счислений, рациональных чисел и расширений полей Галуа — примитивные рассуждения про любые множества, операции и информацию (определённую через мощность, то есть как количество состояний которое нужно закодировать строкой из такого-то количества символов).

верно то, что 1 бит теряется при любой бинарной операции.

Это не верно.

Для множества D бинарная операция (по определению) это функция f : D * D -> D. Их всего |D| ^ (|D| ^ 2) разных. Ты утверждаешь, что для любого множества D и любой такой функции... Что?

Под D нужно n = log(|D|) бит (тоже по определению). Под первый _или_ второй аргумент — n бит. Под первый _и_ второй — 2 n (log(|D * D|) = log(|D| ^ 2) = 2 log(|D|)). Под результат — 0 <= log(|Im(f)|) <= n бит, то есть столько же или на сколько угодно меньше, не на 1.

Дальше, если 1 < |D| < aleph_0, то бинарная операция не может быть вложением/биекцией, то есть аргументы не восстанавливаются однозначно из результат. Это всегда так — тут не о чем говорить (и вообще — коммутативная операция по определению не вложение/биекция, в случае любого D, так как забывает эти самые ярлычки). Между отрезком и его квадратом есть соответствие только в случае если их нет, они точки или дискретные или непрерывные линия и плоскость.

Ещё у тебя может быть идеальное M с операциями (пусть натуральные числа) и модельное D (регистр), тогда из f : M * M -> M делаем f' : D * D -> M и видим, что log(|Im(f')|) может быть относительно n чем угодно — никаких потерь единиц.

это если ты ярлычки к аргументам приклеишь: «первый» и «второй». Без ярлычков не взлетит.

Это называется декартово произведение.

В случае min : D * D -> D образ это ровно D, под результат нужно ровно n бит.

n != n + 1.

операция возвращающая константу выдаёт _всегда_ 0 бит

Я не стал этого говорить, но да — log(1) = 0.

0 != n + 1.

не удваивает.

Строго говоря не удваивает (есть эквивалентные разбиения на множители, так что часть информации теряется), но и не увеличивает на единицу:

> let n = 64
> logBase 2 n
6.0
> logBase 2 $ fromIntegral $ length $ nub [x * y | x <- [1 .. n], y <- [1 .. n]]
10.302638923787553

11 != 6 + 1.

Я больше про то, что крайний случай это вложение D * D в M (D < M) при Im(f) ~ D * D, то есть правильное утверждение — при сужении любой бинарной операции с M на D _достаточно_ вдвое большее количество бит под результат по отношению к битности (одного из) аргумента (D).

2 n != n + 1.

Заметь, никаких систем счислений, рациональных чисел и расширений полей Галуа — примитивные рассуждения про любые множества, операции и информацию (определённую через мощность, то есть как количество состояний которое нужно закодировать строкой из такого-то количества символов).

верно то, что 1 бит теряется при любой бинарной операции.

Это не верно.

Для множества D бинарная операция (по определению) это функция f : D * D -> D. Их всего |D| ^ (|D| ^ 2) разных. Ты утверждаешь, что для любого множества D и любой такой функции... Что?

Под D нужно n = log(|D|) бит (тоже по определению). Под первый _или_ второй аргумент — n бит. Под первый _и_ второй — 2 n (log(|D * D|) = log(|D| ^ 2) = 2 log(|D|)). Под результат — 0 <= log(|Im(f)|) <= n бит, то есть столько же или на сколько угодно меньше, не на 1.

Дальше, если 1 < |D| < aleph_0, то бинарная операция не может быть вложением/биекцией, то есть аргументы не восстанавливаются однозначно из результат. Это всегда так — тут не о чем говорить (и вообще — коммутативная операция по определению не вложение/биекция, в случае любого D, так как забывает эти самые ярлычки). Между отрезком и его квадратом есть соответствие только в случае если их нет, они точки или дискретные или непрерывные линия и плоскость.

Ещё у тебя может быть идеальное M с операциями (пусть натуральные числа) и модельное D (регистр), тогда из f : M * M -> M делаем f' : D * D -> M и видим, что log(|Im(f')|) может быть относительно n чем угодно — никаких потерь единиц.

это если ты ярлычки к аргументам приклеишь: «первый» и «второй». Без ярлычков не взлетит.

Это называется декартово произведение.

В случае min : D * D -> D образ это ровно D, под результат нужно ровно n бит.

n != n + 1.

операция возвращающая константу выдаёт _всегда_ 0 бит

Я не стал этого говорить, но да — log(1) = 0.

0 != n + 1.

не удваивает.

Строго говоря не удваивает, но и не увеличивает на единицу:

> let n = 64
> logBase 2 n
6.0
> logBase 2 $ fromIntegral $ length $ nub [x * y | x <- [1 .. n], y <- [1 .. n]]
10.302638923787553

11 != 6 + 1.

Я больше про то, что крайний случай это вложение D * D в M (D < M) при Im(f) ~ D * D, то есть правильное утверждение — при сужении любой бинарной операции с M на D _достаточно_ вдвое большее количество бит под результат по отношению к битности (одного из) аргумента (D).

2 n != n + 1.

Заметь, никаких систем счислений, рациональных чисел и расширений полей Галуа — примитивные рассуждения про любые множества, операции и информацию (определённую через мощность, то есть как количество состояний которое нужно закодировать строкой из такого-то количества символов).