Elementary Set Theory Problem Checking

[Oxymoron]

Im just going through a practice exam and I was wondering If I could get someone to check my results.

Q1 Let $X = \{1,2,4,5\}$, where elements of $X$ are the sets $1 = \{0\}$, $2 = 1 \cup \{1\}$, etc. Evaluate each of the following:

a) $$X \backslash \{2\} = \{1,2,4,5\} \backslash \{2\} = \{1,4,5\}$$

b) $$\{n \in X\,:\,n = 4\} = \{4\}$$

c) $$\bigcap X = \bigcap \{1,2,4,5\} = 1 \cap 2 \cap 4 \cap 5 = \{0\}$$

d) $$\bigcap \{X\} = X$$

e) $$\bigcap\bigcap X = \bigcap \left( \bigcap \{1,2,4,5\}\right) = \bigcap (1 \cap 2 \cap 4 \cap 5) = \bigcap (\{\emptyset\}) = \emptyset$$

f) $$\bigcup X = \bigcup \{1,2,4,5\} = 1 \cup 2 \cup 4 \cup 5 = 4$$

g) $$\{n \in X\,:\, n \neq n\} = \{\emptyset\}$$

h) $$X \cup \{0,1\} = \{1,2,4,5\} \cup \{0,1\} = X \cup \{0\}$$

 

[matt grime]

c,d,e and f are all wrong as written. I suspect the problem is primarily with what should go on the left hand side of the identity.

In c you have calculated

$$\cap_{x \in X}\ x$$

but that is not what the left hand side, as written, states. The left hand side asks you to intersect X with itself some number of times; you have omitted to put an index in so we don't know what it really means. Any non-empty index set will return X.

g is wrong too. The thing on the right hand side should be a set of elements in X. The empty set is not an element of X so it can't be right. The empty set is not the same as a set containing the empty set.

In h what is wrong with writing {0,1,2,4,5}?

 

[Oxymoron]

If I have a set, say $\{a,b,c\}$ then the intersection is

$$\bigcap \{a,b,c\} = a \cap b \cap c$$

is it not? The intersection essentially removes the braces. So (c) is

$$\bigcap X = \bigcap \{1,2,4,5\} = 1 \cap 2 \cap 4 \cap 5$$

do you agree with this much? But then 1,2,4, and 5 are all sets themselves. And the only common element among them is {0}.

$$1 = \{0\}$$
$$2 = 1 \cup \{1\} = \{0\} \cup \{1\} = \{0,1\}$$
$$3 = 2 \cup \{2\} = \{0,1\} \cup \{2\} = \{0,1,2\}$$
$$4 = 3 \cup \{3\} = \{0,1,2\} \cup \{3\} = \{0,1,2,3\}$$
$$5 = 4 \cup \{4\} = \{0,1,2,3\} \cup \{4\} = \{0,1,2,3,4\}$$

Therefore

$$1 \cap 2 \cap 4 \cap 5 = \{0,1\} \cap \{0,1,2\} \cap \{0,1,2,3\} \cap \{0,1,2,3,4\} = \{0\} =1$$

 

[matt grime]

Absolutely not. In fact I couldn't disagree more. But if that is the convention your book states to use then so be it...

 

[Oxymoron]

For (c), the definition of intersection (from wikipedia) reads

Let X be a non-empty set and suppose that [itex]A \in X[/tex]. Then the intersection of X is

$$\bigcap X = \{x \in A \,:\, x \in B \,\forall\, B \in X\}$$

So if $X = \{1,2,4,5\}$ then

$$\bigcap X = \{x \in 1 \,:\, x \in B \,\forall\, B \in X\}$$

$$= \{x \in 1 \,:\, (x \in 2) \wedge (x \in 4) \wedge (x \in 5)\}$$

$$= \{0\} =1$$

since, as I wrote above, the only element in 1 that is also in 2, 4, and 5 is 0.

Then for (d) we have

$$\bigcap \{X\} = \{x \in X \,:\, x \in B \,\forall\, B \in X\}$$

$$= \{x \in X \,:\, x \in X\}$$ since the only element of {X} is X.

but this is the very definition of the actual set X. Therefore $\bicap \{X\} = X$.

Please tell me where I went wrong in this calculation. Perhaps I am using the definition of "intersection" incorrectly.

 

[matt grime]

Good grief, what an idiotic notation. (Not that wikipedia is an acceptable reference, by the way, for academic purposes.) It isn't immediately clear from the definition that it is independent of the A chosen, for instance.

 

[Oxymoron]

For (e), I think it is wrong too. I believe it should be

