Кіріспе
Салыстыруға келмейтін элементтердің ішкі жиыны
Математикада, тәртіп теориясы саласында, антитізбек – ішінара реттелген жиынның ішкі жиыны, онда кез келген екі түрлі элемент салыстыруға келмейді. Ішінара реттелген жиынның ең ірі антитізбегінің мөлшері оның ені деп аталады. Дилворт теоремасы бойынша, бұл жиынды тізбектерге (толық реттелген ішкі жиындарға) бөлуге қажетті ең аз тізбектер санына тең. Дуальды түрде, ішінара реттелген жиынның биіктігі (оның ең ұзын тізбегінің ұзындығы) Мирский теоремасы бойынша жиынды бөлуге қажетті ең аз антитізбектер санына тең. Шекті ішінара реттелген жиынның барлық антитізбектерінің жиымына қосылу және қиылысу амалдарын қолдануға болады, осылайша оларды үлестірімді торға айналдырады. Егер жиынның барлық ішкі жиындары жиынның кіріктірілуі бойынша жартылай реттелген болса, онда антитізбектер Спернер отбасылары деп аталады, ал олардың торы – бос үлестірімді тор, онда Дедекинд саны бар. Әдетте, шекті ішінара реттелген жиынның антитізбектерінің санын есептеу #P толық есебіне жатады.
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its width. By Dilworth's theorem, this also equals the minimum number of chains (totally ordered subsets) into which the set can be partitioned. Dually, the height of the partially ordered set (the length of its longest chain) equals by Mirsky's theorem the minimum number of antichains into which the set can be partitioned. The family of all antichains in a finite partially ordered set can be given join and meet operations, making them into a distributive lattice. For the partially ordered system of all subsets of a finite set, ordered by set inclusion, the antichains are called Sperner families
and their lattice is a free distributive lattice, with a Dedekind number of elements. More generally, counting the number of antichains of a finite partially ordered set is #P complete.
Анықтамалар
Кез келген жартылай реттелген жиынтық болсын. Егер екі элементтің біреуі екіншісінен кіші немесе тең болса, онда олар салыстырылатын болады. Егер екі элемент салыстырылмайтын болса, олар салыстырылмалы деп аталады; яғни, және салыстырылмалы емес, егер ешқайсысы да екіншісінен кіші немесе тең болмаса.
Жезек – бұл жиынтықтың кіші жиыны, онда әрбір элемент жұбы салыстырылатын болады; яғни, толық реттелген. Антижелек – бұл жиынтықтың кіші жиыны, онда әр түрлі элементтердің әр жұбы салыстырылмайтын болады; яғни, антижелектегі екі түрлі элементтің арасында реттік қатынас жоқ. (Дегенмен, кейбір авторлар "антижелек" терминін күшті антижелек мағынасында қолданады, яғни антижелектегі екі түрлі элементтен кіші элемент жоқ болатын жиын.)
(However, some authors use the term "antichain" to mean strong antichain, a subset such that there is no element of the poset smaller than two distinct elements of the antichain.)
Биіктігі мен ені
Максималды антижелі – басқа антижелілердің дұрыс кіші жиыны емес антижелі. Максималды антижелі – кез келген басқа антижеліге қарағанда кемінде сол сияқты кардиналдылығы бар антижелі. Ішінара реттелген жиынның ені – максималды антижелінің кардиналдығы. Кез келген антижелі кез келген тізбектің бір ғана элементін қиып өте алады, сондықтан егер реттің элементтерін тізбектерге бөле алсақ, онда реттің ені сол тізбектер санынан аспауы керек (антижеліде егер 100-ден көп элемент болса, қабақ принципi бойынша, оның екі элементі бір тізбекке тиесілі болады, бұл қайшылыққа әкеледі). Дилворт теоремасы осы шекке әрқашан жете алатынын көрсетеді: әрқашан антижелі және элементтерді тізбектерге бөлу табылады, мұнда тізбектердің саны антижелідегі элементтер санына тең, демек, ол еніне де тең болуы керек. Сол сияқты, ішінара реттің биіктігін тізбектің ең үлкен кардиналдығы ретінде анықтауға болады. Мирский теоремасы бойынша, шекті биіктігі бар кез келген ішінара реттелген жиын үшін биіктік, осы жиынды бөлуге болатын антижелілердің ең кіші санына тең болады.
Спернер отбасылары
Элементтер жиынының кіші жиынтықтарының кіріктірілу реті бойынша антижелі Спернер отбасы деп аталады. Әртүрлі Спернер отбасыларының саны Дедекинд сандарымен есептеледі, олардың біріншілері: 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788. Тіпті бос жиынның өзінде де қуат жиынында екі антижелі бар: біреуі бір жиынды (бос жиынның өзін) қамтиды, ал екіншісі ешқандай жиынды қамтимайды.
2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 Even the empty set has two antichains in its power set: one containing a single set (the empty set itself) and one containing no sets.
Есептеу күрделілігі
Максималды антижелі (және оның мөлшері, берілген ішінара реттелген жиынның ені) полиномдық уақытта табылмайды. Берілген ішінара реттелген жиынтақтағы антижелілердің санын есептеу #P толық проблемасы болып табылады.