7
$\begingroup$

This is a homework problem for class credit and I would appreciate a hint.

Let $A$ be an infinite set and suppose $x, y$ and $z$ are points in $A$. Show that $A$ has the same cardinality as $A\setminus\{x,y,z\}$.

So far I am trying to solve this for the more general case, let $A$ be an infinite set and $B$ be a finite subset of $A$, show that $A$ has the same cardinality as $A\setminus B$. If $B$ is finite and $A$ is infinite, then $A\setminus B$ is infinite because if $A\setminus B$ were finite then $A = A\setminus B \cup B$, the union of two finite sets and hence $A$ would be finite. Using Cantor-Bernstein we know that if there is a one-to-one function from $A$ to $A\setminus B$ and a one-to-one function from $A\setminus B$ to $A$, then $A$ and $A\setminus B$ are equivalent. It is easy to define a function $f:A\setminus B \to A$ that is one-to-one, $f(x) = x$.

Now I need to define a function $g:A \to A\setminus B$ that is one-to-one. I have a feeling that this involves using the axiom of choice.

Is this the right strategy? Have I made any errors? And can anyone give me a hint on how to define a one to one function from $A$ to $A\setminus B$?

$\endgroup$
  • 2
    $\begingroup$ Hint: One can show (this does indeed require a bit of choice) that any infinite set has a countably infinite subset. $\endgroup$ – Chris Eagle Oct 9 '11 at 19:14
  • $\begingroup$ This really depends on how you define infinite, or whether or not the axiom of choice is assumed. $\endgroup$ – Asaf Karagila Oct 9 '11 at 19:16
  • $\begingroup$ You are right to realize that it is the same as the case of deleting any finite set. Maybe just understand why $A$ and $A-\{x\}$ have the same cardinality? Then $A-\{x\}$ and $A-\{x,y\}$, etc. $\endgroup$ – tkr Oct 9 '11 at 19:16
  • $\begingroup$ Hint. Prove for it for the case $A=\mathbb{N}$. As you said you will need axiom of choice. $\endgroup$ – Murphy Oct 9 '11 at 21:16
7
$\begingroup$

It is enough to build a bijection $g$ from $A$ to $A\setminus\{x_0\}$ for every $x_0$ in $A$. To do that, choose a sequence $\{x_n\}_{n\geqslant1}$ of different points in $A\setminus\{x_0\}$ and define $g(x_n)=x_{n+1}$ for every $n\geqslant0$ and $g(x)=x$ for every $x$ in $A\setminus\{x_n\mid n\geqslant0\}$.

Ultimately, this only uses the existence of an injection from $\mathbb N$ to $A$ and of a bijection between $\mathbb N\cup\{0\}$ and $\mathbb N$.

$\endgroup$
  • $\begingroup$ This proof involves some minor choice, since it is consistent to have infinite sets without countable subsets. $\endgroup$ – Asaf Karagila Oct 9 '11 at 21:09
7
$\begingroup$

Let us assume for a moment that the definition of infinite$^1$ is: $$|X|\ge\aleph_0$$

Let $f\colon\mathbb N\to X$ be a one-to-one function, whose existence is assured from the definition above. Without loss of generality we can assume that $f(0)=x, f(1)=y, f(2)=z$.

Consider the function $g\colon\mathbb N\to\mathbb N$ given by $g(n)=n+3$, this is obviously an injective function.

Define the following function from $X$ into $X\setminus\{x,y,z\}$:

$$h(a)=\begin{cases} f(g(f^{-1}(a))) & \exists n\in\mathbb N: f(n)=a\\ a&\text{otherwise.}\end{cases}$$

We can see that $h$ is injective since $f^{-1}$ is injective on the range of $f$, $g$ is injective, and again $f$ is injective. This is a composition of injective functions, which is injective (if you did not prove this yet, this makes a nice and important exercise)

On the other hand if $a\notin\operatorname{Rng}(f)$ then $a\mapsto a$ which is clearly injective.

Now let $a\in X\setminus\{x,y,z\}$, then either $a\notin\operatorname{Rng}(f)$ and so $a\in\operatorname{Rng}(h)$, or $a=f(n)$ for some $n>2$, and so $h^{-1}(a)=f(n-3)$ which is an element of $X$ (since $n-3\in\mathbb N$).


If the definition of infinite is simply not bijectible with a finite set, and the axiom of choice is not assumed it is possible to have a set $X$ such that $|X|>|X\setminus\{x\}$, such set is called Dedekind-finite, and is used for many interesting counterexamples in set theory.



  1. A set $X$ is called Dedekind-infinite if it has a proper subset $Y$ such that $|Y|=|X|$. It is in fact equivalent to say that $|X|\ge\aleph_0$ or that for some $x\in X$ we have $|X|=|X\setminus\{x\}|$.
$\endgroup$
  • $\begingroup$ While it is not unusual to assume the axiom of choice in introductory courses (without telling that to people, that is) - I often see the definition of infinite as "not finite" rather than "has a countably infinite subset". $\endgroup$ – Asaf Karagila Oct 9 '11 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.