Discrete Mathematics Infinite Set Cardinality

ChewTobacco·3/25/2015, 11:00:08 AM·1 votes·539 views

I have a Discrete Mathematics Exam TOMORROW!!! What is the process to prove a set is countably infinite? For instance the set of ALL integers not divisible by 3. I know it is countably infinite because it is a subset of the integers but I need to find a one-to-one correspondence. What is a function that maps the positive integers to the set of all integers not divisible by 3?

5 Comments

Ragnar423/25/2015, 1:32:28 PM1 votes

Pro-Tip. ALL subsets are countably infinite. Forget about the subset, and think about how you're counting the subset.

True Story. Even the subset of 0-1 is countably infinite.

This is Calculus 101 man.

AMYS GRAVE3/25/2015, 2:28:46 PM1 votes

a one to one correspondence in your example is

n-n/3(truncated)=I

where n is the element of your set and I is an element of the integers.

one way to see the mapping is to write out the first few elements of both sets and think about the relationship they have.