Set Equivalence is Equivalence Relation
As pointed out in discussion, this does not work, as the set of all sets is not a set, it's a class, and an equivalence relation is defined only between sets. Suggested we amend this to apply only to finite sets, as this is how it is presented in, for example the (admittedly lightweight) Chartrand work. The more technically advanced infinite / class-theoretical version can be considered as a separate case. Inspection of the various sources used below will need to be done.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues.
To discuss this proof in more detail, feel free to use the talk page.
If you are able to fix this page, then when you have done so you can remove this instance of {{Questionable}} from the code.
If you would welcome a second opinion as to whether your correction is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
Theorem
Set equivalence is an equivalence relation.
Proof
For two sets to be equivalent, there needs to exist a bijection between them.
In the following, let $\phi$, $\phi_1$, $\phi_2$ etc. be understood to be bijections.
Reflexive
From Identity Mapping is Bijection, the identity mapping $I_S: S \to S$ is the required bijection.
Thus there exists a bijection from $S$ to itself and $S$ is therefore equivalent to itself.
Therefore set equivalence is reflexive.
$\Box$
Symmetric
| \(\ds \) | \(\) | \(\ds S \sim T\) | ||||||||||||
| \(\ds \) | \(\leadsto\) | \(\ds \exists \phi: S \to T\) | Definition of Set Equivalence | |||||||||||
| \(\ds \) | \(\leadsto\) | \(\ds \exists \phi^{-1}: T \to S\) | Bijection iff Inverse is Bijection | |||||||||||
| \(\ds \) | \(\leadsto\) | \(\ds T \sim S\) | Definition of Set Equivalence: $\phi^{-1}$ is also a bijection |
Therefore set equivalence is symmetric.
$\Box$
Transitive
| \(\ds \) | \(\) | \(\ds S_1 \sim S_2 \land S_2 \sim S_3\) | ||||||||||||
| \(\ds \) | \(\leadsto\) | \(\ds \exists \phi_1: S_1 \to S_2 \land \exists \phi_2: S_2 \to S_3\) | Definition of Set Equivalence | |||||||||||
| \(\ds \) | \(\leadsto\) | \(\ds \exists \phi_2 \circ \phi_1: S_1 \to S_3\) | Composite of Bijections is Bijection: $\phi_2 \circ \phi_1$ is a bijection | |||||||||||
| \(\ds \) | \(\leadsto\) | \(\ds S_1 \sim S_3\) | Definition of Set Equivalence |
Therefore set equivalence is transitive.
$\blacksquare$
See talk
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.
To discuss it in more detail, feel free to use the talk page.
If you are able to do this, then when you have done so you can remove this instance of {{Expand}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
Also see
The definition of a cardinal of a set as the equivalence class of that set under set equivalence.
Sources
- 1960: Paul R. Halmos: Naive Set Theory ... (previous) ... (next): $\S 13$: Arithmetic
- 1964: Steven A. Gaal: Point Set Topology ... (previous) ... (next): Introduction to Set Theory: $2$. Set Theoretical Equivalence and Denumerability
- 1965: J.A. Green: Sets and Groups ... (previous) ... (next): $\S 3.7$. Similar sets
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): $\S 17$: Theorem $17.1$
- 1968: A.N. Kolmogorov and S.V. Fomin: Introductory Real Analysis ... (previous) ... (next): $\S 2.3$: Equivalence of sets (footnote $6$)
- 1971: Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory: $\S 10.2$
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Appendix $\text{A}.4$: Functions: Problem Set $\text{A}.4$: $26$
- 1999: András Hajnal and Peter Hamburger: Set Theory ... (previous) ... (next): $2$. Definition of Equivalence. The Concept of Cardinality. The Axiom of Choice: Theorem $2.1$