$$\bigcap\bigcap X = \bigcap \left( \bigcap \{1,2,4,5\}\right) = \bigcap (1 \cap 2 \cap 4 \cap 5) = \bigcap (\{0\}) = \bigcap 1 = 1$$

Same with (g), you are right. It should be

$$\{n \in X\,:\, n \neq n\} = \emptyset$$

 

[Oxymoron]

Posted by Matt Grime:

Good grief, what an idiotic notation. (Not that wikipedia is an acceptable reference, by the way, for academic purposes.) It isn't immediately clear from the definition that it is independent of the A chosen, for instance.

Dont blame me , I am just using the definition that we were given in class:

Let $\mathcal{C}$ be a non-empty set and suppose that $A \in \mathcal{C}$. Then we define the intersection of $\mathcal{C}$ to be the set

$$\bigcap\mathcal{C} = \{x \in A\,:\, x \in B \,\forall\, B \in \mathcal{C}\}$$.

Obviously the collection of sets C must be non-empty for the intersection to be defined. It makes no sense to define the intersection of an empty collection of sets because in the definition we must first pick a subset. This definition relies on us being able to pick a subset first and then compare. I'd like to see your definition of intersection. Remember, I had defined this only after learning the existence, the extension, the specification, and the pairing axiom.

And I am regarding X (={1,2,4,5}) as a collection of sets, because each 1,2,4, and 5 are sets containing elements.

 

[matt grime]

It is not the definition of intersection that is the issue. It is your notation for something that is the issue. I have the same definition of the intersection of two, or more, sets as anyone else. And I am not arguing that one can intersect a collection of sets. I am complaining that your notation for this intersection is a bad one.

If I wish to write down the intersection of a set of sets, then what I wrote in the first reply is precisely the unambiguous notation that I would choose, as would most anyone else I imagine.

$$\cap_{x \in X} \ x$$

 

[Oxymoron]

Ok, I see. So all I have to do is write an index to indicate exactly what it is that I am intersecting? And in these cases it is what you have written (twice now).

 

[matt grime]

Preferably, otherwise it is confusing. I'm sure yout notation is well known in some circles, but I would guess, since I've managed to get a long way into a career in maths and never seen it, that it is not *that* well known.

Just think in terms of sums of numbers. The analogy (for union) would be: let Y be a set of numbers, define

$$\sum Y$$

to be the sum of y in Y. But that is bad notation. We write

$$\sum_{y \in Y} y$$

It does make sense to have an emtpy intersection, by the way. Try googling for 'the empty intersection'

 

[Oxymoron]

Ok, fair enough, I can do that.

The next set of questions went something like this:

Q2) Say whether each of the following partially ordered sets are totally ordered, well-ordered, or neither.

a) $$\{9,2,6\}$$ with the usual order on real numbers.

I figured that this was totally ordered since for each element in the set you have either $x \leq y$ or $y \leq x$. Unless I am mistaken I thought this was rather obvious. It is also well-ordered because the set has a smallest element, namely 2. Do I have to prove anything?

b) $$\mathbb{Q}$$ with the usual order on real numbers.

I think this set is totally ordered. This set does not have a smallest element therefore it is not well-ordered.

c) $$\mathcal{P}(\{a,b,c\})$$ ordered by the subset relation.

I think that this set is not totally ordered since the subset {a} and the subset {b} are not comparable. (however, I think if the set was either empty or single then its power set would be totally ordered.) It is well-ordered if every non-empty subset has a least element. Could I just name the smallest element and build up the well-ordering from there? Or is this cheating?

d) $$\omega$$

This ordinal number is, by definition (I think) a well-ordered set and I believe it is totally ordered (Or am I thinking that a set of ordinals is totally ordered, hmmm...) No, surely if a set is well-ordered then it is totally ordered (In Z-F set theory).

 

[matt grime]

A set is well ordered if *all* non-empty subsets have a least element. It does not suffice to say that it has a least elemen, so your answer to 1 is incorrectly reasoned. But any subset of a well ordered set is well ordered.for c), you could do that for that particular set. But it wouldn't prove any power set is well-ordered (with the natural ordering). Try to think of a better method.

 

[Oxymoron]

Posted by Matt Grime:

A set is well ordered if *all* non-empty subsets have a least element. It does not suffice to say that it has a least elemen, so your answer to 1 is incorrectly reasoned. But any subset of a well ordered set is well ordered.

Ah, of course! However, the set {9,2,6} is still well-ordered though isn't it, but it is because all non-empty subsets of {9,2,6} have a least element (thanks to the usual order).

Posted by Matt Grime:

