Sunday, December 09, 2012

Аксиомы арифметики

Почти без сокращений.


Этот текст -- популярное изложение вопроса о том, на каких основаниях строится такая наука как арифметика...Всякий, кто учился в школе, слышал о том, что в геометрии есть аксиомы. Ну, типа того, что через две различные точки проходит одна и только одна прямая. Полный список аксиом геометрии довольно длинный, и в подробностях это дело в школе не изучается. Но все или почти все так или иначе знают, что на основании аксиом при помощи логических рассуждений доказывают разные теоремы. Например, знаменитую теорему Пифагора.

А как дело обстоит в арифметике?

Ниже есть продолжение.

У многих это слово ассоциируется с любимой таблицей умножения, действиями над числами вроде сложения или умножения "столбиком". Как ни странно, в школе ни слова не говорят о том, что арифметика тоже может быть построена на аксиомах подобно тому, как это делается в геометрии. При этом известные арифметические законы не упадут к нам с неба, а будут выведены из принятых аксиом. Даже такой факт как "дважды два -- четыре" доказывается , хотя само доказательство весьма простое.

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

Я предлагаю сделать сначала несколько простых наблюдений, а потом выписать в явном виде все аксиомы арифметики, которых будет всего пять. Мы возьмём за основу "школьную" версию натурального ряда, считая, что он начинается с единицы. (В некоторых версиях удобнее начинать его с нуля, но это специально оговаривается.)

Итак, посмотрим на натуральный ряд: 1, 2, 3, 4, 5, ... и так далее. Что мы можем заметить? В начале стоит число 1, а за каждым числом стоит следующее. Далее, у каждого числа кроме единицы имеется предыдущее. Эти простейшие замечания охватывают четыре из пяти нужных нам аксиом. О пятой аксиоме, наиболее важной из всех, следует поговорить особо. Пока что мы её можем сформулировать несколько упрощённо, сказав, что до любого натурального числа можно досчитать (хотя бы в принципе), начиная с единицы и переходя от очередного числа к следующему за ним.

Сейчас мы немного отвлечёмся и рассмотрим такую известную задачу: как быстро найти сумму 1+2+...+100, т.е. сложить числа от 1 до 100? Один из способов состоит в том, чтобы сгруппировать первое число с последним, второе -- с предпоследним и так далее. Всего получится 50 пар, а в каждой паре сумма чисел составит 101. Поэтому вся сумма равняется 5050. Нетрудно проверить, что на самом деле сумма первых n натуральных чисел составит n(n+1)/2 для любого n. То есть мы имеем такую формулу: 1+2+...+n = n(n+1)/2. Это один из примеров утверждения, справедливого для всех натуральных чисел. Можно привести и другие примеры. Возьмём известное правило: от перестановки слагаемых сумма не меняется. В виде формулы мы можем записать этот закон так: a+b=b+a (опять же для любых натуральных чисел a и b).

Итак, мы видим, что ситуация, когда нечто требуется доказать для всех натуральных чисел, встречается весьма часто. Поскольку натуральных чисел бесконечно много, то и частных утверждений приходится доказывать бесконечно много. Возьмём в качестве примера упоминавшийся выше закон a+b=b+a. Число a мы зафиксируем, а число b будем менять. Мы получим бесконечное число утверждений: a+1=1+a, a+2=2+a, a+3=3+a, ... и так далее. Как можно в принципе доказать разом бесконечное число утверждений? Представим себе, что мы доказали самое первое. Затем из него вывели второе. Затем из второго вывели третье, и так до бесконечности. Идея состоит в том, что если каждое следующее утверждение выводится из предыдущего одним и тем же способом, то достаточно доказать первое утверждение, а потом объяснить, каким образом из любого утверждения списка выводится следующее за ним.

Сейчас нам удобно будет ввести важное для дальнейшего обозначение. Для любого натурального числа n мы обозначим следующее за ним число через n'. Может возникнуть вопрос: почему n', а не n+1? Ведь n' на самом деле равно n+1. Это правда, но мы при построении аксиоматики будем базироваться только на понятии единицы и понятии следующего натурального числа. Сложение -- это уже отдельная операция, которая будет определена после того, как мы выпишем все аксиомы. То же касается умножения.

Итак, вернёмся к примеру из предыдущего абзаца. Для того, чтобы доказать бесконечную цепочку однотипных утверждений, нам достаточно научиться решать две задачи, которые мы будем называть "Базой" и "Шагом". Базой будет называться доказательство первого утверждения списка. Шагом -- переход от одного утверждения списка к следующему за ним. В рассматриваемом примере это выглядит так:

