0
$\begingroup$

My book - Discrete Mathematics and its Applications

This is my book's definition on if an infinite set is countable enter image description here

And the example it gave enter image description here

The "infinite set is countable if and only if it is possible to list the elements of the set in a sequence" makes sense to me. That is say even integers is countable because you can start listing them out -2, 4, -2, -4, and so on....

What I'am struggling is how showing a one to one correspondence between this set(even) integers and the set of positive integers goes to show. One to one correspondence as in a function that maps the set of positive integers to to perhaps countable set(even integers) I don't understand the logic behind this at all. Can anyone clarify this? I feel like this is making it a lot more complicated than it needs to be. If I encountered a problem like show that the set R is not accountable, I would show that you can't count it because the decimal point would just keep going - 0.001, 0.00001. How would this one to one correspondence work in that situation as well?

$\endgroup$
6
  • $\begingroup$ It sounds like (I might be wrong) your confusion is more to do with what an injective function is than anything? $\endgroup$
    – Matthew Cassell
    Commented Jan 18, 2015 at 7:32
  • $\begingroup$ Isn't the injective function just something that maps a value in one domain to another domain(could be the same)? Say f(x) = 4x, maps value in R, x, to value 4x in R as well. $\endgroup$
    – committedandroider
    Commented Jan 18, 2015 at 7:33
  • $\begingroup$ You need to be more specific because, for example, a surjective function also "maps a value in one domain to another domain" but a surjection does not imply an injection. An injective (or one to one) function is a function that maps every element from your set $A$ to its own unique element in a set $B$. $\endgroup$
    – Matthew Cassell
    Commented Jan 18, 2015 at 7:39
  • $\begingroup$ It might be helpful to mention which book is "your book". $\endgroup$
    – user642796
    Commented Jan 18, 2015 at 7:40
  • $\begingroup$ Sorry I forgot to add that to the question $\endgroup$
    – committedandroider
    Commented Jan 18, 2015 at 7:45

1 Answer 1

Reset to default
1
$\begingroup$

Saying you can informally "list" a set isn't rigorous. This is given as an intuitive explanation only. This is made rigorous by saying $S$ is countably infinite if and only if there exists a bijective map

$$f:\mathbb{N}\to S.$$

From here you're free to call $f(1)$ the first element of the list, $f(2)$, the second, and so on. So by presenting such a function, you're giving a list

$$f(1), f(2), f(3),...$$

$\mathbb{N}$ is a natural choice as the domain, but it can be replaced with $\mathbb{Z}$ or any other countable set without affecting the true meaning.

$\endgroup$
6
  • $\begingroup$ Oh just like counting right? Say for positive even integers, i can count 2, 4, 6, 8. And that would be the function f(c) where a count number(positive) is mapped to the actual positive even integer. So 2 would be 1st positive integer, 4 my 2nd positive integer, and so on. Is that right? $\endgroup$
    – committedandroider
    Commented Jan 18, 2015 at 7:48
  • $\begingroup$ Yes, and to prove it rigorously, you attempt to come up with a function which lists things as you think of the list. In this case $f(n)=2n$ would work to show the positive even integers are countable. You need to show it is bijective to finish it (which is easy). $\endgroup$
    – David P
    Commented Jan 18, 2015 at 7:50
  • $\begingroup$ And bijective is onto and one to one from what i remember? $\endgroup$
    – committedandroider
    Commented Jan 18, 2015 at 7:53
  • $\begingroup$ Yes, it's the same as a one-to-one correspondence $\endgroup$
    – David P
    Commented Jan 18, 2015 at 7:53
  • $\begingroup$ David, can you take a look at my question on how to write a simple function to map a positive integer to a member of a Cartesian product set? $\endgroup$
    – committedandroider
    Commented Jan 18, 2015 at 7:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .