Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

Побудова по комутативній ідемпотентній півгрупі піврешітки

with 4 comments

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

Щоб зрозуміти про що йде мова, досить знати матеріал матаналізу за перший тиждень, бо маємо:

Словничок

Можливо занадто детальний, але це хай це буде повторенням від самого початку…

Побудова

Нехай < D, + > – комутативна ідемпотентна півгрупа. Тобто + – комутативна, ідемпотентна та асоціативна операція.

Задамо на D бінарне відношення \leq:

x \leq y\ \Leftrightarrow x + y = y

Якщо ми доведемо що \leq – відношення часткового порядку, та для будь-яких двох елементів з D існує супремум.

Доведення

Спочатку доводимо, що \leq – відношення часткового порядку, тобто:

  • рефлексивне: x \leq x \Leftrightarrow x + x  = x, а це випливає з ідемпотентності +.
  • антисиметричне: x \leq y \wedge y \leq x \Leftrightarrow x + y = y \wedge y + x = x, і з комутативності + випливає x = y
  • транзитивне: x \leq y \wedge y \leq z \Leftrightarrow x + y = y \wedge y + z = z \Rightarrow x + y + y + z = y + z \Rightarrow x + y + z = z \Rightarrow x + z = z \Leftrightarrow x \leq z.

< D,\leq > – частково впорядкована.

Придумуємо супремум підмножини двох елементів:

\sup \{ x,y \} = x + y

Доводимо що він супремум, шукаємо множину всіх верхніх граней:

\{z | x \leq z \wedge y \leq z\}. x + z = z \wedge y + z = z \Rightarrow x + z + y + z = z + z \Rightarrow x + y + z = z \Rightarrow x + y \leq z, і остання рівність показує що x + y – найменший з усієї множини верхніх граней, тобто справді супремум.

Таким чином можна сформулювати теорему:

Т. Нехай < D, + > – комутативна ідемпотентна півгрупа. Якщо x \leq y\ \Leftrightarrow x + y = y, то < D,\leq > – верхня піврешітка, при чому \sup\{ x, y\} = x + y.

Про те, як копіювати з вікіпедії статті з формулами і правильними посиланнями – буде в наступній серії :).

Advertisements

Written by bunyk

Лютий 10, 2011 at 00:00

Оприлюднено в Конспекти, Передруки

Tagged with

Відповідей: 4

Subscribe to comments with RSS.

  1. А при чому тут матаналіз? Це якби дискретка.

    Afedaxo

    Лютий 10, 2011 at 00:17

    • Це якби абстрактна алгебра. Просто початки теорії множин в нас викладають як в курсі матаналізу, так і дискретки.

      bunyk

      Лютий 10, 2011 at 11:34

      • Ну алгебраїчні системи все ж є підрозділом дискретної математики http://en.wikipedia.org/wiki/Discrete_math#Algebra

        Afedaxo

        Лютий 10, 2011 at 19:26

      • Algebraic structures occur as both discrete examples and continuous examples.
        Алгебра буває як і дискретна так і континуальна. Тому вона перетинається як з матаналізом, так і з дискреткою.

        З матаналізу в мене був харизматичніший викладач, от я й запам’ятав маталаніз. Хоча мені й дискретка подобалась. Тільки з неї я більше пам’ятаю теорему про планарність доведення якої заборонене МОЗ. 🙂

        bunyk

        Лютий 10, 2011 at 23:40


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: