Mathematics - 2017-01-31 (page 2 of 5)

arctic tern

03:00

@user400188 I have a backpack. One of the things inside it is a notebook. You know what "one of the things in [blah]" means.

user400188

so {1}∈{1,2,3} would be allowed but not {1,2}∈{1,2,3}?

DHMO

@user400188 no

1∈{1,2,3}

{1}⊆{1,2,3}

{1,2}⊆{1,2,3}

∈ means εlement

arctic tern

that's just going to confuse him/her more

DHMO

what did I say?

user400188

I am almost certain I have a textbook that uses ∈ fior element or subset

arctic tern

03:05

element yes, subset no

user400188

I have the book here with me now but I'm still looking for an instance where it is used

DHMO

@user400188 then that book doesn't follow the conventions that we use

just because something's in a book doesn't mean we all agree with it

arctic tern

the conventions I'm telling you about are almost universally accepted. either you're misremembering your book or your book is some combination of ancient or foreign.

user400188

well anyway. I will use ∈ for element and ⊆ for subset or element now. Thanks everyone.

DHMO

@user400188 ⊆ is subset not element...

user400188

03:07

cannot a single member of a set be considered a subset of it?

DHMO

no

arctic tern

apple is not a subset of {apple, oranges}

apple is not a set at all

user400188

but DHMO you just wrote {1}⊆{1,2,3}

DHMO

{1} is a set

@arctictern hey

user400188

ah I see now

arctic tern

03:09

@user400188 {1}⊆{1,2,3} is true, 1⊆{1,2,3} is false, {1}∈{1,2,3} is false, 1∈{1,2,3} is true

user400188

{1}⊆{1,2,3} differs from 1∈{1,2,3}. Though it feels odd that the {} have such meaning.

DHMO

@user400188 i like to think of sets as plastic bags

