Partitioning an infinite set

  • Thread starter Bipolarity
  • Start date
  • #1
775
2
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.
 

Answers and Replies

  • #2
lavinia
Science Advisor
Gold Member
3,277
665
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"?
 
Last edited:
  • #3
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,872
419
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.
 
  • #4
WWGD
Science Advisor
Gold Member
5,909
6,970
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"?
 
  • #5
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,872
419
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##.
 
  • #6
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,301
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.
 
  • #7
WWGD
Science Advisor
Gold Member
5,909
6,970
Ah, so we use type theory to disallow certain statements so that ## R \notelement of R ##?
 
  • #8
WWGD
Science Advisor
Gold Member
5,909
6,970
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## ?.
 
  • #9
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,301
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.
 

Related Threads on Partitioning an infinite set

Replies
25
Views
13K
Replies
7
Views
3K
Replies
2
Views
1K
  • Last Post
Replies
6
Views
3K
Replies
3
Views
6K
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
1
Views
3K
Replies
19
Views
2K
Top