Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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. –  Frank Murphy Oct 9 '11 at 21:16

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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\}|$.
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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