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

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    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.
    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 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?
    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 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?
    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 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?
    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 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.
    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: 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.

    Quote 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.
    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 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 |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.
    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 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 |\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.
    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 |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.
    Last edited by kompik; April 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 |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.
    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 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}<br />
f(k),&\text{if }k<n\\<br />
a,&\text{if }k=n\\<br />
b,&\text{if }k>n.<br />
\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.
    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 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.)
    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: January 20th 2010, 02:57 AM
  2. Set Theory Problems (please help)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 26th 2009, 11:48 PM
  3. Set Theory Problems (please help)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 24th 2009, 11:52 AM
  4. Group theory problems
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: September 3rd 2008, 10:01 PM
  5. Problems relating Theory of Automata (Computer Theory)
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 17th 2007, 09:52 AM

Search Tags


/mathhelpforum @mathhelpforum