Post has attachment
Life on the Infinite Farm

This is a great book about infinity - for kids.   For example, there's a cow named Gracie with infinitely many legs.  She likes new shoes, but she wants to keep wearing all her old shoes.  What does she do?

Life on the Infinite Farm is by Richard Evan Schwartz, and it's free here:

https://www.math.brown.edu/~res/farm.pdf

Later it will be published on paper by the American Mathematical Society.  I really like turning the pages when I'm reading a book to a child.  Is that old-fashioned?  What do modern parents think?

Gracie's tale is just a retelling of the first Hilbert Hotel story.  There's a hotel with infinitely many rooms.  Unfortunately they're all full.  A guest walks in.  What do you do? 

You move the guest in room 1 to room 2, the guest in room 2 to room 3, and so on.  Now there's a room available!

The Hilbert Hotel stories were introduced by the great mathematician David Hilbert in a 1924 lecture, and popularized by George Gamow in his classic One Two Three... Infinity.   That book made a huge impression on me as a child: one of my first times I tasted the delights of mathematics.    

But that book is not good for children just learning to read.  Life on the Infinite Farm is.  And there's nothing that smells like "education" in this book.  It's just fun.

You can read more Hilbert Hotel stories here:

https://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel

But it's probably more fun to read Gamow's One Two Three... Infinity.   He was an excellent astrophysicist who in 1942 figured out how the first elements were created - the theory of Big Bang nucleosynthesis.    He was also a coauthor of the famous Alpher-Bethe-Gamow paper on this topic, also known as the αβγ paper.    Alpher was a grad student of Gamow, and they added the famous nuclear physicist Hans Bethe as a coauthor just for fun - since 'Bethe' is pronounced like the Greek letter 'beta':

It seemed unfair to the Greek alphabet to have the article signed by Alpher and Gamow only, and so the name of Dr. Hans A. Bethe was inserted in preparing the manuscript for print. Dr. Bethe, who received a copy of the manuscript, did not object, and, as a matter of fact, was quite helpful in subsequent discussions. There was, however, a rumor that later, when the alpha, beta, gamma theory went temporarily on the rocks, Dr. Bethe seriously considered changing his name to Zacharias.

Gamow also had a real knack for explaining things in fun ways, with the help of charming pictures.   I don't do many advertisements for commercial products, but I will for this!  You can get his book for as little as $2.98 plus shipping:

https://www.amazon.com/One-Two-Three-Infinity-Speculations/dp/0486256642/

You should have read it by the time you were a teenager - but if you didn't, maybe it's not too late.

For more about Gamow, see:

https://en.wikipedia.org/wiki/αβγ_paper

#bigness
Photo

Post has attachment
The quest for larger infinities

There are different kinds of bigness.   But they're connected.

There's a fascinating contest where you try to write the computer program of a certain length that would print out the largest possible integer.    This contest was actually carried out on the xkcd blog, and Eliezer Yudkowsky won.  Unless you know more about logic than he does, you won't be able to beat him.

There's another contest where you try to name the largest "computable ordinal", and that's what my post is about:

https://johncarlosbaez.wordpress.com/2016/07/07/large-countable-ordinals-part-3/

And there's another contest where you try to name the largest "cardinal".   Here we get into inaccessible cardinals, indescribable cardinals, huge cardinals, superhuge cardinals and the like. 

But these three contests turn out to deeply related!   There's a way to name huge integers using fast-growing functions that you can describe using large computable ordinals.  And Yudkowsky won the contest to write a program that prints out a large integer by taking advantage of a very large cardinal.

So, there's a spooky connection between large finite numbers, large computable ordinals - which are all countable, by the way - and large cardinals, which are not countable.  Many theorems point at this connection, but the full story remains obscure.  I believe when it becomes clear we'll get a whole new idea of what the infnite is all about.

As for me, I need a break.  My post takes you up to the large Veblen ordinal, a whopping large computable ordinal... but I know people have studied others that dwarf this one.  As Bilbo said:

