Logika i teoria mnogości – Wykład 2

1

Teoria mnogo

ści

Teoria mnogości to dział matematyki zajmujący się badaniem ogólnych

własności zbiorów niezależnie od natury elementów, z których się składają.

Twórcą tej teorii był matematyk niemiecki Georg Cantor (1845 – 1918).

Pojęcia pierwotne tej teorii to zbiór oraz przynależność do zbioru.

Definiujemy następujące podstawowe pojęcia:

•

 - zbiór pusty (nie ma żadnego elementu,

∅

∉

∀

x

x

)

•

Relacja inkluzji (zawierania) -

)

(

B

x

A

x

B

A

∈

⇒

∈

⇔

⊆

•

Równość zbiorów -

)

(

)

(

A

B

B

A

B

x

A

x

x

B

A

⊆

∧

⊆

⇔

∈

⇔

∈

∀

⇔

=

Uwaga: Zbiór pusty jest tylko jeden i jest on podzbiorem dowolnego zbioru.

Działania na zbiorach:

•

Suma -

}

:

{

B

x

A

x

x

B

A

∈

∨

∈

=

∪

;

•

Iloczyn -

}

:

{

B

x

A

x

x

B

A

∈

∧

∈

=

∩

;

•

Różnica -

}

:

{

}

:

{

\

B

x

A

x

B

x

A

x

x

B

A

∉

∈

=

∉

∧

∈

=

;

•

Dopełnienie – oznaczenia A’ = -A = X\A (

)

'

A

x

A

x

∉

⇔

∈

.

Uwaga: Elementy zbiorów mogą też być zbiorami.

Sposoby określania zbiorów

• Wypisanie elementów zbioru, np. {a

1

, a

2

, …,a

n

};

• Określenie zbioru przy pomocy funkcji zdaniowej – gromadzenie

elementów mających wspólną cechę opisaną pewną funkcją zdaniową.

Ogół elementów x, które mają własność W(x) oznaczamy

)}

(

:

{

x

W

x

.

Uwaga: Może się zdarzyć, że opisana w taki sposób klasa obiektów nie

jest zbiorem (przykład – antynomia Russela). Aby uniknąć takiej

sytuacji wybieramy elementy spełniające określoną własność spośród

ustalonego wcześniej zbioru X. Tworzymy nowy zbiór

)}

(

:

{

x

W

X

x

∈

.

• Określenie zbioru jako obraz zbioru wyznaczony przez funkcję -

}

:

)

(

{

)

(

A

a

a

f

x

A

f

∈

=

=

.

Logika i teoria mnogości – Wykład 2

2

W

łasności działań i relacji na zbiorach

Niech X – ustalony zbiór - przestrzeń (tzn. rozważamy tylko elementy i

podzbiory tego zbioru) oraz A, B, C

 X.

• Własności relacji inkluzji

1. A

 A

zwrotność

2. A

 B  B  C  A  C przechodniość

3. A

 B  B  A  A = B

antysymetryczność

• Własności działań

1.

A

B

B

A

A

B

B

A

∩

=

∩

∪

=

∪

przemienność

2.

C

B

A

C

B

A

C

B

A

C

B

A

∩

∩

=

∩

∩

∪

∪

=

∪

∪

)

(

)

(

)

(

)

(

łączność

3.

)

(

)

(

)

(

)

(

)

(

)

(

C

A

B

A

C

B

A

C

A

B

A

C

B

A

∪

∩

∪

=

∩

∪

∩

∪

∩

=

∪

∩

rozdzielność

4.

)

\

(

)

\

(

)

(

\

)

\

(

)

\

(

)

(

\

B

C

A

C

B

A

C

B

C

A

C

B

A

C

∪

=

∩

∩

=

∪

, stąd

'

'

)'

(

'

'

)'

(

B

A

B

A

B

A

B

A

∪

=

∩

∩

=

∪

prawa de Morgana

5.

;

'

,

\

,

,

,

)'

'

(

,

'

,

\

,

,

∅

=

∩

=

∅

∅

=

∅

∩

=

∅

∪

=

=

∪

∅

=

=

∩

=

∪

A

A

A

A

A

A

A

A

A

X

A

A

A

A

A

A

A

A

A

A

6. Monotoniczność sumy i iloczynu:







∩

⊆

∩

∪

⊆

∪

⇒

⊆

∧

⊆

1

1

1

1

1

1

B

A

B

A

B

A

B

A

B

B

A

A

7.

'

'

\

\

A

B

A

C

B

C

B

A

⊆

∧

⊆

⇒

⊆

8.

B

A

A

B

A

∪

⊆

⊆

∩

9. Następujące warunki są równoważne:

∅

=

⇔

=

∩

⇔

=

∪

⇔

⊆

B

A

A

B

A

B

B

A

B

A

\

.

Zbiór pot

ęgowy

Def. 1. Niech A będzie dowolnym zbiorem. Zbiorem potęgowym zbioru A

nazywamy zbiór wszystkich jego podzbiorów. Stosujemy oznaczenia:

}

:

{

:

)

(

2

A

B

B

A

A

⊆

=

℘

=

.

Uwaga: Zawsze

).

(

,

A

A

℘

∈

∅

Fakt.

).

(

)

(

B

A

B

A

℘

⊆

℘

⇒

⊆

Logika i teoria mnogości – Wykład 2

3

Iloczyn kartezja

ński

Def. 2. Parę uporządkowaną elementów a i b oznaczamy <a,b> lub (a,b),

a - pierwsza współrzędna , b - druga współrzędna. Para uporządkowana ma

własność: (a,b) = (c,d)

 a = c  b = d.

Uwaga: Istotne jest rozróżnienie kolejności elementów. Można wprowadzić

inną definicję (Kuratowskiego): (a,b)= {{a},{a,b}}

Podobnie można zdefiniować n-ki uporządkowane (a

1

, a

2

, …,a

n

) jako obiekty

rozróżniające swoje kolejne współrzędne.

Def. 3. Iloczynem kartezjańskim zbiorów A i B (produktem) nazywamy zbiór







∅

=

∨

∅

=

∅

∅

≠

∧

∅

≠

∈

∧

∈

=

×

B

A

gdy

B

A

gdy

B

b

A

a

b

a

B

A

}

:

)

