Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Partitioning an infinite set

  1. Jan 25, 2015 #1
    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.
     
  2. jcsd
  3. Jan 25, 2015 #2

    lavinia

    User Avatar
    Science Advisor
    Gold Member

    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: Jan 25, 2015
  4. Jan 25, 2015 #3

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  5. Jan 26, 2015 #4

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    But didn't Russell show that this did not always create a set with his "Barber that shaves others only if he shaves himself"?
     
  6. Jan 26, 2015 #5

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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##.
     
  7. Jan 26, 2015 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
  8. Jan 26, 2015 #7

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Ah, so we use type theory to disallow certain statements so that ## R \notelement of R ##?
     
  9. Jan 26, 2015 #8

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    So do we use type theory so that ##R\in R\Leftrightarrow R\notin R## ?.
     
  10. Jan 26, 2015 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Partitioning an infinite set
  1. Infinite sets? (Replies: 2)

Loading...