(but this analogy has problems on its own so don't view it as golden truth)

arctic tern

@user400188 actually, {1}⊆{1,2,3} and 1∈{1,2,3} are equivalent

user400188

! Thats what I was about to ask about

so do the {} on thier own give no new atributes to what is in them?

DHMO

@user400188 we say that X is a subset of Y, if every element of X is an element of Y

arctic tern

03:11

{1}⊆{1,2,3} means every element of {1} is an element of {1,2,3}, and since 1 is the only element of {1}, that's equivalent to saying 1 is an element of {1,2,3}, i.e. 1∈{1,2,3}.

DHMO

@user400188 that's right, it just says that it's a set

arctic tern

@user400188 no idea what you mean

DHMO

@user400188 "is an element of" is something fundamental that cannot be defined

in the ZF theory, at least

user400188

darn

I wanted to know if |is an element of" and "is a subset of when the subset only contains 1 element" were defined differently.

DHMO

"is an element of" is fundamental

the definition of "subset" doesn't care about the number of elements

so they are defined differently

in symbols (which would probably confuse you so just ignore it), we say $X \subseteq Y := \forall a: a \in X \implies a \in Y$

If $X$ only has one element, namely $b$, then $\forall a: a \in X \equiv a = b$

So $\forall a: a \in X \implies a \in Y \equiv \forall a: a = b\implies a \in Y$

have I gone too far @user400188

user400188

03:17

Whats the meaning of := and is ⟹ in this context meaning "implies" or soemthign else?
You haven't gone to far yet but it seems you are about to. Let me write all that down and work through it first before you continue

DHMO

$:=$ means "is defined to be"

$\implies$ means "implies"

user400188

does it have the property a⟹b = $\bar a$+b ?

DHMO

@user400188 I don't think you are supposed to know the definition of subset... that rigorously...

yes

user400188

Ok cool. Also I like to know things rigorously. And I don't have to know anything here becuase I'm doing this recreationaly.

DHMO

oh, nice!

in that case, do you think you have enough mental power to go over the ZF axioms lol

user400188

03:22

I'd raryher wait till I understand the meaning of all the symbols first.

DHMO

sure

user400188

For instance, does the : in ∀a:a∈X⟹a∈Y extend the whole way? i.e. ∀a: (a∈X⟹a∈Y)?

Secret

nvm, I think I got that now, f(A) is of course =f(A), thus f is indeed a bijection between A and f(A)

DHMO

@user400188 ya, I was too lazy to put up the parentheses :p

@Secret hi, do you know how empty set is defined?

user400188

weird; if X does not exist then the statement flase ⊆ Y is true

or did I break something?

DHMO

03:24

what do you mean?

Secret

@DHMO $\emptyset = \{a : a \not\in \emptyset\}$ ?

DHMO

hey, that's circular

user400188

I wrote implies like this a⟹b = a¯+b and got: ∀a: (NOT (a∈X) OR a∈Y)

DHMO

@Secret I mean in terms of the axioms, but I feel that it would also have to be circular

@user400188 yes, continue

user400188

then concluded that if a∈Y was false and so was a∈X. Then false ⊆ false.
Hang on; that actualy makes sense

Secret

03:28

9

Q: What is an Empty set?

We define the term "Set" as, A set is a collection of objects. And an "Empty set" as, An empty set is a set which contains nothing. First problem I encountered: How the definition of "Empty set" is consistent with the definition of "sets" if "Empty set" contains nothing and a "set" ...

It seems it is indeed defined as what I have wrote previously

(or you can use $\not\exists x : x \in \emptyset$

DHMO

@Secret thanks, but as I said, I want to construct the empty set from the axioms

@user400188 have you confused "a∈Y" with "Y"?

user400188

still; if I instead had a∈X was false and a∈Y was true I would get false ⊆ true which is weird.

DHMO

"a∈Y" being false doesn't mean "Y" is false

user400188

Ah yes your right I have

Secret

von neumann or what axioms?

DHMO

03:29

@Secret ZF

user400188

when I right Y I mean a∈Y.

DHMO

@user400188 then how can you say false ⊆ true?

Secret

Axiom schema of specification

In many popular versions of axiomatic set theory the axiom schema of specification, also known as the axiom schema of separation, subset axiom scheme or axiom schema of restricted comprehension is an axiom schema. Essentially, it says that any definable subclass of a set is a set. Some mathematicians call it the axiom schema of comprehension, although others use that term for unrestricted comprehension, discussed below. Because restricting comprehension solved Russell's paradox, several mathematicians including Zermelo, Fraenkel, and Gödel considered it the most important axiom of set theory. ...

Isn't that axiom basicallty set builder notation?

DHMO

@Secret yes

user400188

By writing; a∈X = False, a∈Y = True
then X⊆Y := ∀a: False OR True
Since the false coresponds to X and the True Y I get
false ⊆ true

Secret

03:32

Axiom of empty set

In axiomatic set theory, the axiom of empty set is an axiom of Kripke–Platek set theory and the variant of general set theory that Burgess (2005) calls "ST," and a demonstrable truth in Zermelo set theory and Zermelo–Fraenkel set theory, with or without the axiom of choice. == Formal statement == In the formal language of the Zermelo–Fraenkel axioms, the axiom reads: ∃ x ∀ y ¬ ( y ∈ x ) {\displaystyle \exists x\,\forall y\,\lnot (y\in x)} or in words: There is a set...

user400188

wait I made an error one sec

Secret

ok I felt like the above link will confuse user400188 because $y \in x$

DHMO

@user400188 no, the "false" does not correspond to "X".

user400188

actuakly I think I am ok with $\in$ and the other one having different meanings depending on the disipline now

DHMO

You cannot replace "X" with "false"

"X" is a set

"false" is a logical state

@Secret I'm talking to you, not wiki

user400188

03:34

I replaced a∈X with false. AKA a is not an element of X

also there is a missing negation in that above thing I wrote

DHMO

@user400188 then you cannot replace $\implies$ with $\subseteq$

user400188

I dont think I did. But if so where would I have done it?

DHMO

@user400188 you said "$a \in X \implies a \in Y$", and then said "false $\subseteq$ true".

you changed the middle symbol as well

$\subseteq$ is for sets

user400188

oh no; what I did was write a∈X⟹a∈Y and changed it to NOT(a∈X) OR a∈Y

DHMO

don't you see that you wrote " false ⊆ true"

user400188

03:37

then when I followed that through to the definition of ⊆ I got what you were talking about

its shoul;d actualy be true ⊆ true becuase I forgot one negation

DHMO

you're still misusing the symbol ⊆

user400188

one sec

DHMO

X⊆Y means that ∀a:(a∈X⟹a∈Y)

if you wrote "true ⊆ true", that would mean "∀a:(a∈true⟹a∈true)"

Secret

Axiom of specification gives:
$\emptyset = \{u \in w | (u \in u) \wedge (u \not\in u)\}$
But I don't understand, aren't $u$ an element of some set $w$ thus one cannot write something along the lines of "u is (not) a member of u"

user400188

X⊆Y:=∀a:a∈X⟹a∈Y
To X⊆Y:=∀a:NOT(a∈X)+a∈Y
Then I substitute true for a∈X and true for a∈Y
which gives X⊆Y:=∀a:False+True
and then I am able to write false ⊆ true

DHMO

03:40

@Secret in ZF everything is a set

@user400188 I do not see how the last line follows from the rest of the lines

user400188

Thats probaly where I made the mistake then

I jusrt wanted to know if it could be done really

Secret

ugh, I am obviously not good at set theory...

user400188

If instead I stopped at X⊆Y:=∀a:False+True
How would I continue on?

what would be the definition of X⊆Y in this case?

DHMO

@user400188 I do not see what you are trying to do, nor why you are substituting true for a∈X and true for a∈Y

user400188

I did in fact do that

thing is a "implies" b is the same as NOT(a) OR b

DHMO

03:43

yes it is

user400188

so one of the ture's becomes a false

oh sorry I read your comment wrong

I substituted them that way to see what happens. Just to get a feel for what the formula meant

DHMO

@user400188 but there is a "for-all" quantifier in front

and it is not extraneous

@Secret then who is?

user400188

I left the for all there becuase I was unsure how to removed it.

DHMO

@user400188 maybe you would understand the definition better if I translate it into English?

Secret

@DHMO alessandro, cause he is the only one who seemed to be able to talk about CH and AoC stuff confidently?

DHMO

03:47

@Secret ok

user400188

Ok; go ahead

DHMO

@AlessandroCodenotti I don't understand how the empty set can be constructed from the ZF. They claim that I can do it from Axiom of Infinity and Axiom of Subsets, but I feel that it would be circular, since Axiom of Infinity uses the empty set.

@user400188 X⊆Y ≡ ∀a:(a∈X⟹a∈Y)
"X is a subset of Y" means that "for any object a, (the fact that a is an element of X implies the fact that a is an element of Y)"

user400188

so in english; what does one do when a is not an element of X?

The rest all makes sense in english. Its just that one case

DHMO

@user400188 what do you mean by "what does one do"?

user400188

how would I describe it or use it I guess

DHMO

03:51

I don't understand your question

user400188

Perhaos it would be best phased in the following way:

DHMO

sorry, be back in a moment

user400188

ah ok.

DHMO

you can continue

user400188

What I am having trouble with is a⟹b can be written as $\bar a+b$. So in english it would translate to:
"X is a subset of Y" means that "for any object a, (a is not an element of X or a is an element of Y)"

DHMO

03:55

yes

user400188

but if a is not an element of x then how is x an element of y?

they dont have the a in comon when read this way

DHMO

is the second "x" supposed to be "a"?

user400188

no thats supposed to be an X. I am reading from the left hand side of the definition

DHMO

you mean how is X a subset of Y?

user400188

Ah yes I mean that. Sorry that I made that mistake again

DHMO

03:58

let's use an example to demonstrate the definition

user400188

ok

DHMO

X = {d,e} and Y = {d,e,f}

sorry, a moment

user400188

sure

DHMO

we see that X is a subset of Y

let us verify if indeed "for any object a, a in X implies a in Y"

or equivalently, "for any object a, a not in X or a in Y"

let us consider the object d, that is, when a=d.

we see that "a not in X" is false and "a in Y" is true, so the whole thing is true

let us consider when a=f, can you make a similar judgement?

user400188

not a in X is true and a in Y is also true

DHMO

04:04

so the whole thing is still true

what about when a=g?

user400188

not a in X is true and a in Y is false but the whole thing is still true

DHMO

nice

so we have verified that definition for this case, agreed?

@Secret are you interested in set theory?

Secret

not very much ,given I stil yet to get my head around infinite sets in munkres

DHMO

alright

Secret

and my function proofs are stupid

user400188

04:07

I mean, we showed that is results in true for a few cases and I understand what the other cases will give if thats what you mean by verified

DHMO

@Secret how can you be interested in bijection if you are not interested in set theory?

@user400188 yes, that is what I mean by verify

user400188

Thing is; proving a statement as a whole to be true doesn't seem to have the same meaning. The definition could have just been X⊆Y := True and we would have the same situation.

Secret

@DHMO Well, I only know just enough set theory to make sense of functions, but I have never get into the hardcore stuffs like $\sigma$ algebras, lesebegue measures yet. Also I have not reach the AoC chapter of Munkres thus technically I know nearly nothing about AoC

Mike Miller

Is 2^n choose k always even?

DHMO

@user400188 so let us deal with another case, when X={d,g} and Y={d,e,f}

proving it requires much rigor, which is why we are only studying some cases @user400188

just to understand the intuition behind the definition

@MikeMiller I believe so

though proving it would require some discussion on the number of 2 in prime decomposition

@user400188 can you prove that X is not a subset of Y?

arctic tern

04:12

@MikeMiller apply lucas theorem (or adapt a weaker version of the proof of lucas if you want to be elementary)

user400188

Unfortunately I'm not sure how I would go about a formal proof of that, but the basics would be that X contains g and y does not so X is not a subset of Y

Semiclassical

Student emails me asking why there's equations on the sample quiz for this week which haven't been covered in class

DHMO

@user400188 you just did a formal proof

kind of

Secret

$n!$ is always even for $n\ in \mathbb{N}$ as you always will multiply 2 somewhere. Since even*any=even and 2 is even, it follows that all factorials are even

Semiclassical

Reply: Sure, they haven't been covered in this course. That's because this is the second semester of the course, and those equations were a huge part of first semester.

DHMO

04:14

@user400188 so can we agree that the definition is not equivalent to "X subset Y := true"?

Semiclassical

The extent to which students try to decouple first and second semesters of intro physics always amazes me.

user400188

yes

DHMO

@secret but 2^n choose k is not the same as n!

@user400188 so do you have any questions?

Secret

I have not finished yet as my thinking ran into a roadblock

DHMO

@Secret so am I correct that your primary interest is in algebra?

Secret

04:16

Yes, specifically properties of elements in an algebra

and their geometric implications, if any

Nearly every interest of mine (except for quantum stuff) all have one common goal in mind: They help in worldbuilding

In particular, weird algebraic structures allow me to rationalise alien geometries

Semiclassical

So...you use a human creation to figure out what aliens might create? :)

Secret

You might as well said everything I learnt (except quantum stuffs and chemistry, which is perhaps the only genuine interest that is not tied to scifi) all feed back to creating scifi and making sense of anything that people call weird

user400188

Ok one question:
For the case in which X={d,g} and Y={f,h} and we let a=d.

in such a case, if a is made to be f

X⊆Y comes out as true

no darn it i subs wrong again

Secret

Such aim also means I tend to ask about very weird things because I use those weird things to understand how normal the normal things are.

In particular, pathological counterexamples often help me to visualise the nice results in some theorems

DHMO

congratulations @user400188

user400188

04:22

it is strange that X⊆Y=True when X does not have any common element s with Y

DHMO

@user400188 I don't agree?

user400188

but if it were asked as a question: is X⊆Y? the answer would be true when X does not have any elements in common with Y

Secret

ok back to the problem: Well, $2^n$ choose $2^n$ is $1$ which is odd, thus we have a counterexample

DHMO

I don't think so @user400188 consider X={d} and Y={e}, then X is not a subset of Y

arctic tern

@Secret obviously you have to pick k not trivial

user400188

04:24

if we let a=e in your case

then a is an element of Y is true and therefore the statement as a whole is true

DHMO

@user400188 you forgot that we require the statement to be true for all a

user400188

ah

Now I see the mistake I was making. Thank you

well at least now I will know the definition well.

DHMO

nice

user400188

I hope I didn't tire you all out. Thanks again though.

DHMO

@user400188 so do you have other questions?

user400188

04:30

only unrelated ones

DHMO

go ahead

Secret

uh, $2^n-k$ can be odd or even, and for $(2^n-k)!$ it must be even as all factorials contains $2$ except $0!$ and $1!$. Now $(2^n-k)! < (2^n)!$, and permutation is defined as ${}^mP_r=\frac{m!}{(m-r)!}=m(m-1)(m-2)...(m-r+1)$. Plug $m=2^n$ and $(m-r)=2^n-r$, then the even term $2^n$ always survives, thus $2^n$ choose $k$ is always even for $k\neq 2^n$

user400188

well, I was told somewhere that = and ≡ are different. Somewhere else I was told that $\leftrightarrow$ and = are the same.... Then I was told in another place that ≡ and $\leftrightarrow$ are the same. Obviously one of these definitions is wrong or out of context.

DHMO

@Semiclassical @arctictern are you familiar with set theory?

user400188

I want to know how they differ and if any are the same

arctic tern

04:32

@DHMO what's your question

DHMO

@arctictern construction of empty set from ZF axioms

arctic tern

iunno

DHMO

@user400188 context matters much

Semiclassical

same. I don't know how the empty set is constructed in ZF, and more importantly I'm not really interested in it.

DHMO

ok thanks

user400188

04:35

@DHMO Indeed. I suppose what I want to know the most is how they differ in set theory or logic.

DHMO

@user400188 in set theory only = is used to denote equality of sets

in logic = doesn't mean much, and $\equiv$ and $\iff$ are equal

(you can occassionally see logic in set theory and vice versa)

user400188

thats why I asked for both

DHMO

so are we clear

user400188

hmm; so lets say I have a function and its domain and range match another function but they differ in shape. Can I then write they (along with their function definition) are equal?

there sets would match

arctic tern

@Secret @MikeMiller the elementary abelian group $\Bbb Z_2^n$ acts regularly on itself, and this induces an action on the set $\Gamma$ of $k$-subsets of $\Bbb Z_2^n$. under this action of $\Bbb Z_2^n$ on $\Gamma$, the only time there can be an orbit of size $1$ is when $k=2^n$ (quick exercise). otherwise, all orbits must be even, hence $|\Gamma|=\binom{2^n}{k}$ is even.

DHMO

04:38

you moved to another context @user400188

user400188

its a bit of a grey area for me becuase i was introduced to sets with function definitions

DHMO

@user400188 their domain and range are equal but the functions themselves are not

user400188

I see. That basicly answers the question.

Although in set theory is there a different meaning for $\equiv$?

DHMO

not that I am aware of

user400188

I've heard it read out as "defined as" But I don't see the difference between this and =

I see

DHMO

04:41

well, = is for objects

triple bar would be for statements

I used triple bar for the definition of subset above

user400188

I noticed

thats what put the question in my head

I'm also a bit confused about the difference between object and statement. They seem the same.

DHMO

a statement can be true or false

user400188

and an object cant?

DHMO

pretty much

user400188

I fear I have always read "object" as "a statement about the object"

or a statement about its existance

DHMO

04:44

hmm...

i dont know about this then

user400188

it's a strange distinction; and I don't think I will ever know the difference.

anyway. Thanks again for the help @DHMO @arctic tern. I'll be heading off now.

DHMO

bye

Mike Miller

@arctictern thanks

Secret

05:36

I am not very sure if my proof is rigorous enough, however

Akiva Weinberger

@Secret You should write your math images in LaTeX

Secret

One problem is I tend to mix up orbits Gx with the (insert name if any) gx, since the latter corresponds to the intuitive meaning of orbits and trajectories (i.e. g pushes x around in the set)

Let $g,x,y \in G=Z^2_n$ and $x$ in k-subset of $G$. Then:

Given regular action
$gx=hx=>g=h$,
$gx=y$ unique $x$

$Z_2$ means $a(ax)=x$ for some $a$ in $Z_2$, and $a(x)=e$ or $x$

$Z_2^n$ means for all $s \in G$, $s(sx)=x$ and $s(x)=y$ or $z$ and there is a $t \in G$ such that $t(y)=x$ or $y$.

The case $t(y)=y$ corresponds to an orbit of period 1 (fixed point)

while the case $t(y)=x \implies y=t(ty)=t(x)$ corresponds to an orbit of period 2 (transposition).

For $k=2n$, $t(x)= y$ or $x$ for all $y,x \in G$. Thus $t(G)=G$ and is a fixed point. Hence all orbits are fixed points.

I think the reason $Z_2^n$ has this property is not because that its action on itself is regular, but because every element in it is an involution wrt one of the $Z_2$ (in particular, local identities are trivially involutions). That ensures you have period 2 orbits

But I might be wrong because of how I tend to mix up orbits and gx

arctic tern

it's the transitivity that's important. let $\Gamma$ be the set of $k$-subsets of $\Bbb Z_2^n$. if $X\in\Gamma$ is a fixed point, then $X$ is a $k$-subset of $\Gamma$ stabilized by $G=\Bbb Z_2^n$, which means it's an orbit of $G$ acting on itself which means it must be $G$ itself which means $k=2^n$.

your sentence "every element in it is an involution wrt one of the Z_2 (in particular local identities are trivially involutions). That ensures you have period 2 orbits" means nothing to me

DHMO

05:57

@akiva hola

sabes ZF?

estoy tentando de construir el empty set de los axiomas

Secret

Your proof is a lot cleaner, and you let the collection $\Gamma$ that takes account of all possible $k$ subsets

For that sentence you highlighted. I am trying to describe the following observation in the klein 4 group:

The red boxed always give me an impression that they "looks" like $Z_2$ in isolation

Semiclassical

you'd also get that if you arranged it as e b a c, or as e c a b for that matter.

the klein four-group is just Z_2 x Z_2, after all.

Secret

This might be related to the "adjoining an identity element" that arctic tern discussed a month ago

Semiclassical: and yes

I don't know how to describe the red boxes (and the other boxes that can be obtained according to semiclassical's suggestion on the rearrangement). They are not really $Z_2$ but they have a table that look the same as $Z_2$.

