Is this set countably infinite? If so, how do I exhibit a one to one correspondence between these tw

Jamison Rios 2022-07-01 Answered
Is this set countably infinite? If so, how do I exhibit a one to one correspondence between these two sets?
I am supposed to determine whether or not the set A × Z + where A = { 2 , 3 } is countably infinite. If so, I should exhibit a one to one correspondence between the set of positive integers and the set in question.
Although I'm pretty sure that the set is countably infinite, I am struggling to find a one to one correspondence from the positive integers to the set since it seems to me that there are twice as many elements in the set A × Z + than the set of positive integers since its cardinality is double due to the Cartesian product?
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Charlee Gentry
Answered 2022-07-02 Author has 19 answers
Step 1
The bijection is rather obvious. E.g. for every positive integer n you can define: F ( 2 k 1 ) = ( 2 , k ) when n = 2 k 1 (n is odd)
F ( 2 k ) = ( 3 , k ) when n = 2 k (n is even)
Just prove that F is a bijection (which is quite easy).
This bijection is basically a formal writing of this table:
1 ( 2 , 1 )
2 ( 3 , 1 )
3 ( 2 , 2 )
4 ( 3 , 2 )
5 ( 2 , 3 )
6 ( 3 , 3 )
Step 2
"It seems to me that there are twice as many elements in the set A × Z + than the set of positive integers since its cardinality is double due to the Cartesian product"
Well, the same intuition is probably there for the sets of positive integers and even positive integers. But there is a bijection between the two sets, hence their cardinalities are equal (one cardinality is not "twice" the other cardinality).
So whenever your intuition says that the number of elements of one set C is 2 or 3 or 10 or m times the number of elements of another set B, you should know that the two sets B and C are in fact of the same cardinality. It's somewhat counterintuitive at first sight but that's how it is.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-08-02

Suppose that A is the set of sophomores at your school and B is the set of students taking discrete mathematics at your school. Express each of these sets in terms of A and B. 
a) the set of sophomores taking discrete mathematics in your school 
b) the set of sophomores at your school who are not taking discrete mathematics 
c) the set of students at your school who either are sophomores or are taking discrete mathematics 
Use these symbols: 

asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-18

Discrete Mathematics Basics

1) Find out if the relation R is transitive, symmetric, antisymmetric, or reflexive on the set of all web pages.where (a,b)R if and only if 
I)Web page a has been accessed by everyone who has also accessed Web page b.
II) Both Web page a and Web page b lack any shared links.
III) Web pages a and b both have at least one shared link.

asked 2022-07-17
Discrete math induction problem.
if n is a positive integer, prove that,
1 2 + 2 3 + 3 4 + + n ( n + 1 ) = n ( n + 1 ) ( n + 2 ) 3
Basic step is 1, then assume k is true and we get,
1 2 + 2 3 + 3 4 + + k ( k + 1 ) = k ( k + 1 ) ( k + 2 ) 3
After that I am stuck because the answer key is telling me that the next step is to add ( k + 1 ) ( k + 2 ), but I don't know why we do that. Aren't we supposed to just plugin k + 1 into all k variables. Why are we adding ( k + 1 ) ( k + 2 ) to both sides?
asked 2022-02-11
xy'ln(y/x)=x+yln(y/x)find general solution of the homogenous equation
asked 2022-05-13
From homogeneous to non-homogeneous linear recurrence relation
I'm trying to do the following exercise:
Find a non-homogeneous recurrence relation for the sequence whose general term is
a n = 1 2 3 n 2 5 7 n
From this expression we can obtain the roots of the characteristic polynomial P(x), which are 3 and 7, so P ( x ) = x 2 10 x + 21 and a n = 10 a n 1 21 a n 2 n 2 , a 0 = 1 10 , a 1 = 13 10
Now I don't know how to obtain a non-homogeneous recurrence relation given this homogeneous recurrence relation.

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question