Set of Even Integers is Equivalent to Set of Integers

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\Z$ denote the set of integers.

Let $2 \Z$ denote the set of even integers.


Then:

$2 \Z \sim \Z$

where $\sim$ denotes set equivalence.


Proof

To demonstrate set equivalence, it is sufficient to construct a bijection between the two sets.


Let $f: \Z \to 2 \Z$ defined as:

$\forall x \in \Z: \map f x = 2 x$
\(\displaystyle \map f x\) \(=\) \(\displaystyle \map f y\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 2 x\) \(=\) \(\displaystyle 2 y\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(=\) \(\displaystyle y\)

demonstrating injectivity.


\(\displaystyle y\) \(\in\) \(\displaystyle 2 \Z\)
\(\displaystyle \leadsto \ \ \) \(\, \displaystyle \exists x \in \Z: \, \) \(\displaystyle y\) \(=\) \(\displaystyle 2 x\) Definition of Even Integer
\(\displaystyle \leadsto \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle f \sqbrk \Z\)

demonstrating surjectivity.


Hence by definition $f$ is a bijection.

$\blacksquare$


Sources