Semiclassical

and then one just has the further fact that Z_2 x Z_2 / Z_2 ~= Z_2

the Klein four-group contains the Z_2 subgroup <b>, so one can quotient by this (getting Z_2 again).

The same should work for any Z_{2n}.

Rajesh Dachiraju

06:14

Can we say : $$\int_0^{\lambda}\left|\frac{A\sin(at) + B\sin(bt) + C\sin(ct)}t\right|dt \sim K\log(\lambda)$$

Secret

06:55

When doing $Z_2 \times Z_2 / Z_2$ I got the cosets {ee,ea}={e,a}, {ae,aa}={a,e}, {be,ba}={b,c} and {ce,ca}={c,b}, hence the set of all cosets {{e,a},{b,c}}. Then I am not sure what to do next to show that the elements {e,a} and {b,c} behave like those in $Z_2$

6

Q: What is a coset?

Honestly. I just don't understand the word and keep running into highly technical explanations (wikipedia, I'm looking at you!). If somebody would be so awesome as to explain the concept assuming basic knowledge of group theory and high school algebra I would be delighted.

abstract-algebra group-theory abelian-groups

Ah I see, so that's why those red boxed things popped up everywhere. They are cosets

So that means, all of these boxes (and more have not highlighted) are cosets and this is $\mathbb{Z}_3 \times \mathbb{Z}_2$

