Help with infinite sets

kory

New member
Joined
Mar 8, 2021
Messages
39
Can someone walk me through the process of solving an infinite set that is countable.

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


I could be wrong but I think I need to start off with making a function. Is this correct?
\(\displaystyle N =\) { \(\displaystyle 4,8,12,16,20,24,28,32 \) }
\(\displaystyle O =\) { \(\displaystyle 1,2,3,5,6,7,9,10 \) }
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
10,907
Define the set \(\displaystyle 4Z^+\) as the set of positive integers that are multiples of \(\displaystyle 4 (i.e. 4, 8, 12, 16, ...)\) Show that the set \(\displaystyle 4Z^+\) is countably infinite by identifying a function whose domain is the natural numbers \(\displaystyle N\) and whose co-domain is the \(\displaystyle 4Z^+\)
Your set \(N=\{4\cdot n| n\in\mathbb{Z}^+\}\) That definition gives us the mapping we need.
 

kory

New member
Joined
Mar 8, 2021
Messages
39
So my Domain is {\(\displaystyle 1,2,3,4,5,6......n\)}
and my Co-Domain is {\(\displaystyle 4,8,12,16.....n\)}

Right?...I'm trying to figure out what I'm supposed to know because I dont know what I'm supposed to know...
 

lex

Full Member
Joined
Mar 3, 2021
Messages
386
To prove that a set A is countably infinite you must be able to find a bijection \(\displaystyle f:\mathbb{N} \rightarrow A\)

In this case such a mapping is easy to find:
\(\displaystyle f(n)=4n, n \in \mathbb{N}\)
f is clearly bijective (but you might explain why) and \(\displaystyle f:\mathbb{N} \rightarrow 4\mathbb{Z}^+\)
\(\displaystyle \therefore 4\mathbb{Z}^+\) is countably infinite.
 

kory

New member
Joined
Mar 8, 2021
Messages
39
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?
 

lex

Full Member
Joined
Mar 3, 2021
Messages
386
If you mean by that \(\displaystyle 4\mathbb{Z}^+\) is countably infinite while \(\displaystyle 4\mathbb{R}\) would be uncountably infinite, then you are correct.

\(\displaystyle 4\mathbb{Z}^+\) is countably infinite because it meets the definition: a set A is countably infinite if there exists a bijection\(\displaystyle f:\mathbb{N}→A\).
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 \(\displaystyle 4\mathbb{Z}^+\))
\(\displaystyle 4\mathbb{Z}\) is also countably infinite: 0, 4, -4, 8, -8, 12, -12,... clearly contains all of \(\displaystyle 4\mathbb{Z}\)
\(\displaystyle 4\mathbb{Q}\) is also countably infinite, although the list is a bit trickier to describe! (\(\displaystyle \mathbb{Q}\), the set of rational numbers is countably infinite).
4\(\displaystyle \mathbb{R}\) 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.
 

kory

New member
Joined
Mar 8, 2021
Messages
39
Next I have to prove that the function is a one-to-one correspondence between the set \(\displaystyle N\) and the set \(\displaystyle 4Z^+\)

I have:
Suppose \(\displaystyle y\) is a particular but arbitrarily chosen positive integer.
We must show that \(\displaystyle x\) in the natural numbers, \(\displaystyle x \in N\) such that \(\displaystyle f(n)=y\)
\(\displaystyle 4x+2=y\)
\(\displaystyle 4x=y+2\) by addition
\(\displaystyle 4x\)/\(\displaystyle 4\) = \(\displaystyle y+2\)/\(\displaystyle 4\) by division
\(\displaystyle x=y+1\)/\(\displaystyle 2\)
Since \(\displaystyle y=2k+2\)
then \(\displaystyle x=(2k+2)+1)\)/\(\displaystyle 2\) = \(\displaystyle 2k+2\)/\(\displaystyle 2 = k+1\)

is this right so far?
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
10,368
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 \(\displaystyle N\) and the set \(\displaystyle 4Z^+\)

