Policzalne i niepoliczalne zestawy

Notatkę dodano: 03.06.2013,
Wyświetleń: 124
Podgląd dokumentu

Countable and uncountable sets. There is a one-to- one correspondence between sets N (all natural numbers) and N 2 (even natural numbers). The correspondence has the form f ( n ) = 2 n . There is a one-to-one correspondence between sets N and N odd (odd natural numbers). The correspondence has the form f ( n ) = 2 n + 1 . There is a one-to-one correspondence between sets N = { 0 , 1 , 2 , ... } and Z = { ..., − 1 , 0 , 1 , ... } (all integers): 0 ↔ 0 The correspondence 1 ↔ − 1 has the form: 2 ↔ 1 f ( n ) = n 2 for n = 0 , 2 , 4 , ... 3 ↔ − 2 f ( n ) = − n +1 2 for n = 1 , 3 , 5 , ... 4 ↔ 2 There is a one-to-one correspondence between sets N and Q (all rational numbers). One can number elements of Q as follows: Theorem: Sets N , N 2 , N odd , Z , Q are equinumerous (have the same size, the same cardinality.) Theorem: Two intervals ( a, b ) and ( c, d ) (or [ a, b ] and [ c, d ] ) are equinumerous. One can always find a one-to-one linear function of the form f ( x ) = d − c b − a x + cb − ad b − a transforming all points of ( a, b ) into points of ( c, d ) . Theorem: Open interval ( a, b ) is equinumerous with the closed interval [ a, b ] . Let's define in ( a, b ) a sequence a n = a + b − a 2 n . The one-to-one correspondence is given by the formula: f ( a ) = a 1 ; f ( b ) = a 2 ; f ( a n ) = a n +2 ; f ( x ) = x for others x ∈ [ a, b ] ( x 6 = a, b, a n ). Sets Theorem: The open interval ( a, b ) is equinumerous with R (the set of all real numbers). Every open interval ( a, b ) one can transform on the interval ( − _ 2 , _ 2 ) and then, function f ( x ) = tan x (which is one-to-one in ( − _ 2 , _ 2 ) ) transforms the interval ( − _ 2 , _ 2 ) on the ( −∞ , ∞ ) . Theorem: The set R of all real numbers is not equinumerous with the set N of all natural numbers. One cannot number all real numbers. Sets Definition: Any set that has the same size as the set N of all natural numbers is said to be countable infinite . Any set that is either finite or countable infinite is said to be countable or denumerable . The size of denumerable sets is denoted as