Välordningssatsen

Välordningssatsen eller välordningsprincipen är en utsaga inom mängdteorin som säger att varje mängd kan välordnas. Givet mängdlärans övriga "vanliga" axiom (ZF) är välordningssatsen en av utsagorna som är ekvivalent med urvalsaxiomet. Välordningsprincipen används ofta för att möjliggöra transfinit induktion.

Bevis med hjälp av Zorns lemma

Beviset för att välordningsprincipen är ekvivalent med urvalsaxiomet är litet snårigt. Det är dock relativt enkelt att visa att den följer från en annan av de ekvivalenta utsagorna, nämligen Zorns lemma.

Låt X vara en mängd, och låt U vara mängden av partiella välordningar på X, d. v. s. välordningar av någon delmängd till X. Varje element i Ukan beskrivs av ett par (M,v) där M är en delmängd av X, och v är en välordning av M. (Det bestäms också entydigt av relationsgrafen för v.)

Vi kan nu införa en partialordning på U, genom föreskriften

$(M,v)<(N,w){\text{ om }}M\subset N,{\text{ restriktionen av }}W{\text{ till }}M{\text{ är }}v,{\text{och }}(x\in M\land y\in N\setminus M\Rightarrow w(x,y)).$

Det sista villkoret betyder att elementen i M "kommer först" i N, så att övriga element i N är större än varje element i M. Med litet besvär kan man visa att om vi har en ordnad delmängd av U, så kommer välordningarna på de respektive mängderna att inducera en välordning på deras union. Denna partiella välordning är en övre begränsning för denna ordnade delmängd. Existensen av sådana övre begränsningar är förutsättningen för att Zorns lemma skall kunna tillämpas; så enligt detta lemma finns ett maximalt element (E,o) i U. Om det funnes något element x i X som inte låge i E, så hade (E,o) kunnat utvidgas genom att placera x sist i E ∪ {x}, vilket motsäger maximaliteten för (E,o). Därmed är o en välordning på X = E.