Logic - 2018-09-15

« first day (759 days earlier) ← previous day next day → last day (2058 days later) »

11:20 AM

@user21820 I haven't been here in a while, and I was wondering if you have had any luck finding a proof for induction? I remember it was something we were looking for at least a year ago now, which was never found.

Recently I learned the sequent calculus (from this nice site http://logitext.mit.edu/logitext.fcgi/tutorial) After completing it and doing the last example by hand as an exercises on the train, I decided to have a go at trying to prove induction. I didn't get very far, as I was only able to show that 3 out of 4 of the leafs of my proof were valid but not the last one. Which I am…

1 hour later…

12:45 PM

@user400188 Proving it from what assumptions? Induction is a consequence of well-ordering. You need to have something on the left side of the sequents :)

There's also the recursion theorem I suppose, which says that recursive definitions of functions actually define a function, if that's what you are referring to.

arxiv.org/abs/physics/0103058

muhahahaha, finally found a mention of at least one kind of nonmeasurable set that has a physical application

Vitali sets are needed to describe trajectories in some irrational systems

@Secret nice

1:01 PM

So pretty much every consequence of the axiom of choice can escape set theory and found uses in other areas of mathematics and even physical applications

I'm not sure about #13

just rapidly scrolling through mind you

This is in contrast to ZF, where things like amorphous sets and infinite dedekind finite sets cannot really have an application that is not stuck inside ZF

matwbn.icm.edu.pl/ksiazki/fm/fm63/fm6312.pdf

if k=0 is included in that union you cannot necessarily conclude that the measure of a union is equal to the sum of the measures

that is actually the whole point of measurability as that property doesn't hold for nonmeasurable sets, the best you can get is the measure of the union is less than or equal to the sum of the measures

He probably knows that actually. I honestly didn't read it very closely as I just woke up 5 min ago

@Secret how are you?

Basically busy writing my thesis and investigating the irrationals in my free time

irrational numbers or irrational things?

1:08 PM

the set of irrational numbers

how about transcendental numbers?

I recently do some kind of plot of them. It has some kind of self similar property

Nah, I cannot touch transcendentals without fully understand ring of polynomials

Xander would be the best person to talk to about your last statemennt

I think you can! How about doing Liouville's theorem

Xander already said that the rationals are not fractals, and self similarity is not a necessary property of fractals

Besides, the self similarity (as evident in the thomae function) is nonlinear in some weird way

just worry about transcendentals over the rationals. A number is transcendental in that context if it is not the root of a polynomial having rational coeffecients

The first one discovered was: $\sum_{k=1}^\infty \frac{1}{10^{k!}}$

1:12 PM

True, but there are uncountably many polynomials to test, and the one I am most interested is the sum of any two transcendentals, which because of something like $\pi + e$ it is still an open problem

Liouville number

In number theory, a Liouville number is a real number x with the property that, for every positive integer n, there exist integers p and q with q > 1 and such that 0 < | x − p q | < 1 q n . {\displaystyle 0<\left|x-{\frac {p}...

None of the transcendental number theory theorems can handle that family of cases yet, and I am still trying to understand Lindimena weistrass theorem's proof

Well I can tell you the Liouville proof for the above mentioned number is on Wikipedia and is very easy! The one for $e$ is fairly easy also

You should really buy an abstract algebra book :)

and go through the section on field theory and some of this will be much easier for you :) including lindemann-weierstrauss

hopefully there will not be too many inequalities and absolute values in the proofs, cause one reason I cannot handle number theory is because many of its proofs is full of these two operations

and I get BSOD when I get overwhelmed by them

Which proof? Liouville or lindemann-weirestrauss?

1:18 PM

Lindemann–Weierstrass theorem