Stan Shunpike

07:11

hello

Secret

Quotioning this by $\mathbb{Z}_2$ I get {{1,7},{2,3},{5,6}} which is isomorphic to $\mathbb{Z}_3$

Quotioning by $\mathbb{Z}_3$ I get {{1,2,5},{3,6,7}} which is isomorphic to $\mathbb{Z}_2$

But then, this group is different from the other one on top, but not at the level of cosets and quotient groups, so what exactly is the difference in terms of some group structure?

hmm... their subgroups are different, but isomorphic to $\mathbb{Z}_3$ (Underlying set {1,2,5} vs {7,2,5}) is this the only difference?

Kasmir Khaan

07:40

hi chat

How to learn to type in latex form ?

Tobias Kildetoft

08:18

@KasmirKhaan Put math between dollar signs and look up the symbols you need, for example using detexify or the not so short introduction

Kasmir Khaan

hi tobias

I know few things to do , but where can i find all commands?

am very slow at typing , sometimes i dont post questions because of that

Tobias Kildetoft

@KasmirKhaan That is just a matter of practice

most commands are listed in the introduction, and as I said, there is also detexify which can be good for looking up a specific symbol

Kasmir Khaan

introduction where?

Tobias Kildetoft

other than that, if you can describe what you want to do in words, there is usually a question already answered on the tex stackexchange

the not so short introduction to LaTeX

Kasmir Khaan

Okay thank you Tobias :)

Buddha

08:31

I think @Calvin Lin is fat.

robjohn

1690

Q: MathJax basic tutorial and quick reference

To see how any formula was written in any question or answer, including this one, right-click on the expression it and choose "Show Math As > TeX Commands". (When you do this, the '$' will not display. Make sure you add these. See the next point.) For inline formulas, enclose the formula in $......

discussion faq mathjax reference

Kasmir Khaan

@robjohn Thank you John :)

Secret

Hey guys, I need some help on how to find injective functions between two uncountable sets. Specifically, Munkres Ch. 1 Section 7 Q7. Since in Q6, I have proved the Schoeder Bernstein theorem, and in Q7, by inspection, the set $E \subset D$. I know the first step in solving Q7 is to find an injective function from $D$ to $E$ so I can use the theorem in Q6a.

I first attempted to map all functions in set D that has the image set {0,...} where the rest of the elements are not necessary zero to the subset of functions in E that has image sets {..,x_i,...} where $x^i=1$ and the rest are zeros …

$D$ is the set of all functions $\mathbb{Z}^+\to \mathbb{Z}^+$ and $E$ is the set of all functions $\mathbb{Z}^+ \to \{0,1\}$. both are known to be uncountable

