Mûveletek rendezett halmazokkal

Definíció: Legyen (S,<) és (S', <') rendezett halmazok.

• [Rendezett halmazok összege] (S,<)+(S',<') az a rendezett halmaz, amely alaphalmaza S U S' és x < y akkor és csak akkor ha (x, y S-beli, továbbá x< y) vagy (x,y S'-beli, továbbá x <' y) vagy ( x S-beli, továbbá y S'-beli)
• [Rendezett halmazok szorzata] (S,<)•(S',<') az a rendezett halmaz, amely alaphalmaza S×S' és (x,y) < (X,Y) akkor és csak akkor ha (y<' Y) vagy (y=Y, továbbá x < X) (elnevez'ese a szorzathalmaz antilexikografikus rendezése)

Feladat: Ellenõrizzük, hogy a fenti definíciók tényleg rendezett halmazokat írnak le.

Feladat: Legyen (S,<) és (T,<) két hasonló rendezett halmaz. Legyen (S',<) és (T',<) két hasonló rendezett halmaz.

• Ekkor (S,<)+(S',<') és (T,<)+(T',<') is hasonló.
• Ekkor (S,<)•(S',<') és (T,<)•(T',<') is hasonló.

Megjegyzés: A fenti feladat állítását úgy is megfogalmazhatjuk, hogy a rendezett halmazokkal definiált mûveletek eredményének típusa csak a kiinduló rendezett halmazok típusától függ. Ennek két fontos következménye is van számunkra:

• Tetszõleges két rendezett halmaz összege;t definiálhatjuk. A probléma persze csak akkor merül fel, ha a két alaphalmaz nem diszjunkt. Ekkor az egyik tagot helyettesíthetjük egy olyan rendezett halmazzal, ami hasonló az eredetivel, de alaphalmaza már diszjunkt az elsõ tag alaphalmazától. Az eredmény függ a reprezentanstól, de az eredmény típusa UGYANAZ lesz.
• A mûveletek igazából típusokon is definiálhatók.

Definíció:

• ω₀ az (N,<) rendezett halmaz típusa.
• λ az (R, <) rendezett halmaz típusa.
• η a (Q, <) rendezett halmaz típusa.
• n az ({1,2,3,...,n},<) rendezett halmaz típusa.

Feladat: Az alábbi feladatokban rendezett halmazok típusai szerepelnek. Melyek egyenlõek, melyek különbözõek? Ha valamelyiket egyszerûbb alakra hozhatjuk, akkor tegyük meg.

• 2•ω₀, ω₀•2,
• 2•λ, λ•2,
• 2•η, η•2,
• ω₀+ω₀, ω₀+1+ω₀,
• λ+λ, λ+1+λ,
• η+ η, η+1+ η,
• ω₀, ω₀•ω₀,
• λ, λ•λ,
• η, η•η.

Feladat: Igaz-e, hogy ha az alábbi rendezési típusokat szorzatként felírjuk, akkor valamelyik tényezõnek a felírt típusnak kell lenni?

• ω₀?
• λ?
• η?

Feladat: A rendezett halmazok összeadása, szorzása kommutatív, asszociatív-e? Ha igen a válasz, igazoljuk. Ha nem a válasz, adjunk ellenpéldát. Mi a helyzet a disztributívitással?

Definíció: Legyen (A, <) egy rendezett halmaz. (A, <^*) az a rendezett halmaz, amelyben a <^* b, akkor és csak akkor, ha a > b. (A rendezett halmazokon értelmezett mûveletet a rendezés megfordításának nevezzük.)

Feladat: Igazoljuk, hogy a megfordított rendezés is rendezés, illetve a megfordított rendezés típusa is csak a kiinduló rendezés típusától függ.

Feladat: Igazoljuk, hogy

• (α+β)^*=α^*+β^*,
• (α•β)^*=α^*•β^*.