Как найти порядковый номер наименьшего числа

Ваша проблема в том, что вы печатаете минимальное значение, если любой номер нечетное.

for (int i = 0; i < 7; i++){
    if (array[i] % 2 != 0){
    found == 1;
    }
}

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

found = (array[indexOfMin] % 2) != 0;

Или более элегантно

found = array[indexOfMin] & 1;

… предполагая, что вы действительно нашли значение, чего не произойдет, если вы неправильно инициализировали min. Из вашего примера похоже, что min инициализирован нулем. Вы должны использовать большое число, например INT_MAX, чтобы убедиться, что array[0] всегда меньше, чем min, или явно установить min на array[0] после инициализации, а затем пропустить тестирование array[0].

Примечание В настоящее время ваш код содержит дополнительную ошибку. Если вы собираетесь инициализировать min в array[0], вам нужно сделать это после того, как array[0] будет содержать действительные данные, а не заранее. Написанный код напечатает неправильный индекс, если пользователь введет 8 7 6 5 4 3 2 1.

Эта статья о математической концепции. Для числовых слов, обозначающих позицию в последовательности («первый», «второй», «третий» и т. Д.), См. Порядковые числа .

В теории множеств , с порядковым номером , или порядковый номер , является одним обобщением понятия натурального числа , которое используется , чтобы описать способ , чтобы устроить (возможно бесконечное) коллекцию объектов в порядке, один за другим.

Любой конечный набор объектов может быть упорядочен просто путем подсчета: пометки объектов различными натуральными числами. Основная идея порядковых чисел состоит в том, чтобы обобщить этот процесс на возможно бесконечное количество коллекций и предоставить «метку» для каждого шага в этом процессе. Порядковые номера, таким образом, являются «метками», необходимыми для упорядочивания коллекций объектов.

Порядковый номер используется для описания типа заказа в виде хорошо упорядоченного множества (хотя это не работает хорошо упорядоченном надлежащего класса ). Хорошо упорядоченный набор — это набор с отношением <таким, что:

• ( Трихотомия ) Для любых элементов x и y верно ровно одно из этих утверждений:
  • х < у
  • у < х
  • х = у
• ( Транзитивность ) Для любых элементов x , y , z , если x < y и y < z , то x < z.
• ( Обоснованность ) Каждое непустое подмножество имеет наименьший элемент, то есть имеет такой элемент x , что нет другого элемента y в подмножестве, где y < x .

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

В то время как порядковые числа полезны для упорядочивания объектов в коллекции, они отличаются от количественных чисел , которые полезны для количественной оценки количества объектов в коллекции. Хотя различие между порядковыми числами и кардиналами не всегда очевидно в конечных наборах (можно переходить от одного к другому, просто считая метки), разные бесконечные порядковые числа могут соответствовать одному и тому же кардиналу. Более того, могут быть наборы, которые нельзя хорошо упорядочить, и их количественные номера не соответствуют порядковым номерам. (Например, существование таких множеств следует из теории множеств Цермело-Френкеля с отрицанием выбранной аксиомы.) Как и другие виды чисел, порядковые числа можно складывать, умножать и возводить в степень , хотя ни одна из этих операций не является коммутативной.

Порядковые числа были введены Георгом Кантором в 1883 году, чтобы учесть бесконечные последовательности и классифицировать производные множества , которые он ранее ввел в 1872 году — при изучении уникальности тригонометрических рядов .

Порядковые числа расширяют натуральные числа

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

В то время как понятие кардинального числа связано с множеством без какой-либо конкретной структуры, порядковые числа тесно связаны с особым видом множеств, которые называются хорошо упорядоченными (настолько тесно связаны между собой, что некоторые математики не делают различий между ними. две концепции). Хорошо упорядоченный набор — это полностью упорядоченный набор (для любых двух элементов один определяет меньший и больший согласованным образом), в котором каждое непустое подмножество набора имеет наименьший элемент. В частности, не существует бесконечной убывающей последовательности. (Однако могут быть бесконечные возрастающие последовательности.) Порядковые номера могут использоваться для обозначения элементов любого заданного хорошо упорядоченного набора (наименьший элемент обозначается 0, следующий за ним — 1, следующий 2 и т. Д. ), и для измерения «длины» всего набора наименьшим порядковым номером, который не является меткой для элемента набора. Эта «длина» называется типом заказа набора.

Любой порядковый номер определяется набором предшествующих ему порядковых номеров. Фактически, наиболее распространенное определение порядковых номеров определяет каждый порядковый номер как набор предшествующих ему порядковых номеров. Например, порядковый номер 42 — это порядковый тип порядковых номеров, меньший, чем он, то есть порядковые номера от 0 (наименьший из всех ординалов) до 41 (непосредственный предшественник 42), и его обычно называют набором { 0,1,2,…, 41}. И наоборот, любое множество S ординалов, замкнутое снизу — это означает, что для любого ординала α в S и любого ординала β <α, β также находится в S — является (или может быть отождествлено) ординалом.

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

