Q3) Proving the Cardinality of Infinite Sets: A Rigorous Approach

In summary: R x R and (f(x), f(y)) is in RxR because it is the inverse of f(). But by the Schroeder-Bernstein Theorem, this implies that f is a one-to-one map from RxR to [0,..., 1].
  • #1
kingwinner
1,270
0

Homework Statement


Q1) Assuming that |R|=|[0,1]| is true, how can we rigorously prove that |R2|=|[0,1] x [0,1]|? How to define the bijection? [Q1 is solved, please see Q2]



Q2) Prove that |[0,1] x [0,1]| ≤ |[0,1]|
Proof: Represent points in [0,1] x [0,1] as infinite decimals
x=0.a1a2a3...
y=0.b1b2b3...
Define f(x,y)=0.a1b1a2b2a3b3...
To avoid ambiguity, for any number that has two decimal representations, choose the one with a string of 9's.
f: [0,1] x [0,1] -> [0,1] is one-to-one, but not onto.
This one-to-one map proves that |[0,1] x [0,1]| ≤ |[0,1]|.

Now how can we formally prove that f is a one-to-one map (i.e. f(m)=f(n) => m=n)? All textbooks are avoiding this step, they just say it's obviously one-to-one, but this is exactly where I'm having trouble. How to prove formally?

Homework Equations



The Attempt at a Solution


As shown above.

Thanks a million! :)
 
Last edited:
Physics news on Phys.org
  • #2
Q1 is solved, but I'm still having trouble with Q2.

Can someone help me with Q2, please? It is an example I found on the internet, but I don't understand why the function f is one-to-one. How can we formally PROVE that f is a one-to-one map?

Any help is appreciated!
 
  • #3
There is really nothing to it...you just have to say: suppose [tex]f(a,b)=f(c,d).[/tex] Then:

[tex]0.a_1b_1a_2b_2...=0.c_1d_1c_2d_2...[/tex], so:

[tex]a_i=c_i[/tex] and [tex]b_i=d_i[/tex] for all [tex]i[/tex],

ie: [tex]a=c[/tex] and [tex]b=d[/tex], so [tex](a,b)=(c,d).[/tex]
 
  • #4
mrbohn1 said:
There is really nothing to it...you just have to say: suppose [tex]f(a,b)=f(c,d).[/tex] Then:

[tex]0.a_1b_1a_2b_2...=0.c_1d_1c_2d_2...[/tex], so:

[tex]a_i=c_i[/tex] and [tex]b_i=d_i[/tex] for all [tex]i[/tex],

ie: [tex]a=c[/tex] and [tex]b=d[/tex], so [tex](a,b)=(c,d).[/tex]

We can say [tex]a_i=c_i[/tex] and [tex]b_i=d_i[/tex] for all [tex]i[/tex] only because we have removed all ambiguities, so the decimal expansion of each number is unique, right??

Also, why is f NOT onto??

Thanks!
 
  • #5
kingwinner said:
Also, why is f NOT onto??
Why do you think it's not? It is! Hence it is a bijection, which means [itex]|[0,1]^2|=|[0,1]|[/itex].

The proof is trivial: let [itex]z\in [0,1][/itex], [itex]z=0,z_1z_2z_3z_4z_5...[/itex].
Take [itex]x,y\in[0,1][/itex] with [itex]x=0.z_1z_3z_5...[/itex] and [itex]y=0.z_2z_4z_6...[/itex]. Then obviously [itex]f(x,y)=z[/itex].
 
  • #6
jbunniii said:
It seems to me to make more sense to construct a surjective (onto) map in the other direction, say [itex]g : [0,1] \rightarrow [0,1] \times [0,1][/itex]. If you can find such a map, then it's immediate that [itex]|[0,1]| \geq |[0,1]\times[0,1]|[/itex].
To create such a map, just do the opposite of what your [itex]f[/itex] function does.
First, this is exactly the same since f is bijective, hence you would just be computing the inverse which contributes nothing. Second, |A|<=|B| means by definition that there exists an injection A->B, not that there exists a surjection B->A. These are only equivalent if we invoke the axiom of choice. So it does not make more sense to construct a surjective map in the other direction.

\\edit: it seems jbunniii deleted his reply.
 
  • #7
Landau said:
\\edit: it seems jbunniii deleted his reply.