In transcendental number theory, the Lindemann–Weierstrass theorem is a result that is very useful in establishing the transcendence of numbers. It states the following. In other words the extension field ℚ(eα1, ..., eαn) has transcendence degree n over ℚ. An equivalent formulation (Baker 1990, Chapter 1, Theorem 1.4), is the following. This equivalence transforms a linear relation over the algebraic numbers into an algebraic relation over ℚ: by using the fact that a symmetric polynomial whose arguments are all conjugates of one another gives a rational number. The theorem is named...

The proof looks very dense because of all those summations and integrals

I don't see how exactly it somehow test all polynomials and showed that it never vanishes

Given enough time I might eventually work it through, but I still have not yet

In general the approach to problems like that is proof by contradiction

You assume something has a certain property (say that its algebraic) and derive a contradiction

You then conclude your initial assumption, that said number was algebraic, can't be true

What do you know? Look at the bottom of the Wikipedia page you posted : Note that Lemma A is sufficient to prove that e is irrational, since otherwise we may write e = p / q, where both p and q are nonzero integers, but by Lemma A we would have qe − p ≠ 0, which is a contradiction.

What I don't understand is what that integral in the proof is used for, other than looks suspiciously like a laplace transform

It looks like you just directly integrate via integration by parts to get the summation immediately beneath it

you have to integrate by parts np times

or maybe np-1

try writing it out inductively for the first 2-3 cases

1:38 PM

But what motivates us to define that integral when the proof started with sums?

2:12 PM

@Secret Sorry went out for breakfast

I'm not sure. Frequently people will just play around with things and come across stuff by accident. As such you will often find things in proof that appear to have no motivation.

Case in point: Euler's discovery of the gamma function

2:33 PM

@DavidReed I don't remember whether we talked about this, but indeed I recall noticing that every proof requires IVT at some point. For example, even the almost purely field theory proof requires the fact that every odd degree real polynomial has a real root. The theory T comprising the field axioms plus "∀x ∃y ( y·y=x )" is obviously insufficient to prove that ( t ↦ t^3+2 ) has a root, because T is satisfied by the union of all towers of quadratic extensions of R within C.

@user21820 So it would be correct to say it is impossible to proof the fundamental theorem of algebra without analysis

As opposed to "There is currently no known proof of the fundamental theorem of algebra that does not require analysis"

@DavidReed What I stated above is sufficient to prove that you cannot show that that particular cubic has a root using only field axioms and existence of square-roots. Is that good enough? Well... The strongest claim that we want to make is that ACF has no finite axiomatization. I am not sure how to prove that, but it sounds like someone should have answered that somewhere before. =)

Hmm... This pdf says that ACF is indeed not finitely axiomatizable, answering my question. However, it states an even stronger question that is apparently still open...

Whether ACF is axiomatizable with finitely many variables. Lol!

So that claim in the pdf should suffice to support the claim that there is no possible proof of FTA without at least a pinch of analysis.

Interesting

you are speaking of the galois theory proof I assume as the "most algebraic one"

Wikipedia: In spite of its name, there is no purely algebraic proof of the theorem, since any proof must use some form of completeness, which is not an algebraic concept

@DavidReed Yep.

@DavidReed Ah I see why you asked this question.

That's my favorite proof of it as well

2:46 PM

That's actually not my favourite. I think that the complex analysis one is the nicest haha.. But it's also the hardest to make 100% rigorous.

There's several ones using complex

Well the one that uses Liouville's theorem.

Ah

The interesting thing is that the field theory proof of the existence of an algebraic closure of R requires AC, whereas the complex analysis one does not.

You can avoid it

You are talking about passing to a normal closure

Using Zorn's lemma

2:49 PM

How do you avoid it? R is uncountable.

the trick is to multiply your polynomial of interest by $x^2+1$