Возможно, более ясное представление об ординалах можно получить, изучив несколько первых из них: как упоминалось выше, они начинаются с натуральных чисел 0, 1, 2, 3, 4, 5, … После всех натуральных чисел идет первый бесконечный порядковый номер. , ω, а затем ω + 1, ω + 2, ω + 3 и т. д. (Что именно означает сложение, будет определено позже: просто рассматривайте их как имена.) После всего этого получится ω · 2 (то есть ω + ω), ω · 2 + 1, ω · 2 + 2 и т. Д. затем ω · 3, а затем ω · 4. Теперь с набором ординалов, сформированных таким образом (ω · m + n , где m и n — натуральные числа), сам должен иметь связанный с ним порядковый номер: и это ω ² . Далее будет ω ³ , затем ω ⁴ и так далее, и ω ^ω , затем ω ^{ω ω} , затем ω ^{ω ω ω} и даже позже ε ₀ ( эпсилон ноль ) (чтобы дать несколько примеров относительно малые — счетные — порядковые). Это может продолжаться бесконечно (поскольку каждый раз, когда кто-то говорит «и так далее» при перечислении порядковых номеров, это определяет более крупный порядковый номер). Наименьший несчетный ординал — это набор всех счетных ординалов, выраженный как ω ₁ или .

Определения

Хорошо упорядоченные наборы

В хорошо упорядоченном наборе каждое непустое подмножество содержит отдельный наименьший элемент. Учитывая аксиому зависимого выбора , это равносильно утверждению, что множество полностью упорядочено и не существует бесконечной убывающей последовательности (последнее легче визуализировать). На практике важность хорошего упорядочения оправдывается возможностью применения трансфинитной индукции , которая, по сути, говорит, что любое свойство, которое передается от предшественников элемента к самому этому элементу, должно быть истинным для всех элементов (данного элемента). упорядоченный набор). Если состояния вычисления (компьютерная программа или игра) могут быть хорошо упорядочены — таким образом, что каждый шаг сопровождается «более низким» шагом, то вычисление прекращается.

Неуместно различать два хорошо упорядоченных набора, если они отличаются только «маркировкой своих элементов» или более формально: если элементы первого набора могут быть спарены с элементами второго набора так, что если один элемент меньше другого в первом наборе, тогда партнер первого элемента меньше партнера второго элемента во втором наборе, и наоборот. Такое взаимно однозначное соответствие называется изоморфизмом порядка , и два хорошо упорядоченных множества называются изоморфными по порядку или подобными (с пониманием того, что это отношение эквивалентности ).

Формально, если частичный порядок ≤ определен на множестве S , а частичный порядок ≤ ‘определен на множестве S’ , то множества ( S , ≤) и ( S ‘ , ≤’) изоморфны по порядку, если существует биекция е , сохраняющий упорядочение. То есть f ( a ) ≤ ‘ f ( b ) тогда и только тогда, когда a ≤ b . При условии, что существует изоморфизм порядка между двумя хорошо упорядоченными множествами, изоморфизм порядка уникален: это делает вполне оправданным рассмотрение двух множеств как по существу идентичных и поиск «канонического» представителя типа (класса) изоморфизма. Это именно то, что предоставляют ординалы, а также обеспечивает каноническую маркировку элементов любого хорошо упорядоченного набора. Каждый хорошо упорядоченный набор ( S , <) изоморфен по порядку множеству порядковых номеров, меньших одного определенного порядкового номера, при их естественном порядке. Этот канонический набор является порядковым типом ( S , <).

По сути, порядковый номер предназначен для определения как класс изоморфизма хорошо упорядоченных множеств: то есть как класс эквивалентности для отношения эквивалентности «быть изоморфным по порядку». Однако существует техническая трудность, заключающаяся в том, что класс эквивалентности слишком велик, чтобы быть множеством в обычной формализации Цермело – Френкеля (ZF) теории множеств. Но это не серьезная трудность. Можно сказать, что порядковый номер является типом заказа любого набора в классе.

Определение ординала как класса эквивалентности

Первоначальное определение порядковых чисел, которое можно найти, например, в Principia Mathematica , определяет тип порядка хорошего упорядочивания как набор всех хороших порядков, подобных (изоморфных по порядку) этому правильному порядку: другими словами, порядковый номер number действительно является классом эквивалентности упорядоченных множеств. От этого определения следует отказаться в ZF и родственных системах аксиоматической теории множеств, потому что эти классы эквивалентности слишком велики, чтобы образовать множество. Тем не менее, это определение все еще может использоваться в теории типов и в аксиоматической теории множеств Куайна « Новые основы» и родственных системах (где оно предлагает довольно неожиданное альтернативное решение парадокса Бурали-Форти наибольшего порядкового числа).

Определение фон Неймана ординалов

Первые несколько ординалов фон Неймана
0	знак равно	= ∅
1	= {0}	= {∅}
2	= {0, 1}	= {∅, {∅}}
3	= {0,1,2}	= {∅, {∅}, {∅, {∅}}}
4	= {0,1,2,3}	= {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}}

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

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

Множество S является порядковым , если и только если S является строго упорядоченный по отношению к множеству членов и каждому элементу S также является подмножество S .

Таким образом, по этому определению натуральные числа являются ординалами. Например, 2 является элементом 4 = {0, 1, 2, 3}, а 2 равно {0, 1}, поэтому это подмножество {0, 1, 2, 3}.

С помощью трансфинитной индукции можно показать, что каждое хорошо упорядоченное множество изоморфно по порядку ровно одному из этих ординалов, то есть между ними существует биективная функция, сохраняющая порядок .

Более того, элементы каждого ординала сами являются ординалами. С учетом двух ординалы S и Т , S является элементом Т тогда и только тогда S является собственным подмножеством из T . Более того, либо S является элементом T , либо T является элементом S , либо они равны. Таким образом, каждый набор ординалов полностью упорядочен . Кроме того, каждый набор порядковых номеров упорядочен. Это обобщает тот факт, что каждый набор натуральных чисел упорядочен.

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

Класс всех ординалов не является набором. Если бы это был набор, можно было бы показать, что это порядковый номер и, следовательно, член самого себя, что противоречило бы его строгому упорядочиванию по членству. Это парадокс Бурали-Форти . Класс всех ординалов по-разному называется «Ord», «ON» или «∞».

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

Другие определения

Существуют и другие современные формулировки определения порядкового номера. Например, если принять аксиому регулярности , следующие утверждения эквивалентны для множества x :

• x — порядковый номер (фон Неймана),
• x — транзитивное множество , и членство в множестве трихотомично на x ,
• x — транзитивное множество, полностью упорядоченное включением множества,
• x — транзитивное множество транзитивных множеств.

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

Трансфинитная последовательность

Если α является любым порядковым и Х представляет собой набор, α-индексированной последовательность элементов X является функцией от а до Х . Это понятие, трансфинитная последовательность (если α бесконечно) или последовательность с порядковым индексом , является обобщением концепции последовательности . Обычная последовательность соответствует случаю α = ω, а конечная последовательность α соответствует кортежу , также известному как строка .

Трансфинитная индукция

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

Любое свойство, которое переходит от множества ординалов, меньших заданного ординала α, к самому α, истинно для всех ординалов.

То есть, если P (α) истинно всякий раз, когда P (β) истинно для всех β <α , то P (α) истинно для всех α. Или, более практично: чтобы доказать свойство P для всех ординалов α, можно предположить, что оно уже известно для всех меньших β <α .

Трансфинитная рекурсия

Трансфинитная индукция может использоваться не только для доказательства вещей, но и для их определения. Такое определение обычно называют трансфинитной рекурсией — доказательство того, что результат корректно определен, использует трансфинитную индукцию. Пусть F обозначает (классовую) функцию F, которая должна быть определена на ординалах. Идея теперь состоит в том, что при определении F (α) для неуказанного ординала α можно предположить, что F (β) уже определено для всех β <α, и, таким образом, дать формулу для F (α) в терминах этих F ( β). Затем по трансфинитной индукции следует, что существует одна и только одна функция, удовлетворяющая формуле рекурсии с точностью до α включительно.

Вот пример определения с помощью трансфинитной рекурсии по ординалам (больше будет дано позже): определите функцию F , позволив F (α) быть наименьшим ординалом, не входящим в набор { F (β) | β <α} , то есть множество, состоящее из всех F (β) при β <α . Это определение предполагает, что F (β) известно в самом процессе определения F ; этот кажущийся порочный круг и есть то, что позволяет определение с помощью трансфинитной рекурсии. Фактически, F (0) имеет смысл, поскольку нет ординала β <0 , а множество { F (β) | β <0} пусто. Таким образом, F (0) равно 0 (наименьший порядковый номер из всех). Теперь, когда F (0) известен, определение, примененное к F (1), имеет смысл (это наименьший порядковый номер не в одноэлементном наборе { F (0)} = {0} ) и т. Д. ( И т. Д. в точности трансфинитная индукция). Оказывается, этот пример не очень увлекательный, поскольку доказуемо F (α) = α для всех ординалов α, что можно показать именно с помощью трансфинитной индукции.

Последователи и предельные порядковые номера

Любой ненулевой порядковый номер имеет минимальный элемент — ноль. Он может иметь или не иметь максимальный элемент. Например, 42 имеет максимум 41, а ω + 6 имеет максимум ω + 5. С другой стороны, у ω нет максимума, поскольку нет наибольшего натурального числа. Если ординал имеет максимальное значение α, то это следующий порядковый номер после α, и он называется порядковым номером-преемником , а именно преемником α, записываемым как α + 1. В определении ординалов фон Неймана преемником α является то, что его элементы являются элементами α и самого α.

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

