Proof about successor function

  • Thread starter Thread starter cragar
  • Start date Start date
  • Tags Tags
    Function Proof
Click For Summary

Homework Help Overview

The problem involves proving that if the successor of two sets, defined as S(x) = x ∪ {x}, are equal, then the sets themselves must be equal. The context is rooted in set theory, particularly focusing on the properties of the successor function and the foundation axiom.

Discussion Character

  • Exploratory, Conceptual clarification, Assumption checking

Approaches and Questions Raised

  • Participants discuss the validity of a proof by contradiction, questioning the implications of assuming x ≠ y. There is exploration of the relationship between sets and their successors, with some participants suggesting that if the successors are equal, the original sets must also be equal. Others raise questions about the nature of sets containing themselves and the implications of the foundation axiom.

Discussion Status

The discussion is ongoing, with various interpretations and approaches being explored. Some participants have offered insights into the implications of the foundation axiom and the nature of set equality, while others seek clarification on specific reasoning steps.

Contextual Notes

Participants are navigating the constraints of formal set theory and the axioms that govern it, particularly the foundation axiom, which influences their reasoning about sets containing themselves.

cragar
Messages
2,546
Reaction score
3

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]
 
Physics news on Phys.org
cragar said:

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?)
 
its only possible when s=t.
 
cragar said:
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\}##?
 
So x \cup (x)= (x, (x)) so x must equal y.
 
cragar said:
So x \cup (x)= (x, (x)) so x must equal y.
Can you elaborate? I don't understand how you got that conclusion.
 
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.
 
cragar said:
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.
 

Similar threads

  • · Replies 9 ·
Replies
9
Views
2K
Replies
1
Views
1K
Replies
3
Views
2K
Replies
20
Views
5K
Replies
8
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
2
Views
1K
  • · Replies 2 ·
Replies
2
Views
1K
  • · Replies 2 ·
Replies
2
Views
2K