База. Требуется доказать, что a+1=1+a.
Шаг. Известно, что a+b=b+a для некоторых a,b. Требуется вывести отсюда, что a+b'=b'+a.

Такой приём, который мы здесь использовали, называется методом математической индукции. А теперь дадим полный список аксиом арифметики. Их называют аксиомами Пеано по имени итальянского математика Джузеппе Пеано (1858--1932).

(А1) 1 есть натуральное число.
(А2) Для любого натурального числа n имеется натуральное число, обозначаемое n' и называемое числом, следующим за n.
(А3) Если m'=n' для каких-либо натуральных чисел m,n, то m=n.
(А4) Число 1 не следует ни за каким натуральным числом, т.е. n' никогда не равно 1.
(А5) Если число 1 обладает некоторым свойством P, и для любого числа n, обладающего свойством P, следующее за ним число n' также обладает свойством P, то всякое натуральное число обладает свойством P.

Последняя аксиома называется принципом математической индукции. По сути она и означает, что до любого числа можно досчитать. Метод доказательства, который мы описали выше, как раз и основан на этой аксиоме. То есть если мы хотим доказать что неким свойством P обладают все натуральные числа, то мы осуществляем две проверки. Сначала проверяем, что 1 обладает свойством P -- "База", а затем предполагаем, что какое-то число n уже обладает свойством P и доказываем, что следующее за ним число n' также обладает свойством P -- "Шаг". (Грубо говоря, мы при этом "шагаем" от n к n'.)

Помимо аксиом и теорем в математике также используются определения. Мы имеем право использовать пока только число 1 и применять операцию перехода к следующему числу. Что такое число 2? Пока что оно не определено. Но мы можем дать его определение, сказав, что 2 -- это число, следующее за 1, т.е. 1'. Теперь мы знаем, что такое 2 и имеем право определить число 3 при помощи равенства 3=2'. Понятно, что далее мы определяем число 4 как 3' и так далее. Все числа оказываются теперь в нашем распоряжении.

Пока что мы не умеем ни складывать, ни умножать числа. Поэтому нам потребуется определить операцию сложения, то есть придать смысл записи x+y, где x,y -- натуральные числа. Зафиксируем x и определим последовательно значения выражений x+1, x+2, x+3, ... и так далее. Здесь нам на помощь снова приходит идея индукции. Какова первая задача -- "База"? Надо определить значение выражения x+1. Как это сделать -- понятно: нужно положить по определению, что x+1 есть не что иное как x'. Вторая задача -- это "Шаг". Мы будем "шагать" от числа y к числу y', т.е. будем считать, что значение выражения x+y для данных двух чисел уже определено, и теперь надо определить, чему равно значение выражения x+y'. Легко понять, что это значение на единицу превышает x+y, т.е. следует за ним. И потому за x+y' нам следует принять не что иное как (x+y)'. Выпишем отдельно получившееся определение сложения:

(S1) x+1=x'
(S2) x+y'=(x+y)'

По сути дела, мы последовательно учимся прибавлять к данному числу x все числа: 1, 2, 3, ... . Правило (S1) показывает нам, как прибавить единицу. Чтобы прибавить двойку, т.е. число 1', мы пользуемся правилом (S2), уже зная, что такое x+1. После этого мы знаем, что такое x+2 и по правилу (S2) находим x+3, т.е. x+2'. Тем самым сумму любых двух чисел мы определили.

Осталось определить операцию умножения, т.е. научиться находить произведение x*y любых натуральных чисел. Мы действуем аналогично. Сначала определим выражение x*1 (всем понятно, что оно равно x). Это приводит к правилу (P1) ниже. Далее мы должны предположить, что для каких-то чисел уже известно, что такое x*y, и требуется придать смысл выражению x*y'. Чему оно должно быть равно? Поскольку мы хотим построить обычную арифметику, то должны выполняться все привычные для нас законы. В частности, должно выполняться правило раскрытия скобок. Это значит, что x*y'=x*(y+1)=x*y+x*1=x*y+x. Заметим, что мы здесь не пользовались законом раскрытия скобок (он у нас не доказан), а лишь следовали нашей надежде, что он будет выполняться. В соответствии с ним произведение x*y' должно быть определено именно так, как мы это сделали. Итак, вот определение умножения:


(P1) x*1=x
(P2) x*y'=x*y+x

Обратим внимание на то, что выражение в правой части равенства (P2) имеет смысл. В самом деле, значение x*y для данных чисел определено, а складывать мы умеем какие угодно числа.

Теперь настал торжественный момент. Мы в состоянии доказать (т.е. вывести из аксиом) одно из самых знаменитых равенств: "дважды два -- четыре". При этом, разумеется, мы вовсю будем пользоваться определениями: как самих конкретных чисел -- 2, 3, 4, так и определениями для суммы и произведения, которые у нас выписаны в виде правил.

Теорема. 2*2 = 4.

Доказательство. Мы выпишем цепочку равенств, а затем объясним каждый из переходов: 2*2 = 2*1' = 2*1+2 = 2+2 = 2+1' = (2+1)' = (2')' = 3' = 4. Здесь было использовано восемь равенств. Отметим, что в процессе доказательства мы сначала пришли к выводу, что 2*2=2+2 и лишь затем к тому, что ответом будет 4.

Проанализируем каждое из равенств по отдельности. Сначала мы использовали определение двойки: 2=1'. Второй знак равенства использован на основании правила (P2) при x=2, y=1. Это естественно, так как перед нами стояла задача умножить 2 на 1'. Далее мы воспользовались правилом (P1) при x=2, заменяя 2*1 на 2. Теперь мы должны вычислить 2+2. Второе слагаемое по определению равно 1', т.е. нужно выполнить действие 2+1'. В этом нам поможет правило (S2) при x=2, y=1. Теперь правило (S1) поможет нам вычислить сумму 2+1. Мы получим 2', т.е. 3 в силу определения тройки. Наконец, последний переход основан на использовании определения числа 4. Теорема доказана!

Вот какие "глубины" скрываются за столь простыми фактами. Ясно, что вся таблица умножения может быть получена таким же образом (т.е. каждое равенство из таблицы умножения -- это отдельная теорема).

Возникает вопрос: а что же идёт дальше? На очереди -- доказательство основных законов арифметики , а именно:

1. (a+b)+c=a+(b+c) -- сочетательный (ассоциативный) закон сложения
2. a+b=b+a -- переместительный (коммутативный) закон сложения
3. (a+b)*c=a*c + b*c -- распределительный (дистрибутивный) закон
4. (a*b)*c=a*(b*c) -- сочетательный (ассоциативный) закон умножения
5. a*b=b*a -- переместительный (коммутативный) закон умножения

Заметим, что при кажущейся "простоте" последний закон имеет довольно длинное (хотя и вполне тривиальное) доказательство, основанное на предыдущих законах.

Все законы доказываются примерно по одной и той же схеме -- методом математической индукции. Проиллюстрируем это на примере первого из них.