Когда — это последовательность с порядковым индексом, индексированная пределом γ, и последовательность увеличивается , то есть всякий раз , когда ее предел определяется как наименьшая верхняя граница набора, то есть наименьший порядковый номер (он всегда существует) больше любого члена последовательность. В этом смысле предельный порядковый номер — это предел всех меньших порядковых чисел (индексированных сам по себе). Проще говоря, это верхняя грань множества меньших ординалов.

Другой способ определения предельного ординала — сказать, что α является предельным ординалом тогда и только тогда, когда:

Существует ординал меньше α, и если ζ порядковый номер меньше α, то существует ординал ξ такой, что ζ <ξ <α.

Итак, в следующей последовательности:

0, 1, 2,…, ω, ω + 1

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

Таким образом, каждый порядковый номер является либо нулем, либо преемником (четко определенного предшественника), либо пределом. Это различие важно, потому что многие определения с помощью трансфинитной рекурсии основываются на нем. Очень часто при определении функции F трансфинитной рекурсией по всем ординалам определяют F (0) и F (α + 1), предполагая, что F (α) определено, а затем для предельных ординалов δ определяют F (δ) как предел F (β) для всех β <δ (либо в смысле порядковых пределов, как объяснялось ранее, либо для некоторого другого понятия предела, если F не принимает порядковые значения). Таким образом, интересным шагом в определении является следующий шаг, а не предельные порядковые номера. Такие функции (особенно для F неубывающих и принимающих порядковые значения) называются непрерывными. Порядковое сложение, умножение и возведение в степень непрерывны как функции их второго аргумента (но могут быть определены нерекурсивно).

Индексирование классов порядковых номеров

Любой хорошо упорядоченный набор подобен (изоморфен порядку) уникальному порядковому номеру ; другими словами, его элементы могут быть проиндексированы в возрастающем порядке порядковыми номерами меньше чем . Это применимо, в частности, к любому набору ординалов: любой набор ординалов, естественно, индексируется порядковыми числами меньше некоторых . То же самое, с небольшой модификацией, относится к классам ординалов (набор ординалов, возможно, слишком большой для формирования набора, определяемого некоторым свойством): любой класс ординалов может быть проиндексирован порядковыми числами (и, когда класс неограничен в классе всех ординалов это ставит его в класс-биекцию с классом всех ординалов). Таким образом, о -м элементе в классе (с условием, что «0-й» — самый маленький, «1-й» — следующий по величине, и так далее) можно свободно говорить. Формально определение осуществляется путем трансфинитной индукции: -й элемент класса определяется (при условии, что он уже определен для всех ) как наименьший элемент, больший, чем -й элемент для всех .

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

Замкнутые неограниченные множества и классы

Класс ординалов называется неограниченным или конфинальным , если задан какой-либо ординал , есть in такое, что (тогда класс должен быть собственным классом, т. Е. Он не может быть набором). Он называется замкнутым, когда предел последовательности порядковых номеров в классе снова находится в классе: или, что эквивалентно, когда функция индексации (класс-) является непрерывной в том смысле, что для предельного порядкового номера ( — порядковый номер в классе) — предел всех для ; это также то же самое, что быть замкнутым в топологическом смысле для топологии порядка (чтобы не говорить о топологии на собственных классах, можно потребовать, чтобы пересечение класса с любым заданным ординалом было замкнутым для топологии порядка на этом ординале. , это снова эквивалентно).

Особое значение имеют те классы ординалов, которые являются закрытыми и неограниченными , иногда называемыми клубами . Например, класс всех предельных ординалов замкнут и неограничен: это переводит тот факт, что всегда существует предельный ординал, превышающий данный ординал, и что предел предельных ординалов является предельным ординалом (удачный факт, если терминология иметь хоть какой-то смысл!). Класс аддитивно неразложимых ординалов, или класс ординалов, или класс кардиналов , все замкнуты и неограниченны; набор регулярных кардиналов, однако, неограничен, но не замкнут, и любой конечный набор ординалов замкнут, но не неограничен.

Класс стационарен, если он имеет непустое пересечение с каждым замкнутым неограниченным классом. Все суперклассы замкнутых неограниченных классов являются стационарными, а стационарные классы неограничены, но есть стационарные классы, которые не являются замкнутыми, и стационарные классы, у которых нет замкнутого неограниченного подкласса (например, класс всех предельных ординалов со счетной конфинальностью). Поскольку пересечение двух замкнутых неограниченных классов замкнуто и неограниченно, пересечение стационарного класса и замкнутого неограниченного класса стационарно. Но пересечение двух стационарных классов может быть пустым, например, класс ординалов с конфинальностью ω с классом ординалов с несчетной конфинальностью.

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

Арифметика ординалов

Есть три обычные операции с порядковыми числами: сложение, умножение и (порядковое) возведение в степень. Каждый из них может быть определен двумя разными способами: либо путем создания явного упорядоченного набора, представляющего операцию, либо путем использования трансфинитной рекурсии. Нормальная форма Кантор обеспечивает стандартизированный способ записи порядковых. Он однозначно представляет каждый ординал как конечную сумму порядковых степеней ω. Однако это не может служить основой универсальной порядковой записи из-за таких самореференциальных представлений, как ε ₀ = ω ^{ε ₀} . Так называемые «естественные» арифметические операции сохраняют коммутативность за счет непрерывности.

