Countable sets

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?

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,

Cheers,
JB

Euclid

What about 1/2 - pi? 1/3 - pi? 6/5 - pi?

daveb

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

matt grime

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.

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

NateTG

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]

symplectic_manifold

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!

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.

symplectic_manifold

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!

Nimz

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,

symplectic_manifold

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

NateTG

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]

CrankFan

http://www.math.uchicago.edu/~mileti.../settheory.pdf