1. Not finding help here? Sign up for a free 30min 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!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Cardinal arithmetic
  1. Same cardinality (Replies: 1)

  2. Bijection Cardinality (Replies: 2)

Loading...