1
$\begingroup$

Assume |X| = n ∈ N≥2 and Y is a denumerable set. Prove $Y^{|X|}$ is denumerable. Recall, $Y^{|X|}$ is the set of all functions from X to Y

Approach

By definition, I have to find a bijection from the N to $Y^{|X|}$. Another aproach would be to use induction.

Proof by induction

Base case $Y^{1}$ is denumerable by definition

Inductive hypothesis Assume $Y^{|X|}$ is denumerable. Show $Y^{|X+1|}$ is denumerable

$Y^{|X+1|}= Y^{|X|} \times Y^{1}$

so $Y^{1}$ is denumerable and $Y^{|X|}$ is denumerable by inductive hypothesis so the cartesian product of two denumerable sets is denumerable by a theorem proven in class

I think that the cartesian product makes sense in this case. How does that look?

I am gonna put another question in the same tread because I think it's the same proof.

Assume n ∈ N≥2 and X1, X2, . . . , Xn are denumerable sets. Prove X1 × X2 × · · · × Xn is denumerable.

Same proof?

$\endgroup$
  • $\begingroup$ this has nothing to do with absolute value. It's cardinality so in this case |X+1|=|X|+1. I stated that this theorem was proven in class. $\endgroup$ – TheMathNoob May 27 '16 at 8:27
  • $\begingroup$ so do you consider that I should add the proof of that theorem?. $\endgroup$ – TheMathNoob May 27 '16 at 8:28
  • $\begingroup$ what about the last problem I put. Same proof? $\endgroup$ – TheMathNoob May 27 '16 at 8:30
  • $\begingroup$ I deleted my comments, they were pointless. No, no need to reprove what was proven in class. $\endgroup$ – BrianO May 27 '16 at 8:30
  • $\begingroup$ Inductive step : Assume $X_1 \times X_2 \times ...... \times X_n$ for some $n \in N$ is denumerable. Show that $X_1 \times X_2 \times ...... \times X_{n+1}$ is denumerable. We have that $X_1 \times X_2 \times ...... \times X_n$ for some $n \in N$ is denumerable and assume $x_{n+1}$ is denumerable, so by definition the cross product of two denumerable sets is denumerable which implies that $X_1 \times X_2 \times ...... \times X_{n+1}$ is denumerable. $\endgroup$ – TheMathNoob May 27 '16 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.