Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 29 30 [31] 32 33 ... 47  All

Author Topic: Maths thread.  (Read 307092 times)

0 Members and 4 Guests are viewing this topic.

Haddock

  • Minion
  • *****
  • Offline Offline
  • Posts: 725
  • Shuffle iT Username: Haddock
  • Doc Cod
  • Respect: +558
    • View Profile
Re: Maths thread.
« Reply #750 on: January 18, 2017, 10:54:59 am »
+1

I feel like the only natural definition of a subset A being a proportion X of its superset B is |A|  = X*|B|, where |.| is some measure and 0 \leq X \leq 1.  When |B| is an infinite ordinal, I think these operations still make sense; maybe it should be |B|= Y*|A|, where Y >= 1. (If |.| is the usual cardinality and B is the natural numbers, |B| is the first infinite ordinal, and X can only be 0 or 1 depending on if A is finite or not.)
This might be a valid definition but it is not the only natural one, at least not for subsets of the naturals (or subsets of any countable ordered set).

The definition I have seen (and/or used) most often for subsets of N is (variants of) the following:

X (a subset of N) has density d if
Limsup (|X intersect {1,...,N}| / N) = d,
the limsup being taken as N --> infinity.

See https://en.wikipedia.org/wiki/Natural_density

And for this definition, the thing sudgy is trying to show is most certainly false because you could always remove some infinite set of density 0. But I don't know how helpful that is.
It's not AUTOMATICALLY false, it's just not true in general.  It depends on exactly what sudgy's sequences look like. 
Logged
The best reason to lynch Haddock is the meltdown we get to witness on the wagon runup. I mean, we should totally wagon him every day just for the lulz.

M Town Wins-Losses (6-2, 75%): 71, 72, 76, 81, 83, 87 - 79, 82.  M Scum Wins-Losses (2-1, 67%): 80, 101 - 70.
RMM Town Wins-Losses (3-1, 75%): 42, 47, 49 - 31.  RMM Scum Wins-Losses (3-3, 50%): 33, 37, 43 - 29, 32, 35.
Modded: M75, M84, RMM38.     Mislynched (M-RMM): None - 42.     Correctly lynched (M-RMM): 101 - 33, 33, 35.       MVPs: RMM37, M87

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 623
  • Shuffle iT Username: Cuzz
  • Respect: +1018
    • View Profile
Re: Maths thread.
« Reply #751 on: January 18, 2017, 02:39:20 pm »
0

I feel like the only natural definition of a subset A being a proportion X of its superset B is |A|  = X*|B|, where |.| is some measure and 0 \leq X \leq 1.  When |B| is an infinite ordinal, I think these operations still make sense; maybe it should be |B|= Y*|A|, where Y >= 1. (If |.| is the usual cardinality and B is the natural numbers, |B| is the first infinite ordinal, and X can only be 0 or 1 depending on if A is finite or not.)
This might be a valid definition but it is not the only natural one, at least not for subsets of the naturals (or subsets of any countable ordered set).

The definition I have seen (and/or used) most often for subsets of N is (variants of) the following:

X (a subset of N) has density d if
Limsup (|X intersect {1,...,N}| / N) = d,
the limsup being taken as N --> infinity.

See https://en.wikipedia.org/wiki/Natural_density

And for this definition, the thing sudgy is trying to show is most certainly false because you could always remove some infinite set of density 0. But I don't know how helpful that is.
It's not AUTOMATICALLY false, it's just not true in general.  It depends on exactly what sudgy's sequences look like.

Right, I was referring to this:

Say you are trying to prove that all natural numbers have a certain property.  You find an infinite sum where each term is a fraction of the natural numbers (and all of the numbers one fraction gives the property to only get it from that one fraction).  The sum of this infinite series of fractions is one.  Is that proof that all natural numbers have that property, or just that almost all of them do?

not to any specific scenario.
Logged

