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!

Proof about successor function

  1. Jan 25, 2016 #1
    1. The problem statement, all variables and given/known data
    Successor of a set x is defined as [itex] S(x)=x \cup {x} [/itex]
    Prove that if S(x)=S(y) then x=y
    Our teacher gives us a hint and says use the foundation axiom.
    3. The attempt at a solution

    if [itex] S(x)=S(y)=x \cup {x}=y \cup {y} [/itex]
    I feel like doing a proof by contradiction would work.
    assume for contradiction that [itex] x \neq y [/itex]
    if x does not equal y then [itex] (x \cup {x}) \neq (y \cup {y}) [/itex]
    which contradicts S(x)=S(y) therefore x=y.

     
  2. jcsd
  3. Jan 25, 2016 #2

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    You probably meant ##S(x)=x \cup \{x\}##
    Hint: can two sets be elements of each other? (I mean, is ##s \in t## and ##t \in s## possible?)
     
  4. Jan 25, 2016 #3
    its only possible when s=t.
     
  5. Jan 25, 2016 #4

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    I thought not even then (consequence of axiom of foundation).
    What can you then conclude from ##x \cup \{x\}=y \cup \{y\}##?
     
  6. Jan 25, 2016 #5
    So [itex] x \cup (x)= (x, (x)) [/itex] so x must equal y.
     
  7. Jan 26, 2016 #6

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Can you elaborate? I don't understand how you got that conclusion.
     
  8. Jan 26, 2016 #7
    If x is unioned with the set that contains x, the only elements are x so if x didn't equal y we would have different sets.
     
  9. Jan 26, 2016 #8

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Is that correct?
    Take ##x=\{1,2\}##. Then ##x \cup \{x\}=\{1,2,\{1,2\}\}##. I think you have the correct idea, but as this is an exercise in the foundations (no pun intended) of set theory, the argument should be a little more formal.
     
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: Proof about successor function
Loading...