The Road goes ever on and on
Out from the door where it began.
Now far ahead the Road has gone,
Let others follow it who can!
Let them a journey new begin,
But I at last with weary feet
Will turn towards the lighted inn,
My evening-rest and sleep to meet.

#bigness  
Photo

Post has attachment
♥ ♥ ♥ I love infinity ♥ ♥ ♥

Some infinities are countable, like the number of integers.  Others are uncountable, like the number of points on a line. 

Uncountable infinities are hard to fully comprehend.  For example, even if you think an infinity is uncountable, someone else may consider it countable!  That's roughly what the Löwenheim–Skolem theorem says. 

How is this possible? 

Ultimately, it's because there are only a countable number of sentences in any language with finitely many letters.  So, no matter how much you talk, you can never convince me that you're talking about something uncountable!
 
Now, if we take a really hard-ass attitude, we have to admit we can never actually write infinitely many sentences.   So even countable infinities remain outside our grasp.   However, we come "as close as we want", in the sense that we can keep counting

0, 1, 2, 3, 4,  ...

and nothing seems to stop us.  So, while we never actually reach the countably infinite, it's pretty easy to imagine and work with. 

Thus, my favorite infinities are the countable ordinals - in particular, the computable ones.   You can learn to do arithmetic with them.  You can learn to visualize them just as vividly as the set of all natural numbers, which is the first countable ordinal:

ω = {0,1,2,3,4,5,6,7,8,9,...}

For example,

ω+1 = {0,1,2,3,4,5,6,7,8,9,..., ω}

But as you keep trying to understand larger and larger countable ordinals, strange things happen.  You discover that you're fighting your own mind.

As soon as you see a systematic way to generate a sequence of larger and larger countable ordinals, you know this sequence has a limit that’s larger then all of those! And this opens the door to even larger ones….

So, this journey feels a bit like trying to outrace your car’s own shadow as you drive away from the sunset: the faster you drive, the faster it shoots ahead of you. You’ll never win.

On the other hand, you never need  to lose.  You only lose when you get tired.

And that's what I love: it becomes so obvious that the struggle to understand the infinite is a kind of mind game.  But it's a game that allows clear rules and well-defined outcomes, not a disorganized mess.

In this post:

https://johncarlosbaez.wordpress.com/2016/07/04/large-countable-ordinals-part-2/

I'll take you on a tour of countable ordinals up to the Feferman–Schütte ordinal.  Hop in and take a ride!

And if you don't know the Löwenheim–Skolem theorem, you've gotta learn about it.  It's one of the big surprises of early 20th-century logic:

https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem

The pink and the hearts, by the way, are just to scare certain people.

#bigness  
Photo

Post has attachment
Driving to infinity

A long time ago, before most of you showed up on Google+, I wrote a story about infinity.  It featured a character who was recruited by the US government to fight in the War on Chaos.  His mission was to explore larger and larger infinities.  

You can see that story in my "bigness" collection - lots of posts, each one its own little chapter.

But I keep wanting to talk about infinity - it's endlessly interesting!   I keep learning more about it.  Some posts here by +Refurio Anachro re-ignited my desire to write about it, and now I have.  Here's the first of three articles:

https://johncarlosbaez.wordpress.com/2016/06/29/large-countable-ordinals-part-1/

If you read this, you'll learn about the two basic kinds of infinities discovered by Cantor: cardinals and ordinals.   Then we'll go on a road trip through larger and larger ordinals.

The picture here shows some of the first ones we'll meet on our trip.  Omega, written ω, is the first infinite ordinal:

ω = {0,1,2,3,4,5,6,7,8,9,...}

Each turn of the spiral here takes you to a higher power of omega, and if you go around infinitely many times, you reach omega to the omegath power.   There are many ways to visualize this ordinal, and I explain a few. 

But my road trip will take you much further than that!

In this first episode, we reach an ordinal called epsilon nought, first discovered by Cantor.  In the second episode we'll go up the Feferman–Schütte ordinal.  In the third we'll reach the small Veblen ordinal and even catch a glimpse of the large Veblen ordinal.

