Partitioning an infinite set

  • Thread starter Bipolarity
  • Start date
  • #1
775
1

Main Question or Discussion Point

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,165
575
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,851
406
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
2019 Award
5,180
2,483
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,851
406
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
22,097
3,279
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
2019 Award
5,180
2,483
Ah, so we use type theory to disallow certain statements so that ## R \notelement of R ##?
 
  • #8
WWGD
Science Advisor
Gold Member
2019 Award
5,180
2,483
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
22,097
3,279
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

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
2
Replies
31
Views
26K
  • Last Post
Replies
2
Views
3K
Replies
1
Views
2K
  • Last Post
Replies
22
Views
681
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
11
Views
3K
Replies
2
Views
2K
Replies
2
Views
2K
Top