# Discrete Math Proper Subsets

1. Jan 18, 2010

### Codexmac

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. Jan 18, 2010

### rasmhop

Re: Discrete Math "Proper Subsets"

List all non-proper subsets of X and then the rest must be proper.

3. Jan 18, 2010

### SW VandeCarr

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 $$2^0=1$$, and $$2^1=2$$ 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
4. Jan 19, 2010

### Landau

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|.

5. Jan 19, 2010

### SW VandeCarr

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?

6. Jan 19, 2010

### Landau

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.

7. Jan 19, 2010

### SW VandeCarr

Re: Discrete Math "Proper Subsets"

Yes. My misunderstanding. Sets cannot be members of themselves nor is the empty set a member of any set.

8. Jan 19, 2010

### Landau

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.
$$A=\{\emptyset\}$$ is a set containing exactly one member, namely the empty set.

9. Jan 20, 2010

### HallsofIvy

Re: Discrete Math "Proper Subsets"

What do you mean by "includes"? Every set has the empty set as a subset not as a member.

10. Jan 20, 2010

### SW VandeCarr

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?

11. Jan 20, 2010

### slider142

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.

12. Jan 21, 2010

### SW VandeCarr

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?

13. Jan 21, 2010

### Landau

Re: Discrete Math "Proper Subsets"

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

Also, $$A$$ is a subset of $$A$$.

14. Jan 21, 2010

### SW VandeCarr

Re: Discrete Math "Proper Subsets"

Thanks Landau. I'm assuming that the symbols $$\emptyset$$ and {} mean exactly the same thing. So if A={$$\emptyset$$} 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
15. Jan 21, 2010

### CRGreathouse

Re: Discrete Math "Proper Subsets"

Yes.

You can certainly write $\{\{\}\} = \{\{\}\} \cup \{\}$, 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.

16. Jan 23, 2010

### SW VandeCarr

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
17. Jan 23, 2010

### JSuarez

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:

$$A=B \Leftrightarrow \forall x\left(x \in A \leftrightarrow x\in B\right)$$

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
18. Jan 23, 2010

### CRGreathouse

Re: Discrete Math "Proper Subsets"

There's nothing wrong with {x, y} or {x, x}. Why would there be?

19. Jan 23, 2010

### SW VandeCarr

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
20. Jan 23, 2010

### JSuarez

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 $$\emptyset$$ is not necessarily a member of another set, but it's always a subset of every set). Formally, $$A$$ a being subset of $$B$$ is defined as:

$$A \subseteq B \Leftrightarrow \forall x \left(x \in A \rightarrow x \in B\right)$$

You should compare this expression with the one defining equality in my previous post. On the other hand, elementhood ($$\in$$) 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 $$\in$$).

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