1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Feb 24, 2006 #1
    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. jcsd
  3. Feb 24, 2006 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Feb 24, 2006 #3

    0rthodontist

    User Avatar
    Science Advisor

    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.
     
  5. Feb 24, 2006 #4
    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
  6. Feb 24, 2006 #5

    0rthodontist

    User Avatar
    Science Advisor

    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.
     
  7. Feb 24, 2006 #6
    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?
     
  8. Feb 24, 2006 #7

    0rthodontist

    User Avatar
    Science Advisor

    My only guess is that he was talking about the set of all functions f:A-->B. You should ask him.
     
  9. Feb 25, 2006 #8
    BTW The set of integers is countable, but not finite. I think that's what's going on here...

    -Dan
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A, B are countable. P(s), power set, and f: A-> not always countable?
  1. Probability: P(A|B') (Replies: 11)

Loading...