Results 1 to 14 of 14

Math Help - Numerically Equivalent Sets

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Numerically Equivalent Sets

    For infinite sets A and B to be numerically equivalent. Is bijective function

    f:A \rightarrow B

    the only requirement that needs satisfying?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by novice View Post
    For infinite sets A and B to be numerically equivalent. Is bijective function

    f:A \rightarrow B

    the only requirement that needs satisfying?
    I'm not sure what you mean by numerically equivalent. One way of defining two sets to have the same cardinality if and only if there exists a bijection between the two.

    There is apparently another way of comparing set cardinalities, with cardinal numbers but I never learned anything on the topic and someone more knowledgeable on the matter will have to discuss it.

    (Note that when I say if and only if its merely a logical statement used in every definition, sometimes implicitly.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by gmatt View Post

    There is apparently another way of comparing set cardinalities, with cardinal numbers but I never learned anything on the topic and someone more knowledgeable on the matter will have to discuss it.
    There is nothing new here. If \text{card }A=\alpha,\text{card }B=\beta then \alpha\leqslant\beta\Leftrightarrow \exists f:A\overset{\text{injection}}{\longrightarrow}B
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    If \text{card }A=\alpha,\text{card }B=\beta then \alpha\leqslant\beta\Leftrightarrow \exists f:A\overset{\text{injection}}{\longrightarrow}B
    Are you thinking of A and B being countable?
    In my question, A and B are infinite.

    I know this theorem: An infinite subset of a denumerable set is denumerable.

    But I am tweaking it for a different scenario, where I know that neither A nor B is denumerable, except there is a bijective function from A to B.

    To make it simple. Suppose that A = \mathbb{R} and B=\mathbb{R}

    f:A \rightarrow B or equivalently f:\mathbb{R} \rightarrow \mathbb{R}

    is defined by f(x)=x

    Since we know that f is bijective, despite the fact that A and B being uncountable, is it sufficient to conclude that |A|=|B|?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by gmatt View Post
    I'm not sure what you mean by numerically equivalent. One way of defining two sets to have the same cardinality if and only if there exists a bijection between the two.

    There is apparently another way of comparing set cardinalities, with cardinal numbers but I never learned anything on the topic and someone more knowledgeable on the matter will have to discuss it.

    (Note that when I say if and only if its merely a logical statement used in every definition, sometimes implicitly.)
    Numerically equivalent set by definition is |A|=|B| where the sets are infinite. Please see more details in the question I put to Drexel.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    If I recall correctly, the definition is that |A| = |B| \text{ if } \exists f:A \overset{\text{bijection}} {\longrightarrow} B, and |A| \leq |B| \text{ if } \exists f:A \overset{\text{injection}} {\longrightarrow} B, as drexel has pointed out.

    (This is the definition for any A,B - not just countable sets.)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Defunkt View Post
    If I recall correctly, the definition is that |A| = |B| \text{ if } \exists f:A \overset{\text{bijection}} {\longrightarrow} B, and |A| \leq |B| \text{ if } \exists f:A \overset{\text{injection}} {\longrightarrow} B, as drexel has pointed out.

    (This is the definition for any A,B - not just countable sets.)
    Well, you have made it very clear for me to understand.

    Drexel runs at hypersonic speed when I am still crawling. I only knew that if f is injective, the |A| \leq |B|, but I couldn't see how that automatically translate to f being bijective.

    Now, I think you mean if f is bijective, then f:A\rightarrow B \Rightarrow |A|\leq |B| , and if f is surjective, then |A|\geq |B|. Then only after putting those two together,

    |A|\leq |B| and |A|\geq |B| \Rightarrow |A|=|B| .

    Yah?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by novice View Post
    Well, you have made it very clear for me to understand.

    Drexel runs at hypersonic speed when I am still crawling. I only knew that if f is injective, the |A| \leq |B|, but I couldn't see how that automatically translate to f being bijective.

    Now, I think you mean if f is bijective, then f:A\rightarrow B \Rightarrow |A|\leq |B| , and if f is surjective, then |A|\geq |B|. Then only after putting those two together,

    |A|\leq |B| and |A|\geq |B| \Rightarrow |A|=|B| .

    Yah?
    Yes, if f: A \rightarrow B surjective then this implies A \geq B. However, the general technique is that if f_1:A \rightarrow B is an injection and f_2:B \rightarrow A is also an injection, then |A| \leq |B| and |B| \leq |A| so |A| = |B|.

    For example, there clearly exists an injection f: \mathbb{N} \rightarrow \mathbb{Q}, this is just a \mapsto a. So to prove that |\mathbb{N}| = |\mathbb{Q}| you would just need to find an injection from \mathbb{Q} to \mathbb{N}, you don't need to go the whole hog and find a bijection!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Swlabr View Post
    ... you don't need to go the whole hog and find a bijection!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Sep 2009
    Posts
    502
    Friends, I thought I was done, but something is troubling me when I made A=\varnothing and B=\varnothing.

    Cleary \varnothing is finite, and we all know that |\varnothing|=|\varnothing|. Since there isn't any element to count nor is there a function from \varnothing to \varnothing, how do you prove that |A|=|B|?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by novice View Post
    nor is there a function from \varnothing to \varnothing
    There is a bijection from the empty set onto the empty set. The empty set itself is a bijection from the empty set onto the empty set.

    Moreover, if A = the empty set, and B = the empty set, then you don't need set theory to prove |A| = |B|, since it follows by identity theory alone (A = the empty set = B, so A = B, so |A| = |B|).
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by MoeBlee View Post
    There is a bijection from the empty set onto the empty set. The empty set itself is a bijection from the empty set onto the empty set.

    Moreover, if B = the empty set, and A = the empty set, then you don't need set theory to prove |A| = |B|, since it follows by identity theory alone.
    Oh! You are absolutely right. However dumb it was, I am so glad I asked.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    By the way, I think in some of the discussion above it was taken as implicit that if there is a surjection from A onto B then there is an injection from B into A. However, just to note, that requires the axiom of choice.

    The salient principles here that do not require the axiom of choice:

    By definition, A and B are equinumerous if and only if there is a bijection from A onto B.

    And, if there is a bijection from A onto B, then there is a bijection from B onto A (just take the inverse of the bijection from A onto B).

    And, if there is an injection from A into B and there is an injection from B into A, then there is a bijection from A onto B. And, such a bijection can be recovered from the two given injections (by following any of the constructive proofs of Schroder-Bernstein).
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by MoeBlee View Post
    By the way, I think in some of the discussion above it was taken as implicit that if there is a surjection from A onto B then there is an injection from B into A. However, just to note, that requires the axiom of choice.

    The salient principles here that do not require the axiom of choice:

    By definition, A and B are equinumerous if and only if there is a bijection from A onto B.

    And, if there is a bijection from A onto B, then there is a bijection from B onto A (just take the inverse of the bijection from A onto B).

    And, if there is an injection from A into B and there is an injection from B into A, then there is a bijection from A onto B. And, such a bijection can be recovered from the two given injections (by following any of the constructive proofs of Schroder-Bernstein).
    I would like to remark that just like the above remark there is another thing which needs to be proven using Zorn's Lemma (AKA AOC).

    Theorem: \text{has a smaller cardinal number}\overset{\Delta}{=}\text{ }\leqslant defines a linear ordering on the set of all cardinal numbers.

    Proof: The only thing that is unclear is the linearity of \leqslant. So, we must prove that given sets A,B it is true that \exists f:A\overset{\text{injection}}{\longrightarrow}B\te  xt{ or }\exists g:B\overset{\text{injection}}{\longrightarrow}A. If either A or B is empty the result is clear, so assume not. Fix a_0\in A and b_0\in B and define f_0:\{a_0\}\to\{b_0\} in the only possible way, clearly this is an injection. Let \Omega=\left\{(E,G,f):\{a_0\}\subseteq E,\text{ }\{b_0\}\subseteq G,\text{ }f:E\overset{\text{bijection}}{\longrightarrow}G,\  text{ } x\overset{f}{\mapsto}y\right\}. Define the ordering \overset{\Omega}{\leqslant} on \Omega by (E,G,f)\overset{\Omega}{\leqslant}\left(E',G',f'\r  ight)\Leftrightarrow E\subseteq E',\text{ }G\subseteq G',\text{ }f'\mid_{E}=f. This clearly is a partial ordering. We now must prove that every chain \left\{\left(E_\alpha,G_\alpha,f_\alpha\right)\rig  ht\}_{\alpha\in\mathcal{A}} has an upper bound. But, it is clear (I hope) that \left(\bigcup_{\alpha\in\mathcal{A}}E_\alpha,\bigc  up_{\alpha\in\mathcal{A}}G_\alpha,F\right)\in\Omeg  a where F:\bigcup_{\alpha\in\mathcal{A}}E_\alpha\to\bigcup  _{\alpha\in\mathcal{A}}G_\alpha is defined in the obvious way (@novice there's an exercise, figure it out how to say that in a rigorous manner). Also, once you have defined F it will be clear that \left(\bigcup_{\alpha\in\mathcal{A}}E_\alpha,\bigc  up_{\alpha\in\mathcal{A}}G_\alpha,F\right) is an upper bound for \left\{\left(E_\alpha,G_\alpha,f_\alpha\right)\rig  ht\}_{\alpha\in\mathcal{A}} from where it follows from Zorn's Lemma that \left(\Omega,\overset{\Omega}{\leqslant}\right) must have a maximal element \left(E_\mathfrak{M},G_\mathfrak{M},f_\mathfrak{M}  \right). Now, suppose that E_\mathfrak{M}\ne A\text{ and }G_\mathfrak{M}\ne B. Then, choosing x\in A-E_{\mathfrak{M}}\text{ and }y\in B-G_{\mathfrak{M}} we may define \alpha:E_{\mathfrak{M}}\cup\{x\}\to G_{\mathfrak{M}}\cup\{y\} by \alpha\mid_{E_\mathfrak{M}}=f_{\mathfrak{M}} and x\overset{\alpha}{\mapsto}y and then of course \left(E_{\mathfrak{M}}\cup\{x\},G_{\mathfrak{M}}\c  up\{y\},\alpha\right) would contradict the maximality of \left(E_{\mathfrak{M}},G_{\mathfrak{M}},f_{\mathfr  ak{M}}\right).

    Thus, there exists a bijection from one of A or B into a subset of the other, and the conclusion follows. \blacksquare


    I don't think I said that very eloquently, but oh well.

    In essence all your doing is pairing off elements until you run out.
    Last edited by Drexel28; May 12th 2010 at 05:12 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Are equivalent metrics comparable on compact sets?
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: August 18th 2010, 07:23 AM
  2. Numerically integrating a non-linear DE
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: May 3rd 2010, 02:23 AM
  3. Replies: 8
    Last Post: April 14th 2010, 09:36 AM
  4. evaluating limits numerically.
    Posted in the Calculus Forum
    Replies: 5
    Last Post: May 15th 2009, 05:55 PM
  5. Limits...numerically
    Posted in the Calculus Forum
    Replies: 7
    Last Post: September 6th 2007, 03:49 PM

Search Tags


/mathhelpforum @mathhelpforum