Ординальные числа , интерпретируемые как проворные , также подвергаются резким арифметическим операциям.

Ординалы и кардиналы

Начальный ординал кардинала

Каждый ординал ассоциируется с одним кардиналом , его мощностью. Если между двумя ординалами существует взаимно однозначное соответствие (например, ω = 1 + ω и ω + 1> ω ), то они ассоциируются с одним и тем же кардиналом. Любой хорошо упорядоченный набор, имеющий порядковый номер в качестве типа порядка, имеет ту же мощность, что и этот порядковый номер. Наименьший ординал, связанный с данным кардиналом, называется начальным ординалом этого кардинала. Каждый конечный ординал (натуральное число) является начальным, и никакие другие порядковые числа не связаны с его кардиналом. Но большинство бесконечных ординалов не являются начальными, поскольку многие бесконечные ординалы связаны с одним и тем же кардиналом. Аксиома выбора эквивалентно утверждению , что каждое множество может быть вполне упорядоченным, то есть , что каждый кардинал имеет начальное порядковое. В теориях с аксиомой выбора кардинальное число любого множества имеет начальный порядковый номер, и можно использовать кардинальное присвоение фон Неймана в качестве кардинального представления. (Однако тогда мы должны быть осторожны, чтобы различать кардинальную арифметику и порядковую арифметику.) В теориях множеств без аксиомы выбора кардинал может быть представлен множеством множеств с этой мощностью, имеющей минимальный ранг (см . Трюк Скотта ).

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

Пишется α-й бесконечный начальный ординал , это всегда предельный ординал. Записана его мощность . Например, мощность ω ₀ = ω равна , что также является мощностью ω ² или ε ₀ (все — счетные ординалы). Таким образом, ω можно отождествить с , за исключением того, что обозначение используется при записи кардиналов, а ω при записи порядковых чисел (это важно, поскольку, например, = while ). Кроме того, это наименьший несчетный порядковый номер (чтобы убедиться, что он существует, рассмотрим набор классов эквивалентности правильного упорядочения натуральных чисел: каждый такой правильный порядок определяет счетный порядковый номер и является типом порядка этого набора), является наименьший порядковый номер, мощность которого больше , и так далее, и является пределом для натуральных чисел n (любое ограничение кардиналов является кардиналом, поэтому этот предел действительно является первым кардиналом после всех ).

Cofinality

Конфинальности ординала является наименьшим порядковым , что является тип порядка в конфинальной подмножества . Обратите внимание, что некоторые авторы определяют cofinality или используют его только для порядковых номеров пределов. Конфинальность набора ординалов или любого другого хорошо упорядоченного набора — это конфинальность типа заказа этого набора.

Таким образом, для предельного ординала существует -индексированная строго возрастающая последовательность с пределом . Например, кофинальность ω ² равна ω, потому что последовательность ω · m (где m пробегает натуральные числа) стремится к ω ² ; но, вообще говоря, любой счетный предельный ординал имеет конфинальность ω. Неисчислимый предельный ординал может иметь либо конфинальность ω, как он есть, либо несчетную конфинальность.

Конфинальность 0 равна 0. А конфинальность любого последующего ординала равна 1. Конфинальность любого предельного ординала не меньше .

Ординал, равный своей кофинальности, называется регулярным и всегда является начальным ординалом. Любой предел регулярных порядковых номеров является пределом начальных порядковых номеров и, таким образом, также является начальным, даже если он не является регулярным, что обычно не так. Если аксиома выбора, то регулярна для каждого α. В этом случае, ординалы 0, 1, , и являются регулярными, в то время как 2, 3, и ш _{ш · 2} начальные порядковые, которые не являются регулярными.

Конфинальность любого ординала α является правильным ординалом, т. Е. Конфинальность конфинальности α такая же, как конфинальность α . Таким образом, операция конфинальности идемпотентна .

Некоторые «большие» счетные ординалы

Как упоминалось выше (см канторовым нормальная форма ), порядковый ε ₀ является наименьшим , удовлетворяющий уравнению , так что предел последовательности 0, 1, , , и т.д. Многие ординалы могут быть определены таким образом , как фиксированных точек некоторых порядковых функций ( -й порядковый, такой, который вызывается , тогда можно было бы продолжить попытки найти -й порядковый, такой, что «и так далее», но вся тонкость заключается в «и так далее»). Можно попытаться делать это систематически, но независимо от того, какая система используется для определения и построения ординалов, всегда есть ординал, который находится чуть выше всех ординалов, построенных системой. Пожалуй, самым важным порядковое , что ограничивает система строительства таким образом , является порядковым церковно-Клини , (несмотря на то, во имя, это порядковое счетно), что наименьший порядковый номер, который не может каким — либо образом быть представлен в вычислимой функции (это, конечно, можно сделать и строго). Однако ниже могут быть определены значительно большие ординалы , которые измеряют «теоретико-доказательную силу» некоторых формальных систем (например, измеряют силу арифметики Пеано ). Большие счетные ординалы, такие как допустимые счетные ординалы, также могут быть определены выше ординала Черча-Клини, которые представляют интерес в различных частях логики.

