0
$\begingroup$

Prove that these sets are countable :

A. Set of relations over natural which is composed by exactly one ordered pair.

B. Set of relations over natural composed by finite number of ordered pairs.

thanks.

  • 0
    I assume that the answer should rely on a bijection function from naturals to the sets, but don't know how to express it as answer.2012-05-04

1 Answers 1

2

The set A is essentially the collection of all singletons from the set $\mathbb{N}\times\mathbb{N}$. (Can you see why?) So the question is: can you prove that $\mathbb{N}\times\mathbb{N}$ is countable?

The second set is the collection of all finite subsets of $\mathbb{N}\times\mathbb{N}$. Perhaps you can prove that that the set of all subsets of a given finite size is countable, and then take a union?

  • 0
    @galeck: I would say that *if* you can prove that $\mathbb{N}^k$ is countable for any finite $k$, then you can rely on that fact. If you cannot prove it, then I would be wary of relying on it...2012-05-05