0

Prove that the cardinality of the set X without element a = the cardinality of X - 1.

I know that |X\{a}|=|X|-1 but I'm not sure how to prove this. I was thinking of defining an enumeration of f: [n] -> x and g: [n-1] -> x{a}. But I'm not sure how to define a function g(i) such that n doesn't have to map to a.

anomaly
  • 25,364
  • 5
  • 44
  • 85
Emily
  • 123

1 Answers1

1

If $A$ is finite and $|A| =n$ then there is bijection $f: \{1,2,.....,n\} \to A$.

Let $g: \{1,2,3,.....,n-1\} \to A\setminus \{a\}$ be defined as

$g(k)=\begin{cases}f(k)&f^{-1}(a) > k\\f(k+1)&f^{-1}(a) \le k\end{cases}$

It's easy to show it's a bijection.

But if $A$ is infinite..... I'm not sure where or if it is ever written that for infinite sets $|A| - 1 = |A|$.

But the find a bijection between $A$ and $A-\{a\}$ for infinite sets is well known.

Claim: we can find a countable subset of $A$.

Let $a_1 = a$. As $|A| > 1$ there is an $b\in A$ so that $b\ne a$. Let $a_2 = b$.

Via induction. If $\{a_1,....,a_k\} \subset A$. If $ \{a_1,....,a_k\} = A$ then $|A| = k$ so there is a $c \in A$ so that $c\not \in \{a_1, ....,a_k\}$. Let $a_{k+1} = c$. By induction a set $B=\{a_i|i\in \mathbb N\}\subset A$ exists.

Define $f:\mathbb A \to \mathbb A-\{a\}$ via. $f(x)=\begin{cases}f(a_{i+1})&\text{if }x = a_i \in B\\x&\text{otherwise}\end{cases}$.

Easy to show $f$ is a bijection.

fleablood
  • 124,253
  • how can you show that g(k) is a bijection? with an inverse function? – Emily Feb 21 '20 at 17:44
  • Prove it directly. Surjective: if $b\in A\setminus{a}$ then $b\in A$ and there is $k\in {1,.....,n}$ so that $f(k)=b$. Now if $k\ne f^{-1}(a)$ (else $b = f(k)=f(f^{-1}(a))=a$). So either $k<f^{-1}(a)$ or $k>f^{-1}(a)$. If $k < f^{-1}(a)$ then $g(k) = f(k)=b$ and $k\le n-1$. If $k>f^{-1}(a)$ then $k-1\le f^{-1}(a)$ and $g(k-1)=f(k-1+1)=f(k)=b$ and $k-1\le n-1$. So there is a $m\in{1,...,n-1}$ so that $g(m)=b$. So surjective. Injective proven similarily. – fleablood Feb 21 '20 at 19:29
  • Injectivity: Let $j,k\in {1,...,n-1}; j \ne k$ and, wolog $j<k$. Then $j\ne k$, $j\ne k+1$ and $j+1\ne k+1$. $f$ is injective so $f(j)\ne f(k);f(j)\ne f(k+1)$ and $f(j+1)\ne f(k+1)$. If $j<k<f^{-1}(a)$ then $g(j)=f(j)\ne f(k)=g(k)$. If $j<f^{-1}(a)\le k$ then $g(j)=f(j)\ne f(k+1)=g(k)$. And if $f^{-1}(a)\le j< k$ then $g(j)=f(j+1)\ne f(j+1)= g(k)$. Thus if $j\ne k$ then $g(j)\ne g(k)$ so $g$ is injective. – fleablood Feb 21 '20 at 19:45