Results 1 to 13 of 13
Like Tree6Thanks
  • 1 Post By emakarov
  • 1 Post By chiro
  • 1 Post By emakarov
  • 2 Post By Plato
  • 1 Post By Deveno

Math Help - Proving one-to-one correspondence by Cardinality.

  1. #1
    Junior Member EliteAndoy's Avatar
    Joined
    Feb 2013
    From
    United States
    Posts
    56
    Thanks
    3

    Proving one-to-one correspondence by Cardinality.

    Hello everyone. At last I've reached the final question of my homework set, but I was kinda stuck as to how I can approach it. The question is as follows: Show that if a set S has cardinality m, where m is a positive integer, then there is a one-to-one correspondence between S and the set {1, 2, ..., m}.

    For this one, I can see that the set {1, 2, ..., m} is just the set of all natural numbers, and thus has a cardinality of m. Since |S|=|{1, 2, ..., m}|, then they have to have
    one-to-one correspondence. That's my reasoning for it. Does it look okay?

    The second part of the question goes like this:Show that if S and T are two sets each with m elements, where m is a positive integer,then there is a one-to-one correspondence between S and T.

    For this one, shouldn't I just have to let {1, 2, ..., m} be T? Not really sure as to how to approach the problem as I am new to Discrete Math. Anyways, thanks everyone for your help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jul 2012
    From
    INDIA
    Posts
    829
    Thanks
    209

    Re: Proving one-to-one correspondence by Cardinality.

    Firstly the cardinal number is always positive so we need not specify it. secondly the question of correspondence to be one to one we need to know as to waht it is. it may be or may not be one to one. The cardinality of a set just indicates as to number of elements it has it mat not necessarily have natural numbers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member EliteAndoy's Avatar
    Joined
    Feb 2013
    From
    United States
    Posts
    56
    Thanks
    3

    Re: Proving one-to-one correspondence by Cardinality.

    Ya, I kinda figured that saying m is a positive integer contributes nothing to how the question develops, but I just copied it right out of the text because who knows, someone might be able to interpret it.

    Anyways, as for the first question, do we really have to know what the specific elements S have? I was just wondering because it is said in the theorem that if two sets have the same cardinality, then it is absolutely necessary that there is a one-to-one correspondence between the sets. Since S has cardinality which is given as |S|= m, and we both know that the cardinality of the set of all the natural numbers is is equal to its last digit, which in this case is m. Then it should be true that |S|=|{1, 2, ..., m}|, and thus, from the theorem itself, it should be absolutely necessary that there is a one-to-one correspondence between S and the set {1, 2, ..., m}. Sorry if I have to restate my proof, I was just really convinced about it. But what do you think? Is there a better proof than this?
    Last edited by EliteAndoy; September 1st 2013 at 11:04 PM. Reason: Typo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,651
    Thanks
    602

    Re: Proving one-to-one correspondence by Cardinality.

    Usually you need to specify a map.

    The simplest map from S to the {1,..,m} set is a_i = b_i where a_i belongs to S, b_i belongs to {1,..,m} and i is an index. If you can show that an isomorphism exists then you've shown 1-1 ness between the sets.

    So define a function taking a_i to b_i where f(a_i) = b_i and then show that an inverse exists where f^-1(b_i) = a_i for all appropriate i.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Proving one-to-one correspondence by Cardinality.

    Quote Originally Posted by EliteAndoy View Post
    Show that if a set S has cardinality m, where m is a positive integer, then there is a one-to-one correspondence between S and the set {1, 2, ..., m}.
    It is impossible to give an answer other than that this claim is obvious unless one knows how cardinality is defined in your course. It would also helpful to know the theorems that were proved, such as the "theorem that if two sets have the same cardinality, then it is absolutely necessary that there is a one-to-one correspondence between the sets".

    You used three phrases:

    (1) S has cardinality m
    (2) |S| = m
    (3) S has m elements.

    Do they all mean the same by definition?

    Quote Originally Posted by ibdutt View Post
    Firstly the cardinal number is always positive
    Really?
    Thanks from EliteAndoy
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member EliteAndoy's Avatar
    Joined
    Feb 2013
    From
    United States
    Posts
    56
    Thanks
    3

    Re: Proving one-to-one correspondence by Cardinality.

    Well, my professor didn't really gone over the class as to how the theorem is proved but he said that "if two sets have one-to-one correspondence between them, they should have the same cardinality" and he goes on to say that it it goes the other way around that "if two sets have the same cardinality then they must have a one-to-one correspondence." I just took his word for it as the basis of my proof. The thing that really throws me off is it is not really specified as to what composes set S. So here's how my phrases goes:

    (1)|S|=m
    (2) |{1, 2, ..., m}|=m
    (3)|S|=|{1, 2, ..., m}|
    (4) There is a one-to-one correspondence between them

    But that proof is not valid at all it "if two sets have the same cardinality then they must have a one-to-one correspondence" is not true. Kinda hanging by a thread here, so how would you guys prove this question? Thanks by the way.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,651
    Thanks
    602

    Re: Proving one-to-one correspondence by Cardinality.

    EliteAndoy: Did you try showing that a simple map and its inverse exists between the two sets?
    Thanks from EliteAndoy
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Proving one-to-one correspondence by Cardinality.

    Quote Originally Posted by EliteAndoy View Post
    Well, my professor didn't really gone over the class as to how the theorem is proved but he said that "if two sets have one-to-one correspondence between them, they should have the same cardinality" and he goes on to say that it it goes the other way around that "if two sets have the same cardinality then they must have a one-to-one correspondence." I just took his word for it as the basis of my proof.
    You still have not said how cardinality is defined in your course and whether the phrases "S has cardinality m", "|S| = m" and "S has m elements" all mean the same thing.

    If you forget all technical stuff and could learn just one thing, which will be helpful in all areas of life, from this and other math courses, it's this: it does not make sense to prove something until you know exactly what you are proving. This means you have to know definitions of every term involved in the claim to be proved.

    Quote Originally Posted by EliteAndoy View Post
    Show that if a set S has cardinality m, where m is a positive integer, then there is a one-to-one correspondence between S and the set {1, 2, ..., m}.
    I am saying this because the most reasonable (for me) definition for the phrase that occurs in the premise of your claim: "a set S has cardinality m", means by definition that there is a one-to-one correspondence between S and {1, 2, ..., m}. Then the claim is a tautology, like "empty set does not have any elements". If your definition is different, then there is no sense in attempting a proof until you find out that definition. For example, without the definition, how do you justify that "|{1, 2, ..., m}| = m"?

    Quote Originally Posted by EliteAndoy View Post
    Well, my professor didn't really gone over the class as to how the theorem is proved but he said that "if two sets have one-to-one correspondence between them, they should have the same cardinality" and he goes on to say that it it goes the other way around that "if two sets have the same cardinality then they must have a one-to-one correspondence."
    Often this is given not as a theorem, but as a definition.

    Quote Originally Posted by EliteAndoy View Post
    But that proof is not valid at all it "if two sets have the same cardinality then they must have a one-to-one correspondence" is not true.
    What makes you say it is not true, especially since you said above that you took your professor's word for it?
    Thanks from EliteAndoy
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member EliteAndoy's Avatar
    Joined
    Feb 2013
    From
    United States
    Posts
    56
    Thanks
    3

    Re: Proving one-to-one correspondence by Cardinality.

    Yeah I kinda of did what you told me earlier, and made a piece wise function f(x)=1 if f:x=a_1,f(x)=2x if f:x=a_2i+1, f(x)=2x+1 if f:x=a_2x. This basically says that 1 is mapped to a_1, the even numbers are mapped to the elements of S with odd numbered indexes, and the odd numbers are mapped to the elements of S with even numbered indexes. Thus, everything should be mapped and must have one-to-one correspondence. I'm still trying to show their inverses but eventually ill get there.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member EliteAndoy's Avatar
    Joined
    Feb 2013
    From
    United States
    Posts
    56
    Thanks
    3

    Re: Proving one-to-one correspondence by Cardinality.

    First off, thanks everyone for the replies, I really appreciate it. Anyways, if you were asking if "S has cardinality m", "|S| = m" and "S has m elements" all mean the same thing in our course, then yes it does. As for the claim, It's kinda obvious that |S|=|{1, 2, ..., m}|, but I can't really just say that it's obvious in this homework, can I? Plus I'm asked to show their one-to-one correspondence and so I'm just using those terms as a tool to resort to the "definition" of cardinality. I'm not saying that the definition is not true, I'm just saying that if it is untrue then my whole argument is also untrue.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1615
    Awards
    1

    Re: Proving one-to-one correspondence by Cardinality.

    Quote Originally Posted by emakarov View Post
    You still have not said how cardinality is defined in your course and whether the phrases "S has cardinality m", "|S| = m" and "S has m elements" all mean the same thing.
    Often this is given not as a theorem, but as a definition. What makes you say it is not true, especially since you said above that you took your professor's word for it?

    Quote Originally Posted by EliteAndoy View Post
    First off, thanks everyone for the replies, I really appreciate it. Anyways, if you were asking if "S has cardinality m", "|S| = m" and "S has m elements" all mean the same thing in our course, then yes it does. As for the claim, It's kinda obvious that |S|=|{1, 2, ..., m}|, but I can't really just say that it's obvious in this homework, can I? Plus I'm asked to show their one-to-one correspondence and so I'm just using those terms as a tool to resort to the "definition" of cardinality. I'm not saying that the definition is not true, I'm just saying that if it is untrue then my whole argument is also untrue.
    @EliteAndoy, I actually feel sorry for the situation you find your self in. I realize that you are in a discrete mathematics class, and it is well known that that can mean many different things. It seems to me that you may have an instructor problem or you have not understood the material on sets and mappings.

    Did you read carefully emakarov reply and request? You must have been given an exact definition for finite sets (that seems to be what you are posting about.) Usually there are two ways this is done. Both come down to this: If k\in\mathbb{Z}^+ define \mathcal{N}_k=\{1,2,\cdots,k\}.
    Now define a finite set: The set A is finite if A=\emptyset\text{ or }A \sim \mathcal{N}_j for some j\in\mathbb{Z}^+. That is A is finite if and only if it is empty in which case |A|=0 or there is a bijection A \leftrightarrow {\mathcal{N}_j} in which case |A|=j.

    So it seems to me that you have been asked to show what actually should have been the result of definitions.

    I will give two quotes.
    Paul Helmos writes
    We know quite a bit about cardinal numbers by now, but we still do not what they are.
    Speaking vaguely, we say that the cardinal number of a set is the property that a set has
    in common with all sets equivalent to it.
    Peter Zehna writes:
    Cardinal Axiom: For each set A, there is a primitive notation called the cardinal number of A, denoted by |A|, with the property that:
    |A|=|B|\text{ if and only if }A\sim B~.
    Thanks from emakarov and EliteAndoy
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member EliteAndoy's Avatar
    Joined
    Feb 2013
    From
    United States
    Posts
    56
    Thanks
    3

    Re: Proving one-to-one correspondence by Cardinality.

    Thanks everyone for all the help, especially to Plato. That definition of finite set really helped me understand how to approach the problem. Anyways all I have to do was make a distinct mapping to show that it was one-to-one. My prof even said that saying a_i maps to b_i is good enough as an answer. I guess I was just over thinking things . Anyways, thanks again!
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Proving one-to-one correspondence by Cardinality.

    If one has (and whether or not you CAN assume this, is to me, unknown):

    S = \{s_1,s_2,\dots,s_m\},

    then the mapping f:S \to \{1,2,\dots,m\} given by f(s_i) = i is a bijection, since we have the inverse map g:\{1,2,\dots,m\} \to S given by g(i) = s_i:

    f \circ g(i) = f(g(i)) = f(s_i) = i so that f \circ g = \mathbf{1}_{\{1,2,\dots,m\}} and

    g \circ f(s_i) = g(f(s_i)) = g(i) = s_i so that g \circ f = \mathbf{1}_S

    Alternatively, both sets are indexed by the same set, namely {1,2,...,m} (the second set is indexed by itself, a rather strange set of affairs, but as we see, quite possible).

    The "sticking point" here, is what your course DEFINES a "finite set (of k elements)" to BE. If your definition is as Plato suggests, there is no need to prove anything, the bijection comes "built-in" with the definition.
    Last edited by Deveno; September 5th 2013 at 04:36 PM.
    Thanks from EliteAndoy
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Equal Cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 12th 2011, 11:41 AM
  2. proving that [0,1] has the same cardinality as the power set of N
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: August 28th 2011, 12:02 AM
  3. Proving cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 29th 2011, 09:54 AM
  4. Proving Cardinality
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 30th 2008, 12:32 PM
  5. Proving a function is a one-to-one correspondence
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 27th 2007, 01:06 PM

Search Tags


/mathhelpforum @mathhelpforum