Secret

09:14

Suppose I don't use cardinal arithmetic, how can I get an injective function from D to E (as I cannot even use the diagonal elements since there are as many of these as the enumerations)?

Secret

09:38

Ok let $a,b \in \mathbb{Z}^+$ and $c \in \{0,1\}$. Then $D=\{f|f: a \to b\}$ and $E=\{f|f: a \to c\}$. In $D$, for each $a$ I have countably many choices of $b$ and in $E$, for each $a$, I have 2 choices of $c$. It is known that $D$ and $E$ are uncountable.

For $D$, I can also consider the domain to be a union of subsets $K_n=\{f|f: a \to \{n,n+1\}\}$. by recursively define $\{n,n+1\}$ and start with $\{0,1\}$ as the base case. Then there are countably many such $K_n$. Since $D=\bigcup_{i\in \mathbb{Z}^+}K_i$ and a countable union of uncountable sets are uncountable, $D$ is uncountable as …

SteamyRoot

Have you done exercise $3$ yet?

Secret

10:03

$\mathscr{P}(\mathbb{Z}^+)=\bigcup_{k \in \mathbb{Z}^+}S_k$ where $S_k$ are $k$ subsets of $\mathscr{P}(\mathbb{Z}^+)$. I can thus map all $1$-subsets (which there are $|\mathbb{Z}^+|$ many of them) to the sequences $\{...,x_i,...\}$ where $x_i=1$ and all the rest are zeros, $\{...,x_i,x_j,...\}$ for $2$-subsets (which there are $|2\mathbb{Z}^+|$ many of them, the same as $\mathbb{Z}^+$ because a bijection can be established between $\mathbb{Z}^+$ and $n\mathbb{Z}^+$, for all $n\in\mathbb{Z}^+$)