,

{(

Fakt: Jeżeli X i Y są zbiorami skończonymi, X ma m elementów, a Y ma n

elementów, to X

Y jest skończony i ma mn elementów.

Własności produktu

•

X

Y

Y

X

×

≠

×

•

)

(

)

(

Z

Y

X

Z

Y

X

×

×

=

×

×

•

◊

×

◊

×

=

◊

×

),

(

)

(

)

(

Z

X

Y

X

Z

Y

X

- oznacza działanie

∩

∪

,

lub \.

Dzia

łania nieskończone – uogólnione sumy i iloczyny zbiorów

Niech

∅

≠

X

- dowolna przestrzeń,

∅

≠

T

- dowolny zbiór (zbiór indeksów).

Def. 4. Indeksowaną rodziną podzbiorów X nazywamy każdą funkcję

,

:

,

2

:

t

X

A

t

f

T

f

a

→

gdzie

X

A

T

t

t

⊆

∈

,

.

Oznaczenie rodziny indeksowanej:

}

:

{

)

(

:

)

(

}

{

T

t

A

T

f

A

A

t

T

t

t

T

t

t

∈

=

=

=

∈

∈

Def. 5. Uogólnioną sumą rodziny zbiorów

}

:

{

T

t

A

t

∈

nazywamy zbiór:

}

:

{

:

t

T

t

t

A

x

T

t

X

x

A

∈

∈

∃

∈

=

∈

U

.

Uogólnionym iloczynem rodziny zbiorów

}

:

{

T

t

A

t

∈

nazywamy zbiór:

}

:

{

:

t

T

t

t

A

x

T

t

X

x

A

∈

∈

∀

∈

=

∈

I

.

Uwaga:

t

T

t

t

A

x

T

t

A

x

∈

∈

∃

⇔

∈

∈

U

, zaś

t

T

t

t

A

x

T

t

A

x

∈

∈

∀

⇔

∈

∈

I

.

Logika i teoria mnogości – Wykład 2

4

Własności działań nieskończonych

Tw. Jeżeli

T

t

t

T

t

t

B

A

∈

∈

)

(

,

)

(

są indeksowanymi rodzinami podzbiorów zbioru X

i A

 X, to prawdziwe są zależności:

1.

,

)

(

A

A

A

A

T

t

T

t

t

t

⊆

⇒

⊆

∈

∀

∈

U

2.

,

)

(

I

T

t

t

t

A

A

A

A

T

t

∈

⊆

⇒

⊆

∈

∀

3.

,

)

(

U

U

U

T

t

t

T

t

t

T

t

t

t

B

A

B

A

∈

∈

∈

∪

=

∪

4.

I

I

I

T

t

t

T

t

t

T

t

t

t

B

A

B

A

∈

∈

∈

∩

=

∩

)

(

,

5.

,

)

(

|

U

U

T

t

t

T

t

t

A

A

A

A

∈

∈

∩

=

∩

6.

,

)

(

I

I

T

t

t

T

t

t

A

A

A

A

∈

∈

∪

=

∪

7.

I

U

T

t

t

T

t

t

A

A

A

A

∈

∈

=

)

\

(

\

oraz

U

I

T

t

t

T

t

t

A

A

A

A

∈

∈

=

)

\

(

\

,

stąd

I

U

T

t

t

T

t

t

A

A

∈

∈

=

'

'

)

(

oraz

,'

'

)

(

U

I

T

t

t

T

t

t

A

A

∈

∈

=

8.

I

I

U

U

T

t

t

S

t

t

T

t

t

S

t

t

A

A

A

A

T

S

∈

∈

∈

∈

⊇

∧

⊆

⇒

⊆

,

9.

⇒

⊆

∈

∀

t

t

B

A

T

t

I

I

U

U

T

t

t

T

t

t

T

t

t

T

t

t

B

A

B

A

∈

∈

∈

∈

⊆

∧

⊆

.

Pusta rodzina zbiorów gdy T =

,

}

:

{

∅

∈

t

A

t

, wtedy:

∅

=

∅

∈

U

t

t

A

oraz

X

A

t

t

=

∅

∈

I

.

Rodziny podwójnie indeksowane

Jeśli T = I×J, to rodzinę

)

,

(

)

(

j

i

A

T

f

=

oznaczamy A

i,j

.

Możemy zdefiniować działania uogólnione po dwóch indeksach, np.:

Na początku wyznaczamy

}

:

{

:

,

,

j

i

J

j

j

i

i

A

x

J

j

x

A

B

I

i

∈

∈

∀

=

=

∈

∀

∈

I

,

Następnie otrzymujemy zbiór

U

UI

I

i

i

I

i

J

j

j

i

B

A

∈

∈ ∈

=

,

.

Mamy więc

j

i

I

i

J

j

j

i

A

x

J

j

I

i

A

x

,

,

)

(

)

(

∈

∈

∀

∈

∃

⇔

∈

∈ ∈

UI

.

Analogicznie definiujemy inne podwójne działania uogólnione.