Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Thread: Two set theory problems

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    35

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by Ester View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by Ester View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2010
    Posts
    35
    Quote Originally Posted by kompik View Post
    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$?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Mar 2010
    Posts
    35
    Quote Originally Posted by kompik View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by Ester View Post
    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$.

    Quote 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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by Ester View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Mar 2010
    Posts
    35
    Quote Originally Posted by kompik View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Mar 2010
    Posts
    35
    Quote Originally Posted by kompik View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by Ester View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    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.
    Last edited by kompik; Apr 20th 2010 at 08:29 AM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Mar 2010
    Posts
    35
    Quote Originally Posted by kompik View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by Ester View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by Ester View Post
    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.)
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Problems with proofs in set theory.
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: Jan 20th 2010, 02:57 AM
  2. Set Theory Problems (please help)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jan 26th 2009, 11:48 PM
  3. Set Theory Problems (please help)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jan 24th 2009, 11:52 AM
  4. Group theory problems
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Sep 3rd 2008, 10:01 PM
  5. Problems relating Theory of Automata (Computer Theory)
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Oct 17th 2007, 09:52 AM

Search Tags


/mathhelpforum @mathhelpforum