SteamyRoot

o.O

Tobias Kildetoft

@Secret No, the powerset does not have that form

SteamyRoot

That is the least intuitive attempt at this question I've ever seen, probably.

Secret

I thought power sets are set of all subsets, thus $\mathscr{P}(\mathbb{Z}^+)$ must have k-subsets from the emptyset all the way up to the $\mathbb{Z}^+$ itself?

(NB Munkres have not said much about power sets before section 7. other than it is a set of all subsets, and said that the name for the power set will be justified later (which I suspect is in this question)

SteamyRoot

The definition as the set of all subsets is plenty for this question

DHMO

10:10

@Secret there are n(n-1)/2 many 2-subsets of a set with cardinality n

SteamyRoot

Let $A \subseteq \mathbb{Z}^+$.

For any $z \in \mathbb{Z}^+$, either $z \in A$ or $z \notin A$.

That's a pretty big hint on solving the exercise.

DHMO

@SteamyRoot I don't understand why his bijection is invalid

oh, I understand now

@Secret you assumed finite support

you never accounted for the set {1,3,5,7,9,...}

Secret

O yes, forgot there are many infinite subsets of an infintie set with same cardinality...

DHMO

@Secret finite support is how you can prove that 2^omega = omega...

Sophie

the apple quarterly is in 10 hours. I'm excited

SteamyRoot

10:15

ew, apple

Sophie

it's okay

I'm expecting a bust

DHMO

@Secret there's a proof that forall S: |S| < |P(S)|

Secret

@DHMO Yup, it's theorem 7.8 in Munkres

DHMO

@Secret it is on proofwiki as well

Secret

10:56

Define a function $h$ as follows: Given any subset $M \subset \mathscr{P}(\mathbb{Z}^+)$ $M=B_i\cup A_i$, for some $i \in \mathscr{P}(\mathbb{Z}^+)$ where $B_i \subset A^c$ and $A_i \subset A$. Then by induction from $0$ to $\omega_0$, step through each entry of the subset $M$. If the nth entry is in $A$, then the nth entry in the binary sequence ({x_i}) becomes 1, otherwise it is zero.

By doing this, all subsets of $\mathscr{P}(\mathbb{Z}^+)$ will be labelled by a unique sequence (in particular $\emptyset \to (0,0,...)$, $\mathbb{Z}^+\to (1,1,...)$. All $k$-subsets will map to $(...,\{x_i…

Secret

11:08

Elaboration: this includes sequences where consecutive entries not necessary zero, thus accounting for all the infinite subsets that are not $\mathbb{Z}^+$ itself

The above proof can be generalised to show bijective correspondence of $\mathscr{P}(\mathbb{Z}^+)$ and $n^{\mathbb{Z}^+}$ ($n$ countable) by partitioning $\mathbb{Z}^+$ with $n$ subets $A_j$ such that any given subset $M=\bigcup_{j \in n} A_{ji}$ and $A_{ji}\subset A_j$

sorry typo: $\omega_0$ should be $\aleph_0$

Secret

11:36

However the above strategy will not work for Q7 because a tuple can have repeated entries (unlike sets). It is clear there are countable choices I can make for each entry and there are countable entries, but how should I cram the countable choices into binary sequences?

YOUSEFY

Hello, In this article from wikipedia titled "Algorism" (en.wikipedia.org/wiki/Algorism) I don't know what this means? does it mean that Abu Jafar made one as 1, two as 2, three as 3, etc is the way he means or something else

s.harp

@YOUSEFY an example:
33+28 is 61 because: add 8 and 3 to get 11 and carry the one to the left, now add 3, 2 and the 1 from before to get 6. The result must be 61

At least thats how I understood what the article is talking about

Transcript for

$Mathematics$ Mathematics