How can we show that h is surjective?

[evinda]

Hello! (Wave)

I am looking at the proof of the following proposition:

The union of two finite sets is a finite set.Proof:

Let $X,Y$ finite sets. Then there are $n,m \in \omega$ such that $X \sim n$ and $Y \sim m$, i.e. there are $f: X \overset{\text{1-1 & surjective}}{\longrightarrow}n, g: Y \overset{\text{1-1 & surjective}}{\longrightarrow}m$.First case: $X \cap Y=\varnothing$

We define the fuction $h: X \cup Y \to n+m$

such that $h(x)=f(x)$ if $x \in X$, $h(y)=n+g(y)$ if $y \in Y$.

We will show that $h: X \cup Y \overset{\text{1-1}}{\rightarrow}n+m$.

Let $a,b \in X\cup Y$ with $h(a)=h(b)$.

• if $a,b \in X$ then $h(a)=f(a)$ and $h(b)=f(b)$.
  So $f(a)=f(b) \rightarrow a=b$ since $f$ is injective.
  $$$$
• if $a,b \in Y$ then $h(a)=n+g(a)$ and $h(b)=n+g(b)$.
  So $n+g(a)=n+g(b) \rightarrow g(a)=g(b) \rightarrow a=b$ since $g$ is injective.
  $$$$
• if $a \in X, b \in Y$ then $h(a)=f(a)<n$ and $h(b)=n+g(b) \geq n$.
  So in this case it cannot hold $h(a)=h(b)$.

Now we will show that $h: X \cup Y \overset{\text{surjective}}{\longrightarrow} n+m$.We want to show that $\forall k \in n+m$ there is a $b \in X \cup Y$ such that $f(b)=k$.It suffices to show that $\forall k<n$ there is a $x \in X$ such that $h(x)=k$ and that $\forall n \leq k<n+m$ there is a $y \in Y$ such that $h(y)=k$.

$h(x)=k \Rightarrow f(x)=k$.

Since $f$ is surjective, it holds that $\forall k<n$ there is a $x \in X$ such that $f(x)=k$.

$h(y)=k \Rightarrow n+g(y)=k$We know that $g$ is surjective, but how can we use this knowing that we haven't defined the subtraction of natural numbers?

 

[mmwave]

Hello!

Great work on the proof so far. To address your question about using the surjectivity of $g$, we can use the fact that $g$ is surjective to show that for any $k \in n+m$, there exists a $y \in Y$ such that $n+g(y)=k$. This is because for every $k \in n+m$, there exists an $m \in \omega$ such that $g(y)=m$ and therefore $n+g(y)=k$.

In other words, since $g$ is surjective, for every element $k$ in the range of $h$, there exists an element $y \in Y$ such that $h(y)=k$. This shows that $h$ is surjective, and therefore the union of two finite sets $X$ and $Y$ is also a finite set, since there exists a bijection between $X \cup Y$ and $n+m$.

Keep up the good work!