Hi all, i am confused with the concept of finiteness... I hope you can shed some light by correcting these 4 sentences...

uncountably infinite is NOT finite

uncountably infinite is NOT countable

countably infinite is NOT finite

countably infinite is countable

any explanations would also be helpful! I'm taking the test in 13 hours!

Thanks...

## what is a finite set?

Let me share with you my notes on cardinality. For GRE Mathematics, there are four levels of cardinality, each having more elements than the one before it.

LEVEL 0: FINITE SET: Any set whose number of elements is finite. Example: Set of all primes > 100 and < 200.

LEVEL 1: COUNTABLE/COUNTABLY INFINITE/DENUMERABLE SET: Any set whose cardinality OR number of elements is equal to the set of natural numbers. Examples:

- the set of natural numbers N, the set of integers Z, the set of rationals Q.

- any finite cartesian product of the above.

- the algebraic numbers (solutions of equations with integer coefficients)

- computable numbers and computable sets.

- finite subsets of integers.

- polynomials with integer coefficients.

Sometimes the term countable includes finite and countably infinite sets too, but as a convention it is used for countably infinite sets.

- LEVEL 2: UNCOUNTABLE SETS: Any set with cardinality = R, the set of real numbers.

Examples:

- the transcendental numbers

- irrational numbers, complex numbers, Euclidean Space R^n

- power set of N

- set of sequences of integers (all functions from N -> Z).

- set of sequences of reals (all functions from N -> R)

- finite subsets of real numbers

- polynomials with real coefficients.

- (I CALL THIS LEVEL THREE UNCOUNTABLE): These sets have cardinality greater than that of uncountable sets.

EXAMPLES:

- The power set of R

- Set of all functions from R -> R

- The power set of all functions from the set of natural numbers to itself

- The set of all real valued of n variables to R.

I took the examples from wikipedia. Note that I myself am not clear regarding some of the examples.

Finally regarding your question:

uncountably infinite is NOT finite : CORRECT

uncountably infinite is NOT countable : CORRECT

countably infinite is NOT finite : CORRECT

countably infinite is countable : DEPENDS HOW YOU DEFINE COUNTABLE. IF COUNTABLE MEANS CARDINALITY OF N, THEN ITS CORRECT. IF HOWEVER COUNTABLE INCLUDES FINITE SETS THEN IT IS NOT CORRECT.

Now try this question (It appeared in GRE Computer Science GR 0329) Question 70: (It seems ETS is swapping questions b/w GRE CS and GRE MATH)

70. Let N be the set of all natural numbers. Which of the following sets are countable?

I. The set of all functions from N to { 0,1 }

II. The set of all functions from { 0,1 } to N

III. The largest subset of N

(A) None (B) I and II only (C) I and III only (D) II and III only (E) I, II, and III

For the answer check the ETS GRE Website, GR0329 Computer Science Sample Test OR Check

http://www.urch.com/forums/gre-computer ... stion.html

Happy testing!

### Re: what is a finite set?

This is how I would solve question 70 from that CS test:

The set in (I) is uncountable because such maps are in one-to-one correspondence with the power set of N, which has cardinality strictly greater than that of N by a basic set-theoretic result.

The set in (II) is countable since such maps are in one-to-one correspondence with N x N, which is countable by a simple diagonal argument.

The set in (III) is countable since the largest subset of N is N, and this is obviously countable.

The set in (I) is uncountable because such maps are in one-to-one correspondence with the power set of N, which has cardinality strictly greater than that of N by a basic set-theoretic result.

The set in (II) is countable since such maps are in one-to-one correspondence with N x N, which is countable by a simple diagonal argument.

The set in (III) is countable since the largest subset of N is N, and this is obviously countable.