Haddock

  • Minion
  • *****
  • Offline Offline
  • Posts: 725
  • Shuffle iT Username: Haddock
  • Doc Cod
  • Respect: +558
    • View Profile
Re: Maths thread.
« Reply #752 on: January 19, 2017, 05:05:13 am »
0

I feel like the only natural definition of a subset A being a proportion X of its superset B is |A|  = X*|B|, where |.| is some measure and 0 \leq X \leq 1.  When |B| is an infinite ordinal, I think these operations still make sense; maybe it should be |B|= Y*|A|, where Y >= 1. (If |.| is the usual cardinality and B is the natural numbers, |B| is the first infinite ordinal, and X can only be 0 or 1 depending on if A is finite or not.)
This might be a valid definition but it is not the only natural one, at least not for subsets of the naturals (or subsets of any countable ordered set).

The definition I have seen (and/or used) most often for subsets of N is (variants of) the following:

X (a subset of N) has density d if
Limsup (|X intersect {1,...,N}| / N) = d,
the limsup being taken as N --> infinity.

See https://en.wikipedia.org/wiki/Natural_density

And for this definition, the thing sudgy is trying to show is most certainly false because you could always remove some infinite set of density 0. But I don't know how helpful that is.
It's not AUTOMATICALLY false, it's just not true in general.  It depends on exactly what sudgy's sequences look like.

Right, I was referring to this:

Say you are trying to prove that all natural numbers have a certain property.  You find an infinite sum where each term is a fraction of the natural numbers (and all of the numbers one fraction gives the property to only get it from that one fraction).  The sum of this infinite series of fractions is one.  Is that proof that all natural numbers have that property, or just that almost all of them do?

not to any specific scenario.
Right.

You don't even know that the "exceptional set" has density 0, necessarily.  If the original terms of the infinite union have too much overlap, you learn nothing.

Eg:
The various arithmetic progressions:
{k.2^n  |  k in N} 
(for various n>0)
have density 2^{-n}.

The sum 2^{-n} is 1, obviously, but the union of all the sets is just the set of even numbers. 

So you don't even have "almost all" necessarily.
Logged
The best reason to lynch Haddock is the meltdown we get to witness on the wagon runup. I mean, we should totally wagon him every day just for the lulz.

M Town Wins-Losses (6-2, 75%): 71, 72, 76, 81, 83, 87 - 79, 82.  M Scum Wins-Losses (2-1, 67%): 80, 101 - 70.
RMM Town Wins-Losses (3-1, 75%): 42, 47, 49 - 31.  RMM Scum Wins-Losses (3-3, 50%): 33, 37, 43 - 29, 32, 35.
Modded: M75, M84, RMM38.     Mislynched (M-RMM): None - 42.     Correctly lynched (M-RMM): 101 - 33, 33, 35.       MVPs: RMM37, M87

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 623
  • Shuffle iT Username: Cuzz
  • Respect: +1018
    • View Profile
Re: Maths thread.
« Reply #753 on: January 19, 2017, 02:00:49 pm »
+1

Sudgy can you explain this?

In this case, none of the elements in the sets overlap.

Maybe list some very concrete examples of some of the sets you're talking about too
Logged

Haddock

  • Minion
  • *****
  • Offline Offline
  • Posts: 725
  • Shuffle iT Username: Haddock
  • Doc Cod
  • Respect: +558
    • View Profile
Re: Maths thread.
« Reply #754 on: January 19, 2017, 02:07:11 pm »
+1

Sudgy can you explain this?

In this case, none of the elements in the sets overlap.

Maybe list some very concrete examples of some of the sets you're talking about too
I think he just means that in his infinite union of sets, the sets are all pairwise disjoint (have no numbers in common).

In which case the best answer I can give is the following.

If you have infinitely many DISJOINT sets of numbers Sn, each with density Cn, and the sum of the Cn is 1, then the union of all of the Sn is a set whose complement has density 0.

So if you can prove property P about each of the sets Sn, then every number should have property P except for some "bad" set of numbers with density 0.


Crucial fact:  A set having density 0 does not mean it's empty.  It doesn't even mean it's finite.
Logged
The best reason to lynch Haddock is the meltdown we get to witness on the wagon runup. I mean, we should totally wagon him every day just for the lulz.

M Town Wins-Losses (6-2, 75%): 71, 72, 76, 81, 83, 87 - 79, 82.  M Scum Wins-Losses (2-1, 67%): 80, 101 - 70.
RMM Town Wins-Losses (3-1, 75%): 42, 47, 49 - 31.  RMM Scum Wins-Losses (3-3, 50%): 33, 37, 43 - 29, 32, 35.
Modded: M75, M84, RMM38.     Mislynched (M-RMM): None - 42.     Correctly lynched (M-RMM): 101 - 33, 33, 35.       MVPs: RMM37, M87

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 623
  • Shuffle iT Username: Cuzz
  • Respect: +1018
    • View Profile
Re: Maths thread.
« Reply #755 on: January 19, 2017, 02:20:23 pm »
0

Sudgy can you explain this?

In this case, none of the elements in the sets overlap.

Maybe list some very concrete examples of some of the sets you're talking about too
I think he just means that in his infinite union of sets, the sets are all pairwise disjoint (have no numbers in common).

I get that this is probably what he means, but I have a hard time making that fit with his definition of "fraction of the natural numbers" here:

A subset S of N contains a fraction a/b of N iff for all subsets T of N with length b containing consecutive integers, the size of T ∩ S is a.

I'm finding it a little hard to see how you have a collection of these with "fraction" adding up to 1 that are all pairwise disjoint. The only example I see seems to cover all of N trivially (write a = b*2^k with b odd and a lies in A_k):

A_0 = 1, 3, 5, 7, ...
A_1 = 2, 6, 10, 14,...
A_2 = 4, 12, 20, 28,...
A_3 = 8, 24, 40, 56,...
.
.
.
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #756 on: January 20, 2017, 02:14:25 am »
0

I've seen that I can't really do what I was wanting, so for me the discussion isn't as relevant.  Anyway, I know that that definition for fractions of the naturals isn't good in all cases, it's just what I was intending for this specific example.

I'm finding it a little hard to see how you have a collection of these with "fraction" adding up to 1 that are all pairwise disjoint. The only example I see seems to cover all of N trivially (write a = b*2^k with b odd and a lies in A_k):

A_0 = 1, 3, 5, 7, ...
A_1 = 2, 6, 10, 14,...
A_2 = 4, 12, 20, 28,...
A_3 = 8, 24, 40, 56,...
.
.
.

What I was doing skipped some powers of two.  That opens it up to a lot of nontrivial examples.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

silverspawn

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5300
  • Shuffle iT Username: sty.silver
  • Respect: +3188
    • View Profile
Re: Maths thread.
« Reply #757 on: January 27, 2017, 12:31:30 pm »
0

What is the best thing to read if I want to learn set theory? If there is free access to it online, that's a bonus.

I started here ... I don't think I can judge yet whether that's a good script. a few chapters in I took a peek forward and saw that they define the natural numbers as

0                 =  ∅
1 = {0}        = {∅}
2 = {0, 1}     = {∅, {∅}}
3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}
etc.

Is this how proper set theory works – constructing everything through empty sets and sets of empty sets?

Haddock

  • Minion
  • *****
  • Offline Offline
  • Posts: 725
  • Shuffle iT Username: Haddock
  • Doc Cod
  • Respect: +558
    • View Profile
Re: Maths thread.
« Reply #758 on: January 27, 2017, 12:35:49 pm »
0

What is the best thing to read if I want to learn set theory? If there is free access to it online, that's a bonus.

I started here ... I don't think I can judge yet whether that's a good script. a few chapters in I took a peek forward and saw that they define the natural numbers as

0                 =  ∅
1 = {0}        = {∅}
2 = {0, 1}     = {∅, {∅}}
3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}
etc.

Is this how proper set theory works – constructing everything through empty sets and sets of empty sets?
In answer to your final question, yes.  That's a very standard construction of the naturals. 
As a basic building block, you can't do better than the empty set.  The axioms of Set Theory want to minimise how many sets they just claim to exist out of the blue, so it's best to build everything up piecewise from the one set you know exists (axiom 1) - the empty set.

 I've not seen that text before, but if it's based on lecture notes from an undergraduate course it's probably fine.  The Oxford set theory course also makes its lecture notes publicly available (at least, I can access them without having to sign into anything) and I remember them being very good.

EDIT: Many people have recommended a book by Enderton on Set Theory.  I've not seen it myself, but have seen lots of senior lecturers recommend it to students.  So if you can get hold of a copy that might be a very good resource.
« Last Edit: January 27, 2017, 12:36:56 pm by Haddock »
Logged
The best reason to lynch Haddock is the meltdown we get to witness on the wagon runup. I mean, we should totally wagon him every day just for the lulz.

M Town Wins-Losses (6-2, 75%): 71, 72, 76, 81, 83, 87 - 79, 82.  M Scum Wins-Losses (2-1, 67%): 80, 101 - 70.
RMM Town Wins-Losses (3-1, 75%): 42, 47, 49 - 31.  RMM Scum Wins-Losses (3-3, 50%): 33, 37, 43 - 29, 32, 35.
Modded: M75, M84, RMM38.     Mislynched (M-RMM): None - 42.     Correctly lynched (M-RMM): 101 - 33, 33, 35.       MVPs: RMM37, M87

Haddock

  • Minion
  • *****
  • Offline Offline
  • Posts: 725
  • Shuffle iT Username: Haddock
  • Doc Cod
  • Respect: +558
    • View Profile
Re: Maths thread.
« Reply #759 on: January 27, 2017, 12:41:13 pm »
0

Just had a quick skim of the notes you're looking at.  Looks like he starts with a big description of the underlying formal language.  Which is nice and all, and certainly crucial for understanding the subtleties, but if you're looking for a crash course introduction you might want to find a course that jumps into the set theory a bit earlier. 
You can get away without the logical language for quite some time.
Logged
The best reason to lynch Haddock is the meltdown we get to witness on the wagon runup. I mean, we should totally wagon him every day just for the lulz.

M Town Wins-Losses (6-2, 75%): 71, 72, 76, 81, 83, 87 - 79, 82.  M Scum Wins-Losses (2-1, 67%): 80, 101 - 70.
RMM Town Wins-Losses (3-1, 75%): 42, 47, 49 - 31.  RMM Scum Wins-Losses (3-3, 50%): 33, 37, 43 - 29, 32, 35.
Modded: M75, M84, RMM38.     Mislynched (M-RMM): None - 42.     Correctly lynched (M-RMM): 101 - 33, 33, 35.       MVPs: RMM37, M87

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Maths thread.
« Reply #760 on: January 27, 2017, 12:56:51 pm »
0

That script is weird. The author says that the AC is true, and thinks that there is hope that there will be a solution to the question of wether CH is true or not. The most interesting things I learned in my set theory lectures is that these things are independant of the other axioms.
Logged

silverspawn

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5300
  • Shuffle iT Username: sty.silver
  • Respect: +3188
    • View Profile
Re: Maths thread.
« Reply #761 on: January 27, 2017, 01:06:34 pm »
0

In answer to your final question, yes.  That's a very standard construction of the naturals.

That's kind of awesome... and here I thought that the maths I learned at my university was fundamental. How foolish!

Just had a quick skim of the notes you're looking at.  Looks like he starts with a big description of the underlying formal language.  Which is nice and all, and certainly crucial for understanding the subtleties, but if you're looking for a crash course introduction you might want to find a course that jumps into the set theory a bit earlier. 
You can get away without the logical language for quite some time.

I was actually more thinking about acquiring a really fundamental understanding of sets rather than something quick, so if the approach is good in theory, I don't mind it.

silverspawn

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5300
  • Shuffle iT Username: sty.silver
  • Respect: +3188
    • View Profile
Re: Maths thread.
« Reply #762 on: January 27, 2017, 01:07:35 pm »
0

Although a part of me wants to protest that if everything consists of empty sets, there is ultimately nothing inside!

Haddock

  • Minion
  • *****
  • Offline Offline
  • Posts: 725
  • Shuffle iT Username: Haddock
  • Doc Cod
  • Respect: +558
    • View Profile
Re: Maths thread.
« Reply #763 on: January 27, 2017, 01:21:46 pm »
0

Although a part of me wants to protest that if everything consists of empty sets, there is ultimately nothing inside!
The set {{}} is not empty!  The bracket structure itself is what's inside.

This was one of the things I loved most about basic Set Theory.  It reduces all of mathematics to the question of looking at pretty patterns of brackets.

That script is weird. The author says that the AC is true, and thinks that there is hope that there will be a solution to the question of wether CH is true or not. The most interesting things I learned in my set theory lectures is that these things are independant of the other axioms.
That pretty much settles it - silver, don't use those notes!

