# Homework Help: A, B are countable. P(s), power set, and f: A-> not always countable?

1. Feb 24, 2006

### Tony11235

Suppose A and B are countable. Explain why P(s), power set, and f: A ->B are not necessarily countable.

P(s) is only countable if A and B are finite, am I am correct? Otherwise, the power set of an infinite set is not countable. As for f: A -> B, doesn't f have to be a bijection?

2. Feb 24, 2006

### AKG

I assume you're regarding the function f as a set of ordered pairs. I would think that |f| = |A|, so if A is countable then so is f. I don't know what s is, but I believe that if s is finite, then P(s) is finite, and if s is infinite, then P(s) is uncountable.

3. Feb 24, 2006

### 0rthodontist

He may have meant the set of all functions f:A-->B is not necessarily countable. In that case it is true because, for example, you can represent each function from the positive integers to the positive integers as an infinite sequence of integers, and you can use a diagonal argument to say that the set of all sequences of integers is not countable. For the power set of A the integers, you can represent each subset as a bit string.

4. Feb 24, 2006

### Tony11235

There were initially two quetions but one of them is sort of obvious, but the question is, assumming that A and B are countable sets, under what conditions would f:A->B NOT be countable ?

Last edited: Feb 24, 2006
5. Feb 24, 2006

### 0rthodontist

Do you really mean the function f:A-->B and not the set of all functions f:A-->B? As AKG said if you are only talking about the function, then it is always countable.

6. Feb 24, 2006

### Tony11235

I was talking about the function from sets A to B. I would think that as long as A and B are countable sets, that f:A-->B would always be countable. So why would my professor ask the question, on a homework, "Suppose sets A and B are countable. Explain why P(s) and f:A-->B are not necessarily countable". Any idea?

7. Feb 24, 2006

### 0rthodontist

My only guess is that he was talking about the set of all functions f:A-->B. You should ask him.

8. Feb 25, 2006

### topsquark

BTW The set of integers is countable, but not finite. I think that's what's going on here...

-Dan

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook