1. Jan 25, 2016

### cragar

1. The problem statement, all variables and given/known data
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.
3. 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 $(x \cup {x}) \neq (y \cup {y})$

2. Jan 25, 2016

### Samy_A

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

3. Jan 25, 2016

### cragar

its only possible when s=t.

4. Jan 25, 2016

### Samy_A

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

5. Jan 25, 2016

### cragar

So $x \cup (x)= (x, (x))$ so x must equal y.

6. Jan 26, 2016

### Samy_A

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

7. Jan 26, 2016

### 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.

8. Jan 26, 2016

### Samy_A

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.