# Math Help - Two set theory problems

1. ## Two set theory problems

I have this kind of problems:

1. Let $A$ be a set so that $card(A) \geq 2$. Show that $Sq(A) \preceq A^\omega$. $A ^\omega$ means funtion $g: \omega \rightarrow A$ and $Sq(A)= \bigcup_{n \in \omega} A^n$ ( $A^n$ means funtions $h: n \rightarrow A$).

I know that I have to build injection between those sets, but how to do it?

2. Let's designate $F(A) = \{B \in P(A) \mid B finite\}$. Show that $F(A) \approx A$, when $A$ is infinite.

I know that I have find bijection between those sets, but how to do it in this case?

2. Hm, I don't know if this is the step in the same direction, but the first thing that comes to mind for 2) is, if A were the set of natural numbers, then each finite subse can be encoded by a single number. E.g., the list of prime numbers is $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $p_4 = 7$, ..., so $\{3,4,7,0\}$ would be encoded as $p_1^{3+1}\cdot p_2^{4+1}\cdot p_3^{7+1}\cdot p_4^{0+1}$. By Fundamental Theorem of Arithmetic, factorization into primes is unique, so one gets the original set unambiguously from the code.

3. Originally Posted by Ester
I have this kind of problems:

1. Let $A$ be a set so that $card(A) \geq 2$. Show that $Sq(A) \preceq A^\omega$. $A ^\omega$ means funtion $g: \omega \rightarrow A$ and $Sq(A)= \bigcup_{n \in \omega} A^n$ ( $A^n$ means funtions $h: n \rightarrow A$).

I know that I have to build injection between those sets, but how to do it?
I think it is enough to show that $card(A^n) \preceq A^\omega$. Showing this should be easy. Do you know how to continue after proving this?

4. Originally Posted by Ester
2. Let's designate $F(A) = \{B \in P(A) \mid B finite\}$. Show that $F(A) \approx A$, when $A$ is infinite.

I know that I have find bijection between those sets, but how to do it in this case?
I guess you've forgotten the assumption that A is infinite.
Note that $F(A)=\bigcup_{n\in\mathbb{N}} \{ B\subset A \mid \mathrm{card} B=n\}$. (Finite sets = sets having 0,1,2,3,... elements.)

Can you show (using some results you know from your lecture) that $\{ B\subset A \mid \mathrm{card} B=n\} \approx A$ for any infinite set A? How do you continue from there?

5. Originally Posted by kompik
I think it is enough to show that $card(A^n) \preceq A^\omega$. Showing this should be easy. Do you know how to continue after proving this?
I have been thinking this problem, and I can't get any further. Can you explain why this: $card(A^n) \preceq A^\omega$ instead of $card(\bigcup_{n \in \omega} A^n) \preceq A^\omega$?

6. Originally Posted by kompik
I guess you've forgotten the assumption that A is infinite.
Note that $F(A)=\bigcup_{n\in\mathbb{N}} \{ B\subset A \mid \mathrm{card} B=n\}$. (Finite sets = sets having 0,1,2,3,... elements.)

Can you show (using some results you know from your lecture) that $\{ B\subset A \mid \mathrm{card} B=n\} \approx A$ for any infinite set A? How do you continue from there?
This problem has also cause me some difficulties over the weekend.. I have been thinking this too, and I still haven't been able to solve it.

7. Originally Posted by Ester
I have been thinking this problem, and I can't get any further. Can you explain why this: $card(A^n) \preceq A^\omega$ instead of $card(\bigcup_{n \in \omega} A^n) \preceq A^\omega$?
If you don't mind, I will use $|A|$ instead of $card A$.

If $\kappa$ is a cardinal and $|A^n| \le \varkappa$, then $|\bigcup_{n\in\omega} A^n| \le \aleph_0.\varkappa$, right?

Now, for every infinite cardinal number you have $\aleph_0.\varkappa=\varkappa$.

Originally Posted by wikipedia
If either $\varkappa$ or $\mu$ is infinite and both are non-zero, then
$\kappa\cdot\mu = \max\{\kappa, \mu\}.$
See cardinal multiplication at wikipedia, but I guess you've covered this at your lecture.

8. Originally Posted by Ester
This problem has also cause me some difficulties over the weekend.. I have been thinking this too, and I still haven't been able to solve it.
Have you seen this result at your lecture: If A is infinite then $A\times A \approx A$. Can you continue from there?

9. Originally Posted by kompik
If you don't mind, I will use $|A|$ instead of $card A$.

If $\kappa$ is a cardinal and $|A^n| \le \varkappa$, then $|\bigcup_{n\in\omega} A^n| \le \aleph_0.\varkappa$, right?
Hmm... I'm just wondering, how did you get in $|\bigcup_{n\in\omega} A^n| \le \aleph_0.\kappa$ that $\aleph_0$ there?

I undestand why I only need to show that $card(A^n) \preceq A^\omega$, but now I'm not sure how to contruct injection between these sets.

10. Originally Posted by kompik
Have you seen this result at your lecture: If A is infinite then $A\times A \approx A$. Can you continue from there?
Yes, I have seen that result, but I don't undestand why I need it in this exercise. I'm totally lost.

11. Originally Posted by Ester
Hmm... I'm just wondering, how did you get in $|\bigcup_{n\in\omega} A^n| \le \aleph_0.\kappa$ that $\aleph_0$ there?

I undestand why I only need to show that $card(A^n) \preceq A^\omega$, but now I'm not sure how to contruct injection between these sets.
I think I have mixed up some things. (It wasn't always clear whethe I am speaking about problem 1 or problem 2.) To be sure - now I am talking about problem 1.
You know that $A\times A \approx A$ (for A infinite).
Prove by induction that $A^n \approx A$. This means $|A^n|=|A|$.

Now, if you make a union if countably many sets, each of them having cardinality $\varkappa$ then the cardinality of union is (at most) $\aleph_0.\varkappa$. (This should answer your question concerning $\aleph_0$.)

As far as your question about injection is concerned: To show that there is an inequality between two cardinalities, finding an injection is one possibility. The solution I am suggesting is different - we show the inequality without explicitly constructing an injective map between the two sets.

12. As far as problem 2 is concerned:
We already know that $|A^n|=|A|$ for each n (assuming that A is infinite).

Now, if you can construct an injection from $\{B\subseteq A; |B|=n\}$ to $A^n$, you get the inequality $|\{B\subseteq A; |B|=n\}|\le |A|$.

The opposite inequality is (I believe) easy.

Combining these two inequalities you get (using Cantor-Bernstein) that $|\{B\subseteq A; |B|=n\}|=|A|$ for each n.

13. Originally Posted by kompik
As far as problem 2 is concerned:
We already know that $|A^n|=|A|$ for each n (assuming that A is infinite).

Now, if you can construct an injection from [tex]\{B\subseteq A; |B|=n\}[\math] to $A^n$, you get the inequality $|\{B\subseteq A; |B|=n\}|\le |A|$.

The opposite inequality is (I believe) easy.

Combining these two inequalities you get (using Cantor-Bernstein) that $|\{B\subseteq A; |B|=n\}|=|A|$ for each n.
Okey, this is how I was thinking to "solve" it:

Let's designate $H: \{B \subseteq A \mid card(B) = n\} \rightarrow A^n$, so that $H(B) = f(\{n\})$, where $A^n$ is a function $f:n \rightarrow A$ with every $n\in \omega$.

Let's choose arbitrary $B_1,B_2 \in dom(H)$ so that $B_1 \ne B_2$. Now $card(B_1) = n, card(B_2) = m$, where $n ,m \in \omega, n \ne m$. $H(B_1) = f_1(\{n\})$ and $H(B_2) = f_2(\{m\})$.

Now $f_1 \ne f_2$ so $f_1(\{n\}) \ne f_2(\{m\})$ and that's why $H(B_1) \ne H(B_2)$. So $H$ is injective.

The other direction I was thinking to do like this:

Let's designate $G: A^n \rightarrow \{B \subseteq A \mid card(B) = n\}$, so that $G(f) = B$ where $B \approx n$ and $A^n$ is a function $f:n \rightarrow A$ with every $n\in \omega$.

Let's choose arbitrary $f_1, f_2 \in A^n, n\in \omega, f_1 \ne f_2$. Now $f_1:n \rightarrow A, f_2:m \rightarrow A$. $G(f_1) = B_1, G(f_2) = B_2, B_1 \approx n, B_2 \approx m$, so $B_1 \ne B_2$ and that's why $G(f_1) \ne G(f_2)$. So $G$ is injective.

I think I got that last one some how wrong... And I'm not sure about the first one either.

14. Originally Posted by Ester
1. Let $A$ be a set so that $card(A) \geq 2$. Show that $Sq(A) \preceq A^\omega$. $A ^\omega$ means funtion $g: \omega \rightarrow A$ and $Sq(A)= \bigcup_{n \in \omega} A^n$ ( $A^n$ means funtions $h: n \rightarrow A$).

I know that I have to build injection between those sets, but how to do it?
My original intention was to guide you somehow, so that you come up with a solution by yourself (in several steps). Maybe I am not good at this, or maybe I tried to used the facts about cardinal numbers, which you're not familiar with. So I will simply try to write down some solutions and then we can go through them, if something is not clear.

Problem 1 first. Forget the approach I suggested before (using cardinalities). We construct an injection F from Sq(A) to $A^\omega$.

A has at least two elements. Choose some $a\ne b$ in A.

If f belongs to some $A^n$, i.e., it is a function from $n=\{0,1,\dots,n-1\}$ to A. Let us define $F(f):\omega \to A$ as follows:
$F(f)(k)=\begin{cases}
f(k),&\text{if }k a,&\text{if }k=n\\
b,&\text{if }k>n.
\end{cases}$

The basic idea is using a and b to discriminate between elements of $A^n$ and $A^m$ for $n\ne m$.

You can try to prove that this is indeed an injection. Drawing some pictures might help to understand it.

15. Originally Posted by Ester
2. Let's designate $F(A) = \{B \in P(A) \mid B finite\}$. Show that $F(A) \approx A$, when $A$ is infinite.

I know that I have find bijection between those sets, but how to do it in this case?
In this case I do not know how to describe the bijection explicitly. So I try to prove |F(A)|=|A| instead. (Which is equivalent.)

$|A|\le|F(A)|$ is easy, since we have injection $a\mapsto\{a\}$ from A to F(A).

Now; let us denote $A_n:=\{B\subseteq A; |B|=n\}$. Then $F(A)=\bigcup_{n\in\omega} A_n.$
If I show $|A_n|\le|A|$ then I get $|F(A)|\le|A|$. (I tried to explain this before - check the older posts.)

You agreed that $|A|=|A\times A|$ and this can be used to show (by induction) that $|A|=|A^n|$. (Here $A^n$ means the set of all ordered n-tuples, which is basically the same thing as all functions $n\to A$.)

I want to show $|A_n|\le|A^n|$ by exhibiting an injection $A_n\to A^n$. The injection can be (for example) obtained in a such way that to a set (containing n elements of A) I assign an n-tuple where these elements are ordered in an increasing order.

So we have $|A_n|\le |A^n| = |A|.$

EDIT: Perhaps someone could provide a simpler solution to this one - I was not able to come up with anything easier from the scratch. (In particular, I was not able to avoid using Cantor-Bernstein and cardinalities.)

Page 1 of 2 12 Last