Нам требуется доказать, что (a+b)+c = a+(b+c) для любых натуральных чисел a,b,c. Значения первых двух чисел зафиксируем, а третье число c будет последовательно принимать значения c=1, c=2, c=3, ... и так далее. В соответствии с принципом математической индукции достаточно доказать два утверждения: "Базу" (c=1) и "Шаг" (от c к c').

База. Здесь c=1. Требуется доказать, что (a+b)+1=a+(b+1). Действительно, (a+b)+1=(a+b)'=a+b'=a+(b+1). Здесь мы сначала использовали правило (S1) при x=a+b, поменяв местами правую и левую части. Второй переход основан на правиле (S2). Третий переход -- это правило (S1) при x=b.

Шаг. Пусть дано, что (a+b)+c=a+(b+c) для некоторых чисел a,b,c. Требуется доказать, что (a+b)+c'=a+(b+c'). Доказательство: (a+b)+c'=((a+b)+c)'=(a+(b+c))'=a+(b+c)'=a+(b+c'). Здесь сначала использовано (S2) при x=a+b, y=c, затем данное нам предположение о том, что (a+b)+c=a+(b+c), потом вновь правило (S2) при x=a, y=b+c и на последнем шаге -- снова (S2) при x=b, y=c.

На этом пути доказываются и другие законы. Заметим, что при доказательстве "Базы" для случая второго из законов мы приходим к необходимости проверить равенство a+1=1+a. Оно само по себе содержит бесконечно много утверждений, и в таких случаях снова работает метод математической индукции. То есть наиболее простой путь состоит в том, чтобы сначала доказать лемму о том, что 1+a=a' (при помощи индукции), а потом воспользоваться леммой в ходе доказательства переместительного закона сложения.

Этими законами всё не ограничивается. Так, часто используются следующие законы сокращения:

6. из условия a+c=b+c следует a=b -- закон сокращения для сложения
7. из условия a*c=b*c следует a=b -- закон сокращения для умножения

(Заметим, что закон 6 верен для любых чисел, а закон 7 -- нет, так как на ноль сокращать нельзя. Но в нашей ситуации все числа положительны, и закон справедлив.) Кстати, мы очень часто использовали аксиому (A5); также мы использовали аксиомы (А1) и (А2), говоря о единице и о взятии следующего числа. Аксиомы (А3) и (А4) не использовались; они нужны для доказательства законов сокращения. Причём закон сокращения для умножения не так-то просто доказать "в лоб", и удобнее всего для начала ввести неравенства и доказать их основные свойства. Проиллюстрируем это на примере определения отношения "меньше". Что означает, что число x меньше числа y? Ясно, что большее из чисел равно сумме меньшего из чисел и ещё какого-то (положительного) числа. Поэтому определение выглядит так: считаем, что x меньше y, если найдётся такое (натуральное) число z, что x+z=y.

Вот так строится арифметика. Основные понятия, аксиомы, определения, теоремы...

http://falcao.livejournal.com/23149.html

מכת החנונים - זוכה התחרות בינלאומית בהוליווד כ"הסרט הזר המצליח של השנה". (Hebrew)

Latma: הצד המרכזי (Hebrew)

ערוץ 2: רוני דניאל על נשק כימי סורי (Hebrew)




בישראל מנהלים המון דיונים לגבי מה לעשות עם הנשק הבלתי-קונבנציונלי בסוריה, וישנן שלוש מדרגות לשיקול הדעת בהנהגה הישראלית. הראשונה: אם אסד יפעיל את הכוח הזה נגד המורים - ישראל לא תתערב. אם הוא ייפול בידי המורדים - ספק אם ישראל תתערב. אך עם זאת, אם ייפול הנשק הכימי בידיהם של ארגוני טרור - ישראל תהיה חייבת לפעול. משום שאם המהלך הזה יקרום עור וגידים - אז מדובר בבעיה ישראלית.

http://www.mako.co.il/news-columns/Article-10242bf7ab67b31004.htm

10 канал: Хаим Рамон и Ципи Ливни стоят за партией Давида Кона (Hebrew)



המלחמה על הקול הרוסי: רמון ולבני סייעו בהקמת מפלגה שצפויה לקחת קולות מליברמן


אתמול נסגרו רשימות המפלגות לקראת הבחירות לכנסת ה-19 וממש בדקה האחרונה נרשמה מפלגה בשם "הישראלים". העומד בראשה הוא דוד קון, מגיש בכיר ופופולרי בערוץ 9, המוכר מאוד בקרב הציבור הרוסי. מאחורי הקמתה של המפלגה נמצאים רמון ולבני שמקווים שבעזרת הפופולריות של קון הם יצליחו להעביר חלק ממצביעי ישראל ביתנו ובכך אולי לחזק את גוש המרכז-שמאל מול רשימת הליכוד ביתנו

http://news.nana10.co.il/Article/?ArticleID=942902

Об особенностях подсчёта голосов. Часть VI

Часть I избирательная явка и действительные голоса
Часть II эквивалентность подсчёта
Часть III электоральный барьер
Часть IV метод Бадера-Офера
Часть V преимущество больших списков
Часть VI реальный пример


Как известно, на выборах 22 января мы выбирает законодательную власть, не исполнительную. Тут я написал краткий путеводитель по израильской политической карте. Тут мы разобрались кто формирует правительство после выборов в Кнессет.

Мы разобрались с избирательной явкой и действительными голосами в первой части, в третьей части разобрались с электоральным барьером, а во-второй доказали эквивалентность утверждений, что недействительный голос был выброшен в мусорное ведро и пропорционально распределён между всеми партиями, прошедшими электоральный барьер.

Четвёртая часть была посвящена методу Бадера-Офера об остаточном распределении мандатов. В пятой части мы доказали, что у списка, за который было отдано наибольшее количество голосов, есть преимущество при подсчёте по системе Бадера-Офера.


В этой заметке я приведу реальный пример с выборов 2009 г. (в той его части, где используется метод Бадера Офера).

Ниже есть продолжение.

На выборах 2009 г., выборов Кнессета 19 созыва, всего имевших права голоса было 5 278 985, из них проголосовали 3 416 587 (избирательная явка составила $\frac{3 416 587}{5 278 985} \approx 0,6472 = 64,72%$), недействительных бюллетеней было 43 097 (в ссылке почему-то приведено число 43 091), действительных -
$3 416 587 - 43 097 = 3 373 490$.

Далее определятся электоральный барьер. Он равен 2% от действительных голосов, т.е. $3 373 490*0,02=67 469,8 \approx 67 470$ (округляем вверх, так как надо набрать больше этого числа).

Далее, все списки, которые не набрали в абсолютном выражение как минимум 67 470 вычеркиваем, а голоса, поданные за них считаем недействительными. Всего таких голосов 103 904. Осталось, действительных голосов $3 373 490-103 904=3 269 586$.

Итак, ниже представлена таблица после того, как были выброшены все недействительные голоса, а также голоса, поданные за все списки, не прошедшие электоральный барьер.

Количество голосов участвующий в распределении - 3 269 586.
Количество мандатов - 120.
Электоральный коэффициент одного парламентского мандата
$\frac{3 269 586}{120}=27 246.55 \approx 27 247$ (в ссылке приведено число 27 246, но очевидно, нужно округлять вверх, т.к. мы потом будет делить на это число, чтобы получить нижнюю оценку количества мандатов. $n<n'$ <=> $\frac{1}{n}>\frac{1}{n'}$ <=> $\frac{A}{n}>\frac{A}{n'}$)


Список Голоса Коэффициент Мандаты
אמת 334 900 27 247 12+0,29...
ב 96 765 27 247 3+0,55...
ג 147 954 27 247 5+0,43...
ד 83 739 27 247 3+0,07..
ו 112 130 27 247 4+0,115..
ט 112 570 27 247 4+0,13..
כן 758 032 27 247 27+0,82..
ל 394 577 27 247 14+0,48..
מחל 729 054 27 247 26+0,757..
מרצ 99 611 27 247 3+0,655..
עם 113 954 27 247 4+0,18..
שס 286 300 27 247 10+0,50..

Может показаться, что у списков כן, מחל, מרץ,ב можно "округлить" мандаты до целого числа. Но это неверно. Хочу заметить, что у списков כן, מחל не хватает совсем немного до целого мандата. Здесь мы показали, что из этого нельзя заключить, что именно они получат остаточные голоса, однако, забегая вперёд скажу, что в этом случае они-таки получат. А вот списки ב,מרצ у которых только едва больше половины мандата-таки не получат.

Всего распределены 12+3+5+4+4+27+14+26+6+4+10=115 мандатов, осталось распределить 120-115=5 мандатов.


Итак, перед тем, как применить метод Бадера-Офера, нужно учесть договора об остаточных голосах. Такие договора были заключены между списками:

אמת + מרצ s 334 900+99 611=434 511, 12+3=15
ב + ט s 96 765+112 570=209 335, 3+4=7
עם + ו s 113 954+112 130=226 084, 4+4=8
ל + מחל s 729 054+394 577=1 123 631, 26+14=40
שס + ג s 286 300+147 954=434 254, 10+5=15

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

Имя Список Голоса Мандаты
Ликуд+НДИ מחל+ל 1 123 631 40
Кадима כן 758 032 27
Авода+Мерец אמת+מרצ 434 511 15
Шас+ЯТ שס+ג 434 254 15
РААМ-ТААЛ+ХАДАШ עם+ו 226 084 8
ИЛ+Байт Еhуди ב+ט 209 335 7
БАЛАД ד 83 739 3

НДИ=Наш Дом Израиль (Исраэль Бэйтейну)
ИЛ=hа-ихуд hа-леуми
ЯТ=Яhадут hа-тора

Далее, мы делаем перерасчет "цены" 1 мандата, если бы каждый получил бы ещё 1 мандат. Выбираем максимальную "цену", помечаем жирным, и продолжаем, пока не распределим все оставшихся 5 мандатов. Все округления вниз.




Список Голоса Мандаты Цена-1 Цена-2 Цена-3
מחל+ל 1123631 40 $\frac{1 123 631}{40+1} \approx$ 27405 $\frac{1123631}{41+1} \approx $26753 26753
כן 758032 27 $\frac{758032}{27+1} \approx 27072$ 27072 27072
אמת+מרצ 434511 15 $\frac{434511}{15+1} \approx 27156$ 27156 $\frac{434511}{16+1} \approx 25559$
שס+ג 434254 15 $\frac{434254}{15+1} \approx 27140$ 27140 27140
עם+ו 226084 8 $\frac{226084}{8+1} \approx 25120$ 25120 25120
ב+ט 209335 7 $\frac{209335}{7+1} \approx 26166$ 26166 26166
ד 83739 3 $\frac{83 739}{3+1} \approx 20934$ 20934 20934


Список Голоса Мандаты Цена-4 Цена-5
מחל+ל 1123631 40 26753 26753
כן 758032 27 27072 $\frac{758032}{28+1} \approx 26139$
אמת+מרצ 434511 15 25559 25559
שס+ג 434254 15 $\frac{434254}{16+1} \approx 25544$ 25544
עם+ו 226084 8 25120 25120
ב+ט 209335 7 26166 26166
ד 83739 3 20934 20934

Итак,
מחל+ל должны получить ещё 2 мандата, всего 42 мандата.
כן ещё мандат, всего 28 мандатов
אמת+מרצ ещё мандат, всего 16 мандатов.
שס+ג ещё мандат, всего 16 мандатов.

Наконец, мы должны перейти назад из этих "обобщенных списков".

מחל+ל s 42 мандата 1 123 631 голоса
מחל s 729 054
ל s 394 577

Коэффициент $\frac{1 123 631}{42}=26 753+0,119... \approx 26 754$ (в ссылке приведено число 26 753, но очевидно, нужно округлять вверх).

מחל s $\frac{729 054}{26 754}=27+0,25... \approx 27$ (округление вниз)
ל s $\frac{394 577}{26 754}=14+0,748... \approx 14$ (округление вниз)

Остался 42-27-14=1 мандат.

Далее, мы делаем перерасчет "цены" 1 мандата, если бы каждый получил бы ещё 1 мандат.

מחל s $\frac{729 054}{27+1}=26 037+0,64...$
ל s $\frac{394 577}{14+1}=26 305+0,13..$

Таким образом дополнительный мандат получает ל
Итого,

מחל s 27 мандатов
ל s 15 мандатов


כן s 28 мандатов


אמת+מרצ s 16 мандатов, 434 511 голосов
אמת s 334 900 голосов
מרצ s 99 611 голоса

Коэффициент $\frac{434 511}{16} = 27 156 +0,9375 \approx 27 157$ (в ссылке приведено число 27 156, но очевидно, нужно округлять вверх).

אמת s $\frac{334 900}{27 157} = 12+0,33.. \approx 12$ (округление вниз)
מרצ s $\frac{99 611}{27 157} = 3+0,6679677.. \approx 3$ (округление вниз)

Остался 16-12-3=1 мандат.

Далее, мы делаем перерасчет "цены" 1 мандата, если бы каждый получил бы ещё 1 мандат.

אמת s $\frac{334 900}{12+1}=25 761+0,538...$
מרצ s $\frac{99 611}{3+1}=24 902+0,75..$

Таким образом дополнительный мандат получает אמת
Итого,

אמת s 13 мандатов
מרצ s 3 мандатов


שס+ג s 16 мандатов, 434 254 голосов
שס s 286 300 голосов
ג s 147 954 голоса

Коэффициент $\frac{434 254}{16} = 27 140 +0,875 \approx 27 141$ (в ссылке приведено число 27 140, но очевидно, нужно округлять вверх).

שס s $\frac{286 300}{27 141} = 10+0,5486.. \approx 10$ (округление вниз)
ג s $\frac{147 954}{27 141} = 5+0,45.. \approx 5$ (округление вниз)

Остался 16-10-5=1 мандат.

Далее, мы делаем перерасчет "цены" 1 мандата, если бы каждый получил бы ещё 1 мандат.

שס s $\frac{286 300}{10+1}=26027+0,27...$
ג s $\frac{147 954}{5+1}=24 659+0$

Таким образом дополнительный мандат получает שס
Итого,

שס s 11 мандатов
ג s 5 мандатов


עם+ו s 8 мандатов, 226 084 голоса
עם s 113 954 голосов
ו s 112 130 голоса

Коэффициент $\frac{226 084}{8} = 28 260+0,5 \approx 28 261$ (в ссылке приведено число 28 260, но очевидно, нужно округлять вверх).


עם s $\frac{113 954}{28 261} = 4+0,32.. \approx 4$ (округление вниз)
ו s $\frac{112 130}{28 261} = 3+0,9676586.. \approx 3$ (округление вниз)

Остался 8-4-3=1 мандат.

Далее, мы делаем перерасчет "цены" 1 мандата, если бы каждый получил бы ещё 1 мандат.

עם s $\frac{113 954}{4+1}=22 790+0,8$
ו s $\frac{112 130}{3+1}=28 032+0,5$

Таким образом дополнительный мандат получает ו
Итого,

עם s 4 мандатов
ו s 4 мандатов


ב+ט s 7 мандатов, 209 335 голоса
ט s 112 570 голоса
ב s 96 765 голосов


Коэффициент $\frac{209 335}{7} = 29 905$ (ровно).

ט s $\frac{112 570}{29 905} = 3+0,76.. \approx 3$ (округление вниз)
ב s $\frac{96 765}{29 905} = 3+0,2357.. \approx 3$ (округление вниз)

Остался 7-3-3=1 мандат.

Далее, мы делаем перерасчет "цены" 1 мандата, если бы каждый получил бы ещё 1 мандат.

ט s $\frac{112 570}{3+1}=28 142+0,5$
ב s $\frac{96 765}{3+1}=24 191+0,25$

Таким образом дополнительный мандат получает ט

Итого,

ט s 4 мандата
ב s 3 мандата

ד s 3 мандата


Итого:

Имя Список Мандаты
Кадима כן 28
Ликуд+НДИ מחל 27
НДИ ל 15
Авода אמת 13
Шас שס 11
ЯТ ג 5
Мерец מרצ 3
РААМ-ТААЛ עם 4
ХАДАШ ו 4
ИЛ ט 4
Байт Еhуди ט 3
БАЛАД ד 3

НДИ=Наш Дом Израиль (Исраэль Бэйтейну)
ИЛ=hа-ихуд hа-леуми
ЯТ=Яhадут hа-тора

Итого: 28+27+13+15+11+5+3+4+4+4+3+3=120 мандатов.

Данные с выборов 2009 г. взяты отсюда.
http://www.bechirot.gov.il/elections19/heb/about/MandatesSystem.aspx

Конец.

Об особенностях подсчёта голосов. Часть V

Часть I избирательная явка и действительные голоса
Часть II эквивалентность подсчёта
Часть III электоральный барьер
Часть IV метод Бадера-Офера
Часть V преимущество больших списков
Часть VI реальный пример


Как известно, на выборах 22 января мы выбирает законодательную власть, не исполнительную. Тут я написал краткий путеводитель по израильской политической карте. Тут мы разобрались кто формирует правительство после выборов в Кнессет.

Мы разобрались с избирательной явкой и действительными голосами в первой части, в третьей части разобрались с электоральным барьером, а во-второй доказали эквивалентность утверждений, что недействительный голос был выброшен в мусорное ведро и пропорционально распределён между всеми партиями, прошедшими электоральный барьер.

Четвёртая часть была посвящена методу Бадера-Офера об остаточном распределении мандатов. Эта часть является по-сути продолжением предыдущей.

В этой заметке я приведу доказательство, почему метод Бадера-Офера даёт предпочтение крупным спискам.


Ниже есть продолжение.

Перед тем, как предоставить доказательство в общем виде я приведу данные с примера 2, приведённые в четврётой части.

Пример. Допустим у нас есть три партии, и нет между ними ни одного договора о распределении остаточных голосов. Ниже представлена таблица, после того, как были выброшены все недействительные голоса, а также голоса, поданные за все списки, не прошедшие электоральный барьер. Итак, допустим мы имеем

A - 901 000
B - 203 000
C - 96 000

всего 1 200 000 голосов, которые нужно пропорционально распределить между этими тремя партиями таким образом, чтобы в сумме было 120 мандатов.

По закону о выборах, с учётом поправки Бадера-Офера, считаем сначала электоральный коэффициент одного парламентского мандата. Он равен $\frac{1 200 000}{120}$=10 000 голосов за 1 мандат ровно.

Таким образом, партия A получает
A - $\frac{901 000}{10 000}$=90+0,1
B - $\frac{203 000}{10 000}$=20+0,3
C - $\frac{96 000}{10 000}$=9+0,6

Всего распределили 90+20+9=119 (целых) мандатов, осталось распределить ещё 1 мандат.

Легко видеть, что $\frac{901 000}{90} \approx \frac{203 000}{20} \approx \frac{96 000}{9} \approx 10 000$

Или, что тоже самое, $\frac{90}{901 000} \approx \frac{20}{203 000} \approx \frac{9}{96 000} \approx \frac{1}{10 000}$


Если мы делаем перерасчет "цены" 1 мандата, если бы каждая из них получила бы ещё 1 мандат

A - $\frac{901 000}{90+1}$=9901 и ещё чуть-чуть.
B - $\frac{203 000}{20+1}$=9666 и ещё чуть-чуть.
C - $\frac{96 000}{9+1}$=9600 ровно

Таким образом, "аукцион" выигрывает партия A, так как в этом случае "цена мандата" будет наивысшей (и ближе всего к "теоретической").


$\frac{90+1}{901 000}=\frac{90}{901 000}+\frac{1}{901 000} \approx \frac{1}{10 000} + \frac{1}{901 000}$

$\frac{20+1}{203 000}=\frac{20}{203 000}+\frac{1}{203 000} \approx \frac{1}{10 000} + \frac{1}{203 000}$

$\frac{9+1}{96 000}=\frac{9}{96 000}+\frac{1}{96 000} \approx \frac{1}{10 000} + \frac{1}{96 000}$

Отсюда

A - $\frac{901 000}{90+1} \approx \frac{1}{\frac{1}{10 000} + \frac{1}{901 000}}$
B - $\frac{203 000}{20+1} \approx \frac{1}{\frac{1}{10 000} + \frac{1}{203 000}}$
C - $\frac{96 000}{20+1} \approx \frac{1}{\frac{1}{10 000} + \frac{1}{96 000}}$

Т.к. $\frac{1}{901 000}$ "ближе к нулю" чем $\frac{1}{203 000}$, которое с свою очередь "ближе к нулю" чем $\frac{1}{96 000}}$, то легко видит, что выражение для партии "ближе всех к 10 000. Т.е. у списка, за который было отдано наибольшее количество голосов, есть преимущество при подсчёте по системе Бадера-Офера.

Доказательство.
Итак, обозначим за A количество голосов, поданную за партию, набравшие их максимальное количество, за B - количество голосов поданную за другую партию

(1) $A \geq B>0$

Обозначим за x десятичное (точное) представление количества мандатов, которое получила партия A в результате первой фазы подсчёта, y - то же для партии B.
Имеем,

$\frac{A}{B}=\frac{x}{y}$ (точное равенство)

Теперь "вспомним", что мандаты суть целые числа. Обозначим k=[x], m=[y], где [.] обозначает целую часть числа (для целых положительных чисел, коими являются x и y, это максимум из всех чисел которые меньше или равны x (или y)). Если мы вместо x и y подставим их целые части, то мы получим приблизительное равенство:

(2) $\frac{A}{B} \approx \frac{k}{m}$

Нужно доказать, что дополнительный мандат по методу Бадера-Офера получит партия A, т.е. нужно доказать, что

$\frac{A}{k+1} \geq \frac{B}{m+1}$

Т.к. все входящие числа в неравенство положительные, это эквивалентно тому, что доказать, что

$\frac{k+1}{A} \leq \frac{m+1}{B}$

На самом деле мы докажем более слабую версию:

(*) $\frac{k+1}{A}$ ≲ $\frac{m+1}{B}$ (меньше или примерно равно)

Перечитаем формулировку утверждения:
У списка, за который было отдано наибольшее количество голосов, есть преимущество при подсчёте по методу Бадера-Офера. Обратим внимание, на слово преимущество в формулировке. Оно означает, что мы не утверждаем, что всегда более крупный список будет в выигрыше от применения метода Бадера-Офера, а лишь, что есть преимущество. Поэтому доказательства (*) достаточно для доказательства нашего утверждения.

Итак, дано:

(1) $A \geq B>0$

(2) $\frac{A}{B} \approx \frac{k}{m}$

Все числа целые положительные.

Нужно доказать, что

(*) $\frac{k+1}{A}$ ≲ $\frac{m+1}{B}$ (меньше или примерно равно)


Из неравенства (1) следует

(1.1) $\frac{1}{A} \leq \frac{1}{B}$

Из неравенства (2) следует $kB \approx Am$, отсюда

(2.1) $\frac{k}{A} \approx \frac{m}{B}$

Тогда

$\frac{k+1}{A}=\frac{k}{A}+\frac{1}{A} \approx$ (2.1) $\frac{m}{B}+\frac{1}{A} \leq$ (1.1) $\frac{m}{B}+\frac{1}{B}=\frac{m+1}{B}$

Что и требовалось доказать.

Продолжение следует.