And then? (I've never heard of that trick.)

Let me see if I can find the type up of it

I'll just type it here

Suppose $f \in \mathbb{C}[x]$

Whats the command to put the conjugation symbol above a character?

@DavidReed \bar

But I don't have LaTeX support here so doesn't matter.

$f\bar$

2:57 PM

Yea.

$\bar{f}$

Ok

so let $g = (x^2+1)*f*\bar{f}$

then $g \in \mathbb{R}[x]$, $g(\im)=0$ and $f=0$ implies $g = 0$

agreed?

@DavidReed Um you are already working within C to deduce the first part.

Well I suppose you can set up C = R(i) first.

Yes

Ok go on.

So let $K/R$ be the s.f. for g

since g(I) = 0 we must have $R \subseteq R(I) \subseteq K$

That is $R \subseteq C \subseteq K$

Now you use sylow to show $[K:\mathbf{C}] = 1$

and you are done

3:12 PM

@DavidReed How does this step work?

3:26 PM

Same as if you passed to a closure pretty much

I know I have this typed up somewhere let me look again

@user21820 here it is...

Lol.

oops

Doesn't look like math. =P

ssry

You can delete it.

3:28 PM

yes its from a lawsuit I have filed in arizona

user image

user image

reminder of the primitive element theorem: finite + separable implies simple

4:08 PM

@user21820 Back. Sorry am frequently away as I'm taking care of grandmother at our summer home in RI. The proof is posted above.

The degree 2 part is pretty trivially a consequence of the quadratic formula. The odd degree polynomial having a real root you have already mentioned you are familiar with

@DavidReed No problem. I'm also multi-tasking. Thanks for that; I'll look at it.

So really by making your polynomial bigger it allows you to squeeze the complex numbers in between the reals and the s.f. for g. Since f divides g having g split in C also means f splits in C

I see. It seems vaguely familiar to me, as if that is really the field theory proof I was taught. It means I have simply forgotten that it uses the Sylow theorem.

It's virtually identical to the one that requires taking a closure

Or perhaps the one I was taught just simplified things by working within the algebraic closure.

4:20 PM

@user21820 Btw above someone pinged you regarding proving induction within a gentzen system

@DavidReed Oh I was going to reply but forgot. Thanks for reminding me!

timestamped at 7:20

@user400188 Hello! I don't recall ever looking for a proof for induction. If we discussed philosophical reason for induction before, I would have told you that there isn't any non-circular justification for it.

In fact, it can be shown that PA is strictly stronger than without induction, since it is equivalent to PA− plus the induction schema, but you can easily verify this model of PA− does not satisfy induction.

In particular, "∀x ∃y ( 2·y = x ∨ 2·y+1 = x )" is true in N but false in that model.

5:06 PM

@Secret Unfortunately for your "muhahahaha", the notion of rationality of a real number does not seem to have any empirically measurable real-world consequences. In particular, rational numbers in the form of concrete encodings of course have real-world meaning, but asking whether three points on a line have separations being a rational ratio does not seem to be a meaningful question in reality, in the sense that there does not seem to be any meaningful prediction that depends on rationality.

Of course, that doesn't take away from the interesting mathematics.

For example there is this curious theorem.

5:21 PM

@Secret: And in case you didn't already know, "Chaos Solitons & Fractals" is full of junk.

This does not mean that everything in there is false. But it just means that it is no better than the internet at large.

@user400188: Just in case it is not clear, it means that you cannot prove induction without having induction baked into the foundational system somehow or the other.

I see, still it is better than locking inside set theory stuff when it can reach out all the way to the irrationals (which does not need axiom of choice to construct)

so even though it is nowhere any physical, it is still much better than say... Hamel functions

(the latter I don't know of any result which is not negligible in the sense that if they don't exist, no big theorem will be lost)

@Secret I don't think that distinction makes sense. The notion of rationality cannot be 'simple' except in an encoding that makes it simple, such as the encoding of a rational as a fraction of integers in reduced terms with positive denominator.

Once you look at the notion of rationality within the real line, then it is concurrent with the notion of irrationality, which as you know includes very complicated things.

So much so that Skolem's paradox is not so easily dealt with on philosophical grounds.

But we typically will not exclude irrationals from any formal system that aims to describe the real world even though we cannot really encode them in a way that the string will terminate?

@Secret Of course a foundational system should be able to reason about irrationals in general, but that's not the same as saying that they are simple, and my initial point was just that irrationality is apparently a mathematical concept and not a real-world property in any sense.

And, yes, any foundational system that aims to describe the real-world necessarily should be able to deal with concepts such as irrationality.

Unless one rejects real numbers as actually meaningless, which seems to be quite groundless given the success of real analysis in the real world.

It's just that we still have to separate between the part of the foundational system that can be translated to real-world predictions, and the part that cannot (but remain in the realm of concepts).

Thus the article suggesting that Vitali sets have relationships with irrational torii should mean Vitali set is not as fantasy as many of the constructs in ZFC, even though they remain in the realm of concepts?

5:37 PM

@Secret Well, that question has nothing to do with that article. It had long been known that Vitali sets are actually very tame compared to the full power of ZFC.

I don't know much but one can consider the axiom of choice as using memoization in a functional programming language. This works even when instantiating an existential quantifier results in an object drawn from a random distribution. However, any question about a memoized function's global behaviour then requires knowing the precise way in which the inbuilt memoization works. Alternatively, if the underlying logic is sufficiently constructive and maps existential quantifiers to functions or at least oracles it would automatically give AC. Note that Skolemization is essentially AC. — user21820 Mar 21 '16 at 2:53

Sometimes I am wondering, what mathematical objects are the most useless in that all its applications does not lead to big theorems, but only things related to itself. For example:

8

Q: Uses of ordinals

Are there any interesting theorems outside of set theory that use ordinals in their proofs? The only example I know of is Goodstein's theorem, and I haven't been able to find anything else. In other (more vague) words, what is the use of ordinals? (Other than Goodstein.) Theorems that use the w...

set-theory ordinals

Counterexamples using $\omega_1$ such as long line is, while fun, useless because it has no application in other areas of mathematics except as a counterexample

a counterexample is an application

we aren't the scientific journal community

we do publish null hypothesis

But if we nuke $\omega_1$, then all its counterexamples disappears, and none of the big theorems will be affected

so it seems all applications of $\omega_1$ are depending on its existence and cannot be applied to elsewhere

@Secret Kripke's theory of truth does not need ω[1], but needs at least a quasi-well-ordering of countable well-orderings.

Which is most simply provided by any uncountable well-ordering, into which every countable well-ordering must embed as an initial segment.

Of course, you can then figure out whether that theory of truth is useful or not, but it is surely mathematics that a priori has nothing to do with well-orderings.

There are other uses of well-orderings in 'core' mathematics. If you do want every vector space to have a basis, then you do need a well-ordering of the vectors in that space. They seem to have no real-world implication, but hey it's still mathematics.

I think you can prove it via Zorn's lemma lol

> because Zorn's lemma was invented for the purpose of eliminating ordinals in mathematical proof

5:48 PM

Yes but everything boils down to well-orderings. I was careful not to say it requires (von Neumann) ordinals.

(Unless in the future mathematicians generally reject elegant theorems like Zorn's lemma and the well-ordering theorem.)

(Then maybe it would no longer be considered 'mainstream mathematics'.)

Who knows.

2 hours later…

7:50 PM

@user21820 is it hamel basis' or schrauder that are equivalent to choice?

nvm

3 hours later…

11:18 PM

@Secret I forgot to mention to you how much I've enjoyed physical chemistry

Really has cleared up some ambiguity in a lot of general chem

especially with regards to entropy

« first day (759 days earlier) ← previous day next day → last day (2058 days later) »

Transcript for

Sep '1815

♦ $Mathematics$ Logic

This room is meant for discussion about logic, including found...

formal-systems foundations logic no-trolls

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

$Mathematics$

site design / logo © 2024 Stack Exchange Inc; legal

mobile