## Set Theory [basic concepts]

Notes provided by forum experts as FAQ and reference material. This is not a wiki, but rather a small repository for material relevant to common discussions.  ### Set Theory [basic concepts]

PART ONE
========

The set of natural numbers N = { 1, 2, 3, ... }

The set of integers Z = { .., -2, -1, 0, 1, 2, ... }

The set of rational numbers Q = { a/b : where a,b belongs to Z }

A~B if and only if there is a one-to-one correspondence between the elements of A and the elements of B.

A set S is said to be infinitely countable if there is a one-to-one correspondence between that set and the set N. That is, S~N.

The set of integers Z is countable is a corollary.

The set of rational numbers is infinitely countable is a Theorem.
Giacomo    ### Part Two
======

The number of real numbers between 0 and 1 is not infinitely countable is a Theorem.
----------------------------------------------------------------------------------------------------------

Proof :
--------

(1) Assume that the real numbers between 0 and 1 is infinitely countable so that there is a mapping between these numbers and N.

(2) Then there should be a complete list. All real numbers would have to be included in this mapping.

(3) But it is possible to construct a number that is not one the list.

(4) All numbers in this list are of the form. 0.xxxxxxxxx....

(5) Let x_1 = the first number in the list and x_(1,1) = the first digit of the first number in the list so that 0 =< x_(1,1) =< 9.

(6) Let n_1 = any other digit. For example, if x_(1,1) = 9 then we could have n_1 = 8.

(7) We can see that all numbers that we create from n will not equal x1

(8) Let x_(2,2) = the second digit of the second number on the list.

(9) We can now set n_2 = any other digit so that n is now distinct from x_1 and x_2.

(10) We can continue doing this for as long as i and in each case n is different from all the real numbers that came up to i.

(11) In this way, it is possible to set n = a real number which is not on the list.

(12) But this is impossible since we assumed that there was a complete mapping.

Therefore, we have a contradiction and we reject our assumption at step #1.

Q.E.D.

Corollary : The set of real numbers is uncountable
-------------------------------------------------------------

Proof :
---------

This follows directly from the theorem above since (0,1) is a subset of all real numbers so that if (0,1) is uncountable,

it follows that the R, the superset of (0,1) is also uncountable.

Q.E.D.
Giacomo    ### Part Three
========

Lemma : Criteria for a Countable Set
----------------------------------------------

A set C is countable if and only if there exists an ordering O such that for any element c of C, there exists a whole number i such that O(i) = c.

Proof:
-------

(1) Assume that an ordering exists as described in the hypothesis.

(2) Clearly, then, there is a mapping between the whole numbers and the elements of the set C and by the definition, the set C is countable.

(3) Assume that no ordering exists.

(4) Assume further that a set C is countable.

(5) But if a set C is countable, then there exists a mapping between the whole numbers and the set C.

(6) But this is impossible since we assumed in step #3 that no such ordering exists.

(7) Therefore we have a contradiction and we reject our assumption in step #4.

Q.E.D.

Let's compare the set of integers Z to the set of real numbers R.

Lemma #2: The set of integers Z is countable

(1) We can define an ordering O such that:

1: 0
2: 1
3: -1
4: 2
5: -2
...

(2) Then, for any integer x, we can define the following function:

if x > 0, then i = 2*x
if x < 1, then i = 2*x+1

(3) This then gives us:

Then x = O(i)

(4) So, using Lemma 1 above we can conclude that the integers are countable.

Q.E.D.
Giacomo    ### Part Four
=======

Lemma 4: The ordering of (0,1) using decimals does not prove that (0,1) is countable.
----------------------------------------------------------------------------------------------------------

We can order them, but this does not prove that they are countable.

1) Let us define the following ordering

0.1
...
0.9
0.01
0.02
...
0.09
0.11
...
0.19
0.21
...
0.001
...

So for example:

O(1) = 0.1
O(9) = 0.9

etc.

(2) It is clear that for all i, O(i) is a terminating decimal

(3) This means that for nonterminating decimals such as 1/3 or for irrational numbers such (pi - 1),
there is no i such that O(i) = 1/3 or O(i) = (pi - 1).

(4) Since not all reals in (0,1) have an i associated with them, using Lemma 1 above, this shows that O(i) is not a one-to-one correspondence between the reals in (0,1) and the whole numbers.

Q.E.D.

Take the real numbers in (0,1)

0.1
.....
0.9
0.01
.....
0.09
0.11
.....
0.19
....
0.91
.....
0.99
0.001
.....
0.009
0.010
.....

be called A.

It is clear that every element of A is a terminating decimal (no matter how far you go you will never get anything but a terminating decimal).

Not every real number is a terminating decimal. Therefore A is not the set of all real numbers.

It is true that A is countable, but since A is not the set of all real numbers it does not follow that the real numbers are countable.

Note: It is fairly easy to show that the set of all terminating decimals is countable. From time to time, someone notes this and declares that the reals are countable. Well, if someone says, "I have a proof that the reals are countable" you can say "you forgot about infinite decimals" without even looking at the proof. You will almost always be right. Note further that Cantor's argument deals with infinite decimals.
Giacomo    ### Here's a feature of Set Theory that confuses many students:

Many students feel that there are combinations that are not sets :

A counting argument shows there are collections of integers that are not sets. If a set is implied by the ZFC axioms, a finite chaine of inference forces that set to exist. Such a chain can be encoded as a finite sequence of numbers, and there are countably many such sequences. Therefore the number of sets implied by our axioms is countable. However, there are uncountably many collections of integers. Most of these are never described mathematically, i.e. never gathered together into sets.

Yes, all ordinals are sets, and there are uncountably many ordinals.  