Bijection between products of countable sets

In summary, the conversation discusses how to prove the bijectivity of S1 × Z and S2 × Z, given that S1 = {a} and S2 = {b, c}. It is mentioned that this is more difficult due to S1 and S2 not being equinumerous, but it is possible due to the infinite nature of Z. An example of a bijection between S1 × Z and S2 × Z is given and discussed.
  • #1
The1TL
26
0

Homework Statement


Let S1 = {a} be a set consisting of just one element and let
S2 = {b, c} be a set consisting of two elements.

Show that S1 × Z is bijective to S2 × Z.

Homework Equations





The Attempt at a Solution



So I usually prove bijectivity by showing that two sets are equinumerous, But in this case S1 and S2 are not so that makes it more difficult.
 
Physics news on Phys.org
  • #2
You're right, this problem demonstrates how things can become unintuitive when dealing with infinite sets. If A were any nonempty finite set, this claim would be false, since in that case
[tex]
|S_1 \times A| = |S_1||A| = |A|
[/tex]
[tex]
|S_2 \times A| = |S_2||A| = 2|A| \; .
[/tex]

However, since [itex]\mathbb{Z}[/itex] is infinite, we have more leeway. Can you think of a proper subset of [itex]\mathbb{Z}[/itex] that is equinumerous to [itex] \mathbb{Z}[/itex]?
 
  • #3
here is one idea:

...
...
(a,-3) <--> (c,-2)
(a,-2) <--> (b,-1)
(a,-1) <--> (c,-1)
(a,0) <--> (b,0)
(a,1) <--> (c,0)
(a,2) <--> (b,1)
(a,3) <--> (c,1)
(a,4) <--> (b,2)
...
...

can you prove this is, in fact, a bijection?
 

1. What is a bijection between products of countable sets?

A bijection between products of countable sets is a one-to-one correspondence between the elements of two countably infinite sets. This means that each element in one set is paired with exactly one element in the other set, and vice versa.

2. How is a bijection different from other types of functions?

A bijection is a type of function that is both injective (one-to-one) and surjective (onto). This means that each element in the domain is paired with exactly one element in the co-domain, and every element in the co-domain has at least one corresponding element in the domain.

3. What are some examples of bijections between products of countable sets?

One example of a bijection between products of countable sets is the function f: ℕ x ℕ → ℕ, where f(m,n) = (2^m)(3^n). This function maps each pair of natural numbers to a unique natural number, creating a bijection between the product of two countably infinite sets (ℕ x ℕ) and a single countably infinite set (ℕ).

4. How are bijections used in mathematics?

Bijections are commonly used in mathematics to prove that two sets have the same cardinality (size) by showing that there is a one-to-one correspondence between their elements. They are also used in combinatorics to count the number of ways that objects can be arranged or combined.

5. What is the significance of bijections between products of countable sets?

By establishing a bijection between two countably infinite sets, we can show that they have the same cardinality and are therefore "equally infinite". This has important implications in set theory and other areas of mathematics, as it allows us to compare the sizes of different infinite sets.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
509
  • Calculus and Beyond Homework Help
Replies
4
Views
932
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
Back
Top