Топология и порядковые номера

Любой порядковый номер можно превратить в топологическое пространство , наделив его порядковой топологией ; эта топология дискретна тогда и только тогда, когда ординал является счетным кардиналом, т. е. не более чем ω. Подмножество ω + 1 открыто в топологии порядка тогда и только тогда, когда оно либо кофинитно, либо не содержит ω как элемент.

См. Раздел Топология и порядковые номера статьи «Топология порядка».

Закрытые вниз наборы порядковых номеров

Набор закрывается вниз, если в наборе есть что-то меньшее, чем элемент набора. Если набор порядковых номеров закрыт вниз, то этот набор является порядковым — наименьшим порядковым номером, отсутствующим в наборе.

Примеры:

• Набор порядковых номеров меньше 3 равен 3 = {0, 1, 2}, наименьший порядковый номер не меньше 3.
• Набор конечных ординалов бесконечен, наименьший бесконечный ординал: ω.
• Множество счетных ординалов неисчислимо, наименьший несчетный ординал: ω ₁ .

История

Трансфинитные порядковые числа, впервые появившиеся в 1883 году, возникли в работе Кантора с производными множествами . Если P является множество действительных чисел, производное множество P» есть множество предельных точек в P . В 1872 году, Кантор породил множество Р ^{( п )} , применяя операцию производного множества п раз в P . В 1880 году он указал, что эти множества образуют последовательность P ‘  ⊇ ··· ⊇  P ^{( n )}  ⊇  P ^{( n  + 1)}  ⊇ ···, и продолжил процесс вывода, определив P ^(∞) как пересечение этих наборов. Затем он повторил операцию производного множества и пересечения, чтобы расширить свою последовательность множеств до бесконечности: P ^(∞)  ⊇  P ^{(∞ + 1)}  ⊇  P ^{(∞ + 2)}  ⊇ ··· ⊇  P ^{(2∞) ⊇}  ·· · ⊇  P ^{(∞ 2 )}  ⊇ ···. Верхние индексы, содержащие ∞, — это просто индексы, определенные в процессе вывода.

Кантор использовал эти множества в теоремах: (1) если P ^(α)  = ∅ для некоторого индекса α, то P ‘ счетно; (2) Наоборот, если P ‘ счетно, то существует индекс α такой, что P ^(α)  = ∅. Эти теоремы доказываются путем разбиения P ‘ на попарно непересекающиеся множества: P’  = ( P ‘  ∖  P ⁽²⁾ ) ∪ ( P ⁽²⁾  ∖  P ⁽³⁾ ) ∪ ··· ∪ ( P ^(∞)  ∖  P ^{( ∞ + 1)} ) ∪ ··· ∪  P ^(α) . Для β <α: поскольку P ^{(β + 1)} содержит предельные точки P ^(β) , множества P ^(β)  ∖  P ^{(β + 1) не} имеют предельных точек. Следовательно, они дискретные множества , поэтому они счетны. Доказательство первой теоремы: если P ^(α)  = ∅ для некоторого индекса α, то P ‘ — счетное объединение счетных множеств. Следовательно, P ‘ счетно.

Вторая теорема требует доказательства существования α такого, что P ^(α)  = ∅. Чтобы доказать это, Кантор рассмотрел множество всех α, имеющих счетное число предшественников. Чтобы определить это множество, он определил трансфинитные порядковые числа и преобразовал бесконечные индексы в ординалы, заменив ∞ на ω, первое трансфинитное порядковое число. Кантор назвал множество конечных ординалов первым числовым классом . Второй числовой класс — это набор ординалов, предшественники которых образуют счетное бесконечное множество. Множество всех α, имеющих счетное число предшественников, то есть множество счетных ординалов, является объединением этих двух числовых классов. Кантор доказал, что мощность второго числового класса является первой несчетной мощностью.

Вторая теорема Кантора сводится к следующему: если P ‘ счетно, то существует счетный ординал α такой, что P ^(α)  = ∅. Его доказательство использует доказательство от противного . Пусть P ‘ счетно, и пусть такого α нет. Это предположение дает два случая.

В обоих случаях P ‘ несчетно, что противоречит тому, что P’ счетно. Следовательно, существует счетный ординал α такой, что P ^(α)  = ∅. Работа Кантора с производными множествами и порядковыми числами привела к теореме Кантора-Бендиксона .

Используя преемников, пределы и количество элементов, Кантор сгенерировал неограниченную последовательность порядковых чисел и числовых классов. (Α + 1) -й числовой класс — это набор ординалов, предшественники которых образуют множество той же мощности, что и α-й числовой класс. Мощность (α + 1) -го числового класса — это мощность, следующая сразу за мощностью α-го числового класса. Для предельного ординала α α-ый числовой класс представляет собой объединение β-ых числовых классов для β <α. Его мощность — это предел мощности этих числовых классов.

