Proof about successor function

[cragar]

Homework Statement

Successor of a set x is defined as $S(x)=x \cup {x}$
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 $S(x)=S(y)=x \cup {x}=y \cup {y}$
I feel like doing a proof by contradiction would work.
assume for contradiction that $x \neq y$
if x does not equal y then $(<b>x \cup {x}) \neq (y \cup {y}) </b>$
which contradicts S(x)=S(y) therefore x=y.

[/B]

 

[Samy_A]

Homework Statement

Successor of a set x is defined as $S(x)=x \cup {x}$
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 $S(x)=S(y)=x \cup {x}=y \cup {y}$
I feel like doing a proof by contradiction would work.
assume for contradiction that $x \neq y$
if x does not equal y then $(<b>x \cup {x}) \neq (y \cup {y}) </b>$
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 $x \cup (x)= (x, (x))$ so x must equal y.

 

[Samy_A]

So $x \cup (x)= (x, (x))$ 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.