Войти  |  Регистрация
Авторизация

Полурешётка



Полурешётка (англ. semilattice, до 1960-х годов также использовался термин полуструктура) в общей алгебре — полугруппа, бинарная операция в которой коммутативна и идемпотентна.

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

Алгебраические определения

Полурешётка аксиоматизируется как алгебра, снабжённая бинарной операцией ⟨ V , ⋆ ⟩ {displaystyle langle V,star angle } следующими тождествами:

  • x ⋆ x = x {displaystyle xstar x=x} (идемпотентность);
  • ( x ⋆ y ) ⋆ z = x ⋆ ( y ⋆ z ) {displaystyle (xstar y)star z=xstar (ystar z)} (ассоциативность);
  • x ⋆ y = y ⋆ x {displaystyle xstar y=ystar x} (коммутативность).
  • Если алгебры ⟨ V , ∨ ⟩ {displaystyle langle V,vee angle } и ⟨ V , ∧ ⟩ {displaystyle langle V,wedge angle } — полурешётки, и их операции связаны соотношениями (называемым законами поглощения):

    • x ∨ ( x ∧ y ) = x {displaystyle xvee (xwedge y)=x} ,
    • x ∧ ( x ∨ y ) = x {displaystyle xwedge (xvee y)=x} ,

    то алгебра ⟨ V , ∨ , ∧ ⟩ {displaystyle langle V,vee ,wedge angle } является решёткой. В таком контексте ⟨ V , ∨ ⟩ {displaystyle langle V,vee angle } называют верхней полурешёткой, а ⟨ V , ∧ ⟩ {displaystyle langle V,wedge angle } — нижней. В верхних полурешётках вводится верхний элемент ⊤ ∈ V {displaystyle op in V} такой, что ⊤ ∨ x = ⊤ {displaystyle op vee x= op } для всех элементов x ∈ V {displaystyle xin V} , в нижних — нижний элемент ⊥ ∈ V {displaystyle ot in V} такой, что ⊥ ∧ x = ⊥ {displaystyle ot wedge x=ot } , полурешётки, в которых существуют такие элементы, называют ограниченными.

    Частичный порядок

    Частичный порядок в алгебраически определённой полурешётке ( V , ∧ ) {displaystyle (V,wedge )} может быть введён следующим образом: x ⊑ y {displaystyle xsqsubseteq y} тогда и только тогда, когда x ∧ y = x {displaystyle xwedge y=x} . Поскольку бинарная операция в полурешётке идемпотентна, коммутативна и ассоциативна, то определённый таким образом порядок является рефлексивным ( x ⊑ x {displaystyle xsqsubseteq x} ), антисимметричным ( ( x ⊑ y ) & ( y ⊑ x ) ⇒ ( x = y ) {displaystyle (xsqsubseteq y)And (ysqsubseteq x)Rightarrow (x=y)} и транзитивным ( ( x ⊑ y ) & ( y ⊑ z ) ⇒ ( x ⊑ z ) {displaystyle (xsqsubseteq y)And (ysqsubseteq z)Rightarrow (xsqsubseteq z)} ).


    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail:
    • bowtiesmilelaughingblushsmileyrelaxedsmirk
      heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
      winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
      worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
      expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
      disappointedconfoundedfearfulcold_sweatperseverecrysob
      joyastonishedscreamtired_faceangryragetriumph
      sleepyyummasksunglassesdizzy_faceimpsmiling_imp
      neutral_faceno_mouthinnocent