Если n конечно, n -й числовой класс имеет мощность . Если α ≥ ω, то число α-го класса имеет мощность . Следовательно, мощности числовых классов однозначно соответствуют числам алеф . Кроме того, α-й числовой класс состоит из порядковых номеров, отличных от порядковых номеров в предыдущих числовых классах, тогда и только тогда, когда α является неограниченным порядковым номером. Следовательно, классы с неограниченным числом разбивают ординалы на попарно непересекающиеся множества.

Смотрите также

• Подсчет
• Четные и нечетные ординалы
• Первый несчетный порядковый номер
• Порядковый номер
• Сюрреалистическое число , обобщение порядковых чисел , включающее негативы.

Примечания

использованная литература

внешние ссылки

• «Порядковое число» , Энциклопедия математики , EMS Press , 2001 [1994]
• Порядковые числа в ProvenMath
• Порядковый калькулятор Бесплатное программное обеспечение под GPL для вычислений с порядковыми и порядковыми обозначениями
• Глава 4 конспектов лекций Дона Монка по теории множеств представляет собой введение в ординалы.

Условная тернарная операция используется с тремя операндами. В изображении условной операции применяются два символа ‘?’ и ‘:’ и три выражения – операнда:

выражение_1 ? выражение_2 : выражение_3;

Первым вычисляется значение выражения_1. Если оно истинно, т. е. не равно 0, то вычисляется значение выражения_2, которое становится результатом. Если при вычислении выражения­_1 получится 0, то в качестве результата берётся значение выражения_3, например:

x<0 ? –x : x;

Выражение возвращает абсолютную величину переменной x.

Пример программы вычисления наибольшего из значений функции y1=x²+1, y2=7-x² , y3=x+1 для любого х.

#include <stdlib.h>

#include <stdio.h>

int main(int argc, char *argv[])

{ float x,y1,y2,y3,max;

printf(«Input x «); scanf(«%f»,&x);

y1=x*x+1; y2=7-x*x; y3=x+1;

y1>y2? max=y1:max=y2;

y3>max? max=y3:max=max;

printf («x=%8.2f y1=%8.2f y2=%8.2f y3=%8.2f max=%8.2fn»,x,y1,y2,y3,max);

system(«PAUSE»);

return EXIT_SUCCESS;

}

Множественный выбор

В программах с множественным выбором используется переключатель switch , который сравнивает значение выражения, указанного за ним, и выполняет один из операторов, метка которого совпадает с этим значением. Общий вид:

Switch (выражение)

{ case метка_1: список_операторов_1;

……………………………………….

case метка_n: список_операторов_n;

default : операторы; }

Значения выражения и меток должны быть целочисленными константами.

Например, определим количество дней по введенному номеру месяца.

//lab2_2 множественный выбор

#include<stdio.h>

#include<conio.h> // Заголовочный файл для работы с терминалом

int m;

main()

{

printf(«n Введите номер месяца :»); scanf(«%d»,&m);

printf(«n В %4d месяце дней: «,m);

switch(m){

case 1:case 3:case 5: case 7:case 8:case 10:case 12:printf(«тридцать одинn»);break;

case 2: printf («двадцать восемь n»);break;

case 4: case 6: case 9: case 11: printf(«тридцатьn»);break;

default: printf(«n Номер месяца неверен n»);}

getch (); }

В примере программы, если номер месяца превышает 12, выводится сообщение о неверном вводе месяца, для чего используется default. Оператор break служит для прерывания цикла проверки и перехода в конец переключателя. В случае отсутствия break, происходит переход на следующую ветвь.

Функция getch, подключающаяся заголовочным файлом conio.h, ожидает нажатия любой клавиши. Это позволяет просмотреть результаты, не используя ALT+F5 для просмотра экрана пользователя.

ВЫПОЛНЕНИЕ РАБОТЫ

Составить программы разветвляющейся структуры согласно вариантам задания 1 (используя IF) и задания 2 (используя SWITCH) .

Варианты задания 1

1) Даны четыре числа. На сколько их сумма меньше их произведения?

2) Даны четыре числа. Вычислить сумму положительных среди них чисел.

3) Даны четыре числа. Вычислить произведение отрицательных среди них чисел.

4) Даны четыре числа. Все отрицательные среди них числа заменить на 0.

5) Даны четыре числа. Определить сколько среди них отрицательных и сколько положительных.

6) Даны четыре числа. Определить порядковый номер наименьшего среди них.

7) Даны два числа. Большее из этих двух чисел заменить их полусуммой, а меньшее удвоенным произведением.

Даны три числа. Меньшее среди них заменить на 0 .

9) Даны четыре числа. Найти разность между наибольшим и наименьшим среди них.

10) Даны три числа K, M и N. Поменять их значения местами таким образом, чтобы K < M < N.

11) Даны четыре разных числа. Найти среди них два наибольших.

