Wst

,

ep do Teorii Mnogości i Logiki

Lista 4

Zadanie 4.1 (a) Wypisać wszystkie możliwe relacje R ⊆ {1, 2, 3} × {1, 2, 3}, które są (równocześnie) zwrotne i syme-
tryczne.
(b) Policzyć, ile jest wszystkich relacji zwrotnych na zbiorze 10-elementowym.
(c) Załóżmy, że relacje R

1

, R

2

są symetryczne. Czy własność tę mają również relacje:

R

1

∩R

2

, R

1

∪R

2

, R

1

\R

2

, R

1

÷R

2

?

(d) Zakładamy, że R ⊆ R

2

. Jak ułożony jest w stosunku do osi zbiór {(x, y) : xRy}, jeżeli R jest: symetryczna? antysy-

metryczna? zwrotna?

Zadanie 4.2 Sprawdzić, czy poniższe relacje f ⊆ X × X są funkcjami:

(a)

X = R, xf y ↔ (y = x

2

∧ x ­ 1) ∨ (y = 2 ∧ x ¬ 1).

(b)

X = R, xf y ↔ ((x jest niewymierna ) ∧ y = 1) ∨ ((x jest wymierna ) ∧ y = 0)

(c)

X = N, xf y ↔ (∃n ∈ N ) (∃k ∈ N ( ( y = n + k ∧ x = n · k) .

(d)

X = R, xf y ↔ x = y

2

.

(e)

X = R, xf y ↔ (y ∈ Z ∧ y ¬ x < y + 1.)

Zadanie 4.3 Zakładamy, że f : X → Y jest funkcją, A

t

⊆ X, B

t

⊆ Y. Udowodnić prawdziwość następujących równości i

inkluzji:

(a)

f (A

1

∩ A

2

) ⊆ f (A

1

) ∩ f (A

2

) i ogólniej f (

T

t∈T

A

t

) ⊆

T

t∈T

f (A

t

).

(b)

f (A

1

) \ f (A

2

) ⊆ f (A

1

\ A

2

).

(c)

f

−1

(B

1

∪ B

2

) = f

−1

(B

1

) ∪ f

−1

(B

2

) i ogólniej f

−1

(

S

t∈T

B

t

) =

S

t∈T

f

−1

(B

t

).

(d)

Jeżeli B ⊆ f (X) to f (f

−1

(B)) = B.

(e)

f (A

1

∪ A

2

) = f (A

1

) ∪ f (A

2

) i ogólniej f (

S

t∈T

A

t

) =

S

t∈T

f (A

t

).

(f)

f

−1

(B

1

∩ B

2

) = f

−1

(B

1

) ∩ f

−1

(B

2

) i ogólniej f

−1

(

T

t∈T

B

t

) =

T

t∈T

f

−1

(B

t

).

(g)

f

−1

(B

1

\ B

2

) = f

−1

(B

1

) \ f

−1

(B

2

).

(h)

Jeżeli A ⊆ X to A ⊆ f

−1

(f (A)).

Sprawdzić, dla jakich funkcji można zastąpić w powyższych wzorach inkluzję równością.

Zadanie 4.4 Załóżmy, że funkcja f : X → X spełnia równanie f ◦ f = id

X

. Wykazać, że f jest injekcją.

Zadanie 4.5 Zakładamy, że f : X → Y, g : Y → X. Pokazać, że:

(a)

Jeżeli g ◦ f = id

X

, to f jest różnowartościowa a g jest surjekcją.

(b)

Jeżeli g ◦ f jest różnowartościowa a f jest surjekcją, to g jest różnowartościowa.

(c)

Jeżeli g ◦ f jest suriekcją a g jest różnowartościowa, to f jest surjekcją.

Zadanie 4.6 Zbadać, czy zdefiniowane niżej funkcje f

1

, f

2

, f

3

, f

4

są różnowartościowe i czy są surjekcjami na podane

przeciwdziedziny.

(a)

f

1

: N → N, f

1

(n) = n

2

.

(b)

f

2

: N × N → N, f

2

(k, l) = najmniejsza wspólna wielokrotność liczb k, l.

(c)

Niech P oznacza zbiór (dodatnich) liczb pierwszych. Rozważyć restrykcję f

3

= f

2

|

P×P

.

(d)

Zakładamy, że X 6= Ø. Dla każdego A ∈ P (X) definiujemy jego funkcję charakterystyczną χ

A

:

χ

A

: X → {0, 1} , (χ

A

(x) = 0 ↔ x /

∈ A).

Funkcję f

4

określamy wzorem f

4

: P (X) 3 A → χ

A

∈ {0, 1}

X

.

Zadanie 4.7 Wyznaczyć funkcje odwrotne do f

1

i f

2

, gdzie:

f

1

: R

2

3 (x, y) → (2x + 3y, −x + 3y) ∈ R

2

,

f

2

: C 3 a + bi → (a + 1, −b) ∈ R

2

. Zadanie 4.8 Wykazać, że dla

dowolnych (niepustych) zbiorów X, Y istnienie injekcji f : X → Y jest równoważne istnieniu surjekcji g : Y → X.

Zadanie 4.9 Sprawdzić, czy dla funkcji f

1

i f

2

istnieją funkcje odwrotne. Jeżeli tak, wyznaczyć je.

f

1

: C

2

3 (x

1

+ y

1

i, x

2

+ y

2

i) → (x

1

, x

1

+ x

2

, y

1

, y

1

+ y

2

) ∈ R

4

,

f

2

: N \ {0, 1} 3 k →



2

k

jeżeli (∃ l ∈ N) (k = 2

l

);

k

w przeciwnym przypadku.