Jól megrendelt készlet

A jól rendezett halmaz egy lineárisan rendezett M halmaz úgy, hogy bármely nem üres részhalmazának van minimális eleme. Vagyis ez egy jól megalapozott , lineáris sorrendű halmaz.

Példák

Az üres készlet jól rendezett.
A végtelen, jól rendezett halmaz legegyszerűbb példája a természetes számok természetes sorrendű halmaza.
Az egész számok halmaza nem teljesen rendezett, mivel például a negatív számok között nincs legkisebb . Azonban meglehetősen rendezetté tehető egy nem szabványos "kisebb vagy egyenlő" reláció meghatározásával [1] , amelyet a következőképpen jelölünk és definiálunk: $\preccurlyeq$

a\preccurlyeq b,

ha vagy vagy vagy és

a=b,

|a|<|b|,

|a|=|b|

a<0<b.

Ekkor az egész számok sorrendje a következő lesz: Különösen a legkisebb negatív szám lesz.

0\preccurlyeq -1\preccurlyeq 1\preccurlyeq -2\preccurlyeq 2\dots

-egy

A megszámlálhatatlan, jól rendezett halmaz legegyszerűbb példája az összes megszámlálható sorszám összegyűjtése a reláció szerint . Feltételezve a kontinuum hipotézist, ereje egyenlő a kontinuum hatványával . $\ban ben$

Tulajdonságok

Zermelo tétele szerint , ha valaki elfogadja a választás axiómáját , akkor bármelyik halmaz jól rendezhető. Sőt, az az állítás, hogy minden halmaznak létezik teljes sorrendje, egyenértékű a választás axiómájával. Különösen a választási axióma jelenlétében a valós számok halmaza teljesen rendezhető.
Ha X és Y két jól rendezett halmaz, akkor vagy izomorf egymással, vagy pontosan az egyik izomorf a másik kezdeti szegmensével.

Lásd még

Transzfinit indukció

Irodalom

N. K. Verescsagin, A. Shen. 1. rész. A halmazelmélet kezdetei // Előadások a matematikai logikáról és az algoritmusok elméletéről. — 2. kiadás, javítva. - M. : MTSNMO , 2002. - 128 p.

Jegyzetek

↑ Donald Knuth . A programozás művészete, I. kötet. Alapvető algoritmusok. - M .: Mir , 1976. - S. 571 (15b). — 736 p.