All these are countable ordinals, and you can write computer programs to calculate with them, so I consider them just as concrete as the square root of 2.  And yet, they're quite mind-blowing.

#bigness  
Photo

Post has attachment
The world's most long-winded proof

In the 1980s, the famous mathematician Ronald Graham asked if it's possible to color each positive integer either red or blue, so that no triple of integers a, b and c obeying Pythagoras’ famous equation:

a² + b² = c²

all have the same color.  He offered a prize of $100.

Now it's been solved!  The answer is no.  You can do it for numbers up to 7824, and a solution is shown in this picture.  But you can't do it for numbers up to 7825.

To prove this, you could try all the ways of coloring these numbers and show that nothing works.  Unfortunately that would require trying

3 628 407 622 680 653 855 043 364 707 128 616 108 257 615 873 380 491 654 672 530 751 098 578 199 115 261 452 571 373 352 277 580 182 512 704 196 704 700 964 418 214 007 274 963 650 268 320 833 348 358 055 727 804 748 748 967 798 143 944 388 089 113 386 055 677 702 185 975 201 206 538 492 976 737 189 116 792 750 750 283 863 541 981 894 609 646 155 018 176 099 812 920 819 928 564 304 241 881 419 294 737 371 051 103 347 331 571 936 595 489 437 811 657 956 513 586 177 418 898 046 973 204 724 260 409 472 142 274 035 658 308 994 441 030 207 341 876 595 402 406 132 471 499 889 421 272 469 466 743 202 089 120 267 254 720 539 682 163 304 267 299 158 378 822 985 523 936 240 090 542 261 895 398 063 218 866 065 556 920 106 107 895 261 677 168 544 299 103 259 221 237 129 781 775 846 127 529 160 382 322 984 799 874 720 389 723 262 131 960 763 480 055 015 082 441 821 085 319 372 482 391 253 730 679 304 024 117 656 777 104 250 811 316 994 036 885 016 048 251 200 639 797 871 184 847 323 365 327 890 924 193 402 500 160 273 667 451 747 479 728 733 677 070 215 164 678 820 411 258 921 014 893 185 210 250 670 250 411 512 184 115 164 962 089 724 089 514 186 480 233 860 912 060 039 568 930 065 326 456 428 286 693 446 250 498 886 166 303 662 106 974 996 363 841 314 102 740 092 468 317 856 149 533 746 611 128 406 657 663 556 901 416 145 644 927 496 655 933 158 468 143 482 484 006 372 447 906 612 292 829 541 260 496 970 290 197 465 492 579 693 769 880 105 128 657 628 937 735 039 288 299 048 235 836 690 797 324 513 502 829 134 531 163 352 342 497 313 541 253 617 660 116 325 236 428 177 219 201 276 485 618 928 152 536 082 354 773 892 775 152 956 930 865 700 141 446 169 861 011 718 781 238 307 958 494 122 828 500 438 409 758 341 331 326 359 243 206 743 136 842 911 727 359 310 997 123 441 791 745 020 539 221 575 643 687 646 417 117 456 946 996 365 628 976 457 655 208 423 130 822 936 961 822 716 117 367 694 165 267 852 307 626 092 080 279 836 122 376 918 659 101 107 919 099 514 855 113 769 846 184 593 342 248 535 927 407 152 514 690 465 246 338 232 121 308 958 440 135 194 441 048 499 639 516 303 692 332 532 864 631 075 547 542 841 539 848 320 583 307 785 982 596 093 517 564 724 398 774 449 380 877 817 714 717 298 596 139 689 573 570 820 356 836 562 548 742 103 826 628 952 649 445 195 215 299 968 571 218 175 989 131 452 226 726 280 771 962 970 811 426 993 797 429 280 745 007 389 078 784 134 703 325 573 686 508 850 839 302 112 856 558 329 106 490 855 990 906 295 808 952 377 118 908 425 653 871 786 066 073 831 252 442 345 238 678 271 662 351 535 236 004 206 289 778 489 301 259 384 752 840 495 042 455 478 916 057 156 112 873 606 371 350 264 102 687 648 074 992 121 706 972 612 854 704 154 657 041 404 145 923 642 777 084 367 960 280 878 796 437 947 008 894 044 010 821 287 362 106 232 574 741 311 032 906 880 293 520 619 953 280 544 651 789 897 413 312 253 724 012 410 831 696 803 510 617 000 147 747 294 278 502 175 823 823 024 255 652 077 422 574 922 776 413 427 073 317 197 412 284 579 070 292 042 084 295 513 948 442 461 828 389 757 279 712 121 164 692 705 105 851 647 684 562 196 098 398 773 163 469 604 125 793 092 370 432

