Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[25]

«быть потомком» на множестве людей является частичным порядком, если мы считаем человека своим потомком.

Частично упорядоченное множество, даже конечное, может не иметь наибольшего элемента - такого элемента ж, что yRx для любого элемента у. Следует различать понятия наибольшего и максимального элементов: элемент ж называется максимальным (maximal), если не существует большего элемента, т.е. если из xRy следует ж = у. Например, среди нескольких картонных коробок может не быть наибольшей (в которую помещается любая другая), но заведомо есть одна или несколько максимальных (которые не влезают ни в одну другую).

Частичный порядок называется линейным (total order, linear order), если для любых элементов а и Ь выполнено либо aRb, либо bRa (или оба - тогда они равны по свойству антисимметричности). Например, отношение «»на множестве натуральных чисел является линейным порядком, а отношение «быть потомком» на множестве людей - нет (можно найти двух человек, не являющихся потомками друг друга).

Упражнения

5.2-1 Доказать, что отношение «С» на множестве всех подмножеств множества Z является отношением частичного, но не линейного порядка.

5.2-2 Показать, что для любого положительного га отношение а = b (mod га) является отношением эквивалентности на множестве Z. (Говорят, что а = b (mod га), если существует целое q, для которого a - b = qn.) Сколько классов эквивалентности есть у этого отношения?

5.2-3 Приведите пример отношения, которое

а.рефлексивно и симметрично, но не транзитивно;

б.рефлексивно и транзитивно, но не симметрично;

в.симметрично и транзитивно, но не рефлексивно.

5.2-4 Пусть S - конечное множество, R - отношение эквивалентности на S. Докажите, что если R антисимметрично, что все классы эквивалентности содержат по одному элементу.

5.2-5 Профессор думает, что всякое симметричное и транзитивное отношение рефлексивно, и предлагает такое доказательство: из aRb следует bRa по симметричности, откуда следует aRa по транзитивности. Правильно ли это доказательство?


5.3. Функции

Пусть даны два множества А и В. Функцией (function), отображающей А в В, называется бинарное отношение / С А x В, обладающее таким свойством: для каждого а £ А существует ровно одно b £ В, для которого (а, Ъ) £ /. Множество А называется областью определения (domain) функции; для множества В в русском языке нет общепринятого названия, а по-английски оно называется codomain.

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

f = {(a,b) : а £ N п b = a mod 2}

можно рассматривать как функцию /: N -> {0,1}, поскольку для каждого натурального числа а существует единственное b £ {0,1}, равное a mod 2. Можно записать /(0) = 0, /(1) = 1, /(2) = 0 и так далее. С другой стороны, отношение

д = {(а, Ъ) : а, b £ N и а + b четно}

не является функцией, поскольку (например) пары (1,3) и (1,5), принадлежащие этому отношению, имеют равные первые члены, но разные вторые.

Если пара (а, Ъ) принадлежит отношению /, являющемуся функцией, то говорят, что b является значением (value) функции для аргумента (argument) а, и пишут b = f(a). Чтобы задать функцию, надо указать её значение для каждого аргумента, принадлежащего её области определения. Например, можно задать функцию /: N -т- N формулой /(га) = 2га, которая означает, что / = {(га, 2га) : га £ N}. Две функции f,g: А -> В считаются равными (equal), если /(а) = д(а) для всех а £ А. (Обратите внимание, что с формальной точки зрения мы считаем функции /: А -> В\ и д: А -> В2 различными при В\ ф В2, даже если f(a) = д(а) при всех а!)

Конечной последовательностью (finite sequence) длины га называют функцию /, область определения которой есть множество {0,1, 2,..., га- 1}. Конечную последовательность часто записывают как список её значений, т. е. как (/(0), /(1), • • •, f(n- 1)). Бесконечной последовательностью (infinite sequence) называется функция, областью определения которой является множество N натуральных чисел. Например, последовательность Фибоначчи, заданная уравнением (2.13), может быть записана как (0,1,1, 2, 3, 5, 8,13, 21,...).


Если область определения функции является декартовым произведением нескольких множества, мы обычно опускаем дополнительные скобки вокруг аргументов. Например, если /: А\ x А2 x ... x Ап -т- В, мы пишем f(cii, а2, , ап) вместо более формального f((ai, а2, , ап))- Каждое из аг- также называется аргументом (argument) функции /, хотя формально её аргументов следовало бы считать га-ку (ai, а2,..., ап).

Если Ь = /(а) для некоторой функции /: А -> В и некоторых а £ A, b £ В, то элемент Ь называют образом (image) элемента а. Для произвольного подмножества А1 множества А его образ f(A) определяют формулой

f(A) = {Ь £ В : Ь = /(а)для некоторого а £ А}.

Множество значений (range) функции / определяется как образ области её определения, т.е. как f(A). Например, множество значений функции /: N -т- N, определённой формулой f(n) = 2га, есть множество всех чётных натуральных чисел, которое можно записать как /(N) = {то : то = 2га для некоторого га £ N}.

Функция /: А -т- В называется сюръекцией (surjection), или наложением, если её образ совпадает с множеством В, т.е. всякий элемент Ь £ В является образом некоторого элемента а £ А. Например, функция /: N -> N, заданная формулой /(га) = [п/2\, является сюръекцией. Функция /(га) = 2га не будет сюръекцией, если считать, что /: N -> N, но будет таковой, если считать её отображающей множество натуральных чисел в множество чётных натуральных чисел. Функцию f:A-B, являющуюся сюръекцией, называют также отображением А на В (onto В).

Функция /: А -> В называется инъекцией (injection), или вложением, если различным аргументам соответствуют различные значения, т.е. если /(а) ф f(a) при а ф а. Например, функция /(га) = 2га является инъекцией множества N в множество N, поскольку любое число га является образом самое большее одного элемента (га/2, если га четно; нечётные числа не являются образами никаких элементов). Функция /(га) = [п/2\ не является инъекцией, так как (например) /(2) = /(3) = 1. В английской литературе для инъекций употребляется также термин «one-to-one function*.

Функция /: А -> В называется биекцией (bijection), если она одновременно является инъекцией и сюръекцией. Например, функция /(га) = ( - 1)п[~га/2], рассматриваемая как функция, отображающая



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]