1. Two set theory problems

I have this kind of problems:

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

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

2. Let's designate $\displaystyle F(A) = \{B \in P(A) \mid B finite\}$. Show that $\displaystyle F(A) \approx A$, when $\displaystyle 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 $\displaystyle p_1 = 2$, $\displaystyle p_2 = 3$, $\displaystyle p_3 = 5$, $\displaystyle p_4 = 7$, ..., so $\displaystyle \{3,4,7,0\}$ would be encoded as $\displaystyle 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 $\displaystyle A$ be a set so that $\displaystyle card(A) \geq 2$. Show that $\displaystyle Sq(A) \preceq A^\omega$. $\displaystyle A ^\omega$ means funtion $\displaystyle g: \omega \rightarrow A$ and $\displaystyle Sq(A)= \bigcup_{n \in \omega} A^n$ ($\displaystyle A^n$ means funtions $\displaystyle 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 $\displaystyle 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 $\displaystyle F(A) = \{B \in P(A) \mid B finite\}$. Show that $\displaystyle F(A) \approx A$, when $\displaystyle 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 $\displaystyle 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 $\displaystyle \{ 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 $\displaystyle 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: $\displaystyle card(A^n) \preceq A^\omega$ instead of $\displaystyle 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 $\displaystyle 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 $\displaystyle \{ 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: $\displaystyle card(A^n) \preceq A^\omega$ instead of $\displaystyle card(\bigcup_{n \in \omega} A^n) \preceq A^\omega$?
If you don't mind, I will use $\displaystyle |A|$ instead of $\displaystyle card A$.

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

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

Originally Posted by wikipedia
If either $\displaystyle \varkappa$ or $\displaystyle \mu$ is infinite and both are non-zero, then
$\displaystyle \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 $\displaystyle A\times A \approx A$. Can you continue from there?

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

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

I undestand why I only need to show that $\displaystyle 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 $\displaystyle 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 $\displaystyle |\bigcup_{n\in\omega} A^n| \le \aleph_0.\kappa$ that $\displaystyle \aleph_0$ there?

I undestand why I only need to show that $\displaystyle 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 $\displaystyle A\times A \approx A$ (for A infinite).
Prove by induction that $\displaystyle A^n \approx A$. This means $\displaystyle |A^n|=|A|$.

Now, if you make a union if countably many sets, each of them having cardinality $\displaystyle \varkappa$ then the cardinality of union is (at most) $\displaystyle \aleph_0.\varkappa$. (This should answer your question concerning $\displaystyle \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 $\displaystyle |A^n|=|A|$ for each n (assuming that A is infinite).

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

The opposite inequality is (I believe) easy.

Combining these two inequalities you get (using Cantor-Bernstein) that $\displaystyle |\{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 $\displaystyle |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 $\displaystyle A^n$, you get the inequality $\displaystyle |\{B\subseteq A; |B|=n\}|\le |A|$.

The opposite inequality is (I believe) easy.

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

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

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

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

The other direction I was thinking to do like this:

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

Let's choose arbitrary $\displaystyle f_1, f_2 \in A^n, n\in \omega, f_1 \ne f_2$. Now $\displaystyle f_1:n \rightarrow A, f_2:m \rightarrow A$. $\displaystyle G(f_1) = B_1, G(f_2) = B_2, B_1 \approx n, B_2 \approx m$, so $\displaystyle B_1 \ne B_2$ and that's why $\displaystyle G(f_1) \ne G(f_2)$. So $\displaystyle 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 $\displaystyle A$ be a set so that $\displaystyle card(A) \geq 2$. Show that $\displaystyle Sq(A) \preceq A^\omega$. $\displaystyle A ^\omega$ means funtion $\displaystyle g: \omega \rightarrow A$ and $\displaystyle Sq(A)= \bigcup_{n \in \omega} A^n$ ($\displaystyle A^n$ means funtions $\displaystyle 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 $\displaystyle A^\omega$.

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

If f belongs to some $\displaystyle A^n$, i.e., it is a function from $\displaystyle n=\{0,1,\dots,n-1\}$ to A. Let us define $\displaystyle F(f):\omega \to A$ as follows:
$\displaystyle F(f)(k)=\begin{cases} f(k),&\text{if }k<n\\ 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 $\displaystyle A^n$ and $\displaystyle A^m$ for $\displaystyle 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 $\displaystyle F(A) = \{B \in P(A) \mid B finite\}$. Show that $\displaystyle F(A) \approx A$, when $\displaystyle 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.)

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

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

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

I want to show $\displaystyle |A_n|\le|A^n|$ by exhibiting an injection $\displaystyle 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 $\displaystyle |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