possibilities.  But recently, three mathematicians cleverly figured out how to eliminate most of the options.  That left fewer than a trillion to check!  

So they spent 2 days on a supercomputer, running 800 processors in parallel, and checked all the options.  None worked.   They verified their solution on another computer.

This is the world's biggest proof: it's 200 terabytes long!  That's about equal to all the digitized text held by the US Library of Congress.  There's also a 68-gigabyte digital signature - sort of a proof that a proof exists - if you want to skim it.

It's interesting that these 200 terabytes were used to solve a yes-or-no question, whose answer takes a single bit to state: no.

I'm not sure breaking the world's record for the longest proof is something to be proud of.  Mathematicians prize short, elegant proofs.   I bet a shorter proof of this result will eventually be found.

Still, it's fun that we can do such things.   Here's a story about the proof:

http://www.nature.com/news/two-hundred-terabyte-maths-proof-is-largest-ever-1.19990

and here's the actual paper:

• Marijn J. H. Heule, Oliver Kullmann and Victor W. Marek, Solving and verifying the Boolean Pythagorean triples problem via cube-and-conquer, http://arxiv.org/abs/1605.00723.

The cube-and-conquer paradigm is a "hybrid SAT method for hard problems, employing both look-ahead and CDCL solvers"... whatever that means.  It would be interesting to learn about this.  But it's time for breakfast!

Anyone who makes a joke about Fermat's remark:

"I have discovered a truly marvellous proof of this, which this margin is too narrow to contain."

loses 10 points, for not reading my whole post.

#bigness  
Photo

Post has attachment
Logic hacking

In mathematics, unlike ordinary life, the boundary between the knowable and the unknowable is a precisely defined thing.   But finding it isn't easy.  Its exact location could itself  be unknowable.  But we don't even know that! 

This month, a bunch of 'logic hackers' have stepped up to the plate and made a lot of progress.  They've sharpened our estimate of where this boundary lies.  How?   By writing shorter and shorter computer programs for which it's unknowable whether these programs run forever, or stop.

A Turing machine is a simple kind of computer whose inner workings have N different states, for some number N = 1,2,3,...

The Busy Beaver Game is to look for the Turing machine with N states that runs as long as possible before stopping.  Machines that never stop are not allowed in this game. 

We know the winner of the Busy Beaver Game for N = 1,2,3 and 4.  Already for N = 5, the winner is unknown.  The best known contestant is a machine that runs for 47,176,870 steps before stopping.  There are 43 machines that might or might not stop - we don't know. 

When N is large enough, the winner of the Busy Beaver Game is unknowable

More precisely, if you use the ordinary axioms of mathematics, it's impossible to prove that any particular machine with N states is the winner of the Busy Beaver Game... as long as those axioms are consistent.

How big must N be, before we hit this wall?

We don't know. 

But earlier this month, Adam Yedidia and Scott Aaronson showed that it's 7910 or less. 

And by now, thanks to a group of logic hackers like Stefan O’Rear, we know it's 1919 or less. 

So, the unknowable kicks in - the winner of the Busy Beaver Game for N-state Turing machines becomes unknowable using ordinary math - somewhere between N = 5 and N = 1919. 

The story of how we got here is is fascinating, and you can read about it on my blog post:

https://johncarlosbaez.wordpress.com/2016/05/21/the-busy-beaver-game/

