1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete Math Proper Subsets

  1. Jan 18, 2010 #1
    Discrete Math "Proper Subsets"

    Hey everyone, I am confused on part of this. Any input would be much appreciated!!

    X has ten members. How many members does ~P(X) have? (~P is the set of all subsets)
    How many proper subsets does X have?

    Well the number of members of ~P is 2^10 or 1024. This is the number of members in the set of subsets.
    What I'm confused about is how many proper subsets does X have?
     
  2. jcsd
  3. Jan 18, 2010 #2
    Re: Discrete Math "Proper Subsets"

    List all non-proper subsets of X and then the rest must be proper.
     
  4. Jan 18, 2010 #3
    Re: Discrete Math "Proper Subsets"

    That number could be 1023 or 1022 depending on whether you count the empty set. X is not a proper subset of itself, but I'm not sure the empty set would be counted as either as a non proper set or a proper set.

    EDIT: Since [tex]2^0=1[/tex], and [tex]2^1=2 [/tex] it seems the empty set must be counted as a non proper set, so the answer would seem to be 1022.
     
    Last edited: Jan 18, 2010
  5. Jan 19, 2010 #4

    Landau

    User Avatar
    Science Advisor

    Re: Discrete Math "Proper Subsets"

    A proper subset of X is just (by definition) a subset of X which is not equal to X. So the answer is 1023. The empty set is a subset of every set, and it is a proper subset of every set except of itself.

    If P(X) is the power set of X, and Q(X) the set of all proper subsets, then |Q(X)|=|P(X)-1|.
     
  6. Jan 19, 2010 #5
    Re: Discrete Math "Proper Subsets"

    OK, that makes sense, but in general usage, when a set is said to contain n members, should we understand that n includes the empty set or not?
     
  7. Jan 19, 2010 #6

    Landau

    User Avatar
    Science Advisor

    Re: Discrete Math "Proper Subsets"

    Not sure what you mean; if a set is said to contain n members, then it is what it is: a set containing n members. This means - assuming n is a natural number >0 - the set is in bijective correspondence with {1,...,n}. If n=0 ("the set is said to contain zero members"), then the set is empty.

    But earlier we talked about subsets of a given set, so I'm not sure what the connection is.
     
  8. Jan 19, 2010 #7
    Re: Discrete Math "Proper Subsets"

    Yes. My misunderstanding. Sets cannot be members of themselves nor is the empty set a member of any set.
     
  9. Jan 19, 2010 #8

    Landau

    User Avatar
    Science Advisor

    Re: Discrete Math "Proper Subsets"

    The first is true: a set cannot be a member of itself (that's why we have the Axiom of Regularity). The second is not true: the emty set can easily be a member of a set.
    [tex]A=\{\emptyset\}[/tex] is a set containing exactly one member, namely the empty set.
     
  10. Jan 20, 2010 #9

    HallsofIvy

    User Avatar
    Science Advisor

    Re: Discrete Math "Proper Subsets"

    What do you mean by "includes"? Every set has the empty set as a subset not as a member.
     
  11. Jan 20, 2010 #10
    Re: Discrete Math "Proper Subsets"

    Alright. In Landau's example above, set A has the empty set as a member. Is it true that the empty set is also a subset of A, and A is also a subset of itself?
     
  12. Jan 20, 2010 #11
    Re: Discrete Math "Proper Subsets"

    Both statements are true.
    Every set contains all of its elements, and every element of the empty set is contained in a given set.
     
  13. Jan 21, 2010 #12
    Re: Discrete Math "Proper Subsets"

    This doesn't answer my question. Landau gave the example of set A which contains the empty set as a member. Since the empty set is a subset of every set, is it also a subset of A?
     
  14. Jan 21, 2010 #13

    Landau

    User Avatar
    Science Advisor

    Re: Discrete Math "Proper Subsets"

    Yes it is. The empty set is both a member and a subset of [tex]A=\{\emptyset\}[/tex], i.e.:
    [tex]\emptyset\in A[/tex] and [tex]\emptyset\subset A[/tex].

    Also, [tex]A[/tex] is a subset of [tex]A[/tex].
     
  15. Jan 21, 2010 #14
    Re: Discrete Math "Proper Subsets"

    Thanks Landau. I'm assuming that the symbols [tex]\emptyset[/tex] and {} mean exactly the same thing. So if A={[tex]\emptyset[/tex]} then I can write A={{}}. The size of the power set of A equals two members so I can write A={{}, {{}}}. That is, the proper subset {} and the non-proper subset {{}}.

    I've seen the union of sets indicated by the + symbol in some texts and the expression above exhausts the set A, so can I write {{}}={}+{{}}? Somehow that doesn't look right to me.

    There is only one empty set, so to say that {} can be both a member of A and a subset of A, but not A itself sounds very counter-intuitive to me. It seems clear to me that A is empty.
     
    Last edited: Jan 21, 2010
  16. Jan 21, 2010 #15

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Re: Discrete Math "Proper Subsets"

    Yes.

    You can certainly write [itex]\{\{\}\} = \{\{\}\} \cup \{\}[/itex], but I don't think this says what you seem to think it does.

    There is only one empty set -- this can be proved. But I don't know why the fact that
    {} is a member of {{}}
    and
    {} is a subset of {{}}
    seems counterintuitive to you.
     
  17. Jan 23, 2010 #16
    Re: Discrete Math "Proper Subsets"

    OK. Consider the set X={x,y} such that x and y are variables. If x=y, then this would be an invalid set. What formal prohibition exists for such a set or interpretation of such a set?

    EDIT: I understand that this is a somewhat different question and that {} can be a subset of itself. However if x and y range over sets {},{0}.{1}.{2}....... then if x=y, we can have X={{},{}}. I believe this is a second order logic, but does ZFC specifically exclude elements as variables over sets?
     
    Last edited: Jan 23, 2010
  18. Jan 23, 2010 #17
    Re: Discrete Math "Proper Subsets"

    First, there is no need to say that x and y are "variables"; they are, simply, the elements of the set {x,y}.

    Second, there is nothing, formal or otherwise, that prevents x=y; the equality between sets is defined by extension, that is:

    [tex]A=B \Leftrightarrow \forall x\left(x \in A \leftrightarrow x\in B\right)[/tex]

    And this implies that, if x=y, {x,y} = {x,x} = {x}. It's not an invalid set, in any sense.
     
    Last edited: Jan 23, 2010
  19. Jan 23, 2010 #18

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Re: Discrete Math "Proper Subsets"

    There's nothing wrong with {x, y} or {x, x}. Why would there be?
     
  20. Jan 23, 2010 #19
    Re: Discrete Math "Proper Subsets"

    If {x,x} is a valid countable set with two members other than {} and the improper set, what justifies reducing it to {x}, a set with one member? It makes sense algebraically, but does it in set theory where the cardinality of finite sets is equal to the number of members.



    You're saying a set can contain identical iterations of a member with nothing that distinguishes them? There is only one empty set, so can I write A={{},{}.{},.......,{}}? What about infinite iterations? If not, is the empty set a special case? If so, why? If the whole series of subsets equals the improper subset of A, does it make sense do ask which iteration of {} is the proper subset?
     
    Last edited: Jan 23, 2010
  21. Jan 23, 2010 #20
    Re: Discrete Math "Proper Subsets"

    Now I understand where you went wrong. The empty set and the set itself (I take that it's what you mean by the "improper set") are not members of the set; they are subsets of it, which means that each of their elements is also an element of the set (for example, the [tex]\emptyset[/tex] is not necessarily a member of another set, but it's always a subset of every set). Formally, [tex]A[/tex] a being subset of [tex]B[/tex] is defined as:

    [tex]A \subseteq B \Leftrightarrow \forall x \left(x \in A \rightarrow x \in B\right)[/tex]

    You should compare this expression with the one defining equality in my previous post. On the other hand, elementhood ([tex]\in[/tex]) is primitive in set theory, it's not defined in terms of other relations (note that both equality and subsethood are defined in terms of [tex]\in[/tex]).

    But it's not: it's a set with just one member, x. This is what the definition of set equality tells us. The cardinality of {x,x} = {x} is one.
     
    Last edited: Jan 23, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook