Преемник (математика)

В математике концепции происхождения или преемственности и счета формализованы и обобщены с помощью терминов « преемник» и « предшественник» .

Преемники и предшественники в подсчете и по порядку

Отношение преемника в порядке натуральных чисел. При счете вы переходите от числа к числу в направлении стрелок. В математике вы считаете от 0, поэтому вы начинаете считать прямо перед первым предметом.

При подсчете последователем целого числа интуитивно является следующее большее число: например, 2 является преемником 1, 3 - преемником 2 и т. Д. При обратном отсчете вы получаете от 9 до его предшественника 8 и т. Д. Это в основном наивное открытие, потомки всегда Чтобы понять снова в игре, можно формализовать математическую характеристику натуральных чисел , которая была разработана Джузеппе Пеано и в его честь называется системой аксиом Пеано .

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

Определения

Будьте строго упорядоченное множество , . Затем называется ${\ Displaystyle (М, {<})}$ ${\ displaystyle b \ in M}$

${\ displaystyle a}$ Предшественник или нижний сосед из , если и не является важным элементом , чем существует с этим свойством ${\ displaystyle b}$ ${\ displaystyle a <b}$ ${\ displaystyle a}$

формальный: если .

{\ Displaystyle а \ пре б}

{\ Displaystyle а <б \ \ земля}

{\ displaystyle \ nexists}

{\ displaystyle a '\ in M ​​\ двоеточие (a <a' <b)}

${\ displaystyle c}$ Преемник или верхний сосед из , если это и не меньше , чем элемент с таким свойством существует ${\ displaystyle b}$ ${\ displaystyle b <c}$ ${\ displaystyle c}$

формальный: если ,

{\ displaystyle c \ succ b}

{\ displaystyle b <c \ land \ nexists \, c '\ in M ​​\ двоеточие (b <c' <c)}

Отношение делителей на множестве делителей 12, 1 и 2 имеет по два последователя, 6 и 12 имеют двух предшественников.

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

Теория порядка определяет : ${\ displaystyle b \ in M}$

${\ displaystyle a}$ является предком if is, а любой другой элемент с этим свойством меньше ${\ displaystyle b}$ ${\ displaystyle a <b}$

формальный: если .

{\ Displaystyle а \ пре б}

{\ displaystyle a <b \ land \ forall a '\ in M ​​\ двоеточие \ left ((a' <b) \ Rightarrow (a '\ leq a) \ right)}

${\ displaystyle c}$ является преемником if is, и каждый другой элемент с этим свойством больше ${\ displaystyle b}$ ${\ displaystyle b <c}$

формальный: если ,

{\ displaystyle c \ succ b}

{\ Displaystyle b <с \ земля \ forall c '\ в M \ двоеточие \ влево ((b <c') \ Rightarrow (c \ leq c ') \ right)}

Это означает, что предшественник и последователь, если они есть, однозначны даже в не полностью упорядоченных наборах. Это скорее изображает процесс подсчета.

пример

Показанный график иллюстрирует отношение делителей в наборе делителей числа 12. Абстрактное отношение 3 <6 представлено здесь стрелками и имеет значение 3 делит 6, 1 делит 4 и т. Д. Порядок не является полным, потому что есть элементы которые нельзя сравнивать друг с другом, например, 2 не является делителем 3 и наоборот. В смысле второго, теоретико-упорядоченного определения, у 2 нет последователей, но есть предшественник, в смысле первого, более общего определения, 2 имеет предшественника и двух последователей.

Приложения

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

обобщение

Приведенное выше определение легко распространяется на строгие частичные порядки. В общем случае, особенно в случае (слабого) полного или частичного порядка , все же необходимо требовать, чтобы предшественник или последователь был другим элементом (что всегда выполняется в случае строгого порядка). ${\ Displaystyle (М, \ leq)}$

Для с ${\ displaystyle a, b \ in M}$

{\ displaystyle a \ leq b \ land a \ neq b}

и

{\ displaystyle \ nexists b '\ in M ​​\ двоеточие (a \ leq b' \ land a \ neq b '\ land b' \ leq b \ land b '\ neq b)}

,

называется а (немедленный) предшественник из ; аналогично определяется (непосредственный) преемник . ${\ displaystyle a}$ ${\ displaystyle b}$

Многие авторы используют термины предшественник и последователь в более общем смысле, а именно без второго условия.В этом альтернативном языке термины, определенные здесь, называются непосредственными ( прямыми ) предшественниками или преемниками.

Индивидуальные доказательства

↑ Йоханнес Кёблер: Введение в теоретическую информатику , Университет Гумбольдта, Берлин, Институт компьютерных наук, WS2013 / 14, стр. 79
^ Вибке Петерсен: Математические основы компьютерной лингвистики - Ordnungsrelationen , 4-й набор слайдов, Университет Генриха Гейне, Дюссельдорф, Институт языка и информации, PDF: WS 2011/12, стр. 93 WS 2013/14, стр. 90 , доступ 21 апреля. 2018.

Сноски

↑ Эта процедура определяет новое отношение ( непосредственное , синонимичное прямое ) -предшественник для данного отношения . ${\ displaystyle R}$ ${\ displaystyle R}$
↑ Такой предшественник или преемник в более широком смысле не обязательно должен пройти один путь , т.е. ЧАС. может быть достигнута конечная последовательность прямых (то есть непосредственных) предшественников (квази косвенно или косвенно), например Б. От 0 до 10 , или - в отличие от того , где есть такой конечный способ. О концепции пути в отношениях см. Hans-Rudolf Metz: Relationen, wege, Hüllen, FH Gießen-Friedberg, Diskrete Mathematik (Informatik), SS 2010 - Script 16, 2 июня 2010 г. (по состоянию на 1 мая 2018 г.). В конечном случае отношение можно понимать как ориентированный граф: в теоретико-графовом смысле это ориентированный путь (без весов ребер). ${\ Displaystyle (\ mathbb {R}, <)}$ ${\ Displaystyle (\ mathbb {Q}, <)}$ ${\ Displaystyle (\ mathbb {Z}, <)}$

[1] Йоханнес Кёблер: Введение в теоретическую информатику , Университет Гумбольдта, Берлин, Институт компьютерных наук, WS2013 / 14, стр. 79

[4] Вибке Петерсен: Математические основы компьютерной лингвистики - Ordnungsrelationen , 4-й набор слайдов, Университет Генриха Гейне, Дюссельдорф, Институт языка и информации, PDF: WS 2011/12, стр. 93 WS 2013/14, стр. 90 , доступ 21 апреля. 2018.

[2] Эта процедура определяет новое отношение ( непосредственное , синонимичное прямое ) -предшественник для данного отношения . ${\ displaystyle R}$ ${\ displaystyle R}$

[3] Такой предшественник или преемник в более широком смысле не обязательно должен пройти один путь , т.е. ЧАС. может быть достигнута конечная последовательность прямых (то есть непосредственных) предшественников (квази косвенно или косвенно), например Б. От 0 до 10 , или - в отличие от того , где есть такой конечный способ. О концепции пути в отношениях см. Hans-Rudolf Metz: Relationen, wege, Hüllen, FH Gießen-Friedberg, Diskrete Mathematik (Informatik), SS 2010 - Script 16, 2 июня 2010 г. (по состоянию на 1 мая 2018 г.). В конечном случае отношение можно понимать как ориентированный граф: в теоретико-графовом смысле это ориентированный путь (без весов ребер). ${\ Displaystyle (\ mathbb {R}, <)}$ ${\ Displaystyle (\ mathbb {Q}, <)}$ ${\ Displaystyle (\ mathbb {Z}, <)}$

Languages