[2/19/2006 3:12 PM] Every day, we use to 'categorize' things. [2/19/2006 3:12 PM] And, mathematicians use a special word for these categories. [2/19/2006 3:13 PM] They call them : sets. [2/19/2006 3:13 PM] -->| riftor (riftor@bu-C0240CF7.plus.com) has joined #lecture [2/19/2006 3:13 PM] To describe these sets, mathematicians use symbols. [2/19/2006 3:13 PM] =-= Mode #lecture +o riftor by qwertydawom [2/19/2006 3:14 PM] Now, let's define what a 'set' is. [2/19/2006 3:15 PM] Simply, sets are 'collection of things'. [2/19/2006 3:15 PM] Now, how do we describe a set? [2/19/2006 3:15 PM] There are two ways : [2/19/2006 3:15 PM] the first one is writing all the elements of the set; [2/19/2006 3:16 PM] the second one is telling a property that describes the set. [2/19/2006 3:16 PM] Let's use an example. [2/19/2006 3:17 PM] Say you want to show the set of the integers less than eight. [2/19/2006 3:17 PM] The 2 ways to describe this set would be : [2/19/2006 3:17 PM] 1° : S = {1, 2, 3, 4} [2/19/2006 3:18 PM] 2° : S = {n in N| 1 <= n <= 4} [2/19/2006 3:19 PM] These two definitions are exactly the same thing. [2/19/2006 3:19 PM] qwertydawom: [2/19/2006 3:19 PM] you said a set of integers less than 8 but you only included 1-4 [2/19/2006 3:20 PM] :D [2/19/2006 3:20 PM] good job mu [2/19/2006 3:20 PM] so, isn't that a subset? [2/19/2006 3:20 PM] ah! I see you know some stuff ;) [2/19/2006 3:20 PM] a little bit [2/19/2006 3:20 PM] that's good at least one is paying attention! [2/19/2006 3:20 PM] my kid's right beside me [2/19/2006 3:20 PM] now, what would be the correction mu? [2/19/2006 3:21 PM] S=(1, 2, 3, 4, 5, 6, 7) [2/19/2006 3:21 PM] and [2/19/2006 3:22 PM] S= (n in N| 1<=n<=7) [2/19/2006 3:22 PM] but i don't get why it's written that way [2/19/2006 3:22 PM] yes, mu, you're totally right! :) [2/19/2006 3:22 PM] ok, now, I shall explain these writings. [2/19/2006 3:23 PM] for the first one, I guess there's no real problem? [2/19/2006 3:23 PM] we just use "S" for set [2/19/2006 3:23 PM] right [2/19/2006 3:24 PM] and between "{", we put all the elements of the set, separated with a comma (or a semi-colon). [2/19/2006 3:24 PM] can I just interject here and say that sets are not ordered [2/19/2006 3:24 PM] and can not have duplicate elements [2/19/2006 3:24 PM] so { 1, 1, 1 } is not a valid set [2/19/2006 3:24 PM] and {1, 2, 3} is equal to {3, 1, 2} [2/19/2006 3:26 PM] Indeed. [2/19/2006 3:26 PM] Now, is it ok for the first way? [2/19/2006 3:26 PM] yeah [2/19/2006 3:26 PM] alright, the second way then [2/19/2006 3:27 PM] let's analyze what's between the brackets [2/19/2006 3:27 PM] first, one can see : n in N [2/19/2006 3:27 PM] what's that? [2/19/2006 3:27 PM] well, "n" is just here to represent any number belonging ("in") to "N". [2/19/2006 3:28 PM] N is the set? [2/19/2006 3:28 PM] but, what's N? [2/19/2006 3:28 PM] N = natural numbers? [2/19/2006 3:28 PM] Numbers less than 8 [2/19/2006 3:28 PM] oh [2/19/2006 3:29 PM] yes, N = natural numbers [2/19/2006 3:29 PM] N is the set defined like this : [2/19/2006 3:29 PM] N = {1, 2, 3, ... } [2/19/2006 3:30 PM] so n is? [2/19/2006 3:30 PM] n is any number of this set [2/19/2006 3:30 PM] ok [2/19/2006 3:30 PM] but! with the second part, we add a condition on "n" [2/19/2006 3:32 PM] okay, sorry to interupt again [2/19/2006 3:32 PM] I'd like to propose that we say the set of natural numbers starts at 0 and continues [2/19/2006 3:32 PM] N = {0,1,2,3,.... } [2/19/2006 3:32 PM] as this provides us with what's called a "closure" property for arithmetic [2/19/2006 3:33 PM] a closure property is when you say that if you have some state of some type, and you apply an operation to it, you get a new state that is of the same type as the old one [2/19/2006 3:33 PM] and its very important for us to have something called an "identity" property for arithmetic as well [2/19/2006 3:34 PM] that says, when we perform an operation with two inputs, we get as the result one of those inputs unchanged [2/19/2006 3:34 PM] so in arithmetic [2/19/2006 3:34 PM] A+0=A [2/19/2006 3:34 PM] and [2/19/2006 3:34 PM] A*1 = A [2/19/2006 3:34 PM] so those are the identity properties of multiplication and addition [2/19/2006 3:34 PM] which are part of our "closure" [2/19/2006 3:35 PM] so I feel 0 is important to have in our set of natural numbers :) [2/19/2006 3:35 PM] sorry for that tangent! [2/19/2006 3:35 PM] so yes.. N = {0,1,2,3...} [2/19/2006 3:35 PM] qwerty? [2/19/2006 3:35 PM] ok! [2/19/2006 3:36 PM] so now, if we want to take "natural integers less than eight", we'd only need to write : [2/19/2006 3:36 PM] S = {n in N| n < 8} [2/19/2006 3:36 PM] this "|" means "such that" [2/19/2006 3:37 PM] and "n < 8", like most of you may know it means "n less than eight" [2/19/2006 3:37 PM] so, now, I think you got the 2nd writing. [2/19/2006 3:37 PM] Is it alright? [2/19/2006 3:37 PM] yep [2/19/2006 3:37 PM] aye [2/19/2006 3:38 PM] hmm [2/19/2006 3:38 PM] just to clarify something [2/19/2006 3:38 PM] if I understand correctly... [2/19/2006 3:38 PM] S = {n in N| 1 <= n <= 8} is NOT the same as S = {n in N| n < 8} [2/19/2006 3:38 PM] right? [2/19/2006 3:38 PM] yep [2/19/2006 3:38 PM] ok [2/19/2006 3:38 PM] if we define N to be {0, 1, ... } [2/19/2006 3:39 PM] the first is {1,2,3,4,5,6,7,8} the other is {0,1,2,3,4,5,6,7} [2/19/2006 3:39 PM] ok [2/19/2006 3:39 PM] but, before I go on [2/19/2006 3:39 PM] riftor will explain you what "n < 8" is. [2/19/2006 3:41 PM] after all, it's a logic lecture, and these symbols belong to what's called "predicate logic" [2/19/2006 3:41 PM] heh okay :) [2/19/2006 3:41 PM] so what we have after our | is called a predicate [2/19/2006 3:42 PM] predicate calculus is the next step up from propositional logi which we saw yesterday [2/19/2006 3:43 PM] in propositional logic we were dealing with operators such as and, or and not that dealt with manipulating truth values [2/19/2006 3:44 PM] in predicate logic we are still writing statements that will ultimately evaluate to "true" or "false" but we have a lot more operators to play with [2/19/2006 3:45 PM] the corner stone of predicate calculus/logic is the use of quanitification, where we can bind a variable and provide a formal way of how we are going to deal with it [2/19/2006 3:45 PM] i will now introduce two new operators called the "universal" operator and the "existential" operator [2/19/2006 3:45 PM] the universal operator is drawn as an upside A, but in this IRC format I will have to use an A to represent it [2/19/2006 3:46 PM] the existential quantifies is drawn as a back to front E (so a west fast E if you like), but for this lecture I will have to write it as just E [2/19/2006 3:46 PM] now these "quantifiers" appear at the start of predicate statements to tell us about the 'bindings' of particular variables [2/19/2006 3:47 PM] the universal quantifier can be thought of as saying "for all something" and the existential can be though of saying "there exists some..." [2/19/2006 3:48 PM] so we might say [2/19/2006 3:48 PM] Ax:2x>x [2/19/2006 3:48 PM] this statement says, for all x, 2x is greater than x [2/19/2006 3:48 PM] so we are quantifying x, to be true for all its values [2/19/2006 3:49 PM] in fact that statement needs a bit of extra stuff [2/19/2006 3:49 PM] because we haven't said where x comes from [2/19/2006 3:49 PM] earlier we were looking at sets and saying n in N [2/19/2006 3:50 PM] here we want to do a similar thing but we have to use a set membership symbol, which we haven't seen yet [2/19/2006 3:51 PM] and sadly this is going to get really confusing as it is a capital epsilon character that looks like an E, so we are going to have to use something else for the moment [2/19/2006 3:52 PM] so lets just say Ax in N : 2x>x [2/19/2006 3:52 PM] so, for all x in the set of natural numbers, 2x is greater than x [2/19/2006 3:52 PM] now for existential, we are saying "there exists some..." [2/19/2006 3:52 PM] so [2/19/2006 3:52 PM] for example:- [2/19/2006 3:53 PM] Ex in N : x+3>10 [2/19/2006 3:53 PM] saying, there exists some x in N where x+3>10 [2/19/2006 3:53 PM] now the statement Ax in N : x+3>10 is not true, as 12+3 is not greater than 10, and 12 is in the set of natural numbers [2/19/2006 3:54 PM] but when we are using the existential operator, we are saying there exists some x in the set for which this is true [2/19/2006 3:54 PM] that could be just one value, or it could be all of them [2/19/2006 3:55 PM] typo : "2+3" is not greater than 10 [2/19/2006 3:55 PM] and "2" is in N [2/19/2006 3:55 PM] sorry yes [2/19/2006 3:55 PM] i got myself confused [2/19/2006 3:56 PM] Ax in N : x+3>10 is not true, as 2+3 is not greater than 10, and 2 is in the set of natural numbers [2/19/2006 3:57 PM] now this predicate calculus is very useful for defining other operations [2/19/2006 3:58 PM] -->| CdPirate (CdPirate@bu-3B3CB0EE.as1.wxd.wexford.eircom.net) has joined #lecture [2/19/2006 3:59 PM] and we will probably see it more later, but be aware about it, and the fact that when we are writing these set definitions that we are using a "predicate" of kinds [2/19/2006 3:59 PM] quick last example [2/19/2006 3:59 PM] we might restrict the operation of some function, or even define it in a way by saying [2/19/2006 3:59 PM] -->| skiddieleet (skiddielee@bu-F06C0E33.satx.res.rr.com) has joined #lecture [2/19/2006 3:59 PM] Ax in N: f(x)=x+2 [2/19/2006 4:00 PM] saying, for all x in the set of natural numbers, a function f applied to x is equal to x+2 [2/19/2006 4:00 PM] of course f might take other values than that of the natural numbers [2/19/2006 4:00 PM] -->| switch (switch@bu-CB0B9791.hsd1.ma.comcast.net) has joined #lecture [2/19/2006 4:01 PM] or we might say:- [2/19/2006 4:01 PM] Ax in N, Ey in N : f(x)=y and y=x+2 [2/19/2006 4:01 PM] for all x in the set of natural numbers, there exists a y also in the set of natural numbers such that f(x) is equal to y, and y=x+2 [2/19/2006 4:01 PM] se where we have thrown in "and" from propositional logic, which we can do :) [2/19/2006 4:02 PM] any questions? [2/19/2006 4:02 PM] -->| immortal (immortal@regime.gov) has joined #lecture [2/19/2006 4:02 PM] uhm [2/19/2006 4:02 PM] |<-- CdPirate has left irc.binaryuniverse.net (Quit: Well a yar har har and a compact disk...) [2/19/2006 4:02 PM] my son and i need it dumbed down a bit [2/19/2006 4:02 PM] okay [2/19/2006 4:03 PM] so in predicate calculus, we can have functions [2/19/2006 4:03 PM] yes [2/19/2006 4:03 PM] denoted in by some lower case letter, then paraeters [2/19/2006 4:03 PM] so f(x) for example [2/19/2006 4:03 PM] is the function f, that takes a variable x [2/19/2006 4:03 PM] ok [2/19/2006 4:03 PM] we can use this function with a predicate to describe some of its operation [2/19/2006 4:03 PM] e.g. [2/19/2006 4:04 PM] Ax in N : f(x)>10 [2/19/2006 4:04 PM] no we might not know whats going on inside f [2/19/2006 4:04 PM] but we are saying that for all numbers within the set of natural numbers N, that the function is defined, and produces a result greater than 10 [2/19/2006 4:05 PM] Ax in N, Ey in N : f(x)=y and y=x+2 [2/19/2006 4:05 PM] in that statement we are introducing out "existential" quanitifier also [2/19/2006 4:05 PM] so say that, in english, for all x in the set of natural numbers N, there exists some y in the set of natural numbers (N), such that f(x)=y, and y=x+2 [2/19/2006 4:06 PM] e.g. : if x = 2, then : y = 4 [2/19/2006 4:07 PM] or another example [2/19/2006 4:07 PM] question [2/19/2006 4:07 PM] Ex in { monkeys, cats, dogs, humans } : x has no tail [2/19/2006 4:08 PM] a little bit of a silly example, but we are saying, there exists an x in the set of {monkeys, cars, dogs, humans} such that x has no tail [2/19/2006 4:08 PM] does that define the function as "+"? [2/19/2006 4:08 PM] so we are saying, at least one of the types of animals has no tail [2/19/2006 4:09 PM] the function is aribtrary, we are really only defining the function by its result for all x in the natural numbers [2/19/2006 4:09 PM] but you said [2/19/2006 4:09 PM] Ax in N, Ey in N : f(x)=y and y=x+2 [2/19/2006 4:09 PM] oi [2/19/2006 4:09 PM] i'm confused [2/19/2006 4:10 PM] well, it simply means that : [2/19/2006 4:10 PM] if we take a natural integer, then, we can find another integer that will be our first one... plus two! :) [2/19/2006 4:11 PM] let's take : 1. [2/19/2006 4:11 PM] can you find this "y"? [2/19/2006 4:11 PM] 3? [2/19/2006 4:11 PM] yep [2/19/2006 4:11 PM] my son answered that ;p [2/19/2006 4:11 PM] good work [2/19/2006 4:11 PM] and, you could do the same thing FOR ALL x. [2/19/2006 4:11 PM] ok [2/19/2006 4:12 PM] we got it now [2/19/2006 4:12 PM] ty [2/19/2006 4:12 PM] cool [2/19/2006 4:14 PM] so, let's get back to our first example [2/19/2006 4:14 PM] the natural integers less than eight [2/19/2006 4:14 PM] when I first wrote the set S, mu pointed out the mistake [2/19/2006 4:15 PM] and! she employed the word "subset" [2/19/2006 4:15 PM] indeed, if we define T to be : [2/19/2006 4:15 PM] T = {1, 2, 3, 4} [2/19/2006 4:15 PM] and S = {0, 1, 2, 3, 4, 5, 6, 7} [2/19/2006 4:16 PM] we can see that all the elements of T are in S. [2/19/2006 4:16 PM] that's the definition of a subset. [2/19/2006 4:16 PM] "The set T is a subset of S if every element of T is also in S" [2/19/2006 4:17 PM] or, with our dear logic symbols : x \in T ==> x \in T [2/19/2006 4:18 PM] where '\in' is the epsilon riftor was talking about [2/19/2006 4:18 PM] what is '\'? [2/19/2006 4:18 PM] oh [2/19/2006 4:18 PM] my bad [2/19/2006 4:18 PM] which means, again? [2/19/2006 4:18 PM] or, with our dear logic symbols : x \in T ==> x \in S [2/19/2006 4:19 PM] well : x \in T means that the set T contains the element x [2/19/2006 4:19 PM] i'd just like to indicate that in predicate calculus we would say, Ax \in T: x \in S [2/19/2006 4:20 PM] yep [2/19/2006 4:20 PM] is that ok? [2/19/2006 4:20 PM] uhm [2/19/2006 4:21 PM] i don't understand what the function of '\' is [2/19/2006 4:21 PM] forget about it if you want [2/19/2006 4:21 PM] ok [2/19/2006 4:21 PM] lol [2/19/2006 4:21 PM] it's just that, since we cannot represent the 'epsilon', I use '\in' [2/19/2006 4:21 PM] o [2/19/2006 4:22 PM] ok i gotcha [2/19/2006 4:22 PM] :) [2/19/2006 4:22 PM] good [2/19/2006 4:22 PM] so, now, let N be the set of the natural integers [2/19/2006 4:22 PM] what can you say about S with respect to N? [2/19/2006 4:22 PM] it's a subset <_< [2/19/2006 4:23 PM] that's right! :) [2/19/2006 4:25 PM] alright, so, let's recall our stars of the day... S and T! [2/19/2006 4:26 PM] you've seen that the numbers '1, 2, 3 and 4' were in the two sets, right? [2/19/2006 4:26 PM] yup [2/19/2006 4:27 PM] |<-- Ignite has left irc.binaryuniverse.net (Quit: i'm to tired to take all this in, can't keep my eyes open, night all and keep it up qwertydawom good work) [2/19/2006 4:27 PM] so, we would say that "the intersection of S and T" is the set containing "1, 2, 3 and 4" (in this case S inter. T would be T) [2/19/2006 4:28 PM] Generally speaking, the intersection of two sets S and T consists of all elements present in both set. [2/19/2006 4:28 PM] =-= Mode #lecture +v skiddieleet by qwertydawom [2/19/2006 4:29 PM] We denote the intersection by a reversed "U". [2/19/2006 4:29 PM] But, here I'll just use "inter". [2/19/2006 4:29 PM] (upside down U, it looks like a big 'n') [2/19/2006 4:30 PM] So : S inter T = {x| x \in S and x \in T} [2/19/2006 4:31 PM] got it? [2/19/2006 4:31 PM] yea [2/19/2006 4:31 PM] ok, we'll see it right now with a little practice exercise : [2/19/2006 4:33 PM] Let A = {x \in N | x >= 5} and B = {x \in N | x < 9}. [2/19/2006 4:33 PM] What would be 'A inter B'? [2/19/2006 4:33 PM] A inter B = { 5, 6, 7, 8 } [2/19/2006 4:33 PM] =-= Mode #lecture -m by qwertydawom [2/19/2006 4:33 PM] indeed :) [2/19/2006 4:33 PM] do you all agree with it? [2/19/2006 4:34 PM] uhm [2/19/2006 4:34 PM] yep [2/19/2006 4:34 PM] i think so [2/19/2006 4:34 PM] k. [2/19/2006 4:34 PM] =-= Mode #lecture +m by qwertydawom [2/19/2006 4:34 PM] A = {5,6,7,8,9...} [2/19/2006 4:34 PM] B = {0,1,2,3,4,5,6,7,8} [2/19/2006 4:34 PM] A inter B = {5,6,7,8} [2/19/2006 4:35 PM] yes, and now, a little bit 'trickier' : [2/19/2006 4:36 PM] Let A = {1, 5, 8} and B = {2, 7, 156}. [2/19/2006 4:36 PM] What's 'A inter B'? [2/19/2006 4:36 PM] =-= Mode #lecture -m by qwertydawom [2/19/2006 4:36 PM] empty set? [2/19/2006 4:36 PM] yeah [2/19/2006 4:36 PM] indeed :) [2/19/2006 4:36 PM] :) [2/19/2006 4:36 PM] I win [2/19/2006 4:36 PM] :P [2/19/2006 4:37 PM] So, if you know what the empty set is, then you might also know the symbol? :) [2/19/2006 4:37 PM] =-= Mode #lecture +m by qwertydawom [2/19/2006 4:37 PM] it's like a 0 with a line through it, right? [2/19/2006 4:37 PM] right ;) [2/19/2006 4:37 PM] <--| immortal has left #lecture [2/19/2006 4:38 PM] So, when the intersection of two sets is empty, we say that these two sets are "disjoint" or "mutually exclusive". [2/19/2006 4:38 PM] And, now, who makes a bright remark and notice that the intersection really looks like an operator we've seen just yesterday? :) [2/19/2006 4:38 PM] =-= Mode #lecture -m by qwertydawom [2/19/2006 4:39 PM] Ch4r? [2/19/2006 4:40 PM] skiddieleet? [2/19/2006 4:40 PM] != [2/19/2006 4:40 PM] ? [2/19/2006 4:40 PM] [2/19/2006 4:40 PM] i dunno [2/19/2006 4:40 PM] that was my answer to the question :P [2/19/2006 4:40 PM] |<-- switch has left irc.binaryuniverse.net (Quit: leaving) [2/19/2006 4:41 PM] yes :) [2/19/2006 4:41 PM] so, complete this sentence : [2/19/2006 4:41 PM] when we take 'A inter B', we want the elements of A ... the elements of B. [2/19/2006 4:42 PM] to contain? [2/19/2006 4:42 PM] that are also? [2/19/2006 4:42 PM] a single word :) [2/19/2006 4:42 PM] a logic operator ;) [2/19/2006 4:43 PM] inclusive? [2/19/2006 4:43 PM] in? [2/19/2006 4:43 PM] no no :) [2/19/2006 4:43 PM] we've seen it yesterday [2/19/2006 4:43 PM] or? ;/ [2/19/2006 4:43 PM] no [2/19/2006 4:43 PM] lol [2/19/2006 4:43 PM] I missed class yesterday [2/19/2006 4:43 PM] mmk [2/19/2006 4:44 PM] well, the answer was... "AND" :) [2/19/2006 4:44 PM] lol [2/19/2006 4:44 PM] ohhhh [2/19/2006 4:44 PM] nice to know we don't disappoint our teachers <_< [2/19/2006 4:44 PM] I saw that in the notes someone gave me from yesterday [2/19/2006 4:45 PM] hehe [2/19/2006 4:45 PM] and now, seeing that Ch4r wants to place it, we'll see what is called the "union" :) [2/19/2006 4:45 PM] hmm... I thoought about 'and', but wouldn't that mean it would be all the elements from A as well as the elements of B, which would be incorrect, s ince we're talking about intersections? -_- [2/19/2006 4:45 PM] haha [2/19/2006 4:46 PM] Well, it's correct, since we want the elements that belong to A AND to B ;) [2/19/2006 4:46 PM] the operation AND means they have to be in both [2/19/2006 4:46 PM] ok right [2/19/2006 4:47 PM] yes, and now, we'll see the union is like "or" ;) [2/19/2006 4:48 PM] The union of two sets S and T, denoted by "S U T", is composed by the elements that are in A or those that are in B. [2/19/2006 4:48 PM] i.e. : S U T = {x | x \in S OR x \in T} [2/19/2006 4:49 PM] So, little exercise : [2/19/2006 4:49 PM] A = {1, 2, 4} [2/19/2006 4:49 PM] B = {3, 5} [2/19/2006 4:49 PM] What is "A U B"? [2/19/2006 4:50 PM] A U B = { 1, 2, 3, 4, 5 } [2/19/2006 4:50 PM] {1, 2, 3, 4, 5}? [2/19/2006 4:50 PM] uh [2/19/2006 4:50 PM] >:( [2/19/2006 4:50 PM] sorry [2/19/2006 4:50 PM] lol [2/19/2006 4:50 PM] np [2/19/2006 4:50 PM] yes, you're both right :) [2/19/2006 4:51 PM] and, now, let's see if you're smart cookies ;) [2/19/2006 4:51 PM] A = {1, 3, 5, 7, .... } [2/19/2006 4:51 PM] I love cookies [2/19/2006 4:51 PM] B = {2, 4, 6, 8, ... } [2/19/2006 4:51 PM] what'd be "A U B"? [2/19/2006 4:51 PM] A U B = {1,2,3,4,5,6,7,8...} [2/19/2006 4:51 PM] A U B = { 1, 2, 3, ...} [2/19/2006 4:51 PM] ,...* [2/19/2006 4:51 PM] yea [2/19/2006 4:51 PM] which is? :) [2/19/2006 4:51 PM] N [2/19/2006 4:52 PM] all Natural numbers [2/19/2006 4:52 PM] indeed! :) [2/19/2006 4:52 PM] :) [2/19/2006 4:52 PM] well, we've previously defined N to contain "0", but... that's the idea [2/19/2006 4:52 PM] I didn't know that [2/19/2006 4:52 PM] in fact, this set would be denoted "N*", the star showing that "0" isn't in it. [2/19/2006 4:53 PM] is that our N, or the Natural Numbers have 0 also? [2/19/2006 4:53 PM] natural #s have 0 [2/19/2006 4:53 PM] let's do relations :P [2/19/2006 4:53 PM] uhm [2/19/2006 4:54 PM] well, to be honest, it varies with the countries. [2/19/2006 4:54 PM] from my understanding, N contains 0 when used in set theory and computer science [2/19/2006 4:54 PM] and it doesn't every where else [2/19/2006 4:54 PM] well, I know that in US you're taught : N = {1, 2, 3, ...} [2/19/2006 4:54 PM] but, for example in France, we're told that : N = {0, 1, 2, ... } [2/19/2006 4:55 PM] Z+ [2/19/2006 4:55 PM] i was taught 0 [2/19/2006 4:55 PM] but, like riftor previoulsy stated, it's better to include "0" in our N. [2/19/2006 4:55 PM] in my discrete math book N is 0, 1... [2/19/2006 4:55 PM] ok then ;) [2/19/2006 4:55 PM] Z is the set of all Integers, and Z+ is 1, 2, ... [2/19/2006 4:55 PM] positive integers [2/19/2006 4:55 PM] yes [2/19/2006 4:56 PM] so, now, let's do some 'counting' :) [2/19/2006 4:56 PM] Let's take a set with three elements : [2/19/2006 4:56 PM] A = {a, b, c} [2/19/2006 4:56 PM] Who can show me all the subsets of A? [2/19/2006 4:57 PM] {a}, {a, b}? [2/19/2006 4:57 PM] erm [2/19/2006 4:57 PM] wait [2/19/2006 4:57 PM] {a} [2/19/2006 4:57 PM] {b} [2/19/2006 4:57 PM] {c} [2/19/2006 4:57 PM] {a,b} [2/19/2006 4:57 PM] {ac} [2/19/2006 4:57 PM] {a,c} [2/19/2006 4:57 PM] {b,c} [2/19/2006 4:57 PM] right? [2/19/2006 4:57 PM] hehe, you forgot two in fact :) [2/19/2006 4:57 PM] =x [2/19/2006 4:58 PM] but, I shall explain your mistake (which is normal at that point) : [2/19/2006 4:58 PM] 1) "every set is a subset of itself" [2/19/2006 4:58 PM] so, can you add one? :) [2/19/2006 4:58 PM] ah [2/19/2006 4:58 PM] o.0 [2/19/2006 4:59 PM] is the empty set a subset? [2/19/2006 4:59 PM] that is "2)" :) [2/19/2006 4:59 PM] :P [2/19/2006 4:59 PM] 2) "the empty set is a subset of every set" [2/19/2006 4:59 PM] so, now, who can finish the list? :) [2/19/2006 4:59 PM] huh? [2/19/2006 4:59 PM] {a,b,c} [2/19/2006 4:59 PM] and 0 with a line through it [2/19/2006 4:59 PM] :P [2/19/2006 4:59 PM] empty set, {a}, {a, b}, {a, b, c} [2/19/2006 4:59 PM] yes, ch4r's got them all ;) [2/19/2006 5:00 PM] :) [2/19/2006 5:00 PM] smarties [2/19/2006 5:00 PM] oh [2/19/2006 5:00 PM] how many do we have ch4r? [2/19/2006 5:00 PM] 8? [2/19/2006 5:00 PM] 8 [2/19/2006 5:00 PM] yep :) [2/19/2006 5:00 PM] ;D [2/19/2006 5:00 PM] 2^n [2/19/2006 5:00 PM] grr :p [2/19/2006 5:00 PM] now, mu, just do the same thing with : [2/19/2006 5:00 PM] B = {a, b} [2/19/2006 5:01 PM] k [2/19/2006 5:01 PM] {a}, {b}, empty set, and {ab} [2/19/2006 5:01 PM] alright [2/19/2006 5:01 PM] how many? [2/19/2006 5:01 PM] 4 [2/19/2006 5:01 PM] true :) [2/19/2006 5:01 PM] so, you see that : [2/19/2006 5:02 PM] for a set with "2" elements, you have "4" subsets [2/19/2006 5:02 PM] for a set with "3" elements, you have "8" subsets. [2/19/2006 5:02 PM]