Gratis boolesk algebra

I matematik är en fri boolesk algebra en boolesk algebra med en framstående uppsättning element, kallade generatorer , så att:

Varje element i den booleska algebra kan uttryckas som en finit kombination av generatorer, med hjälp av de booleska operationerna, och
Generatorerna är så oberoende som möjligt, i den meningen att det inte finns några relationer mellan dem (återigen i termer av finita uttryck med de booleska operationerna) som inte håller i varje boolesk algebra oavsett vilka element som väljs.

Ett enkelt exempel

The Hasse diagram of the free Boolean algebra on two generators, p and q. Take p (left circle) to be "John is tall" and q (right circle)to be "Mary is rich". The atoms are the four elements in the row just above FALSE.

Generatorerna av en fri boolesk algebra kan representera oberoende propositioner . Betrakta till exempel påståendena "Johannes är lång" och "Maria är rik". Dessa genererar en boolesk algebra med fyra atomer , nämligen:

John är lång och Maria är rik;
John är lång och Maria är inte rik;
John är inte lång och Maria är rik;
John är inte lång och Mary är inte rik.

Andra element i den booleska algebra är då logiska disjunktioner av atomerna, som "Johannes är lång och Maria är inte rik, eller Johannes är inte lång och Maria är rik". Dessutom finns det ytterligare ett element, FALSK, som kan ses som den tomma disjunktionen; det vill säga disjunktionen av inga atomer.

Detta exempel ger en boolesk algebra med 16 element; i allmänhet, för finita n , har den fria booleska algebra med n generatorer 2 ⁿ atomer och därför $2^{2^{n}}$ element.

Om det finns oändligt många generatorer råder en liknande situation förutom att det nu inte finns några atomer . Varje element i den booleska algebra är en kombination av ändligt många av de genererande propositionerna, med två sådana element som anses vara identiska om de är logiskt ekvivalenta .

Ett annat sätt att se varför den fria booleska algebra på en n-elementuppsättning har $2^{2^{n}}$ element är att notera att varje element är en funktion från n bitar till en. Det finns $2^{n}$ möjliga ingångar till en sådan funktion och funktionen kommer att välja 0 eller 1 att mata ut för varje ingång, så det finns $2^{2^{n} }$ möjliga funktioner.

Kategoriteoretisk definition

I kategoriteorispråket kan fria booleska algebror definieras helt enkelt i termer av ett komplement mellan kategorin mängder och funktioner, Set , och kategorin booleska algebror och booleska algebrahomomorfismer , BA . Faktum är att detta tillvägagångssätt generaliserar till vilken algebraisk struktur som helst som kan definieras inom ramen för universell algebra .

Ovan sa vi att en fri boolesk algebra är en boolesk algebra med en uppsättning generatorer som beter sig på ett visst sätt; alternativt kan man börja med en mängd och fråga vilken algebra den genererar. Varje uppsättning X genererar en fri boolesk algebra FX definierad som algebra så att för varje algebra B och funktion f : X → B , finns det en unik boolesk algebrahomomorfism f ′: FX → B som sträcker sig f . Diagrammatiskt ,

där i _X är inkluderingen och den streckade pilen anger unikhet. Tanken är att när man väl väljer vart elementen i X ska skickas så bestämmer lagarna för booleska algebrahomomorfismer vart allt annat ska skickas i den fria algebra FX . Om FX innehöll element som inte kunde uttryckas som kombinationer av element av X , så skulle f ′ inte vara unikt, och om elementen i X inte var tillräckligt oberoende, skulle f ′ inte vara väldefinierat! Det är lätt att visa att FX är unikt (upp till isomorfism), så denna definition är vettig. Det är också lätt att visa att en fri boolesk algebra med genereringsmängd X, som den ursprungligen definierades, är isomorf till FX , så de två definitionerna överensstämmer.

En brist med definitionen ovan är att diagrammet inte fångar att f ′ är en homomorfism; eftersom det är ett diagram i Set betecknar varje pil bara en funktion. Vi kan fixa detta genom att dela upp det i två diagram, ett i BA och ett i Set . För att relatera de två introducerar vi en funktor U : BA → Mängd som " glömmer " den algebraiska strukturen, avbildar algebror och homomorfismer till deras underliggande mängder och funktioner.

Om vi tolkar den översta pilen som ett diagram i BA och den nedre triangeln som ett diagram i Set , så uttrycker detta diagram korrekt att varje funktion f : X → UB sträcker sig till en unik boolesk algebrahomomorfism f ′: FX → B . Funktionen U kan ses som en anordning för att dra tillbaka homomorfismen f ′ till Set så att den kan relateras till f .

Den anmärkningsvärda aspekten av detta är att det senare diagrammet är en av de olika (motsvarande) definitionerna av när två funktorer är adjoint . Vårt F sträcker sig lätt till en funktionsuppsättning → BA , och vår definition av X som genererar en fri boolesk algebra FX är just att U har en vänsteradjoint F.

Topologisk insikt

Den fria booleska algebra med κ- generatorer , där κ är ett ändligt eller oändligt kardinaltal , kan realiseras som samlingen av alla clopen -delmängder av {0,1} ^κ , givet produkttopologin förutsatt att {0,1} har den diskreta topologi . För varje α<κ är den α: te generatorn mängden av alla element i {0,1} ^κ vars α :te koordinat är 1. I synnerhet genererar den fria booleska algebra med $\aleph _{0}$ är samlingen av alla clopen-delmängder av ett Cantor-rum , ibland kallat Cantor-algebra . Denna samling är räknebar . I själva verket, medan den fria booleska algebra med n generatorer, n ändlig, har kardinalitet $2^{2^{n}}$ , den fria booleska algebra med $\aleph _{0}$ generatorer, som för vilken fri algebra som helst med $\aleph _{0}$ generatorer och otaliga många finitära operationer, har kardinalitet $\aleph _{0}$ .

För mer om detta topologiska tillvägagångssätt för fri boolesk algebra, se Stones representationssats för booleska algebror .

Se även

Steve Awodey (2006) Kategoriteori (Oxford Logic Guides 49). Oxford University Press.
Paul Halmos och Steven Givant (1998) Logic as Algebra . Mathematical Association of America .
Saunders Mac Lane (1998) Kategorier för den arbetande matematikern . 2:a uppl. (Examinerade texter i matematik 5). Springer-Verlag.
Saunders Mac Lane (1999) Algebra , 3d. ed. American Mathematical Society . ISBN 0-8218-1646-2 .
Robert R. Stoll, 1963. Uppsättningsteori och logik , kap. 6.7. Dover nytryck 1979.