Partitioning Infinite Sets: Equivalence Relations and Set Partitions

[Bipolarity]

A theorem on equivalence relation states that for any set S, the set of equivalence classes of S under an equivalence relation R constitutes a partition of a set. Moreover, given any partition of a set, one can define an equivalence relation on the set.

What allows you to "create" a partition of a set, say the set of its equivalence classes? If the set is finite, then it is intuitively easy to see that a partition can be created since the elements of the set must eventually be exhausted. But if the set is infinite, say Z, then what guarantees we can create a partition, of say, cosets of some subgroup of Z.

 

[lavinia]

A theorem on equivalence relation states that for any set S, the set of equivalence classes of S under an equivalence relation R constitutes a partition of a set. Moreover, given any partition of a set, one can define an equivalence relation on the set.

What allows you to "create" a partition of a set, say the set of its equivalence classes? If the set is finite, then it is intuitively easy to see that a partition can be created since the elements of the set must eventually be exhausted. But if the set is infinite, say Z, then what guarantees we can create a partition, of say, cosets of some subgroup of Z.

Not sure what you mean by 'create', so here is an example for you.

Say that two integers are equivalent if their difference is an even number. This defines two equivalence classes, the odd and the even integers. Would you say that these two equivalence classes were "created"?

 

[Fredrik]

What allows you to "create" a partition of a set, say the set of its equivalence classes? If the set is finite, then it is intuitively easy to see that a partition can be created since the elements of the set must eventually be exhausted. But if the set is infinite, say Z, then what guarantees we can create a partition, of say, cosets of some subgroup of Z.

The axiom schema of separation. It's an axiom schema of ZFC set theory. It says (roughly) that for each set S and each property P, there's a set $\{x\in S|P(x)\}$ whose elements are precisely those x that are elements of S and have property P.

The string P(x) that we interpret as "x has property P" is a statement about x, or to be more precise, about the set that the symbol "x" represents. That statement may be true for some values of x and false for other values of x. The elements of $\{x\in S|P(x)\}$ are those elements of S for which P(x) is a true statement. P(x) can for example be the statement that x is an equivalence class of elements of S.

 

[WWGD]

The axiom schema of separation. It's an axiom schema of ZFC set theory. It says (roughly) that for each set S and each property P, there's a set $\{x\in S|P(x)\}$ whose elements are precisely those x that are elements of S and have property P.

The string P(x) that we interpret as "x has property P" is a statement about x, or to be more precise, about the set that the symbol "x" represents. That statement may be true for some values of x and false for other values of x. The elements of $\{x\in S|P(x)\}$ are those elements of S for which P(x) is a true statement. P(x) can for example be the statement that x is an equivalence class of elements of S.

But didn't Russell show that this did not always create a set with his "Barber that shaves others only if he shaves himself"?

 

[Fredrik]

But didn't Russell show that this did not always create a set with his "Barber that shaves others only if he shaves himself"?

Russell's paradox shows up if we allow the set $\{x|P(x)\}$ for all properties P. (This is called the principle of comprehension). If we do, then $\{x|x\notin x\}$ is a set. Let's call it $R$. Now we can show that $R\in R\Leftrightarrow R\notin R$.

The axiom schema I mentioned doesn't have this problem. Define $R=\{x\in S|x\notin x\}$. Now $R\notin R$ doesn't imply that $R\in R$, because it's possible that $R\notin S$.

 

[micromass]

Russell's paradox shows up if we allow the set $\{x|P(x)\}$ for all properties P. (This is called the principle of comprehension). If we do, then $\{x|x\notin x\}$ is a set. Let's call it $R$. Now we can show that $R\in R\Leftrightarrow R\notin R$.

The axiom schema I mentioned doesn't have this problem. Define $R=\{x\in S|x\notin x\}$. Now $R\notin R$ doesn't imply that $R\in R$, because it's possible that $R\notin S$.

Right, the Russell paradox does not immediately show up, so ZFC has no known problems. However, we can never make sure there aren't any problems. Maybe there's some contradiction lurking inside ZFC anyway that we don't yet know about. In either case, we can never prove that no contradictions will ever show up (Godel's theorem). So whether set theory like ZFC is a good system to work with is an open question (and one that will likely remain open forever). For now it suffices though.

 

[WWGD]

Ah, so we use type theory to disallow certain statements so that $R \notelement of R$?

 

[WWGD]

Russell's paradox shows up if we allow the set $\{x|P(x)\}$ for all properties P. (This is called the principle of comprehension). If we do, then $\{x|x\notin x\}$ is a set. Let's call it $R$. Now we can show that $R\in R\Leftrightarrow R\notin R$.

The axiom schema I mentioned doesn't have this problem. Define $R=\{x\in S|x\notin x\}$. Now $R\notin R$ doesn't imply that $R\in R$, because it's possible that $R\notin S$.

So do we use type theory so that $R\in R\Leftrightarrow R\notin R$ ?.

 

[micromass]

Ah, so we use type theory to disallow certain statements so that $R \notelement of R$?

Not at all. That is not the approach of ZFC. Statements like these are perfectly allowed. In other axiom systems such as type theory of NF, we do not allow such statements. But in ZFC, this is perfectly fine.