Cardinal Arithmetic: Finite Set X, #X+1

[HMPARTICLE]

Because y is an element of the set X U {x}

 

[LCKurtz]

No. It is because if $m\le n$, so $m\in S_n$, you have there is $y\in X$ such that $f(y)=m$ because $f$ is a bijection between $X$ and $S_n$. And by the definition of g, if $y\in X$ then $g(y)=f(y)$. That is why $g(y) = m$.

This should complete the argument that $g$ is onto $S_{n+1}$. Now, since we have been through it and it isn't really a homework problem because you aren't actually taking a class, I'm going to stretch the PF rules and show you how you should write it up. We have called$$
S_n = \{ i\in N: i\le n\}$$You are given a bijection $f$ from a set $X$ to $S_n$. If $x$ is not an element of $x$, you want to demonstrate a bijection $g$ from $X\cup \{x\}$ to $S_{n+1}$.

Our proposed bijection is$$
g(y)=\left\{\begin{array}{rl}
f(y),& y\in X\\
n+1,& y=x
\end{array}\right.$$
Claim: $g$ is onto $S_{n+1}$
Proof: Suppose $m\in S_{n+1}$. If $m = n+1$ then $g(x) = n+1=m$. If $m < n+1$ then $m \in S_n$ so, since $f$ is a bijection between $X$ and $S_n$,(hence onto), there is a $y\in X$ such that $f(y) = m$. Since $y\in X$ then $g(y) = f(y)$ by the definition of $g$, so $g(y)=m$.
So in each case, $m=n+1$ or $m\le n$ we have found a $y$ such that $g(y) = m$.

Now we must show that $g$ is 1-1. You do it. Write down carefully what you have to prove and argue it.

 

[HMPARTICLE]

Thank you ever so much.

The first line
If m = n+1 then g(x) = m+1. I find this a little confusing. if m is some element of $S_{n+1}$ and m = n+1, i get this part... but then to say that g(x) = m+1.
This may sound really stupid, but to me, I'm not quite seeing it.

Claim: $g$ is a 1-1 function
Proof: Let $m \in S_{n+1}$ and $y_1, y_2 \in X \cup \{x\}$. suppose that $g(y_1) = g(y_2)$. Then we have two cases to deal with, if $m < n$ then by the definition of $g$, $g(y_1) = g(y_2)$ becomes $f(y_1) = f(y_2)$, but $f$ is a bijection, so it follows that $y_1=y_2$, in the second case, if $m = n +1$ then $g(y_1) = g(y_2)$ can only occur if $y_1 = y_2 = x$, and$g(x) = m+1$. In either case, g maps different elements to different elements. It follows that $g$ is 1-1

 

[LCKurtz]

Thank you ever so much.

The first line
If m = n+1 then g(x) = m+1. I find this a little confusing. if m is some element of $S_{n+1}$ and m = n+1, i get this part... but then to say that g(x) = m+1.
This may sound really stupid, but to me, I'm not quite seeing it.

Not stupid and you shouldn't see it. That was just a typo. I fixed it to $g(x) = n+1$.

Claim: $g$ is a 1-1 function
Proof: Let $m \in S_{n+1}$ and $y_1, y_2 \in X \cup \{x\}$. suppose that $g(y_1) = g(y_2) \color{red}{=m}$. Then we have two cases to deal with, if $\color{red}{m < n}$ then by the definition of $g$, $g(y_1) = g(y_2)$ becomes $f(y_1) = f(y_2)$, but $f$ is a bijection, so it follows that $y_1=y_2$, in the second case, if $m = n +1$ then $g(y_1) = g(y_2)$ can only occur if $y_1 = y_2 = x$, and $g(x) = m+1$. In either case, g maps different elements to different elements. It follows that $g$ is 1-1

Pretty good. You have to say what $m$ is, which I fixed, and is the inequality in red should read $m\le n$.

Have a nice holiday.

 

[HMPARTICLE]

Many thanks again, you also! :)