2
$\begingroup$

I'm trying to understand different sizes of infinities and what everything means (trying to piece everything together).

So if we find a bijection between a set $A$ and another set $B$ where $B$ is countable (countably infinite), then that implies $A$ is countable (is that correct).

Moreover, we can find a bijection between any two countable sets (I think this is correct).

If we find a bijection between two finite sets, then the two sets must be of the same cardinality.

A proper subset of a finite set, A has smaller cardinality than the set $A$.

However, every infinite subset of a countable set is countable. For example, $\mathbb{Z} \subset \mathbb{Q}$ and $\mathbb{Q}$ is countable and $\mathbb{Z}$ is countable.

I get confused, however, when dealing with uncountable sets. Is it true that I can find always bijection between uncountable sets? For example, is it always possible to construct a bijection between two uncountable sets. Are there examples of cases where you can construct a bijection between two uncountable sets and cases where you cannot? For example, is there a bijection between $[0,1]$ and $\mathbb{R}$? (Can't think of one).

In general how do I prove a set is uncountable? I know that if it contains a set that is uncountable then it must be uncountable. Also, I have read through some diagonalization arguments although I find them a bit confusing. Is diagonalization the only way to prove uncountability? Or are there any other ways? What are examples of uncountable sets: $\mathbb{R}$, the set of binary sequences (I think, not sure), intervals such $[0,1]$, any other standard ones? (I want to practice proving sets are uncountable, so any suggestions on examples where I can prove a set is uncountable are much appreciated).If we find a bijection, between a set A and an uncountable set (given) does that mean A is uncountable as well?

Also to show two sets that are at most countable (either finite or countable) do not have the same cardinality do I show that it is impossible to construct a bijection between them.

Thanks.

$\endgroup$
2
  • $\begingroup$ If $A$ is a set, the power set $\mathcal P(A)$ is the set of all subsets of $A$. If $A$ is a finite set with $n$ elements, then $\mathcal P(A)$ has $2^n$ elements. Cantor proved that, for any set $A$, there is no bijection between $A$ and $\mathcal P(A)$, in fact, there is no surjection from $\mathcal P(A)$ to $A$, so $\mathcal P(A)$ is "bigger" than $A$. In particular, if $A$ is an uncountable set, then $\mathcal P(A)$ is another uncountable set which cannot be in bijection with $A$. $\endgroup$
    – bof
    Oct 9, 2019 at 21:23
  • 3
    $\begingroup$ Defining an explicit bijection between two sets, such as $[0,1]$ and $\mathbb R$, can be complicated and messy. Fortunately there is a very useful theorem which avoids the need for defining explicit bijections: If there is an injection $f:A\to B$ and there is an injection $g:B\to A$, then there is a bijection from $A$ to $B$. Now, it's quite easy to define injections $f:[0,1]\to\mathbb R$ and $g:\mathbb R\to[0,1]$. Namely $f(x)=x$ and $g(x)=\frac{e^x}{1+e^x}$. $\endgroup$
    – bof
    Oct 9, 2019 at 21:28

5 Answers 5

2
$\begingroup$

Try to construct a bijection from (0,1) to R by shifting/scaling tangent function.

$\endgroup$
9
  • $\begingroup$ I see so it is possible. But is it possible to always find a bijection between uncountable sets? Are there examples where it is impossible to do so? Suppose we know R is uncountable and we find a bijection between R and (0,1) does this imply (0,1) is uncountable. $\endgroup$
    – Boy Wonder
    Oct 9, 2019 at 21:15
  • 1
    $\begingroup$ I am not sure what your definitions are, but I think you got a bit backwards. If you can find a bijection then two sets are said to have the same cardinality. Now, as mentioned by @Bram28 the power set of a set has always bigger cardiniality. So finding an bijection from the real numbers to the powerset of the real numbers will be impossible. $\endgroup$
    – hal4math
    Oct 9, 2019 at 21:25
  • 1
    $\begingroup$ @BoyWonder you are making a common error of thinking that there are only two infinite cardinalities: countably infinite and and uncountable. Countably infinite sets all have the same size as the integers(that’s the definition), but uncountable sets come in many different sizes. The power set of the reals is larger than the reals, and the power set of the power set of the reals is larger still. (Where something is larger means the other has an injection into it, but not the other way around.) $\endgroup$ Oct 9, 2019 at 21:34
  • 1
    $\begingroup$ Yes. Though, something super interesting is going on with the power sets of the natural numbers, countable sets vs. uncountable sets, that is know as the continuity hypothese. It states that between the cardinality of a countable set such as the natural numbers and the set of the power set of the natural number that there is no set with cardinality strictly between these two. That statement is undecidable!! Amazing stuff. $\endgroup$
    – hal4math
    Oct 9, 2019 at 21:39
  • 1
    $\begingroup$ @BoyWonder (The same size means there is an injection both ways, which per bof’s comment is equivalent to there being a bijection.) $\endgroup$ Oct 9, 2019 at 21:40
2
$\begingroup$

Is it true that I can find always bijection between uncountable sets? For example, is it always possible to construct a bijection between two uncountable sets.

No, you can't always find a bijection between two uncountable sets. For example, there is never a bijection between any set and its powerset (and sorry, but the standard proof is diagonalization) so if you have an uncountable set, then its powerset will also be uncountable, but there is no bijection between them.

Of course, sometimes you can find a bijection between two uncountable set: take any uncountable set and itself. And, there is a bijection between $[0,1]$ and $\mathbb{R}$

$\endgroup$
7
  • $\begingroup$ Say I don't know $[0,1]$ is uncountable but I know $\mathbb{R}$ is uncountable. If I am able to construct a bijection between the two, does that prove $[0,1]$ is uncountable? I.e. does constructing a bijection between some arbitrary set $B$ and an uncountable set prove that $B$ is uncountable? $\endgroup$
    – Boy Wonder
    Oct 9, 2019 at 21:25
  • 1
    $\begingroup$ @BoyWonder Yes, it does ... for if B would be countable, then there would be a bijection between B and $\mathbb{N}$, but you can combine that bijection with the bijection between B and that arbitrary set to obtain a bijection between that arbitrary set and $\mathbb{N}$, and so that arbitrary set would be countable as well .. but it isn't. So, B has to be uncountable as well. $\endgroup$
    – Bram28
    Oct 9, 2019 at 21:26
  • $\begingroup$ Again, yes by definition :). Actually, the standard way to proof $\mathbb{R}$ is not countable is by showing $(0,1)$ is no countable by cantors diagonal argument (there are other ways to reach this claim!) and then use the shifted tangent function to have a bijection between $(0,1)$ and the real numbers thus concluding that the reals are also not countable and actually of the same "size" as $(0,1)$ (and so is every other proper integral in the real numbers, by the way). $\endgroup$
    – hal4math
    Oct 9, 2019 at 21:29
  • 1
    $\begingroup$ @BoyWonder You can either proof that there is no bijection between a set and $\mathbb{N}$ (which typically involves diagonalization), or you construct a bijection between the set under consideration and a set already know to be uncountable. Of course, you now know that it is not true that there is always a bijection between any two uncountable sets ... so if you pick the 'wrong' set to try and create a bijection with, your attempt will be doomed to fail. But if you can create a bijection between $B$ and a known uncountable set (such as $\mathbb{R}$, then $B$ will be uncountable as well. $\endgroup$
    – Bram28
    Oct 9, 2019 at 21:34
  • 1
    $\begingroup$ @BoyWonder No, just because two sets are uncountable does not mean they have the same cardinality. $\mathbb{R}$ has a 'smaller' cardinality than $P(\mathbb{R})$. But of course, $(0,1)$ does have the same cardinality as $(1,2)$ as there is an obvious bijection between them. $\endgroup$
    – Bram28
    Oct 9, 2019 at 21:37
1
$\begingroup$

if we find a bijection between $A$ and $B$ where $B$ is countable, that implies $A$ is countable (is that correct?)

Yes.

we can find a bijection between any two countable sets (I think this is correct)

No. For example, some countable sets are countably infinite while others are finite. However, there is a bijection between any two countably infinite sets.

If we find a bijection between two finite sets, then the two sets must be of the same cardinality.

Yes.

A proper subset of a finite set has smaller cardinality.

Yes.

every infinite subset of a countable set is countable.

Yes.

Are there examples of cases where you can construct a bijection between two uncountable sets and cases where you cannot?

Unless you do set theory, the uncountable sets you deal with will be the size of either $\Bbb R$ or its powerset. The set of continuous functions from $\Bbb R$ to $\Bbb R$ is an example of the former; the set of all functions from $\Bbb R$ to $\Bbb R$ is an example of the latter.

how do I prove a set is uncountable?

Assume it's countable (i.e. can be injected into $\Bbb N$), then derive a contradiction. Alternatively, prove the set is at least as large as a set already known to be uncountable.

Is diagonalization the only way to prove uncountability?

(This is the part of my answer people might challenge.) You could argue it is in some way or another. For instance, the proof that the powerset of $S$ is larger than $S$, a result called Cantor's theorem, uses a diagonalization argument of sorts. Similarly, "$A$ is uncountable because it's at least as large as $B$, which is uncountable, but then how do I know that?" tends to lead back to such an argument eventually.

What are examples of uncountable sets: $\Bbb R$, the set of binary sequences, intervals such $[0,\,1]$, any other standard ones?

Your examples are correct. Other options include the set of sets of integers, number systems that expand $\Bbb R$ such as $\Bbb C$, a countable set's complement with respect to an uncountable one (e.g. the irrationals are $\Bbb R\setminus\Bbb Q$, because $Q$ is countable), a set of functions parameterized by real numbers e.g. the functions $f(x)=kx$ for arbitrary real $k$, or a more inclusive set e.g. the continuous functions from $\Bbb R$ to $\Bbb R$ (or all of them, to be all the more inclusive).

If we find a bijection, between a set $A$ and an uncountable set (given) does that mean $A$ is uncountable as well?

Yes; in fact, they will be equally large uncountable sets.

to show two sets that are at most countable (either finite or countable) do not have the same cardinality do I show that it is impossible to construct a bijection between them.

Firstly, "at most countable" is just "countable", because, again, you seem to use "countable" to mean "countably infinite". Finite sets are countable. Depending on how rigorous you're being, you should be able to "get away with" proving two finite sets are different sizes by just working out what the sizes are. (For example, a set with $17$ elements isn't the same size as one with $29$.) Similarly, no finite set is the same cardinality as any countably infinite one.

$\endgroup$
1
$\begingroup$

Definition: A set $X$ if countable if and only if there exists a bijection $f : \mathbb{N} \rightarrow X$.

Now suppose that there are two sets $X$ and $Y$, both of which are countable. It is a simple exercise to show that there is a bijection between these two sets. You should try to make this argument.

Now suppose that there could be an uncountably infinite subset $Y$ of a countably infinite set $X$. We can think of the elements of $X$ as a sequence $\{ x_n \}$. Since $Y \subset X$, we can list the elements of $Y$ as a subsequence of $\{ x_n\}, $ call it $\{x_{n_k} \}$. But then we could map the natural number $k$ to the $k'th$ element of $\{ x_{n_k} \}$, and so there is a bijection between $\mathbb{N}$ and $Y$, contradicting the hypothesis that $Y$ is uncountable.

On to the next point, no it is not true in general that we can always find a bijection between two uncountable sets. Take for example $\mathbb{R},$ and $\mathcal{P(\mathbb{R})}$, where $\mathcal{P}(\mathbb{R})$ is the power set of $\mathbb{R}.$

Of course it is possible however to find a bijection between two uncountable sets. It is in fact true that $[ 0, 1]$ and $\mathbb{R}$ have the same cardinality. Search it on this site and you will find an answer to this problem.

Finally, in general to show that a set is uncountable you can show that there is a bijection between this set and another uncounable set or to show that it is impossible to show that there is a bijection between this set and the natural numbers.

$\endgroup$
0
$\begingroup$

It is not possible to always define a bijection between two uncountable sets. Let for example A=R and let B=P(A) So B is the set of all subset of A. Since A is uncountable so is B. But one can show that there is never a surjection between a set to its powerset. Hence there is no bijection between A and B.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.