Science Forum - Some Superficial Set theory

The Science Forum - Scientific Discussion and Debate

Live Chat

FAQ

Usergroups

Science Forum Forum Index » Mathematics » Some Superficial Set theory

Goto page 1, 2, 3, 4, 5 Next

Some Superficial Set theory

« View previous topic :: View next topic »

Author

Message

Guitarist

Posted: Fri Jul 04, 2008 6:58 am Post subject: Some Superficial Set theory

Forum Ph.D.

Joined: 08 Jun 2005
Posts: 748

And I do mean superficial; all you will learn here is a few definitions, what the set-theoretic symbols mean, and some very basic concepts.

So, a set is simply a collection of objects for which I can find a suitable unifying property which will allow me to make the following assertion:

A set is well-defined iff, for any object whatever in the universe of objects, an object is either in the definitely in this set or definitely not in this set.

We will see that this assertion neatly side-steps a famous paradox.

Obviously, the objects we shall be dealing with here are mathematical objects. Let's now look at the "algebra" of sets (it's not, of course, really an algebra!), so we will need some notation.

One says that S is a set, and that $x \in S$ if one wants to assert that "x is a member of (an element in) S". In like fashion, it is sometimes syntactically convenient to write $S \ni x$ to mean "S is the set that has x as a member".

(Caveat: militant set theorists will insist these two forms are subtly different - let them go hang!).

Conversely, one would write $x \notin S$ to mean that x is not an element in S.

More notation: when talking about a set, one has two choices; one can give the entire set a label, like X or Y or whatever, or one might want to be more specific. Write, say, X = {x, y, z} to mean that "X is the set whose elements are x, y and z".

Note that this formulation is very rarely useful when x, y and z are not fully defined. The exceptions include, say, Y = {2, 4, 6, 8, 10, ...}, where one may may assume that Y is the set of even numbers.

This brings us full circle for now, and to some useful notation which, unexpectedly, reveals something slightly profound. Recall we agreed that a set is a collection which has a strict membership criterion. In other words, a set is really a collection together with that criterion. We write it like this:

X = {x : membership criterion}. Here's a concrete example. 3Z = {x : x is integer exactly divisible by 3}. Read the colon ( the pipe | is also used) to mean "such that", or "with the property that".

Here is the slight profundity; sets are pretty dumb creature, as we shall see - they know nothing about, say, division (as in the example above). But we are not dumb - we can establish the qualification for set membership in any way we choose, but once "inside the set" the members are not allowed (in general) to use that qualification.

Like, throw a party for footballers only, but stipulate that no football is allowed inside your house.

You'll be tired of reading this drivel, no doubt, and I have barely scratched the surface.

Later, but ask questions, make corrections, put me on ignore, whatever.....

Last edited by Guitarist on Mon Jul 07, 2008 1:50 am; edited 1 time in total

KALSTER

Posted: Fri Jul 04, 2008 7:16 am Post subject:

Forum Cosmic Wizard

Joined: 08 Sep 2007
Posts: 2231
Location: South Africa

Count me in! I am encouraged by being able to understand what you are saying Wink

_________________
"Gullibility kills" - Carl Sagan
As jy dom is, moet jy kak.

bit4bit

Posted: Fri Jul 04, 2008 7:31 am Post subject:

Forum Ph.D.

Joined: 14 Jul 2007
Posts: 625

