The h Bar

@ACuriousMind, for the record, will users get banned for posting political messages?

10:20 PM

@heather If they persist after they have been told not to, that is certainly an option.

@ACuriousMind, okay, and one more question, was BM banned for the, uh, unfortunate comment about you, or the political comment? (Just trying to clarify.)

@heather If this were a main site suspension you'd see a "to cool down" as the reason.

What does that mean?

@ACuriousMind I'm confused as to how that answers the question. I assume it's a chat room only suspension.

AccidentalFourierTransform

@heather Bernardo says you're cool, can ride dirty with him any time you're in Rio

trap on the street corner with a draco

slurpin lean

all that good stuff, y' feel me

10:25 PM

Bernardo right now

@0celo7 tell him thank you, but I don't know what half of that means =)

you probably don't want to

@heather It means: drive around with illegals guns in the car, sell drugs on the street corner with an AK-47, drink codeine cough syrup

@0celo7 uh, well then.

Bernardo to me: "Thanks for transmitting the message precisely"

Wait a moment. Is a reference to drugs against policy @ACuriousMind @rob

@heather So you don't know what a power set is?

How far away are you in Halmos

10:30 PM

@0celo7, nope. Here, let me grab the book.

@0celo7 Not as such, no. However I urge you to reconsider the appropriateness of those..."invitations".

@0celo7 Section 5, Complements and Powers.

@ACuriousMind If heather was in Chiraq she'd be doing all of that. She's hecking 15

or maybe 16 by now, idk

I have a proposal here. Let's separate actual on-topic discussions in this chat room from meta-discussions about what is or isn't on topic, the same way we separate physics questions from meta questions on the main site. There's already another perfectly good chat room which we can adapt for this purpose.

6

It's a hard world in these streets

10:31 PM

@0celo7 14

@ACuriousMind Drugs are kewl. All the beat stuff, y'know. 70's culture

Bernardo: "The current moderation policy here is to prohibit anything that could possibly give the mods a bit of work, with no regards to how much it impairs average conversations"

I find all these discussions about "who's banned" and "mod abuse" and "censorship" to be both boring and distracting.

@rob It's not like you're participating in any discussions here right now.

hmm, actually, i don't think that makes much sense @rob

DanielSank

10:32 PM

Hi, everybody.

hello octopus

@0celo7 I've been kibbitzing.

no one's ever in the other room. that means those discussions will be most likely to die when they need the most attention.

@DanielSank, hello =)

@rob I need a dictionary for that one.

DanielSank

@0celo7 ::waves tentacles::

10:33 PM

@0celo7 Lurking. I think it comes from spectating chess matches.

Loong

Kibitzer

Kibitzer is a Yiddish term for a person who offers (often unwanted) advice or commentary. This term is used for a non-participant spectator in contract bridge, chess, go, and many other games. The verb kibitz can also refer to idle chatting or side conversations. In computer science the term is the title of a programming language released by NIST, as a sub-project of the Expect programming language, that allows two users to share one shell session, taking turns typing one after another. There is a 1930 film called The Kibitzer which is based on the 1929 three-act comedy play by the same name. Jane...

@heather Self-fulfilling prophecy.

DanielSank

Lurking and kibitzing are not the same thing.

@DanielSank Apparently not. Today I learned.

@heather I will use the following convention: a set is a set of points and a class is a set of sets.

10:35 PM

@0celo7, makes sense.

Thus, the power set (the collection of all subsets of a set) is in fact a class.

okay...

This makes things nice in measure theory where you have points and sets and classes and sets of classes

sets of classes are collections

@heather If $X$ is a set, does $\mathcal P(X)=$ "class of all subsets of $X$" make sense?

i think i follow, yes.

Exercise. if X is a set of n elements, count the number of elements of P(X).

10:40 PM

@BalarkaSen $\sin(n\pi)$

Dude.

x is a set of n elements. P(x). well, wouldn't it be...all of the possible combinations of n?

plus the void set

or null set

or whatever its called.

empty set, there we go.

"All possible combinations of n"? What do you mean by that?

Fix some set X of n element rather than working abstractly. My favorite is X = {1, 2, ..., n}.

like, X = {x, y} the subsets would be {x}, {y}, {x,y}, and {}.

Right.

So for the X I said above, how many subsets (with the empty set and the set itself) are there?

Can you explicitly write down the number?

10:42 PM

n+2? that doesn't seem right.

Check examples for higher cardinalities and you'll easily convince yourself that that's not it.

→ 1 message moved to Physics Meta

because if you had 3 elements, like X={x,y,z} you could do {x}{y}{z}{x,y}{y,z},{x,z},{x,y,z},{}

Exactly right. Certainly not 5 elements!

n!+2?

no, ignore that while i check it =P

10:43 PM

Closer, but false. Don't guess, prove!

How are you supposed to guess this

well, okay. so we know there's going to be a minimum of 1: if n=0, {} is the only subset.

I guess if you write them down for $n=0,1,2,3$ it will be easy

that should be enough for the pattern

that's where n!+2 goes wrong...it doesn't work for n=0.

A good programmer can easily guess it. But I want a proof.

10:45 PM

@heather I gave you a hint

$\sin(n\pi)$?

but that makes no sense!

@BalarkaSen Do you want a bijection between the power set and you know what, or can one do induction?

@heather then it's likely false

okay, let me see.

@heather No, write down the cardinalities for $n=0,1,2,3$

i'm afraid I don't know what a cardinality is...*::googles::*

10:46 PM

You already have $1$ for $n=0$

@heather Number of elements.

@heather number of elements in the set

oh. okay.

for n=1, you have $2$.

{} and $\{n_1\}$

@0celo7 Sure, one can prove this is many ways.

But the most illuminating one ain't induction.

for n=2 you have 4

n=3 you have 8

10:48 PM

Wrong. Count again.

must have missed a case previously

@BalarkaSen Hmm?

Sorry, you've got it right.

I misread.

oh, okay.

now guess $n=4$

10:50 PM

um...

1, 2, 4, 8

what's the next number

12?

count and check if that's right

what?

i have no idea @0celo7, it's probably wrong.

10:53 PM

write out the power set for 4 elements

well, okay, there are several different things your counting in P...you're counting

@heather after counting the elements in the power set of {0,1,2,3}, you might think about this: what operation takes you from each number to the next one in 1, 2, 4, 8, P({0,1,2,3})?

the individual elements

the two element combinations, the three element combinations

Right!

and then in this case the whole set

10:54 PM

That's good thinking. What does that tell you?

AccidentalFourierTransform

the number of elements in P is exponentially larger as n increases?

yes

We're not looking for asymptotics, but some exact number. It gives you a systematic way to write down the number of elements if you know combination/permutation

But that is true.

the power set for four elements is P = {{},{x},{y},{z},{w},{x,y},{y,z},{z,w},{x,w},{y,w},{z,x},{x,y,z},{y,z,w},{x,y,w},‌{z,x,w},{x,y,z,w}} I think

16 elements

1,2,4,8,16,...

32?

Mhm

10:58 PM

this is a list of powers of 2

$2^n$

Correct. Now prove.

Proof?

okay...

::gulps::

let's see.

Your initial idea of counting the subsets of {1, 2, ..., n} by counting 0-elements (nullset), 1-elements, 2-elements, etc is useful

I don't know if you know permutation/combination though.

I don't really, but I can always google.

0-elements -> 1 element, always.

1-elements -> n elements, always.

11:00 PM

@BalarkaSen Well there is a simpler way to do it

That takes more time to learn than googling. What is "->"?

@DavidZ Sure, I just mean, that's one way

so then what's the "equation" for the number of 2-elements...

@BalarkaSen an arrow

I have no idea what you're trying to do

What does that arrow signify?

n=0 -> 0
n=1 -> 0
n=2 -> 1
n=3 -> 3
n=4 -> 6

Oh, you're counting n-elements subsets.

11:02 PM

@BalarkaSen i'm trying to break out how many of each "type" of element there is, and then sum it all up.

@BalarkaSen She's counting how many elements the powerset has. "x-elements -> f(n) elements" means the powerset of {1,...,n} has f(n) elements with size x

Nah, don't do that if you don't know the theory.

But you can always try. Look for a simpler way.

@BalarkaSen, no? But it seems like it's working.

simpler way...um.

because I said so?

=P

lol

I think that's called "proof by Chuck Norris" but it only works if you're Chuck Norris

@heather are you Chuck Norris?

0, 0, 1, 3, 6...$3^n-1$

@DavidZ lol no

11:04 PM

Once you tell me a quick, simpler way we (or someone else in the room) can talk about the harder way you were trying to come up with.

so, we've got, $1 + n + 3^n-1$

Bad guess

@heather $3^n-1$ isn't the formula you need there. If you haven't studied combinatorics (permutations and combinations), you're probably not going to figure it out that way.

@DavidZ It's my favorite way to prove the binomial theorem by combinatorics.

and then, let me guess, would the number of 3-elements in each thing be 4^n - 2?

or something like that?

11:05 PM

Nah

@DavidZ oh. =/

::looks for different way::

@BalarkaSen Eh, whatever floats your boat ;-)

@heather at least for the way I had in mind, a hint would be not to group the subsets by their length. Group them by whether or not they contain a specific element.

whether or not they contain a specific element...

maybe whether or not they contain a 1-element, 2-element, etc?

What do you mean by 1-element?

oh, no wait, you were talking about the subsets, not the sets.

sorry.

so, whether they contain $n_1$, $n_2$, $n_3$,..., $n_n$

hmm, well in n=0, there will be no subsets containing any of those, but there will be one containing nothing...the empty set

in n=1, there will be one subset containing $n_1$ and one containing nothing

11:10 PM

The fact that there are 2^n many n-bit binary numbers is relevant (which I suppose a programmer like you would know).

in n=2, there will be one subset containing nothing, two subsets containing $n_1$ and two subsets containing $n_2$

@heather well, one subset containing $1$. Maybe best not to use $n$ for both the number of elements in the set and the elements themselves ;-)

But generally speaking, you're right

i don't know how that leads to $2^n$ though, because there's overlap between the $n_1$ and $n_2$ sets

Did you see my comment? :)

It relates to DavidZ's way of thinking, in a way

Let me suggest breaking it down like this: in $P(\{n_1,n_2\})$, there are two subsets that contain $n_1$. Out of those, how many contain $n_2$?

Sir Cumference

11:16 PM

Any stellar astrophysicists here?

@DavidZ, one.

There never are

;-;

@heather Yeah, and out of the two subsets that don't contain $n_1$, how many contain $n_2$?

1

hmm...

a guess:

for n=3, there are 3 subsets that contain n_1, three that contain n_2 and three that contain n_3

and of these, two n_1's contain n_2, two n_2's contain n_3, and two n_3's contain n_1/n_2, and 1 of each contain both of the others

11:19 PM

Nope. {n1}, {n1, n2}, {n1, n3}, {n1, n2, n3}

All contain n1

4 contain n1...oh.

=/

Also, you really should be counting (1) how many contain n1 (2) out of the rest, how many contain n2 (3) out of the rest how many contain n3 etc etc etc

Otherwise you'd overcount

@BalarkaSen yeah, exactly

So do we know that it's $2^n$ yet?

0celo7, nope, because I'm slow =)

@BalarkaSen, oh, okay.

11:32 PM

Maybe this will help @heather: make a list of the subsets of $\{n_1,n_2\}$ which don't contain $n_2$.

{}, {$n_1$}

Does that look familiar?

n=1?

@heather meaning what? (I think you're right, but can you be more clear?)

the subsets of {n1, n2} that don't contain n2 are the subsets of {n1}.

11:34 PM

Yeah, exactly.

Now make a list of the subsets of $\{n_1, n_2\}$ that do contain $n_2$

{}, {n1},{n2},{n1,n2}

the number of subsets of {n1} times two

@heather I think you misread or something. I asked for the subsets that do contain $n_2$.

oh, only the subsets that contain n2.

{n2}, {n1,n2}

Yeah, now how do those relate to the subsets of $\{n_1\}$?

they're the complement of {n1}?

the two sets of subsets together add up to P(X)

wait, ignore that...

11:39 PM

@heather no... well, not unless you mean something different by "complement". But that's not what I'm getting at.

@heather That is true, though also not what I was getting at.

@heather Are you dead-set on this line of reasoning or are you open so something new

@0celo7 Well, we're getting really close

ok

@DavidZ, I don't know what you're looking for. the subsets that do contain n2 don't have any of the subsets of {n1}.

@heather True, well, think about this: starting from the subsets which don't contain $n_2$, what can you do to them to obtain the subsets which do contain $n_2$?

11:41 PM

I really dislike "counting" proofs like these

@0celo7 If I were trying to explain this to you I'm sure I'd be doing it differently ;-)

combine {n1} and {n2} and {} and {n2}?

@heather yeah

Note that in both cases, you're combining with $\{n_2\}$

right...

@DavidZ My proof uses induction and cartesian products, which she might not know...

11:46 PM

@heather OK, so consider this: you start with the subsets of $\{n_1\}$. Then from there, you can get the subsets of $\{n_1,n_2\}$ which don't contain $n_2$ by doing X, and you can get the subsets of $\{n_1, n_2\}$ which do contain $n_2$ by doing Y. Self-check: do you remember what X and Y are?

@0celo7 you taught me what a cartesian product is, i think.

@heather It's kind of the same thing I'm trying to explain

@heather then you should come to the dark side and learn my proof

X: is taking the empty set and n1 itself. Y: is taking the subsets of {n1} and adding n2 to each subset.

@0celo7 sure, after I go through this way with DavidZ.

@heather You're right on Y

11:49 PM

taking the empty set and the empty set and adding n1 to the second?

But for X, remember that you start with the subsets of $\{n_1\}$, which are $\{\}$ and $\{n_1\}$. What do you have to do to that collection of subsets to get the subsets of $\{n_1,n_2\}$ which don't contain $n_2$?

nothing?

Yeah, exactly. X is "do nothing".

So, to recap: you start with the subsets of $\{n_1\}$. Then from there, you can get the subsets of $\{n_1,n_2\}$ which don't contain $n_2$ by doing nothing, and you can get the subsets of $\{n_1, n_2\}$ which do contain $n_2$ by adding $n_2$.

right.

And together, those two collections of subsets make up all the subsets of $\{n_1, n_2\}$. Does that make sense?

11:52 PM

right.

yes, it does.

So now you have a procedure for starting with the subsets of $\{n_1\}$ and turning them into all the subsets of $\{n_1, n_2\}$. Clear?