## Countable sets

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.

Cheers,
JB

 PhysOrg.com science news on PhysOrg.com >> 'Whodunnit' of Irish potato famine solved>> The mammoth's lament: Study shows how cosmic impact sparked devastating climate change>> Curiosity Mars rover drills second rock target

 Quote by jackbauer 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?
What about 1/2 - pi? 1/3 - pi? 6/5 - pi?

 Countability of infinite sets is possible. The natural numbers are infinte and are certainly countable. However, 2^N is not countable

Recognitions:
Homework Help

## Countable sets

 Quote by jackbauer 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?
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.

 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.
why are you adding 'x' to the square root of 'k'? reread the question.

 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,
that is false, P(N) is uncountable, and is I'd wager the only set you've been shown is uncountable.

 Could anyone offer some advice, Cheers, JB

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

Recognitions:
Homework Help
 Quote by symplectic_manifold 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...
Well, for any set $X$, the empty map is an injection of $\emptyset$ into that set, so $|\emptyset |\leq |X|$

 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!

 Quote by symplectic_manifold 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.
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.

 Quote by CrankFan 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.
So is the empty map useless, obscure?
But how can we speak about cardinality and countability then??

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:
http://en.wikipedia.org/wiki/Cardinality
http://en.wikipedia.org/wiki/Empty_set

- edit -
Notably,
 We say that two sets A and B have the same cardinality if there exists a bijection, i.e. an injective and surjective function, from A to B. [...] We say that a set A has cardinality greater than or equal to the cardinality of B (and B has cardinality less than or equal to the cardinality of A) if there exists an injective function from B into A. We say that A has cardinality strictly greater than the cardinality of B if A has cardinality greater than or equal to the cardinality of B, but A and B do not have the same cardinality, i.e. if there is an injective function from B to A but no bijective function from A to B.

OK, NateTG thought in terms of an injection into a set, while I thought about a bijection onto a subset of a given set.

 There is no bijection from the empty set to any set that isn't the empty set, including the natural numbers.
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"?

Recognitions:
Homework Help
 Quote by symplectic_manifold Nimz, if I'm not mistaken from the quotation follows that the strict inequality in NateTG's post is justified too!
In the context of my previous post, $X$ is an arbitrary set. Since $X = \emptyset[/tex] is a possibility, the inequality cannot be strict.  What about a map from the empty set that goes to the empty set. Is it defined? 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$ is a set of ordered pairs $F=\{(a,b)\}$ where $a \in A$ and $b \in B$ and $\forall a \in A$ there is exactly one $b \in B$ such that $(a,b) \in F$.

If $A = \emptyset$ then the only possible function is $F=\emptyset$.

 And how is countability of the empty set explained in the end...by "every finite set is countable"?
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 $0$.
The finite set is $\emptyset$ and the emtpy function is suffficient.

Case N:
The cardinality of the finite set is $|N| > 0$.
Clearly there is some element $x \in N$. Since $N$ is finite we have $|N|-1 = |N - \{x\}|$.
By the inductive hypothesis we know that there is some injective function $F_{N - \{x\}}:(N-\{x\}) \rightarrow \mathbb{N}$, so we can construct
$$F_N:N \rightarrow \mathbb{N}$$
as follows:
$$F_N(n)=\left \begin{array}{cc}1&\mbox{ if }n=x\\F_{N - \{x\}}(n)+1&\mbox{otherwise}\end{array}\right$$