Basic Mathematics - 2020-09-26

user21820

1:03 AM

← 26 messages moved from Logic

geocalc33

I have a basic math question

user21820

@EM4 @MaliceVidrine already gave you the intuitive explanation for why this pair encoding is sufficient. But if you want to really see the formal wheels turning rigorously, you should explicitly prove (over pure FOL) the sentences that capture that encoding.

Encoding: ∀x,y ∃!p ∃u,v ( p={u,v} ∧ u={x} ∧ v={x,y} ).

Equivalently: ∀x,y ∃!p ( ispair(p,x,y) ) where ispair(p,x,y) ≡ ∃u,v ( p={u,v} ∧ u={x} ∧ v={x,y} ).

Note that all those "{...}" notation can be further expanded. For example, p={u,v} ≡ ∀t ( t∈p ⇔ t=u ∨ t=v ).

Decoding: ∀p,p' ∃x,y,x',y' ( ispair(p,x,y) ∧ ispair(p',x',y') ⇒ ( p=p' ⇔ x=x' ∧ y=y' ) ).

Encoding says that for every x,y there is a unique pair p under this encoding.

Decoding says that for every pairs p and p' that encode ⟨x,y⟩ and ⟨x',y'⟩ respectively under this encoding, they are equal iff x=x' and y=y'.

These two are easy exercises in pure FOL (first-order logic).

So you should try to prove them to convince yourself that everything works perfectly!

user21820

2:05 AM

→ 19 messages moved to Sandbox

geocalc33

lol

now the messages aren't here

user21820

@geocalc33 You left, so I moved it off to the Sandbox because in my opinion it's not a real question (yet).

geocalc33

okay fair enough :(

user21820

Once you make your question mathematically precise, I suggest you post it in the main chat-room.

geocalc33

ok

user21820

2:11 AM

@geocalc33: Anyway, if you are having trouble making your questions mathematically precise, then I actually suggest you put those questions aside and first learn basic FOL (first-order logic).

And that would be more suited for this room.

@geocalc33 The messages are still there; click on "19 messages" to see them.

Stupid question inc

11:38 AM

well it has 8 pages long proof but I don't understand. Why this proof are like it came from God's mind it is from like thin air.

The frist 2 pages has wierd notation that I don't understand.

what does (k,l)=1 mean? does it mean g.c.d is 1?

And that summation notation is something that I have never seen.

and what relation does prime and exponential series bounded below has a relation?

what I know until now is that let's say $\pi(x)$ is size of prime number then $\frac{x}{log(x)}$ is order of magnitude of $\pi(x)$

I don't know but my book says $A\frac{x}{log(x)}<\pi(x)<A\frac{x}{log(x)}$

and it says two $A$'s are naturally not the same (scratches head with confusion)

It is named Tchebychef's Theorem

which I haven't proved yet.

jstor.org/stable/pdf/…

This is the website of the proof which I gave you picture of.

user21820

12:01 PM

@Stupidquestioninc If your book really says what you wrote, then your book is a bad book.

Stupid question inc

@user21820 well yes you can check it was written by hardy

user21820

That is false.

Stupid question inc

And I don't know what the hell does order of magnitude of size of prime means. I blindly assumed it as approximately equal now I don't think I understand what it means. Do you know what it means?

user21820

@Stupidquestioninc Of course I do. You don't, simply because you don't properly understand asymptotic notation.

And just to make sure everyone is clear, Hardy does not write such rubbish as (you said) was in your book.

Stupid question inc

@user21820 I mean book was written by hardy also Wright so I don't know who is the culprit.

user21820

12:07 PM

@Stupidquestioninc If it was really written by Hardy then (almost surely) you are not quoting it accurately.

Stupid question inc

@user21820 wait I don't think big O notation is defined as same order of magnitude it was the rubbish as book states $A\phi<f<A\phi$ asserts that '$f$ is of the same order of magnitude as $\phi$'

@user21820 Well I am not trolling let me give actual picture of the page.

user21820

@Stupidquestioninc As I already said, I do not believe that you are accurately quoting your book. Both here and earlier. Do not continue unless you give me a word-for-word quote.

@Stupidquestioninc Please do.

Stupid question inc

amazon.com/Introduction-Theory-Numbers-G-Hardy/dp/0199219869 this is the book

user21820

@Stupidquestioninc Ok so I can confirm that it is a bad book. Please do not refer to it if you want to learn rigorous mathematics.

The wikipedia page I gave you a link to earlier is much better (scroll down to "Formal Definition").

Stupid question inc

@user21820 there is even a foreword by Andrew wiles on it lol

user21820

12:15 PM

@Stupidquestioninc Well, it doesn't matter who write a bad book. A bad book is a bad book. It may be amusing, but that's just too bad.

Stupid question inc

this is such a waste of money

user21820

It doesn't imply that the authors don't know the mathematics.

It just implies that you can't learn well from it.

Anyway, look at the formal definitions on the wikipedia page.

And (if you don't mind) please avoid starring comments unless they are really super. Not all wikipedia pages are good, but this one at least does its job quite well. =)

In particular, you want the definition of Θ:

Personally, I would not even use "=" like wikipedia did, but that's not really their fault because almost everyone except pedantic people like me do so.

I would write:

> f(n) ∈ Θ(g(n)) as n∈ℕ→∞ iff ∃c,d>0 ∃m∈ℕ ∀n∈ℕ ( m≤n ⇒ c·g(n) ≤ f(n) ≤ d·g(n) ).

Note that this is for n→∞. The meaning of the asymptotic notation is of course different if you have a different asymptotic limiting condition.

Stupid question inc

i.stack.imgur.com/ngXSQ.jpg yes this is defined in my book. It's kinda same as wikipedia one.

@user21820 that's pretty long notation to digest

user21820

Note that I write "f(n) ∈ Θ(g(n))" rather than "f(n) = Θ(g(n))" because it is not actually equality, which is an abuse of notation as I said above. The reason I still say this wikipedia page is good is because it actually mentions this issue (search for "abuse of notation").

@Stupidquestioninc Sorry your book is completely wrong. My definition (and wikipedia's) is correct. Your book's definition in terms of a simple limit is WRONG.

Stupid question inc

@user21820 yes the issue is also mentioned in book

user21820

12:24 PM

Doesn't matter because its definition is wrong.

Stupid question inc

@user21820 sad to hear that ;_;

user21820

For a simple counter-example to your book, (2+cos(n)) ∈ Θ(1) as n→∞.

Stupid question inc

it looks like limit definition from analysis

user21820

Hang on, it depends on what they mean by "~". The limit definition does not give "Θ", and that is what the counter-example shows.

And the useful notation is usually "Θ" rather than your book's "~".

So if they do not use "~" in the same way as "Θ", I retract my claim that it is wrong. I had assumed you were claiming they defined "Θ" that way.

It simply is not the same.

@Stupidquestioninc: Note that the original question you were asking about the PNT is actually involving "Θ", not "~".

Incidentally, I just saw that wikipedia has a footnote under that table saying that Hardy's "Ω" isn't even the standard one, so you should be careful when reading his earlier(?) stuff.

That's why ultimately the only way to be properly rigorous is to explicitly give the formal logical definition as I did above (and as wikipedia did), so that there is no uncertainty as to what we are doing.

Stupid question inc

I was aware the book is not so rigorous.

user21820

12:34 PM

Anyway, just make sure you fully understand the logical definition I gave you.

PNT states π(n)·ln(n)/n → 1 as n → ∞, which implies π(n) ∈ Θ(n/ln(n)) as n → ∞, which was what you were originally asking about.

Ok I got to go now.

Stupid question inc

Ok I will take time to digest it. This kinda game me depression.

@user21820 Ah yes that is also written.

@user21820 Bye =)

Threnody

1:19 PM

Can every set be turned into a cyclic group with the correct operator?

Furthermore - when we prove that the group identity is unique, we're looking at it from the tools of group theory, i.e. as far as the group axioms go, the identity "elements" are indistinguishable from each other. I have perhaps a small misconception.

Suppose you're given a set and a binary operation that respects closure, associativity, and there is a chosen element that behaves as the identity.

However, it just so happens that from a set-theoretic perspective the inverse is not unique. It is guaranteed to exist, but not guaranteed to be unique.

I noticed that the existence of the identity in group axioms is often not "enforced" to be unique, i.e. no ! in the quantifier.

user21820

@Threnody Well... just go by definition. What is a cyclic group? Then you know whether every set can underlie a cyclic group or not.

Threnody

A cyclic group is a group that is generated by a single element, correct?

user21820

Yes. So do some work. And prove something about the size of the group...

@Threnody That doesn't make sense. "inverse" is meaningless in an absolute sense.

Threnody

@user21820 I would argue that if the set is well-orderable, we can pick the first element to be the identity and the second to be the generator. How well this translates to infinite sets, I'm not sure.

user21820

1:34 PM

@Threnody That is not what the definition says.

Write down the axiomatization of a group (G,·) and let me see.

Threnody

1. Closure. "For all x, y in G : x · y in G"
2. Associativity. "For all x, y, z in G : x · (y · z) = (x · y) · z"
3. Identity. "There exists e in G : For all x in G : e · x = x · e = x"
4. Inverse. "For all x in G : There exists y in G : xy = yx = e"

I'm lost. Do I need some weird choice for this?

user21820

1:56 PM

@Threnody No. It's exactly as you wrote. And it's good that you wrote it exactly in that way. Sorry I didn't notice you finished posting it.

You're missing some "·" in (4), though.

Wait.

Your version is not quite right.

If you want to have the symbol "e", you cannot just axiomatize (G,·), but rather (G,e,·). Otherwise, your (4) even with the "·"s added is meaningless (because e is not defined).

To save time, I'll give you the correct version, but you must make sure you can subsequently produce it correctly by yourself:

(1) e∈G. ·∈func(G,G).
(2) ∀x,y,z∈G ( x·(y·z) = (x·y)·z ).
(3) ∀x∈G ( x·e = e·x = x ).
(4) ∀x∈G ∃y∈G ( x·y = y·x = e ).

Well I decided to change (1) to include the axiomatization of e as an element as well as properly define the meaning of ·.

In conventional FOL, (1) will be captured by the language of the theory, and only (2) to (4) are axioms of the theory of groups.

But I want to use my variant of FOL, as it is more practical and also it is pedagogically better.

So... The proof that the identity is unique is simply the proof (over FOL) that those axioms imply ∀x∈G ∃!y∈G ( x·y=y·x = e ).

In other words, using nothing but the rules in my deductive system for FOL, you can literally prove that statement.

Oops! Sorry I don't know what I was writing for (1).

(1) e∈G. ·∈func(G^2,G).

Lol.

It's a binary function, so of course input is from G^2.

Also we need to stipulate that · is syntactically written as an infix operation, so that those syntax like "x·(y·z)" make sense.

So with these details down, we have truly set up the axiomatization of the theory of groups.

Although this axiomatization is in the meta-system, all the quantifiers are over G, and we can ensure that you (essentially) cannot prove more than the theory of groups by replacing (1) with:

(1') e∈G. ∀x,y∈G ( x·y∈G ).

So why do I want the meta-system version? Because we can directly start doing group theory, which is outside the theory of groups, without needing to talk about models of the theory of groups.

For example, a group (G,e,·) is called cyclic iff ∃u∈G ∀x∈G ( ... ). What is filled in the blank? @Threnody

Threnody

3:02 PM

@user21820 I see. So far I follow

@user21820 Yes... ok

@user21820 This is due to the fact that group theory requires some pre-existing "collection theory" for you to work with?

I, perhaps loosely, understand what you mean when you say "without needing to talk about models..."

I.e. you can prove some general truths that are to be true across all models that satisfy the group axioms - i.e. truths that follow immediately from the axioms alone, and not some specific properties of the model. (Just shooting blind here)

As for the blank, I would put in: x = u^k for some k in N

By the way, where do you get those symbols from? Do you copy-paste them from an online cheat-sheet :D

Or are there keyboard shortcuts for FOL symbols in ASCII?

user21820

@Threnody "^" is not defined, so that's wrong.

Threnody

True...

user21820

@Threnody No it doesn't. In really rigorous textbooks you may see the group axioms being stated without any restricted quantifiers. That is the conventional FOL quantifiers.

That is bad for pedagogy because then to talk about whether a group satisfies the axioms you have to bring in FOL semantics.

Namely, (G,e,·) is a group iff (G,e,·) ⊨ ...

Threnody

mhm... I see

Do you have an example of a "really rigorous textbook" for group theory?

user21820

@Threnody No I cheated; it's by definition haha.. I define a really rigorous textbook as a textbook that does what I said.

Threnody

3:11 PM

Hhaahahah

user21820

(Because you can't be really rigorous if you don't do that and you don't use the variant of FOL that I'm using. And most people don't use my FOL variant, so...)

Threnody

I see :) Ok. All my group theory notes are somewhat informal

user21820

@Threnody That's normal. What you need to make sure is that you can convert them to 100% rigour.

In particular, you would have to define ^ by recursion on ℕ.

Threnody

That's the plan... once I graduate I'll try to go over everything I've learnt, but correctly.

@user21820 I see... this makes sense. So how would you define a cyclic group then?

Would it require you to first define ^, or is there a workaround

user21820

@Threnody My symbols are auto-produced. I have an AHK script with hotstrings that replaces things like "\in " with "∈".

Threnody

3:13 PM

@user21820 Oh sweet.

user21820

And it runs on startup and works everywhere, and I specifically instruct it to not do hotstring replacement in a LaTeX editor program.

@Threnody A group (G,e,·) is called cyclic iff ∃u∈G ∀x∈G ∃f∈func(ℕ,G) ∃m∈ℕ ( f(0)=e ∧ ∀k∈ℕ ( f(k)·u = f(k+1) ) ∧ f(m) = x ).

Clearly, many textbooks don't do it, but that is literally the simplest way to do it rigorously.

The alternative is to define ^ first and then use it. What I wrote is what you get by inlining that definition and getting rid of unnecessary parts.

Threnody

@user21820 I see it, yes.

user21820

You can practice by defining "order" of an element in a group, and other things like this.

Note that once such stuff are defined in this completely formal manner, proving things about them become a pure question of FOL.

And also this logical form immediately begs you to explore variant properties:

(0) ∃u∈G ∀x∈G ∃f∈func(ℕ,G) ∃m∈ℕ ( f(0)=e ∧ ∀k∈ℕ ( f(k)·u = f(k+1) ) ∧ f(m) = x ).
(1) ∀x∈G ∃u∈G ∃f∈func(ℕ,G) ∃m∈ℕ ( f(0)=e ∧ ∀k∈ℕ ( f(k)·u = f(k+1) ) ∧ f(m) = x ).
(2) ∃u∈G ∃f∈func(ℕ,G) ∃m∈ℕ ∀x∈G ( f(0)=e ∧ ∀k∈ℕ ( f(k)·u = f(k+1) ) ∧ f(m) = x ).

Threnody

Order: k is called the order of g in G iff ∀n∈N . (g^n = e => ( k = 0 mod n ∧ n <= k ) )

Does this make any sense?

user21820

It is sensible, but uses so many undefined things that I am not sure you will be able to get it all in one piece.

Try to follow the technique I used to define cyclic groups to define order.

Threnody

3:24 PM

True... mod and ^ in particular have to be expanded

And k... we have no idea where k is coming from

user21820

@Threnody Oh yes it's not sensible. I didn't read carefully...

You could fix your attempt, but it is better to just try doing it my way.

It's just one line if you get it right.

Before you carry on, look at the 3 variant properties I gave above. (0) is the original. (1) is trivially true. (Check it!) (2') is equivalent to (0). (Prove it!)

(2) is wrong. I don't know why I'm so careless. The fixed version is:

(2') ∃u∈G ∃f∈func(ℕ,G) ∀x∈G ∃m∈ℕ ( f(0)=e ∧ ∀k∈ℕ ( f(k)·u = f(k+1) ) ∧ f(m) = x ).

You could explore (2) also, but it's quite pointless.

Threnody

@user21820 So (1) is trivially true if you take m = 1, because f(0+1) = f(0) . x = e . x = x

user21820

@Threnody Yes you need to set u = x as well, but I assume you figured that out too.

Threnody

Ah yes, I agree

user21820

To define order: x has order n in group (G,e,·) iff ∃f∈func(ℕ,G) ∃m∈ℕ ( ... ∧ f(m) = e ). Fill in the blank.

Ok so you have two pieces of homework: Prove that (2') ⇔ (0). Define order.

Consequence of homework: Observe that ( (0) ⇔ (2') ) implies that every cyclic group is countable.

Conversely, every non-empty countable set underlies some cyclic group, and this is easy to construct.

Threnody

3:37 PM

I was doing order this way: Roughly, 'order' is a 3-predicate (??):
order((G, e, .), g, k) iff
∀n∈ℕ ∃f∈func(ℕ,G) ∃m∈ℕ ( f(0)=e ∧ ∀k∈ℕ ( f(k)·g = f(k+1) ) ∧ (f(m) = f(n) ∧ f(n) = e => m \leq n) )
In particular, u is g here.
I'm not sure it's correct, I'll try to fill in your blanks too.

user21820

@Threnody It's wrong, but I'm too lazy to find a counter-example.

Threnody

∃f∈func(ℕ,G) ∃m∈ℕ ( X ∧ ¬[ ∃n∈ℕ . f(n) = e ∧ n < m ∧ f(m) = e ] )
Where X := f(0) = e ∧ ∀k∈ℕ . [ f(k).g = f(k+1) ]

user21820

Wrong, because you put "f(m) = e" in the wrong place.

Right idea though; just fix the careless error.

Threnody

Oh I see it

user21820

You're as careless as me hahaha..

=)

Threnody

3:52 PM

Great! It means I'm learning :D

user21820

Noo... don't learn the wrong things...

Threnody

∃f∈func(ℕ,G) ∃m∈ℕ ( X ∧ ¬[ ∃n∈ℕ . f(n) = e ∧ n < m ] ∧ f(m) = e )
Is this better?

user21820

Yup.

Wait it's still wrong though, because f(0) = e...

Threnody

Right

user21820

But that's easy to fix; two ways. The 'proper' way would be to have 0 < n < m.

Threnody

3:53 PM

∃f∈func(ℕ,G) ∃m∈ℕ ( X ∧ ¬[ ∃n∈ℕ . n > 0 ∧ f(n) = e ∧ n < m ] ∧ f(m) = e )

@user21820 0 < n < m would simply expand to n > 0 and m > n, right?

user21820

Yes.

So you can see that there are a lot of tiny little things in ordinary mathematics that can and should be carefully made rigorous. Chained relation-symbols is one of them.

Good now? So you're left with proving (0) ⇔ (2').

Threnody

@user21820 Yeah, but I should probably do the FOL exercises first

@user21820 Also I'm not sure what this means

user21820

@Threnody It means that "x has an inverse in group (G,e,·)" is a well-defined sentence, but "x has an inverse" is not.

@Threnody Yes you should!

I hope this little excursion with group theory has shown you the benefits of having a full grasp of FOL! =)

Threnody

@user21820 I planned on doing them after I finished Q4 because I already did Q5... but then I quickly realised I pretty much FORGOT all of linear algebra's basics

So now I'm reading a book on it... I'm a mess!

user21820

Lol. Computational linear algebra (i.e. with actual matrix computations), I'm sad to say, is painful to fully formalize. But at least the logical reasoning is the same.

Threnody

4:01 PM

I despise matrices. That's all I have to say.

user21820

Haha..

Threnody

@user21820 So what if I said "let's call the quasi-inverse of x the set of elements in G (the set, for now) called I(x) such that for all y in I(x), x.y = e?"

user21820

@Threnody That's not a proper definition. Your criterion holds even if I(x) = ∅.

You want I(x) = { y : y∈G ∧ x·y = e }.

Threnody

Yes... I see. So my idea was to pick one from I(x), throw everything else out, and see if that is now a proper group.

user21820

But the uniqueness of inverse directly implies that I(x) is a singleton for every x∈G.

Threnody

4:09 PM

Yes but here G is not yet a group - and it isn't a group under the operator "O". The idea is that (G, e, O) is not a group because there is no unique element which functions as the inverse for any arbitrary element.
So because we're stubborn, we change G, not O, in such a way that (K, e, O) is now a group and K is a subset of G.

This is what I want to try and find a method for.

user21820

@Threnody That doesn't make sense; if you don't tell me what O is, then the question is meaningless. If you specify some funny O, then you don't have a group, but so what? If you don't have a group, you won't get a group by just arbitrarily throwing things around.

Threnody

@user21820 Suppose S is the set of strings and O is string concatenation

user21820

Ah I see; I keep getting misled by the context in which people ask questions...

If you want to ask me about non-groups, don't start talking about groups and in the same breath jump to non-groups. Lol.

Threnody

You're right, sorry :)

user21820

So you want closure, associativity and identity. That is called a monoid.

And even in a monoid, identity is unique...

Threnody

4:14 PM

I'm fine with that

user21820

So you don't get to talk about monoids with multiple possible identities.

But there may not be inverses.

Actually your original question did state existence of inverse. So in a natural reading of your comments, you are talking about groups.

Threnody

I worded it very poorly

user21820

Ok. Then write a formal logical statement and I will try to say "true" or "false".

=D

Threnody

Ok!

user21820

(I'm just joking a bit, but yea the more formal the better.)

Threnody

4:19 PM

Consider the 'structure' (S, e, .) where S is the set of strings of some alphabet, e is the empty string, and . is the usual string concatenation.

3 of the axioms of groups we get for free. String concatenation is closed, associative, and e works just as we want. Therefore (S, e, .) is "almost" a group.

Where we fail is when we have the inverse of a group being unique. We cannot find a unique way to build a.b. If we take c, a proper substring of a, we can have c.(rest of a . b) = a.b

user21820

@Threnody No.

Where we fail is existence of inverse.

There is no inverse in the first place, contrary to your original question!

Threnody

@user21820 Oh right! Under usual concatenation there isn't...

user21820

So does it clear up your confusion?

Threnody

What I'm talking about isn't even an inverse then... yeah

user21820

There is something called cancellation though...

4

Q: Model of concatenation theory with left-cancellation but no right-cancellation

The theory of concatenation (TC) can be equivalently expressed as the following assumptions: Closure of strings under concatenation $+$. Existence of an empty string $e$, namely $e+x = x = x+e$ for any string $x$. Associativity of $+$ on strings, namely $(x+y)+z = x+(y+z)$ for any strings $x,y,z...

Threnody

4:24 PM

Interesting...

user21820

Alright; I've to go off again.

See you next time!

Threnody

Thank you! Take care :)
My keyboard's not cooperating today

Threnody

8:44 PM

@user21820 In the post, I think you make use of an implicit sort, S. Am I right in saying there's nothing too special about the letters that denote a sort? They reside in the same alphabet as the rest of the constants, symbols and variables, correct?

Threnody

9:30 PM

"Incidentally, LC and TC can be proven by TC plus a suitable induction schema"

Shouldn't this say LC and RC?

Transcript for

♦ $Mathematics$ Basic Mathematics

Transcript for

♦ Basic Mathematics

♦ $Mathematics$ Basic Mathematics