Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Countable sets

  1. Mar 26, 2006 #1
    Hi people, I need some help with these questions please:

    1.Is the set of all x in the real numbers such that (x+pi) is
    rational, countable?

    I don't think this is countable, isn't the only possible value for x = -pi, all other irrationals will not make x+pi rational i thought?

    2.Is the set of all x in the real numbers, such that for all k, (x+the square root of k) is not a natural number, countable?

    Again I don't think this is countable because if the square root of k is irrational, like it is for k=2, then you can add infinitely many values of x to root k for which the sum of x and root k is not natural.

    Lastly, is every infinite subset of the power set of the naturals uncountable?
    I don't think so because P(N), the power set of N, has cardinality 2^(aleph nought) and is countable, hence it's subsets will be countable.

    Could anyone offer some advice,

  2. jcsd
  3. Mar 26, 2006 #2
    What about 1/2 - pi? 1/3 - pi? 6/5 - pi?
  4. Mar 26, 2006 #3
    Countability of infinite sets is possible. The natural numbers are infinte and are certainly countable. However, 2^N is not countable
  5. Mar 27, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    think again. and are you asserting that finite sets are not countable? It is a matter of convention but one to get straight at the start.

    why are you adding 'x' to the square root of 'k'? reread the question.

    that is false, P(N) is uncountable, and is I'd wager the only set you've been shown is uncountable.

    you need to reread your notes and questions far more carefully.
  6. Mar 29, 2006 #5
    The empty set is finite, so it must be countable!
    But which bijective mapping do we actually have here??
    Does it depend on whether we take 0 as a natural number or not?
    I've never thought of it before...
    Last edited: Mar 29, 2006
  7. Mar 29, 2006 #6


    User Avatar
    Science Advisor
    Homework Helper

    Well, for any set [itex]X[/itex], the empty map is an injection of [itex]\emptyset[/itex] into that set, so [itex]|\emptyset |\leq |X|[/itex]
  8. Mar 29, 2006 #7
    Hm, why injection?? You meant bijection, didn't you? You need it to show "not larger", so we biject a set X onto a subset Z of Y to show that cardX<=cardY (since cardX=cardZ)
    Nevertheless I think I got it. I forgot about the empty map.
    So we can map the empty set onto a subset of any set X using the empty map. Thus we get the inequality.
    Although we don't need the inequality, do we? We simply biject the empty set onto the set of natural numbers by the empty map. It does the whole job, doesn't it?! Hence, countability!
    Last edited: Mar 29, 2006
  9. Mar 29, 2006 #8
    You seem to be confused. There is no bijection from the empty set to any set that isn't the empty set, including the natural numbers.
  10. Mar 30, 2006 #9
    So is the empty map useless, obscure?
    But how can we speak about cardinality and countability then??
    OK, Guys I seem to need more info on this matter. Give me some links or references, please! :rolleyes:
  11. Mar 30, 2006 #10
    A bijection between two sets implies they have exactly the same cardinality. The empty set has cardinality zero, while any non-empty set has positive cardinality. That doesn't make the empty set or the empty map useless, obscure, etc. For some references, check out these wiki sites:

    - edit -
    Last edited: Mar 30, 2006
  12. Mar 30, 2006 #11
    OK, NateTG thought in terms of an injection into a set, while I thought about a bijection onto a subset of a given set.

    So the empty map is always an injection, right.

    Nimz, if I'm not mistaken from the quotation follows that the strict inequality in NateTG's post is justified too!

    What about a map from the empty set that goes to the empty set. Is it defined?

    And how is countability of the empty set explained in the end...by "every finite set is countable"?
    Last edited: Mar 30, 2006
  13. Mar 30, 2006 #12


    User Avatar
    Science Advisor
    Homework Helper

    In the context of my previous post, [itex]X[/itex] is an arbitrary set. Since [itex]X = \emptyset[/tex] is a possibility, the inequality cannot be strict.

    Yes. The only possible function from the empty set to any other set is the empty function, and in the usual formalism, it's defined.

    (A brief digression.)
    Formally a function [itex]F:A \rightarrow B[/itex] is a set of ordered pairs [itex]F=\{(a,b)\}[/itex] where [itex]a \in A[/itex] and [itex]b \in B[/itex] and [itex]\forall a \in A[/itex] there is exactly one [itex]b \in B[/itex] such that [itex](a,b) \in F[/itex].

    If [itex]A = \emptyset[/itex] then the only possible function is [itex]F=\emptyset[/itex].

    Here's a proof that the cardinality of any finite set is less than or equal to the cardinality of the natural numbers:
    Proof by induction on the cardinality of the finite set:
    Case 0:
    The cardinality of the finite set is [itex]0[/itex].
    The finite set is [itex]\emptyset[/itex] and the emtpy function is suffficient.

    Case N:
    The cardinality of the finite set is [itex]|N| > 0[/itex].
    Clearly there is some element [itex]x \in N[/itex]. Since [itex]N[/itex] is finite we have [itex]|N|-1 = |N - \{x\}|[/itex].
    By the inductive hypothesis we know that there is some injective function [itex]F_{N - \{x\}}:(N-\{x\}) \rightarrow \mathbb{N}[/itex], so we can construct
    [tex]F_N:N \rightarrow \mathbb{N}[/tex]
    as follows:
    [tex]F_N(n)=\left \begin{array}{cc}1&\mbox{ if }$n=x$\\F_{N - \{x\}}(n)+1&\mbox{otherwise}\end{array}\right[/tex]
    Last edited: Mar 30, 2006
  14. Mar 30, 2006 #13
    http://www.math.uchicago.edu/~mileti/teaching/math278/settheory.pdf [Broken]
    Last edited by a moderator: May 2, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook