◀ ▲ ▶Branches / Set-theory / Proof: By Induction

Proof: By Induction

(related to Proposition: Set-Theoretical Meaning of Ordered Tuples)

We use a proof by complete induction.

Base case: $n=1$

• If $(x_1)=(y_1)$ then, by definition of $n$-tuple $\{x_1\}=\{y_1\}.$
• By definition of singleton and using the axiom of foundation as well as the axiom of extensionality, it followis $x_1=y_1.$

Induction step: $n\ge 1$

• By base case, $(x_1,\ldots,x_n)=(y_1,\ldots,y_n)$. For readability reasons, we write $x^{(n)}=y^{(n)}.$
• By the definition of $n$-tuple, we have $(x_1,\ldots,x_{n+1})=(x^{(n)},x_{n+1})$ and $(y_1,\ldots,y_{n+1})=(y^{(n)},y_{n+1}).$
• By the definition of ordered pairs we have $(x^{(n)},x_{n+1})=\{\{x^{(n)},x_{n+1}\},\{x_{n+1}\}\}$ and $(y^{(n)},y_{n+1})=\{\{y^{(n)},y_{n+1}\},\{y_{n+1}\}\}.$
• By the base case, the definition of singleton, the axiom of foundation and the axiom of extensionality, we have $x_{n+1}=y_{n+1}.$
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Ebbinghaus, H.-D.: "Einführung in die Mengenlehre", BI Wisschenschaftsverlag, 1994, 3th Edition