for c), you could do that for that particular set. But it wouldn't prove any power set is well-ordered (with the natural ordering). Try to think of a better method.

So in this case, I have been given a particular set and so my reasoning holds. However, you say now what about $\mathcal{P}(X)$ for some set X (possibly infinite). Could I try to set up a 1-1 correspondence between the power set and, say, another set which I already know to be well-ordered?

 

[matt grime]

No. You would just show it is well ordered (if it indeed is...) by producing a minimal element from any collection of objects. However, I think you're missing something far more important. It is not totally ordered. So how can it be well ordered? In particular, in the example given above, since {a} and {b} are not comparable, the set {{a},{b}} has no minimal element...

 

[Oxymoron]

Posted by Matt Grime

It is not totally ordered. So how can it be well ordered? In particular, in the example given above, since {a} and {b} are not comparable, the set {{a},{b}} has no minimal element...

Ah, of course. If a set is not totally ordered then it is not well-ordered.

Now, onto the next set of questions.

Q3) a) What is an initial segment?

When you have a partially ordered set X you can define an initial segment S(x) for some element x of that set. The initial segment, S(x) is a set that consists of all those elements y from X that are "less than" x (of course this depends on the relation "<" for the set). My original idea of an initial segment was that of an interval. For example, the initial segment of $x \in \mathbb{R}$ with the usual notion of < is $(-\infty,x)$. But the initial segment could be a "region" or a "volume" too, for example the initial segment of $(x,y) \in \mathbb{R}^2$ with the lexicographic relation (I think).

b) What is an ordinal? And is {0,2} an ordinal?

An ordinal, $\alpha$, is a well-ordered set such that for every $\xi \in \alpha$ we have $S(\xi) = \xi$.

The set {0,2} is well-ordered (considering that $1 = 0 \cup \{0\} = \{0\}$ and $2 = 1 \cup \{1\} = \{0,1\}$). The question remains, does $S(n) = n$ for all $n \in \{0,2\}$? I'm assuming the question requires me to use the usual order relation on natural numbers. So if I pick an element, say 0, is S(0) = 0? Well, there are no elements in {0,2} less than 0. So, in fact, $S(0) = \emptyset$, but remember $0 = \emptyset$ which is good so far. But there is one more element to check. Now $S(2) = \{0\} = 1$. Therefore, {0,2} is not an ordinal.

c) Prove that if $\alpha$ is a non-empty ordinal, then $0 \in \alpha$.

Since $\alpha$ is an ordinal it must be well-ordered, therefore since the ordinal is non-empty it has a least element n. Also, since it is an ordinal, the initial segment of this least element must equal itself. That is $S(n) = n$. But, by the definition of the initial segment, we have

$$S(n) = \{\eta \in \alpha \,:\, \eta < n\} = \emptyset$$

since n is a least element there cannot be any other elements less than it. But the only element whose initial segment is zero is the element zero. That is $S(0) = \emptyset$. Therefore n = 0 is an element of $\alpha$ (and it is also the least element).

 

[matt grime]

b) What is an ordinal? And is {0,2} an ordinal?

An ordinal, $\alpha$, is a well-ordered set such that for every $\xi \in \alpha$ we have $S(\xi) = \xi$.

The set {0,2} is well-ordered (considering that $1 = 0 \cup \{0\} = \{0\}$ and $2 = 1 \cup \{1\} = \{0,1\}$). The question remains, does $S(n) = n$ for all $n \in \{0,2\}$? I'm assuming the question requires me to use the usual order relation on natural numbers. So if I pick an element, say 0, is S(0) = 0? Well, there are no elements in {0,2} less than 0. So, in fact, $S(0) = \emptyset$, but remember $0 = \emptyset$ which is good so far. But there is one more element to check. Now $S(2) = \{0\} = 1$. Therefore, {0,2} is not an ordinal.

I don't think I understand your conventions once more. Firstly {0,2} with the usual order relation is order isomorphic *as a set* to {0,1}. Now is that an ordinal in your definition of what 0 and 1 are? If so then your notion here is not closed under isomorphism, which is troubling. Thus we must be requiring that these things are sets of sets again, or something.

 

[Oxymoron]

Yeah they are sets of sets. The number 0 is a set {}, 0 = {}, 1 = {0}, 2 = {0,1}, 3 = {0,1,2}, etc.

 

[Oxymoron]

Q4) Prove that $|[-1,1]| = |[-1,1]^2|$.

I thought that I would use the Schroeder-Bernstein theorem and find two injective functions

$$f\,:\,[-1,1] \rightarrow [-1,1]^2$$

$$g\,:\,[-1,1]^2 \rightarrow [-1,1]$$

is this right?