Help with infinite sets

kory

Junior Member
Joined
Mar 8, 2021
Messages
66
Can someone walk me through the process of solving an infinite set that is countable.

Define the set [MATH]4Z^+[/MATH] as the set of positive integers that are multiples of [MATH]4 (i.e. 4, 8, 12, 16, ...)[/MATH] Show that the set [MATH]4Z^+[/MATH] is countably infinite by identifying a function whose domain is the natural numbers [MATH]N[/MATH] and whose co-domain is the [MATH]4Z^+[/MATH]

I could be wrong but I think I need to start off with making a function. Is this correct?
[MATH]N =[/math] { [math]4,8,12,16,20,24,28,32 [/math] }
[MATH]O =[/math] { [math]1,2,3,5,6,7,9,10 [/math] }
 
Define the set [MATH]4Z^+[/MATH] as the set of positive integers that are multiples of [MATH]4 (i.e. 4, 8, 12, 16, ...)[/MATH] Show that the set [MATH]4Z^+[/MATH] is countably infinite by identifying a function whose domain is the natural numbers [MATH]N[/MATH] and whose co-domain is the [MATH]4Z^+[/MATH]
Your set \(N=\{4\cdot n| n\in\mathbb{Z}^+\}\) That definition gives us the mapping we need.
 
So my Domain is {[MATH]1,2,3,4,5,6......n[/MATH]}
and my Co-Domain is {[MATH]4,8,12,16.....n[/MATH]}

Right?...I'm trying to figure out what I'm supposed to know because I dont know what I'm supposed to know...
 
To prove that a set A is countably infinite you must be able to find a bijection [MATH] f:\mathbb{N} \rightarrow A[/MATH]
In this case such a mapping is easy to find:
[MATH]f(n)=4n, n \in \mathbb{N}[/MATH]f is clearly bijective (but you might explain why) and [MATH]f:\mathbb{N} \rightarrow 4\mathbb{Z}^+[/MATH][MATH]\therefore 4\mathbb{Z}^+[/MATH] is countably infinite.
 
OK. So for clarification, 4n is infinitely countable because its not a real number. If it was a real number, then it would be uncountable because a decimal can go on forever?
 
If you mean by that [MATH]4\mathbb{Z}^+[/MATH] is countably infinite while [MATH]4\mathbb{R}[/MATH] would be uncountably infinite, then you are correct.

[MATH]4\mathbb{Z}^+[/MATH] is countably infinite because it meets the definition: a set A is countably infinite if there exists a bijection[MATH] f:\mathbb{N}→A[/MATH].
That basically means the set is infinite and you can describe a way of making a list containing all the elements: e.g. the list 4, 8, 12, 16... (clearly contains all the elements of [MATH]4\mathbb{Z}^+[/MATH])
[MATH]4\mathbb{Z}[/MATH] is also countably infinite: 0, 4, -4, 8, -8, 12, -12,... clearly contains all of [MATH]4\mathbb{Z}[/MATH][MATH]4\mathbb{Q}[/MATH] is also countably infinite, although the list is a bit trickier to describe! ([MATH]\mathbb{Q}[/MATH], the set of rational numbers is countably infinite).
4[MATH]\mathbb{R}[/MATH] is not countably infinite as no list can be described without missing out some of the numbers.
The set of irrational numbers is also uncountable.
 
Next I have to prove that the function is a one-to-one correspondence between the set [math]N[/math] and the set [math]4Z^+[/math]
I have:
Suppose [math]y[/math] is a particular but arbitrarily chosen positive integer.
We must show that [math]x[/math] in the natural numbers, [math]x \in N[/math] such that [math]f(n)=y[/math][math]4x+2=y[/math][math]4x=y+2[/math] by addition
[math]4x[/math]/[math]4[/math] = [math]y+2[/math]/[math]4[/math] by division
[math]x=y+1[/math]/[math]2[/math]Since [math]y=2k+2[/math]then [math]x=(2k+2)+1)[/math]/[math]2[/math] = [math]2k+2[/math]/[math]2 = k+1[/math]
is this right so far?
 
The 1-1 mapping is not that hard to find
1 goes to 4*1 or 4
2 goes to 4*2 or 8
3 goes to 4*3 or 12
...
n goes to 4*n
Next I have to prove that the function is a one-to-one correspondence between the set [math]N[/math] and the set [math]4Z^+[/math]
I have:
Suppose [math]y[/math] is a particular but arbitrarily chosen positive integer.
We must show that [math]x[/math] in the natural numbers, [math]x \in N[/math] such that [math]f(n)=y[/math][math]4x+2=y[/math][math]4x=y+2[/math] by addition
[math]4x[/math]/[math]4[/math] = [math]y+2[/math]/[math]4[/math] by division
[math]x=y+1[/math]/[math]2[/math]Since [math]y=2k+2[/math]then [math]x=(2k+2)+1)[/math]/[math]2[/math] = [math]2k+2[/math]/[math]2 = k+1[/math]
is this right so far?
????
 