I have:
Suppose \(\displaystyle y\) is a particular but arbitrarily chosen positive integer.
We must show that \(\displaystyle x\) in the natural numbers, \(\displaystyle x \in N\) such that \(\displaystyle f(n)=y\)
\(\displaystyle 4x+2=y\)
\(\displaystyle 4x=y+2\) by addition
\(\displaystyle 4x\)/\(\displaystyle 4\) = \(\displaystyle y+2\)/\(\displaystyle 4\) by division
\(\displaystyle x=y+1\)/\(\displaystyle 2\)
Since \(\displaystyle y=2k+2\)
then \(\displaystyle x=(2k+2)+1)\)/\(\displaystyle 2\) = \(\displaystyle 2k+2\)/\(\displaystyle 2 = k+1\)

is this right so far?
????
 

lex

Full Member
Joined
Mar 3, 2021
Messages
386
@kory
Your overall aim is not just to show that the function \(\displaystyle f:\mathbb{N} \rightarrow\) 4\(\displaystyle \mathbb{Z}^+\) is 1-1 but also that it is onto.
Informally, 'onto' means that any element of 4\(\displaystyle \mathbb{Z}^+\) is \(\displaystyle f(n)\) for some \(\displaystyle n \in \mathbb{N}\).
Informally, '1-1' means that any element of 4\(\displaystyle \mathbb{Z}^+\) is \(\displaystyle f(n)\) for at most one value of \(\displaystyle n \in \mathbb{N}\).
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 \(\displaystyle f:\mathbb{N} \rightarrow 4\mathbb{Z}^+\) is a bijection (1-1 and onto)
where \(\displaystyle f(n)=4n, n \in \mathbb{N}\)


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

1-1:\(\displaystyle \quad f(n_1)=f(n_2) \rightarrow n_1=n_2 \quad\) (from definition)
Proof
\(\displaystyle f(n_1)=f(n_2)\)
\(\displaystyle \leftrightarrow 4n_1=4n_2\)
\(\displaystyle \leftrightarrow n_1=n_2\)
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 \(\displaystyle N\) and the set \(\displaystyle 4Z^+\)
(2) Suppose \(\displaystyle y\) is a particular but arbitrarily chosen positive integer.
(3) We must show that \(\displaystyle x\) in the natural numbers, \(\displaystyle x \in N\) such that \(\displaystyle f(n)=y\)
(4) \(\displaystyle 4x+2=y\)
(5) \(\displaystyle 4x=y+2\) by addition
(6) \(\displaystyle 4x\)/\(\displaystyle 4\) = \(\displaystyle y+2\)/\(\displaystyle 4\) by division
(7) \(\displaystyle x=y+1\)/\(\displaystyle 2\)
(8) Since \(\displaystyle y=2k+2\)
(9) then \(\displaystyle x=(2k+2)+1)\)/\(\displaystyle 2\) = \(\displaystyle 2k+2\)/\(\displaystyle 2 = k+1\)

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\(\displaystyle \mathbb{Z}^+\) not \(\displaystyle \mathbb{Z}^+\)
(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 \(\displaystyle \frac{y}{4} + \frac{2}{4} \text{ or } \frac{y+2}{4}\)
(8) we know that y is of the form \(\displaystyle 4k\)
(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:

HallsofIvy

Elite Member
Joined
Jan 27, 2012
Messages
7,453
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.
 

kory

New member
Joined
Mar 8, 2021
Messages
39
My brain is leaking out of my ears......this is so hard
 

lex

Full Member
Joined
Mar 3, 2021
Messages
386
My brain is leaking out of my ears......this is so hard
You’re doing grand. Writing rigorous proofs takes a lot of practice.
 
Last edited:

HallsofIvy

Elite Member
Joined
Jan 27, 2012
Messages
7,453
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).
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
10,368
On the contrary 4n IS a real number! You need to review the basic definitions.
If n is an integer, then 4n is a real number. I need to give this one some great thought. OK, I thought about it and you're correct.
 

HallsofIvy

Elite Member
Joined
Jan 27, 2012
Messages
7,453
I am so glad!
 
Top