◀ ▲ ▶Branches / Set-theory / Solution

Solution

(related to Problem: To Construct a Partition of a Given Set)

Creating Partitions Using Fibers of Surjective Functions

• Let $f:X\to Y$ be a given surjective function.
• By definition of surjective functions, every element $y\in Y$ has an $x\in X$ with $f(x)=y.$
• In general, there can be many such elements $x\in X,$ with $f(x)=y,$ called the fiber $f^{-1}(y):=\{x\in X\mid f(x)=y,\;y\in Y\}.$
• Since $f$ is a function, for any two $y_1,y_2\in Y,$ the fibers $f^{-1}(y_1)$ and $f^{-1}(y_2)$ are disjoint in $X.$
• Therefore, the all fibers $f^{-1}(y),$ $y\in Y$ arbitrary, are mutually disjoint in $X.$
• This means that the set of all fibers $$\{f^{-1}(y)\mid y\in Y\}$$ is a set partition of $X.$

Creating Partitions Using Equivalence Relations

• Let $R\subseteq X\times X$ be a given equivalence relation.
• Then, for every element $x\in X,$ we have an equivalence class $[x]:=\{z\in X, zRx\}.$
• Now, any two equivalence classes $[x]\neq [y]$ are disjoint in $X,$ because otherwise,
  • for an element $z\in [x]\cap [y]$ we would have $zRx$ and $zRy.$
  • Because $R$ is an equivalence relation, it is transitive and symmetric.
  • Therefore, from $zRx$ and $zRy$ it would follow that $xRy$, in contradiction to $[x]\neq [y].$
• Therefore, all equvalence classes $[x]$, $x\in X$ are mutually disjoint.
• This means that the quotient set of all equivalence classes $$\{[x]\mid x\in X\}$$ is a set partition of $X.$

Differences between the two possibilities

A partition built by a given equivalence relation can itself be reversely used to define this equivalence relation, i.e. if we are given partition, then its elements can be re-interpreted as equivalence classes of an equivalence relation. In other words, partitions and equivalence relations are mathematical concepts, which are very closely related to each other.

This one-to-one correspondence between partitions and equivalence relations cannot be observed for partitions built by means of fibers of a given surjective function. For a given partition, it is usually not possible to find an appropriate surjective function. The reason for this is simple. A given partition of a set $X$ is independent of another set $Y$, which we need to define a function between $X$ and $Y.$

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

Github:

References

Bibliography

1. Flachsmeyer, Jürgen: "Kombinatorik", VEB Deutscher Verlag der Wissenschaften, 1972, 3rd Edition