Proper Subsets in Discrete Math

[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?

 

[rasmhop]

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

 

[SW VandeCarr]

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

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.

 

[Landau]

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

 

[SW VandeCarr]

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

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?

 

[Landau]

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.

 

[SW VandeCarr]

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.

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

 

[Landau]

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.

 

[HallsofIvy]

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?

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

 

[SW VandeCarr]

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.

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

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?

 

[slider142]

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?

Both statements are true.
Every set contains all of its elements, and every element of the empty set is contained in a given set.

 

[SW VandeCarr]

Both statements are true.
Every set contains all of its elements, and every element of the empty set is contained in a given set.

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?

 

[Landau]

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

 

[SW VandeCarr]

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

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.

 

[CRGreathouse]

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

Yes.

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.

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

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.

 

[SW VandeCarr]

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.

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?

 

[JSuarez]

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?

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.

 

[CRGreathouse]

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?

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

 

[SW VandeCarr]

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.

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.

GR Greathouse;2545299]There's nothing wrong with {x, y} or {x, x}. Why would there be?

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?

 

[JSuarez]

If {x,x} is a valid countable set with two members other than {} and the improper set

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

If {x,x} is a valid countable set with two members

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.

 

[CRGreathouse]

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 seem confused. If x ≠ {} ≠ y, then {x, y} has one or two members, neither of which is {}. Assuming we're working in ZF, {x, y} is not a member of {x, y}.

And I certainly never claimed that {x, y} has two members. It may have one or two, depending on whether x = y or x ≠ y.

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?

You can write {{}} = {{}, {}} = {{}, {}, {}, {}} if you like, sure. It's correct.

This has nothing to do with the fact that the set is empty. For any set S, {S} = {S, S} = {S, S, S}, etc.

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?

It is not the case (in ZF) that {A} = {A, A} = A. The first equality holds, but the second fails. In particular, it is never true (in ZF) that A = {A, ...} for any value of "...".

 

[CRGreathouse]

JSuarez is of course correct in his (?) explanation, but I wanted to nitpick slightly:

This is what the definition of set equality tells us.

I think it's standard to call that the Axiom of Extensionality rather than the definition of =.

 

[JSuarez]

(Reply to CRGreathouse)

Yes, of course. But the function of the Axiom of Extensionality is to define equality between two elements in the universe of sets, in terms of the membership relation (which is the only primitive relation). There are other possibilities; you could, for example, define set equality intensionaly, by stating that two sets are equal if they have exactly the same properties (not necessarily the same elements), but you can only do that in second-order logic.

 

[CRGreathouse]

Agreed on all counts.