what is a finite set?

Forum for the GRE subject test in mathematics.
aspirant
Posts: 7
Joined: Thu Nov 06, 2008 2:51 am

what is a finite set?

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...

amateur
Posts: 42
Joined: Wed Sep 10, 2008 9:41 am
Hi,

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.

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!

aspirant
Posts: 7
Joined: Thu Nov 06, 2008 2:51 am
amateur, thanks so much for sharing your knowledge on finiteness! It has improved my understanding somewhat although I still cannot attempt the question you posted at the end. With 9 hours to the start of the paper, I can only hope for the best and calm down before I go to bed. Thanks again, really appreciate it!

amateur
Posts: 42
Joined: Wed Sep 10, 2008 9:41 am
It seems you'll be testing at a place where the time is GMT +8:00, likely East Asia. Anyway, Good Luck!

zpconn
Posts: 2
Joined: Wed Dec 02, 2009 5:02 pm

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.