Guitarist, how far are you going to take this thread? I know a little set theory, but it only really goes so far as to talk about subsets/supersets, and also injective/bijective/surjective functions (which I'm not sure are really a central idea in set theory anyway, but just use set notation?). Anyways, could you please outline what you plan to do, since I'd like to know what is beyond my current knowledge of it. To me, it seems like a subject that isn't very extensive, but I'm sure you'll tell me there's alot to it.
_________________
Chance favours the prepared mind.

Guitarist

Posted: Fri Jul 04, 2008 9:16 am Post subject:

Forum Ph.D.

Joined: 08 Jun 2005
Posts: 748

bit4bit: As far as you want, so long as it is in the within the range of my understanding/interest.

Wait for more!

bit4bit

Posted: Fri Jul 04, 2008 9:36 am Post subject:

Forum Ph.D.

Joined: 14 Jul 2007
Posts: 625

Ok, thanks.
_________________
Chance favours the prepared mind.

Chemboy

Posted: Fri Jul 04, 2008 1:12 pm Post subject: Re: Some Superficial Set theory

Forum Ph.D.

Joined: 01 Jul 2006
Posts: 1095
Location: NY

Guitarist wrote:

Here is the slight profundity; sets are pretty dumb creature, as we shall see - they know nothing about, say, division (as in the example above). But we are not dumb - we can establish the qualification for set membership in any way we choose, but once "inside the set" the members are not allowed (in general) to use that qualification.

Like, throw a party for footballers only, but stipulate that no football is allowed inside your house.

I'm fine with everything but could you give a mathematical example in some way of the first paragraph above? I understand it, but if you can give an example in some way it would be cool. I'm enjoying it so far, thanks for doing this.
_________________
"There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges

Guitarist

Posted: Sat Jul 05, 2008 2:47 am Post subject:

Forum Ph.D.

Joined: 08 Jun 2005
Posts: 748

The point I was trying make was this; a set may have as members real numbers, or it may be complex numbers or it may be polynomials, or it may be chocolate brownies. Set theory is completely agnostic, and treats these sets all in exactly the same way. This should become clear shortly.

So, I said "set theory treats....". What does this mean?

By stretching a point ever so slightly, we may say that the only thing set theory knows about is what we may call "inclusion". Now inclusion can be passive or it can be active; in the former case we will call this a "set relation", in the latter a "set operation"

We have seen an example of a relation already: $x \in S$ ; x is included in S.

But not only can we talk about the inclusion of elements in sets, we can talk about the inclusion of sets in sets. In this circumstance, one says that the included set is a subset of the including set.

Let's have a proper definition: if every element of the set A is also an element of the set B, one says that A is a subset of B. Now look at that a minute - notice I haven't said that "not every element of B is an element of A" (though I will shortly..)

This has the curious (but useful) consequence that every set is a subset of itself. One writes $A \subseteq B$ to denote this. Read it as "subset or equal". This relation is reciprocal, so that in the case above we have that B is a superset of A; $B \supseteq A$ .

So we should know what we mean by equality. Obvious really; two sets are said to be equal if every member of one is also a member of the other and vice versa.

So there is rather stricter inclusion relation; if it is the case that A is a subset of B such that $A \ne B$ one says that A is a "proper"subset of B; $A \subset B$ . This is also reciprocal.

I shall give just 2 examples of the above. The set of real numbers is a subset of the complex numbers; $\mathbb{R} \subseteq \mathbb{C}$ (since, when every $z \in \mathbb{C} = x + iy$ , every $x \in \mathbb{R} = x +i0 = x$ )

The set of integers is a proper subset of the set of rational numbers; $\mathbb{Z} \subset \mathbb{Q}$ (since every $a \in \mathbb{Z} = b/c$ for some $b,\. c \in \mathbb{Z}$ ).

PS; although now might seem the obvious place to introduce the complement, there's a couple other things it will be useful to know first. So I shall defer it.

Next we want to talk about "active" inclusions, the set operations. Later for that.

Last edited by Guitarist on Mon Jul 07, 2008 2:00 am; edited 1 time in total

Guitarist

Posted: Sat Jul 05, 2008 5:59 am Post subject:

Forum Ph.D.

Joined: 08 Jun 2005
Posts: 748

OK, before pressing on, let me alert you to one boo-boo, an one abuse of terminology.

Boo-boo: it can never be true, as I seemed to be asserting, that $\mathbb{R} \subseteq \mathbb{C}$ , since R never equals C. I should have written proper subset.

Abuse: the terms "passive inclusion" and "active inclusion" are entirely my own pedagogic inventions. They are never used in practice.

So let's now look at the set operations. Given sets A and B, one is always free to "amalgamate" them. This is called "set union", and is written $A \cup B$ . One is free to write $A \cup B = C$ , but this is rarely useful, rather it is generally helpful to have a notational device to remind ourselves of the following;

$A \subseteq A \cup B$ and $B \subseteq A \cup B$ .

We have the following far from pedestrian result;

If $A \subseteq B$ , then $A \cup B = B$ .

This can only mean that no element in any set can be counted more than once - it's fundamental to the theory.

Another operation allows us to recover the set of elements shared by both A and B. This is called "set intersection", and is written $A \cap B$ . Here it is useful to give the set of shared elements a name

We then have the result that, if $A \subseteq B$ , then $A \cap B = A$ .

Compare this with the above - they are almost "dual" notions.

Now, here's a piece of fun. We are always free to take the intersection of sets that have no elements in common. Let X and Y be such sets. Rhe notion that they share no elements in common is succinctly expressed by saying that their intersection is "empty".

In fact we define a set called the "empty set", and write it $\emptyset$ , hence $X \cap Y = \emptyset$ This is not as crazy as in might seem, because of the following;

For any set S, we have that $S \cup \emptyset = S$

and $S \cap \emptyset = \emptyset$

Again a pleasing duality. In fact it's more than that. Comparing this duality with the one above, one might be tempted to conclude that this implies that $\emnptyset \subset S$ . And one would be right!!

The empty set is a subset of any and all sets.

Now let us suppose that A is a proper subset of B; $A \subset B$ . We say that every element in B that is not in A is in the "complement of A in B" and is written A^c

. Obviously $A^c \subset B$ .

Notice by our original definition of a set (i.e. the well-definedness condition) this can only mean that

and

have no elements in common, hence $A \cap A^c = \emptyset$ .

This is called a "partition" of B. Obviously we also have that $A \cup A^c = B$ .

Last edited by Guitarist on Tue Jul 08, 2008 1:28 am; edited 2 times in total

bit4bit

Posted: Sat Jul 05, 2008 6:41 am Post subject:

Forum Ph.D.

Joined: 14 Jul 2007
Posts: 625

Cheers still with you so far.
_________________
Chance favours the prepared mind.

JaneBennet

Posted: Sat Jul 05, 2008 7:37 am Post subject:

Forum Ph.D.

Joined: 06 Apr 2008
Posts: 878

Guitarist wrote:

Now let us suppose that A is a proper subset of B; A ⊂ B. We say that every element in B that is not in A is in the "complement of A in B" and is written A^c. Obviously A^c ⊂ B.

Two points:

(1) There is no need for A to be a proper subset for A^c to exist. If A = B, then A^c = Ã˜.

(2) A can be a subset of many sets, not just B. The complement notation ^c should only be used when there is no ambiguity as to which set A is a subset of. I donâ€™t like the complement notation myself; instead I always write B\A to mean the complement of A relative to B.

Of couse the complement notation can be useful when itâ€™s properly used. For example, if you are considering subsets of a fixed topological space, then complement notation certainly makes the statement â€œA is open if and only if A^c is closedâ€ look very elegant on paper â€“ which is a great help to those rely a lot on intuition. Wink

_________________

Did You Know?
Random Fact: Electromagnetic waves

Guitarist

Posted: Sat Jul 05, 2008 11:36 am Post subject:

Forum Ph.D.

Joined: 08 Jun 2005
Posts: 748

JaneBennet wrote:

(1) There is no need for A to be a proper subset for A^c to exist. If A = B, then A^c = Ã˜.

Yes, you are right. Let's just say I was trying to keep it as simple and as intuitive as possible. Thanks for the correction

Quote:

(2) A can be a subset of many sets, not just B. The complement notation ^c should only be used when there is no ambiguity as to which set A is a subset of. I donâ€™t like the complement notation myself; instead I always write B\A to mean the complement of A relative to B.

Well I was leaving it like that, in order to use precisely this ambiguity to introduce the notion of "set difference".

So let's do that now.

As Jane points out, there may be a certain ambiguity in the notation A^c

for the complement of

. Complement wrt what?. One may, I suppose, use A_B^c

to emphasize, where there may be ambiguity, that this is the complement of A in B.

No-one ever does. however.

More useful (sometimes) is the notion of "set difference". This is the set-theoretic analogue of the arithmetic "minus". One writes $B \setminus A$ to denote all those elements in B that are not in A.

As expected from our analogy, we have that $B \setminus \emptyset = B$ .

OK, what next? Well this perhaps.....

Notice first that we may define the set {x} as the "singleton set" (since {x, y, z} is a set, and {x, y} is a set, then logic dictates {x} is a set). Then if $x \in \{x, y, z\}$ , so $\{x\} \subset \{x, y, z\}$ , and $\{x, y\} \subset \{x, y, z\}$ and so on

Now suppose that S = {a, b, c}. I will define the set of all the subsets of S to be the "powerset on S", whose elements are of the form {a}, {b}, {a, b} etc.

Then the powerset on S is written $\mathcal{P}(S) = \{\{a\}, \{b\}, \{c\}. \{a, b\}, \{a, c\}, \{b, c\}, \{a, b ,c\}, \emptyset\}$ , where I include the empty set since this, from an earlier post, is always a subset of S,

Notice that S here is a 3-element set, $\mathcal{P}(S)$ is an 8 = 2^3

- element set.

Now, using all available fingers and toes, those of your boyfriend/girlfriend, you should be able to convince yourself that, if S has n elements, then it seems possible that, in general, $\mathcal{P}(S)$ has 2^n

elements.

this turns out to be true.

For even more fun, we need to define the "cardinality" of a set, but right now I have an urgent appointment with a pint of beer.

Last edited by Guitarist on Mon Jul 07, 2008 2:22 am; edited 2 times in total

Guitarist

Posted: Sun Jul 06, 2008 3:15 am Post subject:

Forum Ph.D.

Joined: 08 Jun 2005
Posts: 748

OK, I promised some fun.

The "cardinality" of a set is nothing more that its number of elements. This is sometimes written card(S), more usually |S|, in spite of this being an over-used notation.

It might appear that it goes without saying that the cardinality of a set is always a natural ("counting") number. Aha!

From our last discussion of the powerset, we may write $|\mathcal{P}(S)| = 2^{|S|}$ . It should be fairly obvious that, for any $n \in \mathbb{N},\, 2^n \ge n$ . (here I am not including 0 in N).

So the question now arises; when $|S| = \infty$ , what is $|\mathcal{P}(S)|$ . I invite you to brood on that a bit, it's a lot of fun. Hint1: note my "Aha!" above, Hint2: recall the guy who went off his head thinking about "different kinds of infinity"

OK, some more set operations. One of the most useful and all-pervading set operations is called "the Cartesian product" of sets (in fact it is so pervasive, one frequently fails to mention it - I'll give an example in a mo.)

Let A and B be sets, $a \in A,\. b \in B$ . The Cartesian product of A and B is written $A \times B$ . Note that is is a brand, spanking new set, whose elements are written (a, b).

(a, b) is called an "ordered pair" so as to emphasize the fact that, in general, $(a, b) \ne (b, a)$ .

Here is an example in use. When we learned in school that 1 + 2 = 3, what we should really have been told is something like this. Let $\mathbb{R}$ be the set of real numbers, and let + denote a commutative binary operation on R.

Then define $+: R \times R \to R$ by $+((a, b)) \equiv (a + b) = (b + a) \in \mathbb{R}$

We would have freaked!!

Last edited by Guitarist on Mon Jul 07, 2008 2:34 am; edited 1 time in total

Chemboy

Posted: Sun Jul 06, 2008 7:37 pm Post subject:

Forum Ph.D.

Joined: 01 Jul 2006
Posts: 1095
Location: NY

I'm following everything well, but about the only symbol you've used that isn't a little box to me (in other words I can't see the real symbol), is the one for an intersection. Anything I can do about this?
_________________
"There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges

Guitarist

Posted: Mon Jul 07, 2008 12:15 am Post subject:

Forum Ph.D.

Joined: 08 Jun 2005
Posts: 748

Well this is a very serious problem for you. In fact I am astounded you followed this thread at all.

If I get bored, I'll go back and reformat in LaTex.

Cheers.

P.S. 'Tis done!

Guitarist

Posted: Mon Jul 07, 2008 6:42 am Post subject:

Forum Ph.D.

Joined: 08 Jun 2005
Posts: 748

OK, so there is another sort of set operation called "disjoint union", but it is rather specialized, so I shan't bother with it (unless requested).

I now want to show you the Law of de Morgan, principally for its extreme beauty.

We will start with some simple assertions; "today is not a wet Sunday" means "today it isn't raining" OR "today is not Sunday"

Likewise "today is neither wet nor Sunday" means "today is not Sunday" AND "today it is not raining".

Logicians put it like this; let P and Q be propositions. Then,

not(P AND Q) = notP OR notQ

not(P OR Q) = notP AND notQ.

This has been stolen by set theorists as follows. Let A and B be sets, and let the complement of

etc (I don't think it matters what the complement is with respect to, but some-one is free to set me straight on that).

Then de Mogan as applied here is

$(A \cup B)^c = A^c \cap B^c$

$(A \cap B)^c = A^c \cup B^c$

This is nice; it succinctly illustrates that

a) the complement of a set is it's "negation" which follows from $A \cap A^c = \emptyset$ (assuming the Law of Excluded Middle)

b) set union is analogous to the Boolean AND

c) set intersection is analogous to the Boolean OR

Next we will discuss the Axiom of Choice, and try to raise a few hackles in the process!

Display posts from previous:

Goto page 1, 2, 3, 4, 5 Next

Page 1 of 5

Science Forum Forum Index » Mathematics » Some Superficial Set theory

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum