Egzamin z logiki, II termin, 6 wrze´

snia 2005

0. Rozwa˙zamy algebr

,

e A = hN × N, f i, z jedn

,

a operacj

,

a jednoargumen-

tow

,

a okre´slon

,

a tak:

• f (n, m) = (n, n + m), gdy n jest nieparzyste.

• f (n, m) = (n, m + 1), gdy n jest parzyste, a liczba m nie jest

postaci k · 3

n

+ 3

n

− 1.

• f (n, k · 3

n

+ 3

n

− 1) = (n, k · 3

n

), gdy n jest parzyste.

Kt´

ore z nast

,

epuj

,

acych stwierdze´

n s

,

a prawdziwe i dlaczego?

(a) Algebra A jest izomorficzna z pewn

,

a swoj

,

a podalgebr

,

a w la´sciw

,

a.

(b) Algebra A ma nieprzeliczalnie wiele podalgebr.

(c) Algebra A ma nieprzeliczalnie wiele wzajemnie nieizomorficznych

podalgebr.

(d) Algebra A ma nieprzeliczalnie wiele wzajemnie nieizomorficznych

obraz´

ow homomorficznych.

(e) Algebra A ma nieprzeliczalnie wiele wzajemnie nieizomorficznych

iloraz´

ow.

(f) Ka˙zdy obraz homomorficzny algebry A jest izomorficzny z pewn

,

a

jej podalgebr

,

a.

(g) Ka˙zda podalgebra algebry A jest jej obrazem homomorficznym.

(h) Produkt dowolnych dw´

och podalgebr algebry A jest izomorficzny

z pewn

,

a jej podalgebr

,

a.

(i) Klasa wszystkich iloraz´

ow podalgebr algebry A jest definiowalna

r´

owno´sciowo.

Rozwi

,

azanie

Algebra A sk lada si

,

e z przeliczalnie wielu

”

la´

ncuch´

ow”, ka˙zdy postaci (n, i) →

(n, n + i) → (n, 2n + i) → · · · dla i < n i nieparzystych n, oraz przeliczalnie
wielu

”

p

,

etli” postaci (n, k · 3

n

) → (n, k · 3

n

+ 1) → · · · → (n, k · 3

n

+ 3

n

− 1) →

(n, k ·3

n

) dla parzystych n. Dla ka˙zdego parzystego n jest niesko´

nczenie wiele

p

,

etli rozmiaru 3

n

(w tym p

,

etli jednoelementowych).

(0a) Tak. Wystarczy usun

,

a´

c na przyk lad jedn

,

a p

,

etl

,

e rozmiaru 9 i otrzy-

mamy podelgebr

,

e izomorficzn

,

a z A.

(0b) Tak. Ka˙zda rodzina p

,

etli rozmiaru 9 wyznacza podalgebr

,

e.

(0c) Tak. Dla dowolnego podzbioru M zbioru liczb parzystych mo˙zna wybra´

c

podalgebr

,

e zawieraj

,

ac

,

a po jednej p

,

etli rozmiaru 3

n

, dla n ∈ M i po

dwie p

,

etle dla n 6∈ M .

(0d) Tak. Podalgebra z odpowiedzi (0c) jest obrazem homomorficznym A.

(

”

La´

ncuchy” przekszta lcamy w jak

,

akolwiek p

,

etl

,

e.)

(0e) Tak. Wynika to natychmiast z odpowiedzi

”

tak” na pytanie (0d).

(0f) Nie. Homomorfizm mo˙ze

”

sklei´

c” niesko´

nczony

”

la´

ncuch” do p

,

etli dowol-

nego rozmiaru (niekoniecznie 3

n

).

(0g) Nie. Na przyk lad podalgebra sk ladaj

,

aca si

,

e z jednej p

,

etli rozmiaru 9 nie

jest obrazem algebry A. W algebrze A s

,

a elementy spe lniaj

,

ace warunek

f (a) = a. Je´sli h jest homomorfizmem, to musi by´

c h(a) = f (h(a)),

a takiego elementu nie ma w nietrywialnej p

,

etli.

(0h) Tak. Produkt dw´

och podalgebr jest sum

,

a produkt´

ow sk ladowych (

”

p

,

etli”

i

”

la´

ncuch´

ow”). Produkt dw´

och

”

p

,

etli” rozmiaru 3

n

i 3

m

, gdzie n ≤ m,

sk lada si

,

e z 3

n

egzemplarzy wi

,

ekszej

”

p

,

etli”. Produkt dw´

och

”

la´

ncuch´

ow”

to niesko´

nczona rodzina

”

la´

ncuch´

ow”, a produkt

”

p

,

etli” i

”

la´

ncucha” to

niesko´

nczona rodzina

”

p

,

etli”. Zatem produkt dw´

och podalgebr zawsze

sk lada si

,

e z odpowiednich sk ladowych.

(0i) Nie, bo sk lada si

,

e z algebr przeliczalnych, wi

,

ec nie jest zamkni

,

eta ze

wzgl

,

edu na (dowolne) produkty.

2