Лекция 2

Лекция 2

МЭИ. Инновационная образовательная программа

Соответствие, отображение

  1. Упорядоченной парой называют пару элементов (x,y) такую, что равенство двух пар (x,y) = (a,b) возможно тогда и только тогда, когда x = a и y = b.
  2. Прямым (декартовым) произведением двух множеств A и B называется множество A×B = {(x,y)|   x О A,   y О B }
  3. Три свойства прямого произведения.
    A×Ж = Ж,

    A×(BИC)=(A×B)И(A×C),

    A×(BЗC)=(A×B)З(A×C).
  4. Соответствием между множествами A и B называют любое подмножество G их прямого произведения.
  5. Областью определения соответствия (или первой проекцией) называется множество
    Dom G = пр1 G = { x|    ( x,y ) О G  }
  6. Областью значений соответствия (или второй проекцией) называется множество
    ImG = пр2 G = {  y|    (x,y ) О G }.
  7. Сечением соответствия G по элементу x0 называется множество G|x0 = { y (x0,y) О G }.
  8. Сечением соответствия G по элементу y0 называется множество G|y0 = {  y( x,y0 ) О G  }.
  9. Соответствием, обратным соответствию G, называется множество
    G - 1 = {  ( y,x )|   ( x,y ) О G  }.
  10. Пустым называется соответствие, которое не содержит ни одного элемента.
  11. Соответствие называется полным, если G = A×B.
  12. Матрицы, каждый элемент которых равен нулю или единице, называются булевыми.
  13. Дизъюнкция Ъ и конъюнкция Щ.
    1Ъ1 = 1 1Щ1 = 1
    1Ъ0 = 11Щ0 = 0
    0Ъ1 = 10Щ1 = 0
    0Ъ0 = 00Щ0 = 0
  14. Пусть заданы три множества X, Y и Z и два соответствия - G 1 М X×Y и G 2 М Y×Z. Композицией соответствий G 1 и G 2 называется подмножество G 3 прямого произведения X×Z: G 3 = G 2 °G 1 = { (x,z)  |    (x,y) О G 1 ,    (y,z) О G 2  }.
  15. Композиция G2 °G 1 № Ж, если пересечение Dom G2 ЗImG 1 № Ж.
  16. Соответствие G М X×Y называется отображением, если область определения соответствия совпадает с множеством X (т.е. Dom G = X или пр1 G = X).
  17. Отображение называется функциональным (или однозначным), если любое сечение G|x содержит только один элемент.
  18. Шесть свойств отображений. Если f: X® Y и A1 М A2 М X, B1 М B2 М Y, то
    1. f(A1) М f(A2),
    2. f(A1ИA2)=f(A1)Иf(A2),
    3. f(A1ЗA2) М f(A1)Зf(A2),
    4. f-1(B1) М f-1(B2),
    5. f-1(B1ИB2)=f-1(B1)Иf-1(B2),
    6. f-1(B1ЗB2)=f-1(B1)Зf-1(B2),
  19. Отображение f:X ® Y называется сюръективным или отображением на множество Y, если Imf = Y. Другими словами, f сюръективно, если каждый элемент y О Y имеет хотя бы один прообраз, т.е. " y О Y   $ x О X:y = f( x ).
  20. Отображение f:X ® Y называется инъективным, если из условия x1 № x2 следует, что f( x1 ) № f( x2 ), т.е. различные элементы множества X должны иметь различные образы.
  21. Отображение называется биективным если оно одновременно сюръективно и инъективно.
  22. Пусть заданы два отображения f:X ® Y и g:Y ® Z. Композицией отображений (сложным отображением, суперпозицией отображений) называют отображение j:X ® Z, определяемое условием j( x) = g °f( x ) = g( f( x ) ), "x О X.
  23. Композиция отображений ассоциативна, т.е. для заданных трех отображений f:X® Y, g:Y ® Z, h:X ® Z, справедливо равенство h °( g°f ) = ( h °g ) °f.
  24. Отображение g называется обратным к отображению f если одновременно выполняются два условия g °f = eX и f °g = eY .
  25. Когда справедливо только одно из двух условий, например, g °f = eX , то g называют левым обратным отображением. Соответственно, если выполнено только второе равенство f °g = eY , то g называют правым обратным отображением.
  26. Лемма. Если для композиции двух отображений выполняется равенство g °f = eX , то g является сюръекцией, а f - инъекцией.
  27. Теорема. Отображение f:X ® Y имеет обратное тогда и только тогда, когда f является биективным отображением.
  28. Если f:X ® Y биективно, то обратное отображение f - 1:Y ® X также является биекцией, причем ( f - 1 ) - 1 = f.
  29. Пусть f:X ® Y и g:Y ® Z биективные отображения. Тогда: композиция g°f биективных отображений биективна. ( g °f ) -1 = f - 1 °g - 1.