@kory
Your overall aim is not just to show that the function [MATH]f:\mathbb{N} \rightarrow[/MATH] 4[MATH]\mathbb{Z}^+[/MATH] is 1-1 but also that it is onto.
Informally, 'onto' means that any element of 4[MATH]\mathbb{Z}^+[/MATH] is [MATH] f(n)[/MATH] for some [MATH]n \in \mathbb{N}[/MATH].
Informally, '1-1' means that any element of 4[MATH]\mathbb{Z}^+[/MATH] is [MATH] f(n)[/MATH] for at most one value of [MATH]n \in \mathbb{N}[/MATH].
Even though it is obvious that f is both, in proofs you must always start with the definitions. So I look up the definition of 1-1 and I look up the definition of onto (even though I 'know' what they mean), write out the definitions as they apply to this question and simply prove those statments (no matter what looks obvious or not to me). Lots of statements in mathematics are obvious and many of them are not true! So you always stick rigidly to the definitions. Here is a proof.

Prove that [MATH]f:\mathbb{N} \rightarrow 4\mathbb{Z}^+[/MATH] is a bijection (1-1 and onto)
where [MATH]f(n)=4n, n \in \mathbb{N}[/MATH]

Onto: [MATH]\quad y \in 4\mathbb{Z}^+ \rightarrow \exists n \in \mathbb{N}: f(n)=y \quad[/MATH] (from definition)
Proof
[MATH]4\mathbb{Z}^+ = \{4n:n \in \mathbb{N}\}[/MATH][MATH]\therefore y \in 4\mathbb{Z}^+ \rightarrow \exists n \in \mathbb{N}: 4n=y[/MATH][MATH]\therefore \exists n \in \mathbb{N}: f(n)=y[/MATH]Q.E.D.

1-1:[MATH]\quad f(n_1)=f(n_2) \rightarrow n_1=n_2 \quad[/MATH] (from definition)
Proof
[MATH]f(n_1)=f(n_2)[/MATH][MATH]\leftrightarrow 4n_1=4n_2[/MATH][MATH]\leftrightarrow n_1=n_2[/MATH]Q.E.D.

f is a bijection

ºººººººººººººººººººººººººººº

(1) Next I have to prove that the function is a one-to-one correspondence between the set [math]N[/math] and the set [math]4Z^+[/math](2) Suppose [math]y[/math] is a particular but arbitrarily chosen positive integer.
(3) We must show that [math]x[/math] in the natural numbers, [math]x \in N[/math] such that [math]f(n)=y[/math](4) [math]4x+2=y[/math](5) [math]4x=y+2[/math] by addition
(6) [math]4x[/math]/[math]4[/math] = [math]y+2[/math]/[math]4[/math] by division
(7) [math]x=y+1[/math]/[math]2[/math](8) Since [math]y=2k+2[/math](9) then [math]x=(2k+2)+1)[/math]/[math]2[/math] = [math]2k+2[/math]/[math]2 = k+1[/math]
A few comments
(1) you are only trying to prove it is 1-1 (but also needs to be onto)
(2) y should be an element of 4[MATH]\mathbb{Z}^+[/MATH] not [MATH]\mathbb{Z}^+[/MATH](3) ...that there exists x...f(x)=y (you have x and n)
(4) the function f(x)=4x not 4x+2
(5) this line does not follow from the previous one
(6)(7) when you divide y+2 by 4, you get [MATH]\frac{y}{4} + \frac{2}{4} \text{ or } \frac{y+2}{4}[/MATH](8) we know that y is of the form [MATH]4k[/MATH](9) the brackets don't match and the division by 2 is done incorrectly.

In summary, this is a good example of a formal proof and there are some good points to learn from it.
It all helps. You'll pick up a few things from this for next time. It all takes time and practice!
 
Last edited:
OK. So for clarification, 4n is infinitely countable because its not a real number. If it was a real number, then it would be uncountable because a decimal can go on forever?
On the contrary 4n IS a real number! You need to review the basic definitions.
 
Let me again mention DEFINITIONS. Definitions in mathematics (and science in general) are "working definitions"- you use the precise words of the definitions in proofs and solving problems. Years ago I asked a student for the definition of a certain word and his response was to give examples. That was why he was poor at proofs.

In mathematics we have the "natural numbers" (also called "counting numbers"), the "whole numbers" which includes the "natural numbers" as a subset, the "integers" which includes the "whole numbers" (and so the "natural numbers) as a subset, the "rational numbers" which includes the "integers" (and all of its subsets), the "real numbers" which includes the "rational numbers" (and all of its subsets), and the "complex numbers" which includes the "real numbers" (and all of its subsets).
 
Top