Dedekind-luvut ovat nopeasti kasvava kokonaislukusarja , joka on nimetty Richard Dedekindin mukaan, joka määritteli ne vuonna 1897. Dedekind-luku M ( n ) laskee n muuttujan monotonisten Boolen funktioiden lukumäärän . Vastaavasti nämä luvut laskevat n -alkiojoukon osajoukkojen antiketjujen lukumäärän, vapaan distributiivisen hilan alkioiden määrän , jossa on n generaattoria , tai abstraktien yksinkertaisten kompleksien , joissa on n elementtiä.
M ( n ) [1] [2] [3] tarkat asymptoottiset estimaatit ja tarkka lauseke summana [4] tunnetaan. Dedekindin ongelma M ( n ):n arvojen laskemisessa on kuitenkin edelleen vaikea – suljetun muotoista lauseketta arvolle M ( n ) ei tunneta, ja M ( n ):n tarkat arvot on löydetty vain [5] .
Boolen funktio on funktio, joka ottaa syötteenä n loogista muuttujaa (eli arvoja, jotka voivat olla joko epätosi (false) tai tosi (tosi), tai vastaavasti binääriarvoja , jotka voivat olla joko 0 tai 1) ja antaa toisen loogisen muuttujan tulosteena. Funktio on monotoninen , jos yhden syötemuuttujan vaihtaminen epätosi arvosta tosi voi muuttaa tulosteen vain epätosi arvosta tosi, mutta ei tosi arvosta epätosi. Dedekind-luku M ( n ) on n muuttujan eri monotonisten Boolen funktioiden lukumäärä.
Joukkojen vastaketju (tunnetaan myös nimellä Spencer-perhe ) on joukko joukkoja, joista mikään ei sisälly mihinkään muuhun joukkoon. Jos V on joukko n Boolen muuttujaa, V :n osajoukkojen antiketju A määrittää monotonisen Boolen funktion f , kun f:n arvo on tosi annetulle syötejoukolle, jos jokin funktion f syötteiden osajoukko on tosi, jos se kuuluu A ja false muuten. Sitä vastoin mikä tahansa monotoninen Boolen funktio määrittää siten antiketjun, Boolen muuttujien vähimmäisosajoukot, jotka pakottavat funktion evaluoitumaan todeksi. Siksi Dedekind-luku M ( n ) on yhtä suuri kuin n - elementtijoukon [3] osajoukkojen eri antiketjujen lukumäärä .
Kolmas vastaava tapa kuvata samaa luokkaa käyttää hilateoriaa . Kahdesta monotonisesta Boolen funktiosta f ja g löydämme kaksi muuta monotonista Boolen funktiota ja , niiden looginen konjunktio ja looginen disjunktio . Kaikkien n syötteen monotonisten Boolen funktioiden perhe muodostaa yhdessä näiden kahden operaation kanssa Birkhoffin esityslauseella en] määritellyn distributiivisen hilan n: n muuttujan osajoukkojen joukosta osittaisen joukon sisällyttämisjärjestyksen kanssa. . Tämä konstruktio antaa vapaan distributiivisen hilan , jossa on n generaattoria [6] . Siten Dedekind-luvut laskevat elementtien lukumäärän vapaassa distributiivisessa hilassa [7] [8] [9] .
Dedekind-luvut laskevat myös (yhden lisää) abstraktien yksinkertaisten kompleksien lukumäärän n alkiolla , joukkojen perhettä, jolla on ominaisuus, että mikä tahansa joukon osajoukko perheessä kuuluu myös perheeseen. Mikä tahansa antiketju määrittelee yksinkertaisen kompleksin , antiketjujen jäsenten osajoukkojen perheen, ja päinvastoin, kompleksien suurimmat yksinkertaisuudet muodostavat antiketjun [4] .
Arvolle n =2 on kuusi monotonista Boolen funktiota ja kuusi kaksielementtijoukon { x , y } osajoukkojen antiketjua:
Dedekind-lukujen tarkat arvot tunnetaan seuraavista :
2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 sekvenssi A000372 OEIS : ssä .Ensimmäiset kuusi näistä luvuista antoi kirkko [7] . M (6) laski Ward [10] , M (7) laski Church [8] Berman ja Köhler [11] ja M (8) laski Wiederman [5] .
Jos n on parillinen, niin M ( n ) on myös parillinen [12] . Viidennen Dedekind-luvun laskeminen kumoaa Garrett Birkhoffin oletuksen, jonka mukaan M ( n ) on aina jaollinen [7] :llä .
Kiselevich [4] kirjoitti uudelleen antiketjujen loogisen määritelmän seuraavaksi aritmeettiseksi kaavaksi Dedekind-luvuille:
missä on -th bitti , joka voidaan kirjoittaa pyöristämällä alaspäin
Tämä kaava on kuitenkin hyödytön M ( n ) -arvojen laskemiseen suurelle n :lle, koska summatermejä on paljon.
Dedekind-lukujen logaritmi voidaan arvioida tarkasti rajojen avulla
Tässä vasemmanpuoleinen epäyhtälö laskee niiden antiketjujen määrän, joissa jokaisessa joukossa on täsmälleen elementtejä, ja oikean epäyhtälön osoittivat Kleitman ja Markovsky [1] .
Koršunov [2] antoi vielä tarkempia arvioita [9]
jopa n , ja
parittomille n , missä
ja
Näiden arvioiden pääidea on, että useimmissa antiketjuissa kaikkien joukkojen koot ovat hyvin lähellä n /2 :ta [9] . Kun n = 2, 4, 6, 8, Koršunovin kaava antaa arvion, jonka virhe on 9,8 %, 10,2 %, 4,1 % ja -3,3 % [13] .