Set Equivalence is Equivalence Relation
Jump to navigation
Jump to search
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$
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$