- #1

docnet

Gold Member

- 734

- 384

- Homework Statement
- 1) What does it mean if two sets ##X## and ##Y## have the same cardinality?

2) Given sets ##A## and ##B## what does ##|A|\leq |B|## mean?

3) Does there exist a surjection from the natural numbers to the reals? If so, define one. If not, explain why one cannot exist.

- Relevant Equations
- ##\mathbb{N}## and ## \mathbb{R}##

1)

Two sets have the same cardinality if there exists a bijection (one to one correspondence) from ##X## to ##Y##. Bijections are both injective and surjective. Such sets are said to be equipotent, or equinumerous. (credit to wiki)

2)

##|A|\leq |B|## means that there is an injective function from ##A## to ##B##. An injective function maps distinct elements of ##A## to distinct elements in ##B##.

3)

No.

Cantor's proof that there is no surjection ##f:\mathbb{N}\longrightarrow \mathbb{R}## seems relevant here.

I'm wondering if there is a lazier way to answer this question, although I think the following logic is flawed.

In class, we are given as a theorem that there is no bijection ##f:\mathbb{N}\longrightarrow \mathbb{R}##. Bijective functions are both injective and surjective, so there is no such ##f:\mathbb{N}\longrightarrow \mathbb{R}## that is both injective and surjective.

An example of an injection ##f:\mathbb{N}\longrightarrow \mathbb{R}##:

Let ##f:\mathbb{N}\longrightarrow \mathbb{R}## be a function defined by the rule ##f(n)=n##. ##f(n)\neq f(m)## whenever ##n\neq m##, so ##f## is injective. Since an injection ##f:\mathbb{N}\longrightarrow \mathbb{R}## was defined, it exists.

The issue is that this logic cannot deal with the possibility of an ##f## being surjective and not injective.

Two sets have the same cardinality if there exists a bijection (one to one correspondence) from ##X## to ##Y##. Bijections are both injective and surjective. Such sets are said to be equipotent, or equinumerous. (credit to wiki)

2)

##|A|\leq |B|## means that there is an injective function from ##A## to ##B##. An injective function maps distinct elements of ##A## to distinct elements in ##B##.

3)

No.

Cantor's proof that there is no surjection ##f:\mathbb{N}\longrightarrow \mathbb{R}## seems relevant here.

I'm wondering if there is a lazier way to answer this question, although I think the following logic is flawed.

In class, we are given as a theorem that there is no bijection ##f:\mathbb{N}\longrightarrow \mathbb{R}##. Bijective functions are both injective and surjective, so there is no such ##f:\mathbb{N}\longrightarrow \mathbb{R}## that is both injective and surjective.

An example of an injection ##f:\mathbb{N}\longrightarrow \mathbb{R}##:

Let ##f:\mathbb{N}\longrightarrow \mathbb{R}## be a function defined by the rule ##f(n)=n##. ##f(n)\neq f(m)## whenever ##n\neq m##, so ##f## is injective. Since an injection ##f:\mathbb{N}\longrightarrow \mathbb{R}## was defined, it exists.

The issue is that this logic cannot deal with the possibility of an ##f## being surjective and not injective.

Last edited: