Cardinal Arithmetic: Finite Set X, #X+1

[LCKurtz]

I am setting out to prove that g is onto;
let $m \in S_{n+1}$, we must show that there exist $y \in X \cup \{x\}$ such that $g(y) = m$.

since $f$ is a bijection between X and $S_n$ there is some $y \in X$ such that $f(y) = m$

That is only true if $m\le n$, not if $m$ happens to be $n+1$. So state that in your argument.

and if $m= n+1$ then $g(x) = m$ by the definition of g

That is the other case

ALSO by the definition of $g$, $y \in X \cup \{x\}$ this implies that $y \in X$ or $y \in \{x\}$, since $x \in \{x\}$ we have $x,y \in \{x\}$ this implies that if $m = n+1$, then $g(x) = g(y) = m$.

I guess that is a very confusing way to say the domain of $g$ is $X\cup \{x\}$ and $g(x) = m+1$. You already said that above "by the definition of g".

Here i have show that there exist $y \in X \cup \{x\}$ such that $g(y) = m$

No you haven't. You have shown that if $m=n+1$ that $g(x)=m$. And you have shown that if $m\le n$ there is a $y\in X$ such that $\color{red}{f}(y) = m$. YOU HAVE TO SHOW THAT $\color{red}{g}(y) = m$.

You have to understand, i have run out of ideas. RUN out of ideas.

Perhaps it is time to print out this thread, take it to your teacher, and go over it with him/her in person. That would be a much more efficient use of time.

 

[HMPARTICLE]

Actually i don't have a teacher/ lecturer, i made the choice to drop out of university to look after a dying grandparent, this resulted in me taking a degree with the open university which does not cover analysis of this kind. so i am self-studying Analysis 1 by terrence tao. When i do come across a problem i have to post it on here. I have NO other choice. I don't have a lecturer to ask.

It's not that I am not applying myself, i spend countless hours on this book.

But thanks for your time

 

[LCKurtz]

OK. Then respond to my last post. You have to show $g(y)=m$. What is $g(y)$ according to its definition?

 

[HMPARTICLE]

for any $y \in X \cup \{x\}$
we define;
$g(y):= f(y)$ for all $y \in X$,
$g(x):=n+1$

 

[LCKurtz]

for any $y \in X \cup \{x\}$
we define;
$g(y):= f(y)$ for all $y \in X$,
$g(x):=n+1$

So tell me how you know there is a $y$ such that $g(y)=m$. I know, it's easy. But you have to say why.

 

[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! :)