Следствие для однородных систем

Теорема об эквивалентности

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

Доказательство:

a`<sub>11</sub>x<sub>1</sub>+a`₁₂x₂+…a`<sub>1n</sub>x<sub>n</sub>=b`₁

… (2’)

a`<sub>m1</sub>x<sub>1</sub>+a`_m2x₂+…a`<sub>mn</sub>x<sub>n</sub>=b`_m

докажем преобразования систем 2 и 2’, полученной из 2 системой элементарного преобразования

в случае 1 переставив местами i и k вернёмся к первоначальной системе (т к преобразования обратимы)

аналогично в случае 2 прибавив к i-ому уравнению в 2’ k-е, умноженное на (-c), получим i-ое уравнение системы 2

Докажем, что любое решение системы 2 является решением 2’

При 1-ом эл.пр. ур-ия не изменились – изменился порядок

При 2-ом ур-ия кроме 1-го не изменились=> решение им удовлетворяет

Т.к. наше решение удовлетворяет i-ому и k-ому уравнениям системы 2, то

a_i1x₁⁰+…+a_inx_n⁰=b_i a_k1x₁⁰+...+a_knx_n⁰=b_k

умножив обе части посл.ур. на с и прибавив к 1-ому, получим тождество с xi=xi⁰

в силу отмеченной обратимости эл.пр. любое решение системы 2’ будет решением системы 2

2.СЛУ. Приведение к ступенчатому виду. Теорема об эквивалентности системы системе в ступенчатом виде. Критерий совместности системы.

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

1) Найдем строку, где a_i≠ 0 и a₁ó a_i

2) каждой строки ai вычтем a₁*a_i1/a₁₁

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁

0 +a₂₂x₂+…+a_2nx_n=b₂

0+ +a_m2x2+…+a_mnx_n=b_m

3) Применим шаги 1, 2 для системы без 1-го уравнения, и получим такую систему:

{a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁

{0 +a₂₂x₂+…+a_2nx_n=b₂

{0+0+…+a_rx_n=b_r+1

{0+0+…+0=b_m

Теорема об эквивалентности системы системе в ступенчатом виде

Любая СЛУ эквивалентна системе в ступенчатом виде

Док-во: указанным способом любая система приводится к ступенчатому виду с сохранением решений

3.СЛУ. Критерий определенности. Следствие. Следствие для однородных систем.

Критерий Определённости (r=n)

Критерий определённости

СЛУ совместна ó когда эквив ей система в ступенчатом виде не имеет уравнений вида 0=bi≠ 0

Док-во: =>

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁

0…

a_rnx_n=b_r=0

0=b_r+1=0

очевидно, что уравнение r имеет решение

подставляем это решение в пред. уравнение, выбираем произвольное значение для свободных переменных, тогда любое А предыдущее ур-ие имеет решение => система совместна

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁

0…a₂₂

a₃₃

a_nnx_n=b_n

0=b_r+1=0

0=b_m=0

Следствие

Когда r≠ n есть общее и частное решение системы

3.СЛУ. Критерий определенности. Следствие. Следствие для однородных систем.

Критерий Определённости (r=n)

Совместная система является определенной ó r=n (кол-во уравнений совпадает с кол-вом неизвестных)

Следствие

Раз r=n => при переходе от ур-ия i к i-1 не может появиться свободных переменных => А ур-ие имеет единственное решение => вся система имеет единственное решение => система называется однородной;

Следствие для однородных систем

однородная система всегда совместна => однородная система будет определена ó когда нулевое решение – единственное решение

4.Множества. Способы задания множеств. Операции над множествами.

Множество – любая совокупность элементов

Способы задания множеств

1) Перечисление элементов

2) Указание признака {p │ p€N, – простые}

3) Через предыдущие элементы множества 1€N, если x€N => x+1€N

Операции над множествами

1)Пересечение

A∩ B={x │ x€A и x€B}

2)Объединение

AVB={x │ x€A или x€B}

3)Разность A\(-)B={x │ x€A и x не прин B}

4)Если АсВ => В\А=не А

5)(АVВ)∩ С=(АVС)∩ (АVВ)
5.Отображения. Сюрьекции, инъекции и биекции. Композиция отображений. Теорема об отображении множества самого на себя.

Отображение – правило, которое ставит в соответствие элементы 1-го множества элементы др множества

Сюрьекция – если Im(f)=Y, если каждому элементу множества Y соответствует хотя бы 1 элемент множества X

Инъекция – если f(x₁)=f(x₂) => x₁=x_2, если разным элементам множества Х соответствуют разные элементы множества Y

Пусть Отображение – правило, которое ставит в соответствие элементы 1-го множества элементы др множества

Пусть f: X→ Y g: Y→ Z сложной функцией (композицией или суперпозицией) называется функция h: X→ Zпо правилу h(x)=g(f(x))

Теорема об отображении множества самого на себя

пусть f: X→ X => след утверждения эквивалентны

f – инъективно f – сюрьективно f – биективно

Док-во:

(3→ 1), (3→ 2) – очевидно

(1, 2→ 3) очевидно по определению

(1→ 2) – доказать от противного

Еy Аx f(x)≠ y

│ Im(f)│ - мощность образа f

│ Im(f)│ ≥ │ х│ =>

с др стороны {│ Im(f)│ ≤ │ х│ }

{│ Im(f)│ ≥ │ х│ } => │ Im(f)│ = │ х│ => (2=1)

6.Бинарные отношения. Свойства отношений. Отношение эквивалентности. Теорема о разбиении множества и отношении эквивалентности.

Бинарное отношение – множество упорядоченных пар элементов множества

Свойства:

1)Рефлексивность – если всякий элемент множ находится в соотношении с самим собой

2)Симметричность – если для каждой пары элементов х, у выполнение отношений xRy влечет отношение yRx

3)Транзитивность – выполнение отношений xRy yRz влечет xRz

Эквивалентность – R удовлетворяет свойствам 1, 2, 3

Теорема о разбиении множества и отношениях эквивалентности

Множество классов эквивалентности по отношению ~ является разбиением множества Х в том смысле, что Х является объединением непересекающихся подмножеств (разбиение обозначается Х(π ~(x))

Так как x€x, то X=U_x€Xx Если x`∩ х``≠ ○ и х х` x`` то х x` и х х``, откуда в силу транзитивности x` x`` и x` x``, значит различные классы не пересекаются ∆

7.Принцип математической индукции. Применение.

х-множ-во с заданным порядком, s – свойство

Если из того, что S(x₀), S(x₁), …, S(x_n)=> S(x_n+1) то сущность натурального ряда сводится к принципу мат инд

Док-во

C_n^k – кол-во подмножеств мощности k во множестве мощности получаем рекур. формулу

{x1, x2,..xn}

C_n^k=C_n-1+C_n-1^k-1

C_n^k=n! /((n-k)! k!)

Докажем по индукции

1)База индукции

С₁²=2! /((2-1)! 1!)=2 С₃¹=3 С₃²=3 С₂²=1

2)Предположение индукции

Предположим, что формула верна для всех n≤ N_o

3)Шаг индукции(формула верна для след.)

Nk+1

C_n⁰+1=C_No^k+C_N0^k+1=N_o! /((N_o-1)! k!) n-1≠ 0

8.Перестановки. Композиция перестановок. Группа перестановок. Мощность группы перестановок (доказательство).

Перестановка-упорядоч набор чисел 1, 2,..n или биекция на множестве, которая числу iставит в соответствие i-ый элемент из набора

Композицией перестановок f и g называется перестановка f ◦ g, определенная формулой

(f ◦ g)(x): = f (g (x)).

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

Мощность группы перестановок

Перестановка - упорядоченный набор чисел 1, 2,..т, которая числу i ставит в соответствие i-ый элемент из набора

Мощность симметрической группы:

9.Перестановки. Циклическая запись перестановки. Теорема о разложении перестановки в произведение независимых циклов.

Цикл – произведение более простых перестановок

Каждую перестановку единственным образом можно записать в виде объединения независимых циклов

Если α ○ β =β ○ α то они перестановочные π =α ₁ α ₂…α _k = β ₁ β ₂… β _i докажем от противного

у нас есть 2 перестановки независ. циклов возьмем 1, она лежит в циклах α _i и β _j

α _i(1)=β _j(1), α _i²(1)=β _j²(1) и т д =>

цикл α _i совпадает с циклом β _j аналогично для всех остальных циклов