Proof about successor function

[cragar]

Homework Statement

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.

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.

[/B]

 

[Samy_A]

Homework Statement

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.

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.
[/B]

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?)

 

[cragar]

its only possible when s=t.

 

[Samy_A]

its only possible when s=t.

I thought not even then (consequence of axiom of foundation).
What can you then conclude from ##x \cup \{x\}=y \cup \{y\}##?

 

[cragar]

So [itex] x \cup (x)= (x, (x)) [/itex] so x must equal y.

 

[Samy_A]

So [itex] x \cup (x)= (x, (x)) [/itex] so x must equal y.

Can you elaborate? I don't understand how you got that conclusion.

 

[cragar]

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.

 

[Samy_A]

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.

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.