Rendezett halmazok

Definíció (I): Legyen A egy halmaz és < egy reláció rajta. (A,<) egy rendezett halmaz, ha

• x < x NEM igaz,
• x < y és y< z esetén x < z,
• tetszõleges x, y esetén x < y vagy x = y vagy y < x,

Definíció (II): Legyen A egy halmaz és <₌ egy reláció rajta. (A,<_-) egy rendezett halmaz, ha

• x <₌ x,
• x <₌ y és y <₌ x esetén x = y,
• x <₌ y és y <₌ z esetén x <₌ z,
• tetszõleges x, y esetén x <₌ y vagy y <₌ x,

Feladat:

1. Legyen (A,<) egy rendezett halmaz(I). Definiáljuk a <₌ relációt úgy, hogy a <₌ b akkor és csak akkor teljesüljön, ha a < b vagy a = b. Ekkor (A,<₌) rendezett halmaz (II).
2. Legyen (A,<₌) egy rendezett halmaz(II). Definiáljuk a < relációt úgy, hogy a < b akkor és csak akkor teljesüljön, ha a <₌ b és a = b NEM igaz. Ekkor (A,<) rendezett halmaz(I).
3. A fenti két irányú megfeleltetés párbaállítja a két definíció által leírt struktúrákat.

Megjegyzés: Tehát bármelyik definícióban leírt feltételeket elfogadhatjuk axiómarendszernek, a feladat alapján bevezethetjük a másik fogalomrendszer relációját és az ott leírt tulajdonságokra mint tételekre hívatkozhatunk.

Definíció: (A,<_A) és (B,<_B) két rendezett halmaz hasonló, ha van olyan f:A→ B bijekció, ami rendezéstartó, azaz a <_A a´ akkor és csak akkor, ha f(a) <_B f(a´).

Megjegyzés: Két hasonló rendezett halmazra úgy tekintünk mint két lényegében azonos rendezett halmazra. Használjuk a rendezés-izomorf, illetve azonos típusú leírását is ennek a viszonynak.

Feladat: A következõ pontokban leírt rendezett halmazok közül állapítsuk meg melyek típusa ugyanaz:

• • (N, <),
  • (N₀, <),
  • ({páros természetes számok}, <)
  • (Z,<),
  • (Z-{0}, <),
  • ({negatív egészek}, <)
  • (N U {végtelen}, <), (a rendezést józan ésszel találjuk ki)
  • (N, <)×({0,1}, <) (két pár rendezését a második koordinátájuk dönti el, egyenlõség esetén pedig az elsõ koordináta dönt).
  • (N, <)×^~({0,1}, <) (két pár rendezését az elsõ koordinátájuk dönti el, egyenlõség esetén pedig a második koordináta dönt).
• • (Q, <),
  • (Q⁺, <),
  • ({a (0,1) intervallum racionális számai}, <)
  • ({nemnegatív racionális számok}, <)
  • ({nempozitív racionális számok}, <)
  • (Q-{0}, <)
  • (Q U {π}, <),
  • (Q U {végtelen}, <), (a rendezést józan ésszel találjuk ki)
  • (Q,<)×({0,1}, <) (két pár rendezését a második koordinátájuk dönti el, egyenlõség esetén pedig az elsõ koordináta dönt).
  • (R, <)×^~({0,1}, <) (két pár rendezését az elsõ koordinátájuk dönti el, egyenlõség esetén pedig a második koordináta dönt).
• • (R, <),
  • (R⁺, <),
  • (R-{0}, <),
  • (R-{π}, <),
  • (R-(0,1), <),
  • (R-[0,1), <),
  • (R,<)×({0,1}, <) (két pár rendezését a második koordinátájuk dönti el, egyenlõség esetén pedig az elsõ koordináta dönt).
  • (R, <)×_~({0,1}, <) (két pár rendezését az elsõ koordinátájuk dönti el, egyenlõség esetén pedig a második koordináta dönt).

Feladat: Legyen (A, <_A) és (B, <_B) két rendezett halmaz véges halmazokon. Igazoljuk, hogy a két rendezett halmaz akkor és csak akkor hasonló, ha |A|=|B|.

Feladat: Legyen (A, <) egy rendezett halmaz, amelyre A megszámlálhatóan végtelen. Igazoljuk, hogy van olyan részhalmaza a racionális számok halmazának, amely a szokásos rendezéssel hasonló (A, <)-val.

Feladat:

• Legyen (A, <) egy rendezett halmaz, amelyre A megszámlálhatóan végtelen. Igazoljuk, hogy van olyan részhalmaza A-nak, amely az A-ból örökölt rendezéssel hasonló vagy a pozitív egész számok rendezett halmazával (a szokásos rendezéssel) vagy a negatív egész számok rendezett halmazával (a szokásos rendezéssel).
• Vegyük a természetes számok halmazát a szokásos rendezéssel. Igazoljuk, hogy az alaphalmaz bármely végtelen részhalmzát vesszük az öröklött (természetes) rendezéssel, akkor hasonló rendezett halmazt kapunk.
• Igazoljuk a fenti állítást a negatív egészek halmazára is.

Feladat: Legyen A egy olyan részhalmaza a valós számoknak, hogy minden nem üres részének van minimális eleme. Igazoljuk, hogy A megszámlálható.

Feladat: Legyen A egy megszámlálhatóan végtelen halmaz.

• Hány rendezés adható meg A-n?
• Hány különbözõ típusú rendezés adható meg?

Feladat: Legyen (A, <) egy megszámlálhatóan végtelen rendezés. Tegyük fel, hogy ez a rendezés rendelkezik a következõ tulajdonságokkal:

• sûrû, azaz minden a < b elemre van alkalmas k elem, amelyre a < k < b,
• nincs legkisebb eleme, azaz minden a elemre van alkalmas m elem, amelyre m < a,
• nincs legnagyobb eleme, azaz minden a elemre van alkalmas M elem, amelyre a < M.