Anything that I didn't make clear here, should be explained there.  If it ain't clear there, ask me!

#bigness  

Post has attachment
The inaccessible infinite

In math there are infinite numbers called cardinals, which say how big sets are.  Some are small.  Some are big.  Some are infinite.  Some are so infinitely big that they're inaccessible - very roughly, you can't reach them using operations you can define in terms of smaller cardinals. 

An inaccessible cardinal is so big that if it exists, we can't prove that using the standard axioms of set theory! 

The reason why is pretty interesting.  Assume there's an inaccessible cardinal K.  If we restrict attention to sets that we can build up using fewer than K operations, we get a whole lot of sets.   Indeed, we get a set of sets that does not contain every set, but which is big enough that it's "just as good" for all practical purposes.

We call such a set a Grothendieck universe.   It's not the universe - we reserve that name for the collection of all sets, which is too big to be a set.  But all the usual axioms of set theory apply if we restrict attention to sets in a Grothendieck universe.  

In fact, if an inaccessible cardinal exists, we can use the resulting Grothendieck universe to prove that the usual axioms of set theory are consistent!   The reason is that the Grothendieck universe gives a "model" of the axioms - it obeys the axioms, so the axioms must be consistent.

However, Gödel's first incompleteness theorem says we can't use the axioms of set theory to prove themselves consistent.... unless they're inconsistent, in which case all bets are off.

The upshot is that we probably can't use the usual axioms of set theory to prove that it's consistent to assume there's an inaccessible cardinal.  If we could, set theory would be inconsistent!

Nonetheless, bold set theorists are fascinated by inaccessible cardinals, and even much bigger cardinals.  For starters, they love the infinite and its mysteries.   But also, if we assume these huge infinities exist, we can prove things about arithmetic that we can't prove using the standard axioms of set theory!

I gave a very rough definition of inaccessible cardinals.  It's not hard to be precise.  A cardinal X is inaccessible if you can't write it as a sum of fewer than X cardinals that are all smaller X, and if any cardinal Y is smaller than X, 2 to the Yth power is also smaller than X. 

Well, not quite.   According to this definition, 0 would be inaccessible - and so would the very smallest infinity.   Neither of these can be gotten "from below".  But we don't count these two cardinals as inaccessible.

https://ncatlab.org/nlab/show/inaccessible+cardinal

#bigness
Photo

Post has attachment
Computing the uncomputable

Last month the logician +Joel David Hamkins proved a surprising result: you can compute uncomputable functions!  

Of course there's a catch, but it's still interesting.

Alan Turing showed that a simple kind of computer, now called a Turing machine, can calculate a lot of functions.  In fact we believe Turing machines can calculate anything you can calculate with any fancier sort of computer.  So we say a function is computable if you can calculate it with some Turing machine.

Some functions are computable, others aren't.  That's a fundamental fact.

But there's a loophole.

We think we know what the natural numbers are:

0, 1, 2, 3, ...

and how to add and multiply them.  We know a bunch of axioms that describe this sort of arithmetic: the Peano axioms.  But these axioms don't completely capture our intuitions!  There are facts about natural numbers that most mathematicians would agree are true, but can't be proved from the Peano axioms.

Besides the natural numbers you think you know - but do you really? - there are lots of other models of arithmetic.  They all obey the Peano axioms, but they're different.  Whenever there's a question you can't settle using the Peano axioms, it's true in some model of arithmetic and false in some other model.

There's no way to decide which model of arithmetic is the right one - the so-called "standard" natural numbers.   

Hamkins showed there's a Turing machine that does something amazing.  It can compute any function from the natural numbers to the natural numbers, depending on which model of arithmetic we use. 

In particular, it can compute the uncomputable... but only in some weird "alternative universe" where the natural numbers aren't what we think they are. 

These other universes have "nonstandard" natural numbers that are bigger than the ones you understand.   A Turing machine can compute an uncomputable function... but it takes a nonstandard number of steps to do so.

So: computing the computable takes a "standard" number of steps.   Computing the uncomputable takes a little longer.

