Logic - 2017-04-08

« first day (234 days earlier) ← previous day next day → last day (2876 days later) »

user21820

06:55

@shredalert NOT(x) = NOR(x,x) ; NOT(y) = NOR(y,y) ; this takes just 2 NOR gates so what am I missing?

@FabianGerhardt I didn't say NSA is unsound, but it depends crucially on certain set theoretic assumptions that may be meaningless or even arithmetically unsound. I'll give a brief explanation but feel free to ask for details or clarification.

Basically, we can pretty much do all of real analysis with just first-order logic plus the naturals (meaning a collection that satisfies first-order PA) plus the collection of subsets of the naturals (namely its power-set). Rarely we might need a few more power-sets, but that's about it. So if you believe in the meaningfulness of the naturals, and the meaningfulness of the notion of power-sets of it, you would have to believe that real analysis is meaningful.

Now NSA is built on a specific kind of model R* of the first-order theory of the real numbers. The issue is that R* requires an ultrafilter on the naturals, which cannot be constructed in any reasonably constructive way, because even ZF set theory cannot prove that it exists. ZFC can prove that ultrafilters exist in general.

1 hour later…

user21820

08:26

As far as I know there is no valid ontological justification for ZF, not to say ZFC. Secondly, consistency of a formal system is a useless gauge of meaningfulness because ( PA + not Con(PA) ) is consistent (assuming PA is). We want at least arithmetical soundness, meaning that it does not prove any false arithmetical statement (as viewed from the meta-system). To treat NSA as meaningful, in modern mathematics it comes down to assuming that ZFC is meaningful.

This is much much more than what you need to assume when doing standard real analysis, as has been shown in the field of reverse mathematics. Furthermore, it is a false dichotomy to assume that NSA is the only alternative to standard real analysis. I personally feel that the most intuitive way to do real analysis is via both the rigorous ε-δ definitions and asymptotic analysis (see linked posts from my profile), and in doing so NSA will completely lose its appeal.

In fact, asymptotic analysis comes down to manipulating and thinking in terms of sequences of reals instead of just single reals. For a brief explanation of what this means see:

A: When is the derivative of an inverse function equal to the reciprocal of the derivative?

The answers so far are not correct; they merely give sufficient but not necessary conditions, yet some of them state that their conditions are necessary. You do not need differentiability in some neighbourhood of the point. You do not even need one-to-one correspondence between the values of $x$ ...

And:

A: Does the notion of "goes to" exists in mathematical logic?

Your question is actually not very clear to me, but I'll assume that you're asking whether there is a way to formalize the notion of "as ... goes to ..." that occurs in analysis and that mathematicians happily manipulate in their heads with hardly a thought about quantifiers over $ε,δ$. The answ...

And here's a simple example together with explanation of how one can rewrite the asymptotic analysis in terms of standard analysis:

A: If $m=\omega(N log N)$, then what is the order of $N$ in terms of $m$?

Take any variables $m,N \ge 0$ such that $m \in ω(N \log(N))$ as $N \to \infty$. $ \def\lfrac#1#2{{\large\frac{#1}{#2}}} $ Given any constant $c > 0$: As $m \to \infty$: If $N > c \cdot \lfrac{m}{\log(m)}$: $N \to \infty$. $m \ge \lfrac2c \cdot N \log(N) > 2 \lfrac{m}{\log(...

Finally, to understand NSA better, if you actually know the underlying mathematics behind NSA, you will realize that convergent sequences of reals are put together in the same equivalence class corresponding to a standard real. The problem is that to achieve a model of the first-order theory of the reals, you need to also put arbitrary non-convergent sequences into equivalence classes, and in a way that satisfies certain properties. This can only be achieved via an ultrafilter.

That is exactly where the non-constructive nature of R* comes from, namely the desire to classify all sequences of reals an an arbitrary fashion just so as to form a model, in particular to be able to say of every pair of sequences x,y whether x < y or x = y or x > y in the equivalence relation. If you think about it, you'll realize that this is not only useless for non-convergent sequences but also silly. On the other hand asymptotic analysis essentially stays with convergent sequences.

@FabianGerhardt: But as I told shredalert, (assuming ZFC) the beauty of R* is in its properties as a construction in logic, not its application to analysis. Specifically, it is fascinating that an ultrafilter on the naturals can be used to construct a model of the first-order theory of the reals that fails to satisfy the completeness property everywhere! It gives an actual example of the distinction between first-order and second-order categoricity.

A Math SE thread you may be interested in is:

108

Q: Is non-standard analysis worth learning?

As a former physics major, I did a lot of (seemingly sloppy) calculus using the notion of infinitesimals. Recently I heard that there is a branch of math called non-standard analysis that provides some formalism to this type of calculus. So, do you guys think it is a subject worth learning? Is ...

shredalert

09:27

@FabianGerhardt morning

Fabian Gerhardt

morning

@user21820 thank you for your answer.

shredalert

@FabianGerhardt what makes you interested in logic? :)

Fabian Gerhardt

In short normal real analysis is easier to belief than NSA, yes? I don't actually care too much about NSA, I was just confused, because it seemed like you had more than very good reasons against using it. but it seems like you only have good reasons.

did some courses connected to logic at my university. liked it alot

shredalert

I'm enjoying it too, studying it on my own

Fabian Gerhardt

especially the whole gödel thing. but all the weird things, like EF games

shredalert

09:33

I find the logical identities pleasing

Fabian Gerhardt

so you're going the whole completeness, compactness, incompleteness road?

what do you mean by that? first order sentences which are equivalent?

shredalert

I'll give them a look at later, I'm actually more interested to see if I can mesh it together with topology

Yeah

user21820

@FabianGerhardt: Hello!

Fabian Gerhardt

what is up with that? the identities

hi!

shredalert

I just like simplifying things haha

Fabian Gerhardt

09:35

I may take topology next semester too!

haha I hate it

shredalert

Why wait until next semester? Grab a book and start now! :D

Fabian Gerhardt

I usually prefer words to formalisms

shredalert

You don't need any prerequisites to study topology

user21820

@FabianGerhardt My reasons against NSA are because I have doubts about the soundness of ZFC.

Fabian Gerhardt

@user21820 woah, I don't want to get into that biz

nah I have to write a bachelors thesis. and even if I was designating extra time for study, I'd read about colmogorov complexity

shredalert

09:37

Kolmogorov is great, I look forward to when I know more analysis so I can understand more of what he did.

Fabian Gerhardt

studying computer science btw.

shredalert

nice

pure and applied maths here

Fabian Gerhardt

colmogorov complexity doesn't have much to do with analysis I think. its about how short you can write things down, without losing information

shredalert

oh yeah, I was referring to his work on dynamics

and stochastic analysis

user21820

@FabianGerhardt Well but it's an important consideration. In particular, the proof that NSA is valid is a proof in ZFC. So there's no reason to believe that NSA is valid unless you first believe that ZFC is meaningful.

And by the way, do you know of SBA's random chat-room? =)

Fabian Gerhardt

09:39

@shredalert sadly I never cared too much about analysis

user21820

Kolmogorov worked in many fields. Computability theory was just one of them.

Fabian Gerhardt

no I don't know any other chatrooms

user21820

He also developed the Kolgomorov axioms for probability.

SBA's chat-room is literally for random stuff!

shredalert

Yep

user21820

He'd be glad if you joined.

Fabian Gerhardt

09:41

yeah, with colmogorov complexity he also invented a useless theory of randomness. at least useless for predicitions, but interesting for foundations of computer science

« first day (234 days earlier) ← previous day next day → last day (2876 days later) »

all rooms