1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Cardinal arithmetic

  1. Dec 20, 2014 #1
    1. The problem statement, all variables and given/known data
    Let X be a finite set and let x be an object which is not an element of X. Then X U {x} is finite and #(X U {x}) = #(X) + 1



    3. The attempt at a solution

    Let X be a finite set such that X has cardinality n, denoted by #X.
    Suppose that ## x \notin X##, then the set X U {x} has cardinality n + 1, that is #X +1, as required.

    If i must be honest, i don't think i have proven anything :(
     
    Last edited by a moderator: Dec 20, 2014
  2. jcsd
  3. Dec 20, 2014 #2

    Mark44

    Staff: Mentor

    Do you have some theorem that shows how to calculate the cardinality of a finite set?
     
  4. Dec 20, 2014 #3
    A set is finite iff it has cardinality n for some natural number n; otherwise, the set if called infintie. If X is a finite set, we use #(X) to denote the cardinality of X.


    That is what your asking for, i think?
     
  5. Dec 20, 2014 #4

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Then, what is your definition for a set to have cardinality n?
     
  6. Dec 20, 2014 #5
    Oh there is another one;

    Let n be a natural number. A set X is said to have cardinality n, iff it has equal cardinality with $$ \{i \in N : 1 \le i \le n\} $$. We also say that X has n elements iff it has cardinality n.
     
  7. Dec 20, 2014 #6

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    And how do you determine if a set X has equal cardinality with ##\{ i \in N: 1\le i \le n\}##?
     
  8. Dec 21, 2014 #7
    Let X be a finite set with cardinality n, denoted by #X, then there exists a bijection;
    $$f:X \rightarrow \{ i \in N : 1 \le i \le n\} $$. Since x is not an element of X then $$X \cup \{x\} $$ is the set of elements that contains X or {x}, then there must exist a bijection $$ g:X \cup \{x\} \rightarrow \{ i \in N : 1 \le i \le n++\} $$
    By the definition of cardinality of finite sets $$X \cup \{x\} $$ has cardinality n++, that is n+1, denoted by #(X U {x}) .

    That slightly better, or have i jumped th gun again?
     
    Last edited: Dec 21, 2014
  9. Dec 21, 2014 #8

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member


    That is what you are trying to prove. You have a bijection from X to the first n integers. Now you need to demonstrate a bijection ##g##.
     
  10. Dec 21, 2014 #9
    i'm really sorry, i'm gonna need a little help in that case, i'm stuck
     
  11. Dec 21, 2014 #10

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You just need to think about it some more. You have X matched up with 1,2,...n. Now you have an extra x and need to demonstrate a matchup with 1,2,...n+1. There is a pretty obvious way. You just have to show it works.
     
  12. Dec 22, 2014 #11
    I cant think of anything more basic other than actually letting $$ X = \{x_1, x_2....x_n\}$$ then showing that $$ X \cup {x} = \{x_1, x_2....x_{n+1}\} $$. since x is not an element of X. Other than that LCKurtz...
     
  13. Dec 22, 2014 #12

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You need to use the definitions and proper notation. Look at post #8. To save a little typing, let's call$$
    S_n = \{i \in N: 1\le i \le n\}$$In post #8 you have given that ##X## has cardinality ##n## which means there exists a bijection ##f:X\to S_n##. You are trying to show that ##X\cup \{x\}## has cardinality ##n+1##. So you have to find a bijection ##g## ....(finish that sentence).

    Once you have that sentence finished, show how to define a ##g## using what you are given about ##f##.
     
  14. Dec 22, 2014 #13

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    There's not a lot wrong with that unless you are trying to be very rigorous and use the bijection definition explicitly. What you have done there is define a bijection implicitly by labelling the elements.

    If you were doing Linear Algebra, say, that's exactly how you'd extend a set of vectors.

    That said, it's definitely worth nailing the formal bijection method, following the advice you've been given.
     
  15. Dec 22, 2014 #14
    right, here is some work on a function g;


    I will now define a function g, such that
    $$g: X\cup\{x\} \rightarrow \{ i \in N:1 \le i \le n+1\} $$
    by the following rule
    for any $$ y \in X \cup \{x\}, $$
    we define $$ g(y):=f(y) for y \in X $$ and $$ g(y):=f(y) + 1 when y = x $$


    since f is a bijection and g(y):=f(y) + 1 only when y = x, g is also a bijection.
    it follows that.... and the conclusion follows.
    The last part sounds fishy, but surely since f is one-one and onto, the pairwise is essentially adding an element to give the new set and a mapping of that element has been defined.
     
  16. Dec 22, 2014 #15

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The problem you have is that f is not defined on x. You're okay to define g(y) = f(y) for all other y. Can you see a simple way to define g(x)?

    Also, you might think about proving g is a bijection. It's not hard, but you must show formally things that appear obvious.
     
  17. Dec 22, 2014 #16
    g(y): = g(x) when y = x?

    To prove that g is a bijection , i just have to show that X U {x} has equal cardinality with the set $$ \{i \in N : 1 \le i \le n +1 \} $$ right?
     
  18. Dec 22, 2014 #17

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    On this first point, you need to specify g(x). Or g(y) when y = x if you prefer.

    On the second point, you have to show g is a bijection. Showing that is what proves that X union {x} has cardinality n + 1.

    In general, to show a function g is a bijection, you have to show two things: that g is 1-1 and onto. Can you write down what this means formally?
     
  19. Dec 22, 2014 #18
    g(y) = n+1 ? because thats the element its mapped to when y = x? i know this is true, surely?

    ONE- ONE; so each element in the domain of g is mapped to a unique element in the co-domain. so y = x iff f(y) = f(x).
    ONTO; the image set of g is equal to the co-domain.

    could i use the fact that f is a bijection to prove this though? since the only difference is one element?
     
  20. Dec 22, 2014 #19

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes! I would have simply said g(x) = n + 1.

    Yes, it's best to formalise this further for this situation:

    g is 1-1 means g(y_1) = g(y_2) => y_1 = y_2

    g is onto means ##\forall i \ (where \ 1 \le i \le n + 1) \ \exists \ y \in \ X \cup \lbrace x \rbrace \ s.t. \ g(y) = i##

    Can you show that these are both true for the g you've defined?
     
  21. Dec 22, 2014 #20
    right for the onto proof, i have said that;

    given any $$ i \in \{i \in N : 1 \le i \le n + 1 \} $$
    there exists $$ y \in X \cup \{x\} $$ such that $$ g(y) = i $$ it follows that g is onto, this quite simply has to be true!

    for the one to one proof;
    suppose that $$ g(y_{1}) = g(y_{2})$$
    then $$ i_1 = i_2 $$ as required.
    This proves that g is injective.
     
  22. Dec 22, 2014 #21

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No. All you have done is state what you have to prove. The "there exists" is where the proof goes. If I pick a natural number ##m\in S_{n+1}## you have to show me what element in ##X \cup \{x\}## is mapped onto it.

    Same objection. You have just restated the problem.
     
  23. Dec 22, 2014 #22
    I'm sorry, a little more detail please?
    so is it the wording thats the problem in the first issue? so if i was to say 'we have' instead of 'there exists', secondly that was a typo, i meant to type $$ y_1 = y_2 $$ instead of $$ i_1 = i_2 $$.

    surely the last one proves it that it is injective? if it doesn't please could i have a little more detail.
     
  24. Dec 22, 2014 #23

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It is the claim that "there exists". Just stating it doesn't make it so. You have to prove it. I'm thinking of a natural number ##m\in S_{n+1}##. Show me, with equations, what ##y\in X\cup\{x\}## maps onto it. You have the bijection ##f## and the definition of ##g## to work with.
     
  25. Dec 22, 2014 #24
    g(y) = f(y) for all y in X,
    g(y) = n + 1 when x = y.

    ok, now to prove the 'there exists' part;
    let $$ m \in S_{n+1} $$ we must show that there exists $$ y \in X \cup \{x\} such that g(y) = m $$, now $$ g(y) = f(y) = m $$ for all $$ y \in X. $$and $$ g(y) = n+ 1 = m for y = x $$

    so $$ g(y) = m $$ as required.

    Is that any better? with my typo corrected on the injective proof, is that ok?
    also how to do i type inline math on PF? this is a pain in the butt
     
  26. Dec 22, 2014 #25

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I know that you "see" why ##g## is onto. But the trick is to learn how to write a proper argument. I will intersperse comments.

    Don't say "g(y) = n + 1 when x = y", just say g(x) = n+1

    Good. That's exactly right.

    No. That isn't what you mean. ##m## is a fixed number that I'm thinking of. You don't know whether it is ##n+1## or some smaller number. You might have to think about two cases because of that. But even if ##m\in S_n##, it certainly isn't true that for all ##y\in X## that ##f(y) = m##. What is true is that since ##f## is a bijection between ##X## and ##S_n## there is some ##y\in X## such that ##f(y)=m##. Do you see the difference? And this works only for the case where ##m\in S_n##.

    Here you should say that if ##m=n+1## then ##g(x) = m## by the definition of ##g##.



    With the above comments, almost correct. If ##m\in S_n## you have a ##y\in X## such that ##f(y) = m##. You need ##g(y) = m##. It's easy, but you have to explain how you have that.

    Use double # signs instead of double $ signs for inline equations.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted