Finite and Infinite Sets

Tugas Akhir
Ari Santosa
05305144031
MATEMATIKA NR 05

finite and infinite sets

When we count the element in a set, we say "one,two,there,...", stopping when we have exhausted the set. From a mathematical perspective, whai we are doing is defining a bijective mapping betwen the set and a portion of the set of natural number. if theset is such that the counting does not terminate, such as the set of natural number itself, then we describe the set as being infinite.
The nation of "finite" and "infinite" are extremely primitive, and it is very likely that the reader has never examined these notions very careffuly. in this section we will define thes terms precisely and establish a few basic result and state some other inportant result that seem obviouse but whose proofs are a bit tricky. These proofs can be found in appendix B and can be read later.

Definition

1. The empty set # is said to have 0 elements
2. if n (- N, a set S is said to have n elements if there exists a bijection from the set N:=1,2,...,n) onto S
3. A set S is said to be finite if it is either empty or it has n elements for some n anggota N
4. A set S is said to be infinite if it is not finite

Since the invers of a bijection, it is easy to see that a set S has n elements if and only if there is a bijection from S onto the set {1,2,...,n}. Also since the compossition of two bijections is a bijections, we see that a set S1 has n element if and only if there is a bijection from S1 onto another set S2 that has n elements. Further,a set T1 is finite if and only if there is a bijection from T1 onto another set T2 that is finite.

Theorem
The set N of natural numbers is an infinite set

Theorem

1. If a is a set with m elements and B is a set with n element and if A n B = 0, then A u B has m+n elements
2. if C is an infinite set ann B is a finite set, then C/B is an infinite set.

Suppose that every nonemty subset of a set with k element is finite. Now let S be a set having k + 1 element. if ( k + 1 ) bukan anggita T, we can consider T to be a subset of S1:=S/{f(k+1)}. which has k element by theorem.
On the other hand, if f(k+1) anggota T, then T/{f(k+1) is a subset of S1. since has k elements, the induction hypotesis implis that T1 is a finite set. But this implis that T=T1 u {f(k+1)} is also a finite set

Definition

1. A set S is said to be denumerable if there exists a bijection of N onto S.
2. A set S is said to be countable if it is either finite or denumerable
3. A set S is said to be uncountable if it is not countable

From the properties of bijection, it is clear that S is denumerable if and only if there exists a bijection of S onto N. Also a sey S1 is denumerable if and only if there exist a bijection from S1 onto a set S2 that is denumerable. Further, a set T1 is countable if and only if there exists a bijection from T1 onto T2 that is countable. Finally, an finite countable set is denumerable.

Examples
a. The set E := {2n:n anggota N} of even natural numbers is denumerable, since the mapping f:n->E defined by f(n):=2n for n anggota N, is a bijection of N onto E. similarly, the set o:={2n-1:nanggota N} of add natural numbers is denumerable.

b. The set Z of all integers is denumerable.
To counstruct a bijection of N onto Z, we map 1 onto 0, we map the set of even natural numbers onto the set N of positive integers, and we map the set of odd natural numbers onto the negative integers. This mapping can be displayed by the enumeration:
Z = { 0,1,-1,2,-2,-2,3,-3, ... }

c. Thw union of two disjoin denumerable sets is denumerable. Indeed, if A={a1,a2,a3, ... } and B= {b1,b2,b3, ... }, we can enumerate the elements of A u B as :
a1.b1a2.b2.a3.b3, ...