(Though it's arguably legitimate to state that you believe in AC - or CH.  But really that's just the mathematician's equivalent of faith in <insert deity here>.)

Logged
The best reason to lynch Haddock is the meltdown we get to witness on the wagon runup. I mean, we should totally wagon him every day just for the lulz.

M Town Wins-Losses (6-2, 75%): 71, 72, 76, 81, 83, 87 - 79, 82.  M Scum Wins-Losses (2-1, 67%): 80, 101 - 70.
RMM Town Wins-Losses (3-1, 75%): 42, 47, 49 - 31.  RMM Scum Wins-Losses (3-3, 50%): 33, 37, 43 - 29, 32, 35.
Modded: M75, M84, RMM38.     Mislynched (M-RMM): None - 42.     Correctly lynched (M-RMM): 101 - 33, 33, 35.       MVPs: RMM37, M87

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Maths thread.
« Reply #764 on: January 27, 2017, 01:25:57 pm »
0

That script is weird. The author says that the AC is true, and thinks that there is hope that there will be a solution to the question of wether CH is true or not. The most interesting things I learned in my set theory lectures is that these things are independant of the other axioms.
That pretty much settles it - silver, don't use those notes!

(Though it's arguably legitimate to state that you believe in AC - or CH.  But really that's just the mathematician's equivalent of faith in <insert deity here>.)

Yeah, it is. However the main thing set theory is good for is to establish that it's both valid to think that CH (and to a lesser extent AC) is true or that it's false.
Logged

silverspawn

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5300
  • Shuffle iT Username: sty.silver
  • Respect: +3188
    • View Profile
Re: Maths thread.
« Reply #765 on: January 27, 2017, 01:58:37 pm »
0

The set {{}} is not empty!  The bracket structure itself is what's inside.
I know :P

That pretty much settles it - silver, don't use those notes!
Alright – do you have a link to the Oxford Script?

Haddock

  • Minion
  • *****
  • Offline Offline
  • Posts: 725
  • Shuffle iT Username: Haddock
  • Doc Cod
  • Respect: +558
    • View Profile
Re: Maths thread.
« Reply #766 on: January 27, 2017, 04:23:57 pm »
0

That script is weird. The author says that the AC is true, and thinks that there is hope that there will be a solution to the question of wether CH is true or not. The most interesting things I learned in my set theory lectures is that these things are independant of the other axioms.
That pretty much settles it - silver, don't use those notes!

(Though it's arguably legitimate to state that you believe in AC - or CH.  But really that's just the mathematician's equivalent of faith in <insert deity here>.)

Yeah, it is. However the main thing set theory is good for is to establish that it's both valid to think that CH (and to a lesser extent AC) is true or that it's false.
Ha! A fair perspective I guess, though I think it also has other values.  :Do

The set {{}} is not empty!  The bracket structure itself is what's inside.
I know :P

That pretty much settles it - silver, don't use those notes!
Alright – do you have a link to the Oxford Script?
I'll PM you.
Logged
The best reason to lynch Haddock is the meltdown we get to witness on the wagon runup. I mean, we should totally wagon him every day just for the lulz.

M Town Wins-Losses (6-2, 75%): 71, 72, 76, 81, 83, 87 - 79, 82.  M Scum Wins-Losses (2-1, 67%): 80, 101 - 70.
RMM Town Wins-Losses (3-1, 75%): 42, 47, 49 - 31.  RMM Scum Wins-Losses (3-3, 50%): 33, 37, 43 - 29, 32, 35.
Modded: M75, M84, RMM38.     Mislynched (M-RMM): None - 42.     Correctly lynched (M-RMM): 101 - 33, 33, 35.       MVPs: RMM37, M87

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #767 on: January 27, 2017, 10:01:17 pm »
0

I am taking a course on set theory this semester, here is what we are using: https://www.math.ku.edu/~roitman/SetTheory.pdf
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #768 on: January 28, 2017, 11:28:01 am »
0

What is the best thing to read if I want to learn set theory? If there is free access to it online, that's a bonus.

I started here ... I don't think I can judge yet whether that's a good script. a few chapters in I took a peek forward and saw that they define the natural numbers as

0                 =  ∅
1 = {0}        = {∅}
2 = {0, 1}     = {∅, {∅}}
3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}
etc.

Is this how proper set theory works – constructing everything through empty sets and sets of empty sets?

Well, there are really two things going on here. First we write down the rules for what arithmetic ought to obey, which we call axioms, e.g. the Peano axioms.

Next, we go about constructing a model of these axioms, that is a set of objects and operations that satisfy the axioms. There are usually lots and lots of different models, and they might not all behave the same way. One model is this one involving nested sets and empty sets.

For another example, in real analysis you usually write down a few axioms for the real numbers, namely those of being a complete ordered field. One model is given by Dedekind cuts, another is given by equivalence classes of Cauchy sequences. Neither model can be said to be the "true" real numbers.

When people say that AC is independent of ZF, they mean that there is both a model of ZF which satisfies AC and a model of ZF where AC fails.
« Last Edit: January 28, 2017, 11:29:05 am by SirPeebles »
Logged
Well you *do* need a signature...

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #769 on: February 22, 2017, 09:21:15 pm »
+1

Is this a correct proof that the square root of all natural numbers that aren't perfect squares is irrational?

Consider a natural number n that is not a perfect square.

Case 1. The prime factorization of n contains one of each of its factors.

Assume sqrt(n) = a/b, with a, b ∈ N with no common factors.  Then n = a2/b2 and b2n=a2.  This means than n|a2.  Because n only contains one of each of its factors, and a contains each of its factors at least twice, n|a.  Let c = a/n.  c ∈ N because n|a.  Then a = cn and putting it in the earlier equation gives b2n = c2n2, or just b2=c2n.  This means that n|b^2, and by the same reasoning as earlier, n|b.  This is a contradiction, as a and b should have no common factors.

Case 2. The prime factorization of n contains more than one of some of its factors.

Keep pulling out squares from the prime factorization of n until there are no duplicates in its factors.  The result will be a number that contains one of each of its factors (which is irrational by Case 1) times an integer.  This is an irrational number times an integer, which itself is an irrational number.


Now, I can't see anything wrong with it.  However, I did some googling and I didn't really see anybody use something this simple.  Someone said all the proofs he's seen used the fundamental theorem of arithmetic.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #770 on: February 22, 2017, 10:29:07 pm »
0

The fundamental theorem of arithmetic simply states that every positive integer has a unique prime factorization, which you use in your proof. So it's really nothing special, and your proof seems normal to me.

Here's a slightly shorter way of putting it that might be a bit too succinct:

Suppose for contradiction that there is a natural n not a perfect square with sqrt(n) rational. Then there exist natural a,b such  that b2n = a2. A natural number is a perfect square if and only if the exponents in the prime factorization of the number are all even. Since b2 is a perfect square and n is not, there is an odd exponent in the prime factorization of n and therefore there is an odd exponent in the prime factorization of b2n, since an odd exponent is added to an even one. But then b2n is not a perfect square, while a2 is, a contradiction.

EDIT: I am reminded of an overkill proof that 21/n is irrational for all natural n > 1. For the case n = 2 use the proof above. For n > 2, suppose that 21/n = b/a is rational. Then 2 = bn/an, and so 2an = bn. Well, in this case, an + an = bn would be a contradiction of fermat's last theorem, so 21/n cannot be rational.
« Last Edit: February 22, 2017, 10:38:41 pm by liopoil »
Logged

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2210
  • Respect: +2854
    • View Profile
Re: Maths thread.
« Reply #771 on: February 22, 2017, 11:43:52 pm »
+1

Your proof looks correct.

Some searching turned up http://math.stackexchange.com/questions/189130/prove-that-if-n-is-not-the-square-of-a-natural-number-then-sqrtn-is-irra which looks similarly simple and works along the same lines as yours (but it does the contradiction earlier.)

I also found the thread with the comment you specified, where they talk about unique factorization domains, rings, etc. The problem is that thread is made of people who are used to thinking at a more abstract level, so the proofs they give are simple to them, or have potential to generalize better to more abstract algebras.

Note: sudgy's proof doesn't require unique prime factorization. If numbers had more than 1 prime factorization, you could pick one of those factorizations arbitrarily and the proof would still work.

Edit: I heard the overkill proof technically doesn't work because requiring Fermat's Last Theorem makes it circular, but I don't want to bother checking whether that's true.
« Last Edit: February 22, 2017, 11:47:06 pm by Titandrake »
Logged
I have a blog! It's called Sorta Insightful. Check it out?

theorel

  • Spy
  • ****
  • Offline Offline
  • Posts: 86
  • Shuffle iT Username: theorel
  • Respect: +57
    • View Profile
Re: Maths thread.
« Reply #772 on: February 24, 2017, 04:14:52 pm »
+1

I don't think sudgy's proof works without the fundamental theorem of arithmetic.

In particular, I'm not sure that
Quote
Because n only contains one of each of its factors, and a2 contains each of its factors at least twice, n|a
holds without fundamental theorem of arithmetic. 

I think with non-unique factorizations, you can't require n to have one of each factor and a2 to have 2 of each factor and every factor of n to be one of those duplicated factors.  You can only require any 2 of them.
Logged

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 623
  • Shuffle iT Username: Cuzz
  • Respect: +1018
    • View Profile
Re: Maths thread.
« Reply #773 on: February 24, 2017, 05:57:55 pm »
+1

I've just been reading a bunch of Doron Zeilberger's opinions and other writings on ultrafinitism and I legitimately can't tell whether I just find them hilariously snarky or if they're actually starting to sway me. 
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #774 on: February 24, 2017, 06:05:49 pm »
0

I've just been reading a bunch of Doron Zeilberger's opinions and other writings on ultrafinitism and I legitimately can't tell whether I just find them hilariously snarky or if they're actually starting to sway me.

Wait, how do you know Doron Zeilberger?  He's at Rutgers; I did my PhD there.
Logged
Pages: 1 ... 29 30 [31] 32 33 ... 47  All
 

Page created in 0.083 seconds with 21 queries.