Yeah, I realized pretty quickly that it didn't make any sense, but not quickly enough!
 
  • #8
I apologize ;)
 
  • #9
Hi,

But now I seriously think that f is NOT onto.

For example, 0.17070707... is not in the image of f.
It must come from (0.10000..., 0.7777...), but by our definition of f, 0.10000... is always represented as 0.0999..., (we have to remove all the ambiguities, for any number that has two decimal representations, we choose the one with a string of 9's. When we define f, we have to remove the ambiguities, otherwise, f won't be one-to-one, actually I think f wouldn't even be a function.)
So (0.10000..., 0.7777...) is always represented as (0.09999..., 0.7777...). There is no way we can get the element 0.17070707... in the image of f.

Hence, f is definitely NOT onto, am I right?
 
  • #10
It looks to me like you are trying to prove that [tex]|[0,1] \times [0,1]| = |[0,1]|[/tex]. Now, I do not know what facts of life you are allowed to assume here, but it seems like the easiest way to go is to appeal to the Schroeder-Bernstein Theorem. If you are unfamiliar with it, the Schroeder-Bernstein Theorem says, briefly, that if [tex]A[/tex] and [tex]B[/tex] are sets, with both [tex]|A| \leq |B|[/tex] and [tex]|B| \leq |A|[/tex], then [tex]|A| = |B|[/tex]. This is more than a mere triviality, since it means that if we have an injection (one-one map, not necessarily onto, as pointed out above) [tex]A \rightarrow B[/tex] and an injection [tex]B \rightarrow A[/tex], then [tex]A[/tex] and [tex]B[/tex] have the same cardinal number.

In this case, an injection [tex] [0,1] \rightarrow [0,1] \times [0,1][/tex] is easy. An injection [tex] [0,1] \times [0,1] \rightarrow [0,1][/tex] requires a bit more thought, but is readily exhibited, as you have seen.
 
  • #11
If you are given that |R|= |[0,1]|, you already know that there exists a bijection f(x) from R to [0,1]. Then F(x,y)= (f(x), f(y)) is a bijection from RxR to [0, 1]x[0,1].
 
  • #12
Great proof Halls!
 
  • #13
Hi,

For Q2, to prove |[0,1]|=|[0,1]x[0,1]|, I was going to use the Schroeder-Bernstein theorem, too.

But someone said that f(x,y)=0.a1b1a2b2a3b3... is a BIJECTION. If it is a bijection, then we don't need that theorem. Can someone explain why f(x,y)=0.a1b1a2b2a3b3... is onto? I think my post #9 demonstrates that f is NOT onto. Am I missing something??
 
  • #14
No, you're right. f(x,y) is not a bijection. Ignore statements it is and go ahead and prove the result anyway.
 

Related to Q3) Proving the Cardinality of Infinite Sets: A Rigorous Approach

What is the concept of "Cardinality of Infinite Sets"?

The cardinality of infinite sets is a mathematical concept that measures the size or number of elements in a set. It is used to compare the size of different infinite sets and determine if they have the same number of elements or if one set is larger than the other.

How is the cardinality of infinite sets determined?

The cardinality of infinite sets is determined by finding a one-to-one correspondence, or a function that matches each element in one set to a unique element in another set. If such a correspondence exists, then the sets have the same cardinality. If not, then one set has a larger cardinality than the other.

What is the difference between countably infinite and uncountably infinite sets?

A countably infinite set is one in which the elements can be put into a one-to-one correspondence with the positive integers, meaning that the set can be counted. An uncountably infinite set, on the other hand, is one that cannot be counted and has a larger cardinality than the countably infinite sets.

Can the cardinality of infinite sets be compared to the cardinality of finite sets?

No, the concept of cardinality is not applicable to finite sets. Two finite sets can be compared by simply counting their elements, but infinite sets cannot be counted in the same way. The cardinality of infinite sets can only be compared to other infinite sets.

What is the importance of the concept of cardinality in mathematics?

The concept of cardinality is fundamental in mathematics as it allows us to compare the sizes of different sets, including infinite sets. It also provides a way to classify the different types of infinite sets and understand their properties. Cardinality is used in various branches of mathematics, including set theory, analysis, and topology.

Similar threads

  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
13
Views
3K
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
546
Back
Top