12) Даны три числа. Поменять местами большее и меньшее из этих чисел.

Варианты задания 2

Предусмотреть ситуацию неправильного ввода исходных данных.

1) Вводится число программ N<=20. Напечатать фразу «Я разработал N программ», согласовав слово «программа» с числом N.

2) Вводится число экзаменов N<=20. Напечатать фразу «Мы успешно сдали N экзаменов», согласовав слово «экзамен» с числом N.

3) Вводится число лет (N<=25). Напечатать фразу «Мне N лет», согласовав слово «лет, год, года» с числом N.

4) Вводится число студентов N<=30. Вывести фразу «В нашей группе N студентов», согласовав слово «студент» с числом N.

5) Вводится число М — номер месяца.
Определить номер квартала по введенному номеру месяца и номер полугодия.

6) Вводится число М — номер месяца. Определить время года по введенному номеру месяца и номер полугодия.

7) Вводится целое число С. Если -9<=c<=9 вывести величину числа в словесной форме с учетом знака, в противном случае — предупреждающее сообщение и повторный ввод.

Вводится номер семестра N<=10. Вывести фразу «Я проучился N семестров», согласовав слово «семестр» с числом N. Определить номер курса.

9) В китайском гороскопе года носят следующие названия: крыса, корова, тигр, заяц, дракон, змея, лошадь, овца, обезьяна, петух, собака, свинья. Учитывая, что 1996 – год крысы, написать программу, определяющую название года по его номеру.

10) Вводится число Т – порядковый день в году. Определить номер месяца М и дня недели D, соответствующих Т.(Например, если Т=365 . то М=12, а D=31)

11) Вводится номер месяца М и дня D. Определить порядковый номер дня в году Т соответсвующий этой дате.

12) Вводится номер месяца М и дня D. Определить день недели с датой М и D, считая, что год начинается с понедельника.

КОНТРОЛЬНЫЕ ВОПРОСЫ

4.1. Сравните виды условных операторов Си.

4.2. Всегда ли ставятся скобки и какие в условном операторе?

4.3. Зачем ставятся в переключателе операторы break и default?

4.4. Как будет работать программа из примера без break?

Лабораторная работа №3

Программы циклической структуры

1. ЦЕЛЬ РАБОТЫ: приобретение практических навыков в составлении алгоритмов и программ циклической структуры.

ОСНОВНЫЕ СВЕДЕНИЯ

Операторы циклов

В языке Си существует 3 вида циклов: 1) цикл с параметром или цикл типа for; 2) цикл с предусловием или цикл типа while, 3) цикл с постусловием или цикл типа do … while. Во всех этих циклах условие продолжения цикла заключается в круглые скобки. В циклах типов for и while повторяющаяся часть состоит из одного оператора, если требуется выполнить в цикле несколько операторов, они заключаются в фигурные скобки, образуя составной оператор. В цикле с постусловием тело цикла помещается между словами do и while. В отличие от цикла с предусловием, цикл с постусловием выполнится хотя бы один раз. Циклы с пред- и постусловием продолжаются, если условие продолжения истинно.

Цикл с параметром

Цикл forиспользуется тогда, когда количество повторений цикла заранее известно или может быть вычислено. Цикл forсостоит из заголовка и тела цикла. В заголовке после слова forв круглых скобках записываются через точку с запятой три выражения:

А) начальные значения: операторы присваивания, которые выполняются один раз перед выполнением цикла;

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

С)действия в конце каждого шагацикла (в большинстве случаев это операторы присваивания).

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

Примеры заголовков:

for ( i = 0; i < 10; i ++ ) { … }

for ( i = 0, x = 1.; i < 10; i += 2, x *= 0.1 ){ … }

• Тело цикла заключается в фигурные скобки; если в теле цикла стоит всего один оператор, скобки можно не ставить.

• В тело цикла могут входить любые другие операторы, в том числе и другие циклы (такой прием называется «вложенные циклы»).

• Для того, чтобы легче разобраться в программе, все тело цикла и ограничивающие его скобки сдвигаются вправо на 2-3 символа (запись «лесенкой»).

Пример вычисления суммы квадратов натурального ряда чисел от 1 до n.

S= = 1² + 2 ² + . . . + n ².

//lab3_1 сумма квадратов натурального ряда

#include <stdio.h>

main()

{ int S,n,i;

printf(“Введите n ”); scanf(“%d”,&n);

for (S=0, i=1; i<=n; i++)

S+=i*i; // соответствует S=S+i*i

printf (“n=%d S=%d”,n,S);

}

В разделе инициализации присваиваются начальные значения переменным S и i. При i, не превышающем n, цикл повторяется, иначе выполняется выход из цикла. Оператор инкремента i++ (или декремента i—), эквивалентен i=i +1 (i=i-1). Для досрочного выхода из цикла и перехода на следующий оператор после цикла используется оператор break. Для пропуска всех операторов, оставшихся до конца тела цикла и перехода к следующему повторению цикла используется оператор continue.