This is not a practical result.  But it shows how strange simple things like logic and the natural numbers really are.

For a better explanation, read my blog post:

https://johncarlosbaez.wordpress.com/2016/04/02/computing-the-uncomputable/

And for the actual proof, go on from there to the blog article by +Joel David Hamkins.

#bigness  
Photo

Post has attachment
Music of the primes

I often hear there's no formula for prime numbers. But Riemann came up with something just as good: a formula for the prime counting function.

This function, called π(x), counts how many prime numbers there are less than x, where x is any number you want. It keeps climbing like a staircase, and it has a step at each prime. You can see it in this gif.

Riemann's formula is complicated, but it lets us compute the prime counting function using a sum of wiggly functions. These wiggly functions vibrate at different frequencies. Poetically, you could say they reveal the secret music of the primes.

The frequencies of these wiggly functions depend on where the Riemann zeta function equals zero.

So, Riemann's formula turns the problem of counting primes less than some number into another problem: finding the zeros of the Riemann zeta function!

This doesn't make the problem easier... but, it unlocks a whole new battery of tricks for understanding prime numbers! Many of the amazing things we now understand about primes are based on Riemann's idea.

It also opens up new puzzles, like the Riemann Hypothesis: a guess about where the Riemann zeta function can be zero. If someone could prove this, we'd know a lot more about prime numbers!

The animated gif here shows how the prime counting function is approximated by adding up wiggly functions, one for each of the first 500 zeros of the Riemann zeta function. So when you see something like "k = 230", you're getting an approximation that uses the first 230 zeros.

You may need to reload this picture to get the animated gif to move - it's not looped.

And that's a problem I want to solve! Is there a way to "loopify" a gif? Or can someone make a nice looped gif of something like this? If so, I could feature it on my blog Visual Insight, and credit you!

I got this gif here:

http://www.dartmouth.edu/~chance/chance_news/recent_news/chance_news_10.10y.html

and here you can see Riemann's formula. You'll see that some other functions, related to the prime counting function, have simpler formulas.

And by the way: when I'm talking about zeros of the Riemann zeta function, I only mean zeros in the critical strip, where the real part is between 0 and 1. The Riemann Hypothesis says that for all of these, the real part is exactly 1/2.  This has been checked for the first 10,000,000,000,000 zeros.

That sounds pretty convincing, but it shouldn't be. After all, the number 6 is the most common gap between consecutive primes if we look at numbers less than something like 17,427,000,000,000,000,000,000,000,000,000... but then that pattern stops!

So, you shouldn't look at a measly few examples and jump to big conclusions when it comes to primes.

#bigness
Animated Photo

Post has attachment
Scared of big numbers? Don't read this!

People love twin primes - primes separated by two, like 11 and 13. Nobody knows if there are infinitely many. There probably are. There are certainly lots.

But a while back, a computer search showed that among numbers less than a trillion, most common distance between successive primes is 6.

It seems that this trend goes on for quite a while longer…

... but in 1999, three mathematicians discovered that at some point, the number 6 ceases to be the most common gap between successive primes!

When does this change happen? It seems to happen around here:

17,427,000,000,000,000,000,000,000,000,000

At about this point, the most common gap between consecutive primes switches from 6 to 30. They didn't prove this, but their argument has convinced the experts, and they checked it with some other calculations.

The same argument shows that eventually 30 ceases to be the most common gap between successive primes. The number 210 takes over! It happens somewhere roughly around here:

1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

That's 10 to the 450th power.

In fact, they argued that this pattern keeps on forever. For a little while 2 is the most common prime gap, then it's 6, then it's 30, then it's 210, then it's 2310, and so on. And these numbers are very interesting. They're called primorials:

2

2⋅3=6

2⋅3⋅5= 30

2⋅3⋅5⋅7=210

2⋅3⋅5⋅7⋅11=2310

For more details, check out my blog article:

https://golem.ph.utexas.edu/category/2016/03/the_most_common_prime_gaps.html

#bigness

Photo
Wait while more posts are being loaded