# Show that A has the same cardinality as $A\setminus\{x,y,z\}$

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$?

• Hint: One can show (this does indeed require a bit of choice) that any infinite set has a countably infinite subset. – Chris Eagle Oct 9 '11 at 19:14
• This really depends on how you define infinite, or whether or not the axiom of choice is assumed. – Asaf Karagila Oct 9 '11 at 19:16
• 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. – tkr Oct 9 '11 at 19:16
• Hint. Prove for it for the case $A=\mathbb{N}$. As you said you will need axiom of choice. – Murphy Oct 9 '11 at 21:16

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$.

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

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\}|$.
• 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". – Asaf Karagila Oct 9 '11 at 19:44