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

[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?

 

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

 

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

 

[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 ?

 

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

 

[Tony11235]

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.

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?

 

[0rthodontist]

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

 

[topsquark]

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?

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

-Dan