-
Mathematical Magic Tricks - Numericana
-
10 Easy Arithmetic Tricks - Listverse
-
Mathematical Tricks
Mathematical tricks and mental arithmetic, multiply up to 19 x 19 in your head. Other methods of multiplying large numbers.
www.splung.com/content/sid/1/page/tricks - Cached - Similar - -
Mathematical Puzzles and Tricks
www.doe.virginia.gov/Div/Winchester/jhhs/math/.../puzzles.html - Similar - - [PDF]
Mathematical Card Tricks
File Format: PDF/Adobe Acrobat - View
Mathematical Card Tricks. Tom Davis tomrdavis@earthlink.net http://www.geometer.org/mathcircles. May 26, 2008. At the April 10, 2008 meeting of the ...
www.geometer.org/mathcircles/CardTricks.pdf - Similar - -
Impress your friends with mental Math tricks » Fun Math Blog
-
Math Tricks and Treats
Mathematical Tricks and Treats. Steve Bergen ( ). Overview: I started teaching math back in 1973 when I graduated from college. Over the years, I have loved ...
www.summercore.com/math/trickstreats.html - Similar - -
Colm's Cards -- Mathematical Card Tricks
Earlier, several mathematical card tricks were discussed in an article at the AMS's October 2000 What's New in Mathematics site. ...
www.spelman.edu/~colm/cards.html - Cached - Similar - -
Card Tricks and Mathematics - Feature Column from the AMS
``Mathematical card tricks, let it be admitted at once, are precisely the kind of tricks that are the most boring to most people,'' warned Martin Gardner as ...
www.ams.org/featurecolumn/archive/mulcahy1.html - Similar -
by C Mulcahy - Cited by 1 - Related articles - All 8 versions -
Interactive Mathematics Miscellany and Puzzles, Index
Use it to solve more advanced problems and explain the wondeful and funny arithmetic tricks. Mathematics is really a great fun. There is no wonder that math ...
www.cut-the-knot.org/ - Cached - Similar - -
Welcome to the Tricki | Tricki
-
Groups Discussing mathematical tricks and puzzles | Yahoo! Groups
-
Mathematical Magic Tricks — Department of Mathematics and Computer ...
-
Mathematical Tricks
All articles related to Mathematical Tricks written by Suite101 experts - enter curious.
www.suite101.com/reference/mathematical_tricks - Cached - Similar - -
video Math Number Tricks and Math Games - math, number, tricks ...
video Math Number Tricks and Math Games - http://welovesolutions.com/index.html Math Number Tricks and Math Games Are you Excited to do some magic number ...
www.kewego.com/video/iLyROoafJstd.html - Cached - Similar - -
Scratch Your Brain Where It Itches: Math Games, Tricks and Quick ...
ED401159 - Scratch Your Brain Where It Itches: Math Games, Tricks and Quick Activities, Book B-1.
www.eric.ed.gov/ERICWebPortal/recordDetail?accno... - Cached - Similar -
by L Brumbaugh - 1994 -
Mathematical Card Tricks
-
Free Card Tricks - Easy, Self Working, Mathematical, Unusual
Free card tricks including easy, self working, mathematical and unusual card tricks. Also sleight of hand tricks.
www.card-trick.com/free_card_tricks.htm - Cached - Similar -
More results from www.card-trick.com » -
Tricks for Solving Math Problems - Math Forum - Ask Dr. Math
-
Math Forum: Calculation Tips & Tricks
From the Archives of the Math Forum's Internet project Ask Dr. Math - our thanks to Ethan 'Dr. Math' Magness, Steven 'Dr. Math' Sinnott, and, ...
mathforum.org/k12/mathtips/division.tips.html - Cached - Similar -
More results from mathforum.org » -
Amazon.com: Rapid Math Tricks & Tips: 30 Days to Number Power ...
Amazon.com: Rapid Math Tricks & Tips: 30 Days to Number Power (9780471575634): Edward H. Julius: Books.
www.amazon.com/Rapid-Math-Tricks-Tips.../0471575631 - Cached - Similar - -
Amazon.com: More Rapid Math: Tricks and Tips: 30 Days to Number ...
Key Phrases: rapid math tricks, emphasizing place value, brain builder example, .... Contains 50 fun new math tricks plus over 20 fresh parlor tricks, tips, ...
www.amazon.com/More-Rapid-Math-Tricks.../0471122386 - Cached - Similar -
More results from www.amazon.com » -
Mathematical Tricks Lesson #1 - Pricing - T-Shirt Forums
Alright I don't post much as you can see. However, I want to share with you a little secret. Now before I continue I want to make a few things clear.
www.t-shirtforums.com/pricing-heat-transfer.../t80012.html - Cached - Similar - -
Mathematical Magic Tricks In Multiplication
-
More mathematical tricks | Beautiful World | Sex | Drawings Arts ...
-
math card tricks
-
artdiamondblog.com: Publishing Pretty Papers Full of Clever ...
24 Dec 2006 ... (p. viii) Before I met Feynman, I had published a number of mathematical papers, full of clever tricks but totally lacking in im-(p. ...
www.artdiamondblog.com/archives/2006/12/post_77.html - Cached - Similar - -
Tricks & Mathematical Tips - Matlab Programming Tips - Page 5
-
Mathematical tricks using quadrilateral - Search Engine Rankings ...
-
Mathematical Tricks - Online Classes
2 Upcoming Classes found for Mathematical Tricks, See all public classes ... The Mathematics Millionaire : Series 1 Session 2 ...
www.wiziq.com/online-classes/mathematical-tricks - Cached - Similar - -
Tips and Tricks for Teaching Math Online
Just getting started? Need new techniques? Get encouragement and advice for everything from picking a course management system to adding instructor-cr....
www.wiziq.com/.../18208-Tips-and-Tricks-for-Teaching-Math-Online - Cached - Similar - -
Mathematical card tricks - Mathmatical magic
-
mathematical tricks | books tagged mathematical tricks | LibraryThing
Most often tagged mathematical tricks. Hexaflexagons and Other Mathematical Diversions: The First… by Martin Gardner (1); New mathematical diversions from ...
www.librarything.com/tag/mathematical+tricks - Cached - Similar - -
Mathematical methods and tricks to win money in online casinos
Mathematical methods and tricks to win in online casinos we have created some systems to extract cash quickly you can win between 100 To 300 dollars.
www.ganaraloscasinos.com/methods_tricks_win_casinos.php - Cached - Similar - -
Mathematical tricks - Rapidshare Search
Sponsored Links, mathematical tricks.full.rar · mathematical tricks [FullVersion] · [HIGHSPEED] mathematical tricks · [TRUSTED DOWNLOAD] mathematical tricks ...
rapidlibrary.com/index.php?q=mathematical+tricks - Similar - -
How to Perform Mathematical Card Tricks | eHow.com
How to Perform Mathematical Card Tricks. Mathematical card tricks are an easy way for beginners to get into magic because mathematical tricks rely on ...
www.ehow.com/how_2106606_perform-mathematical-card-tricks.html - Cached - Similar - -
Tricks With Numbers: Math Problems & History | eHow.com
Tricks With Numbers. Part of the series: Math Problems & History. Tricks with numbers are a great way to impress friends and work on basic math skills, ...
www.ehow.com/video_4754378_tricks-numbers.html - Cached - Similar -
More results from www.ehow.com » -
Start Saving Young, Mathematical Money Tricks @ The Carnivals
Time for the money carnivals. We start off with The Carnival of Personal Finance #118 at Money, Matter and More Musings.
www.thedigeratilife.com/.../start-saving-young-mathematical-money-tricks-the-carnivals/ - Cached - Similar - - [PDF]
Mathematical tricks
-
Tricks of the Windows game programming gurus - Google Books Result
by André LaMothe - 2002 - Games - 1063 pages
Mathematical Tricks Because a great deal of game programming is mathematical in nature, it pays to know better ways to perform math functions. ...
books.google.com/books?isbn=0672323699... - -
Math Tricks
-
eBook Math Magic (Magic Tricks)
eBook Math Magic (Magic Tricks). engineering Mathematics probability maths Geometry Graphs.
www.scribd.com/doc/.../eBook-Math-Magic-Magic-Tricks - Cached - Similar - -
Five Easy to Remember Mathematical Tricks You Can't Live Without ...
These simple math tricks can make day to day tasks much easier.
www.primermagazine.com/.../5-easy-to-remember-mathematical-tricks-you-cant-live-without - Cached - Similar - -
PROCON TECHNOLOGY - Maths tricks and tips
-
Online resources for TRAVEL GUIDE TO INDIA, MATHEMATICAL TRICKS ...
Ebooks providing tips on making money online, guide on travel to India and mathematical tricks fun!
www.welovesolutions.com/ - Cached - Similar - -
The Magical Bag of Mathematical Tricks - Wikipedia, the free ...
-
Tricks 4U - Home - Mathematical Tricks
-
Math Tricks Articles from ArticlesBase.com
Find math tricks articles at ArticlesBase.com a free articles directory. Submit your articles for free distribution and find content for your website, ...
www.articlesbase.com/article-tags/math-tricks - Cached - Similar - -
Tips And Tricks for Teaching Math Online Ppt Presentation
23 Jun 2008 ... Ideas, guidelines, and best practices for teaching math online posted by a community college professor.
www.authorstream.com/.../ffeldon-73416-tips-tricks-teaching-math-online-mathematics-learning-distance-education-itc-ppt-powerpoint/ - Cached - Similar - -
What are the best rules, formulas and tricks in math? | Ask Metafilter
-
Free PDF: Mathematical Card Tricks Pdf - PDFoo.com
Result for mathematical card tricks pdf on PDFoo.com, We provide free PDF files, free PDF ebooks and free PDF articles to be download.
www.pdfoo.com/result-mathematical-card-tricks--pdf.html - Cached - Similar - -
Hexaflexagons and other mathematical diversions: the first ... - Google Books Result
by Martin Gardner - 1988 - Mathematics - 200 pages
CHAPTER TEN Mathematical Card Tricks SOMERSET MAUGHAM'S short story "Mr. Know-All" contains the following dialogue: "Do you like card tricks? ...
books.google.com/books?isbn=0226282546... - -
A Mathematical Problem - Magic Tricks
Magic Trick: A Mathematical Problem. To pick out from a pack in one's pocket the card thought of, without asking a question. ...
www.classicmagic.net/tricks/124.php - Cached - Similar - -
Using magic to learn about maths
3 Jun 2009 ... “It's fascinating how many great magic tricks and more worryingly con tricks work using hidden mathematical principles”, explained Professor ...
www.physorg.com/news163261772.html - Cached - Similar - -
Flipkart.com: Math Challenges Puzzles Tricks & Games: Glen ...
Buy Math Challenges Puzzles Tricks & Games in India. Price:Rs.149 Free Shipping on Math Challenges Puzzles Tricks & Games. Book Review of Math Challenges ...
www.flipkart.com/math...tricks.../9831362055-1533f918g3 - Cached - Similar - -
Cool Math Tricks | Download Math Ebooks & Poems | Math by Joe
-
A wiki for math tricks! « Entertaining Research
-
Wiley::More Rapid Math: Tricks and Tips: 30 Days to Number Mastery
In this eagerly awaited sequel to the popular Rapid Math Tricks and Tips, Professor Ed Julius shows you how to master difficult problems in addition, ...
www.wiley.com/WileyCDA/.../productCd-0471122386.html - Cached - Similar - -
collection of mathematically elegant tricks | Comp.DSP ...
10 posts - 2 authors - Last post: 24 Jul 2005I don't remember how often I have been amazed by nice and elegant mathematical tricks that make difficult problem suddenly very easy and ...
www.dsprelated.com/showmessage/39294/1.php - Cached - Similar - -
Funschool - Carnival - Math Magic Tricks
-
Rapid Math Tricks and Tips: Thirty Days to Number Power: Amazon.co ...
Rapid Math Tricks and Tips: Thirty Days to Number Power: Amazon.co.uk: Edward H. Julius: Books.
www.amazon.co.uk/Rapid-Math-Tricks-Tips.../0471575631 - Cached - Similar - -
Science & Math Tricks ebooks : Lybrary.com
Science often appears like magic. Even some small physics or chemical experiment can be utterly baffling. Same is true with math.
www.lybrary.com/magic-science-math-tricks-c-21_40.html - Cached - Similar - -
Math Number Tricks and Math Games
http://welovesolutions.com/index.htmlMath Number Tricks and Math GamesAre you Excited to do some magic number tricks math games with your friends. ...
www.zango.com/Destination/Catalog/Play/Play.aspx?pid... - Cached - Similar - -
Mathematical problems and proofs: combinatorics, number theory, ... - Google Books Result
by Branislav Kisačanin - 1998 - Mathematics - 220 pages
Two Geometric Tricks At the end of this chapter we examine two mathematical tricks first published in l892 in the first edition of Ref. ...
books.google.com/books?isbn=0306459671... - -
Number Magic Tricks That Help Students Learn Math
“We have enjoyed watching and participating in the math tricks. It is fun to see our son astound our friends as well as ourselves. ...
www.morningriverpubs.com/W-MathShowtime.htm - Cached - Similar - -
Math Night Module: Topology Tricks
-
Tips and Tricks for Teaching Math Online
Hints, tips and best practices for teaching math online from a community college professor.
www.slideshare.net/.../tips-and-tricks-for-teaching-math-online - Cached - Similar - -
Card Tricks Anyone Can Do: A Mathematical Approach to Card Magic ...
16 Jun 2009 ... Download Free eBook:Card Tricks Anyone Can Do: A Mathematical Approach to Card Magic - Free chm, pdf ebooks rapidshare download, ...
www.ebookee.com/Card-Tricks-Anyone-Can-Do-A-Mathematical-Approach-to-Card-Magic_298231.html - Cached - Similar - -
Math Point: Mathematical Card Tricks
-
Download| math emagic (magic tricks) | Free PDF Ebook Download
-
Long Lynette Books - Math Smarts: Tips, Tricks, And Secrets For ...
-
Division Tips and Tricks | Dividing | Math | Homework Help ...
If your palms sweat and you hear the Jeopardy theme song every time you do division, we've got the tips for you. Check 'em out!
www.kidzworld.com/.../4979-math-help-division-tips-and-tricks - Cached - Similar - -
Ivars Peterson's MathTrek - Guessing Cards
24 Dec 2001 ... Mathematical Card Tricks. American Mathematical Society. Oct. 1. Available at http://www.ams.org/new-in-math/cover/mulcahy1.html. ...
www.maa.org/mathland/mathtrek_12_24_01.html - Cached - Similar - -
Calculator Tricks :: curiousmath :: math is an attitude
10 Feb 2003 ... It's an incredible bit of mathematical trivia. Begin with any two whole numbers, make a Fibonacci-type addition list, take the ratio of two ...
www.curiousmath.com/index.php?name=News&file...5 - Cached - Similar - -
The Online Mathematics Subject Tree
Math Tricks – Learn these mathematical tricks and start solving math problems in a flash. These helpful short cuts make learning math easy. ...
www.workathomenoscams.com/.../online-mathematics-subject-tree.html - Cached - Similar - -
MatheMajik - Indian site featuring calculation tricks and math ...
Science Central - 493282 - Mathemajic: Where maths means more.
www.sciencecentral.com/site/493282 - Cached - Similar - -
Easy Magic Tricks: The Telephone Predictor - Easy Magic Tricks ...
-
The Secret to Juggling -- Simulation Software Derives New Tricks ...
September 1, 2006 — Even old jugglers can learn new tricks from mathematics. Several computer algorithms are able to simulate the combinatorial patterns of ...
www.sciencedaily.com/.../0912-the_secret_to_juggling.htm - Cached - Similar - -
Mathematical Hacks and Tricks on the TI Calculator - United-TI
11 posts - 9 authors - Last post: 25 Nov 2007Now, I want to talk about little hacks you can do on a TI calculator for mathematical computations. (Sorry, no programs allowed in this ...
www.unitedti.org/index.php?showtopic=4367 - Cached - Similar - -
Mathematics, magic and mystery - Google Books Result
by Martin Gardner - 1956 - Games - 176 pages
Because of this richness of appropriate properties, mathematical card tricks are undoubtedly as old as playing cards themselves. ...
books.google.com/books?isbn=0486203352... - -
Math Magic Tricks
Math Magic Tricks. SAY: ALGEBRA: 1. Think of a number between 1 and 20. 2. Double it in your head. 3. Add 6. 4. Divide by 2. 5. Subtract the original number ...
app.ucdavis.edu/images/mathresources/MathMagicTricks.pdf - Similar - -
Simple Mathematical Trick — logical thinking
-
Math Card Tricks Are A Cool Way To Get Kids Excited About Math And ...
Discover how math card tricks help kids learn math skills and are alot of fun. You'll find both math card tricks and math card games on our site.
www.learn-with-math-games.com/math-card-tricks.html - Cached - Similar - - [PDF]
Fun Math Tips and Tricks
File Format: PDF/Adobe Acrobat - View as HTML
Fun Math Tips and Tricks. Explain to students that they always have the nine times table right in their hands. Make a large set of hands ...
wdtimes.net/NIE/FunMath.pdf - Similar - -
Friday Math Movie – Google Tricks, Hacks and Easter Eggs ...
3 Responses to “Friday Math Movie – Google Tricks, Hacks and Easter Eggs”. Happenings in the Math blogosphere » Fun Math Blog on March 22nd, 2008 8:27 am ...
www.squarecirclez.com/blog/friday-math...tricks.../1035 - Cached - Similar - -
Math Finger Tricks and Games to Learn and Practice the ...
Circle time is a great opportunity to demonstrate fun tricks that will get students interested in practicing their times tables. Nines Trick This trick will ...
www.googolpower.com/.../math-finger-tricks-and-games-to-learn-and-practice-the-multiplication-times-tables - Cached - Similar - -
Professor uses magic tricks to teach students math - International ...
3 Jun 2009 ... A professor from a British university has created a new way to help students to learn math by teaching them magic tricks.
www.ibtimes.com/.../professor-uses-magic-trick-teach-student-math.htm - Cached - Similar - -
AvaxHome -> Card Tricks Anyone Can Do: A Mathematical Approach to ...
-
Making math with yarn - LiveScience- msnbc.com
6 Jun 2008 ... New math tricks: knitting and crocheting. Yarn work helping to provide answers to wide range of math problems ...
www.msnbc.msn.com/id/25011806/ - Cached - Similar - -
Mathematical Card Tricks
Card Trick 2. updated 14July00.
www.laits.utexas.edu/hebrew/logic/cards/trick2.html - Cached - Similar - -
The Moscow puzzles: 359 mathematical recreations - Google Books Result
by Boris A. Kordemsky, Martin Gardner, Albert Parry - 1992 - Games - 320 pages
X Mathematical Games and Tricks Games 284. ELEVEN MATCHES On the table are 1 1 matches (or other objects). The first player picks up 1, 2, or 3 matches. ...
books.google.com/books?isbn=0486270785... - -
View topic - [DIS] [ASM] Dirty Math Tricks: Adventures in Division ...
20 posts - 5 authors - Last post: 31 Mar 2006Since division by 256 can be accomplished with the Dirty Math Trick of ignoring the lowest byte, we'll leave that to last and our equation ...
www.avrfreaks.net/index.php?name=PNphpBB2&file... - Cached - Similar - -
Paint Shop Pro: jpg quality, color saturation, mathematical tricks
-
Math Tricks
Here is a compendium of some of the more bizarre and impressive mathematical tricks, games, and demonstrations. Enjoy them at your leisure. ...
www.keithschwarz.com/mathtricks/ - Cached - Similar - -
Math Jubilee
-
Trick Bank, Tricks, Math Tricks, Magics, Phone Number Trick ...
-
The Mathematical Association - supporting mathematics in education
There is also a section dealing with mathematical card tricks that require no special card-handling skills to perform but still have the potential to create ...
www.m-a.org.uk/ - Similar - -
Video results for mathematical tricks
Jul 24, 2009
mathematical tricks - Google Search
Jul 14, 2009
An Interesting Problem
Continuing doing this until all the p cards are distributed completely.
Which person will get the last card? Or the p/2 (middle) cards?
Jun 17, 2009
Math « Luke Palmer
Archive for the ‘Math’ Category
Recursive Types in IΞ
In the last IΞ post, I introduced the calculus and sketched the construction of some standard mathematical objects. In this post, I will dive a little deeper and construct of all the positive recursive types. The proof will be in an informal style (in particular, omitting the H constraints), but I have little doubt that the proof will go through.
Only a superficial familiarity with IΞ is needed to understand this proof; I adopt a set-theoretic style notation, so the proof should be approachable. Here’s a quick refresher of the primitives of IΞ.
- Membership is application, so when I write
, this is translated into IΞ as
. Thus sets, unary predicates, and types are all the same thing.
- Because membership and application are identified, universal quantification and the subset relation are also.
means “A is a subset of B”, or “x in A implies x in B”. In particular, the pattern
can be interpreted as “for every a in A, P a”.
- L is the set of all sets (whose existence does not lead to a contradiction in this system!). I will give its definition at the end of the article.
- Other symbols have their usual interpretation, and I’ll include an appendix which gives them all precise definitions at the end.
Definition: A function is called monotone if
.
Intuitively, the monotone functions correspond roughly to the functors in Haskell; they use their parameter in a positive way (appear to the left of an even number of arrows).
Definition: The type recursion combinator μ is defined as: .
We are allowed to define things simply by giving a condition for membership like this. Formally, this definition starts out:
This definition intuitively says, x is in μ F if x is in every type closed under F. We will see that this definition corresponds to a type recursion combinator.
Lemma 1: If F is monotone, then .
Proof. Given
; show
. Expanding the definition of μ above:
Given
; show
.
Observe
: Suppose
, show
. Since
, we have
by definition of μ. Letting
, we have
from above, so
.
Therefore,
(by the monotonicity of F and
). QED.
Now for the easy direction:
Lemma 2: If F is monotone, then .
Proof. Given
; show
.
By the definition of μ, we have
. Let
. We have
by monotonicity of F and Lemma 1, therefore
. QED.
Which leads us to the recursion equation.
Theorem: If F is monotone, . (Proof trivial by the two lemmas)
I’m using set equality here, i.e. mutual containment, which is probably a bit weaker than Leibniz equality. It is obvious from the definition that this fixed point is minimal.
Monotonicity is easy to prove for any of the standard positive types (products, coproducts, functions). So we can model a good variety of Haskell data types already; however these are standard inductive (least fixed point) types, no infinite structures allowed. I’m still working on the encoding and analogous proofs for ν (greatest fixed point), which is closer to Haskell.
Hopefully I’ll be able to port many libraries (maybe after a few totality annotations) without having to worry about partiality. But there are more pressing matters, such as finishing my interactive proof assistant for IΞ.
Definitions
, the True proposition.
, the constant function.
, the set of all objects.
, function composition.
, the set of functions from a to b.
, the set of all sets.
, implication.
, universal quantification of types (like forall in Haskell)
, product type.
, coproduct type.
Some Constructions in IΞ
Over the past couple months, I have been attempting to find a language to use as a core calculus for Dana, as anyone who follows this blog knows. I have been slowly converging on IΞ for its elegance and simplicity. It turns out to be very powerful, capable of modeling many structures while avoiding many of the paradoxes typically involved with those structures. In this post, I give an exposition of IΞ and construct some common structures.
The main idea is to use lambda calculus for all of our symbol manipulation needs, adding a constant Ξ for quantification. “Types” are unary predicates, so membership is application. For example, “Nat 0″ is a proposition saying that 0 has type Nat (where 0 and Nat are given previous definitions somewhere).
ΞXY means “forall x, if X x, then Y x”, or, if you think of predicates as sets, simply “X is a subset of Y”. So if we have types Nat and Bool, we can say that f has type Nat → Bool with “ΞNat(\x. Bool (f x))”, read “forall x in Nat, f x is in Bool”. Very direct, is it not?
System I
Interpreting these meanings directly, we arrive at Curry’s System I, whose rules follow. A proposition (sequent) has the form “Γ |- X”, which has the interpretation “assuming Γ, X is provable”.
Γ |- X ⇐ X ∈ Γ Γ |- Y ⇐ Γ |- X ; X is βη convertible with Y Γ |- YZ ⇐ Γ |- XZ ; Γ |- ΞXY Γ |- ΞXY ⇐ Γ,Xa |- Ya ; a does not occur free in X,Y,Γ
I have stated the rules as “to prove X, you need to prove Y”, because that’s kinda how my brain works. Take a moment to internalize them. They are obvious given the above intuitions, and shouldn’t be hard to read.
On top of this, we can build propositional calculus. Define “K = \x. \y. x”, and write “X ⇒ Y” as shorthand for “Ξ(KX)(KY)”. This system has the properties you would expect of a simple propositional calculus.
Sadly, this system is inconsistent. We can prove any proposition X:
Let Y = (\x. x x ⇒ X) (\x. x x ⇒ X) Observe that Y = Y ⇒ X. [1] Y |- Y [2] Y |- Y ⇒ X [3] Y |- X -- modus ponens on [1],[2] [4] |- Y ⇒ X [5] |- Y [6] |- X -- modus ponens on [4],[5]
Martin Bunder had a brilliant idea to block this paradox, and also many others, which brings us to the object of my infatuation:
System IΞ
The crucial step above was [3]-[4], where we abstracted over the infinite proposition “((… ⇒ X) ⇒ X) ⇒ X”. The way we will block this is to only allow abstraction over finite propositions. Introduce a new symbol, H, such that HX means “X is a finite proposition” (or simply “X is a proposition”). We will derive finiteness from the finiteness of proofs: to prove HX, we first have to prove H of each component of X. Our system becomes (the new additions are in bold):
Γ |- X ⇐ X ∈ Γ Γ |- Y ⇐ Γ |- X ; X is βη convertible with Y Γ |- YZ ⇐ Γ |- XZ ; Γ |- ΞXY Γ |- ΞXY ⇐ Γ |- H(Xa) ; Γ,Xa |- Ya ; a does not occur free in X,Y,Γ Γ |- H(ΞXY) ⇐ Γ |- H(Xa) ; Γ,Xa |- H(Ya) ; a does not occur free in X,Y,Γ Γ |- H(HX)
The final rule is an axiom, simply saying that “X is a proposition” is always a proposition.
Constructing the Naturals
Now I will embark on constructing the type of naturals. Since types are predicates, I also need to come up with a representation for naturals. It turns out that it doesn’t matter what representation I use, as long as it has zero and a 1-1 successor function. For the sake of discussion, let’s use the Church encoding.
0 = \f. \x. x S n = \f. \x. f (n f x)
So a natural is an iteration function. For example, the number 3 iterates a function 3 times on its argument: 3 f x = f (f (f x)).
Coming up with a way to classify all of these, but not any others (such as infinity f x = f (f (f (f (f ...))))), was quite a challenge. You might try to classify these function on the property that they are an iteration function, but any sensible method of doing that ends up including infinity. I began thinking that IΞ was not strong enough, and looking for ways to enrich it by adding more axioms.
Fortunately, no new axioms are necessary! The encoding is obvious in retrospect. What is the first thing a mathematician thinks when you talk about the naturals: induction! Let’s define a natural as any object which you can do induction (with 0 and S) over.
To make this readable, we need to introduce a few more symbols:
f . g = \x. f (g x) -- composition A → B = \f. ΞA(B . f) -- the type of functions from A to B True = ΞHH -- the true proposition U = K True -- the type of all objects (mnemonic: universe) L = U → H -- the type of predicates/types
Now, for the naturals:
Nat x = ΞL(\p. p 0 ⇒ ΞU(\n. p n ⇒ p (S n)) ⇒ p x)
Reading this in English: “x is a Natural if, for all predicates p, if p 0, and p n implies p (S n), then p x”. In other words, x is a natural if you can do induction up to it.
Exercise: prove |- Nat 0 and |- (Nat → Nat) S. Note that this can be done independent of our definitions of 0 and S.
More Inductive Constructions
Using this scheme, we can construct all sorts of things. For example, equality:
Eq x y = ΞL(\p. p x ⇒ p y)
Lists:
nil = \n. \c. n cons x xs = \n. \c. c x xs List a x = ΞL(\p. p nil ⇒ ΞU(\ys. p ys ⇒ Ξa(\y. p (cons y ys))) ⇒ p x)
There is a classic paradox involving the inductive type Set = Set → H, which is definable using this scheme:
Set x = ΞL(\p. Ξ(p → H)p ⇒ p x)
However, as I tried to prove the inconsistency, I was blocked by the H rules. This gives me hope.
Coinductive Constructions
It is also possible to construct coinductive types. Here are the “conaturals”, the naturals with infinity. We can’t use the constructor definition anymore; coinductive types are all about projections. So the conaturals have only one projection, onto a disjunction. So to eliminate a conatural n, you pass it what to do if n = 0, and what to do with n’ if n = S n’. For example, to check if a conatural is zero, you can use n True (K False).
CoNat x = ΞL(\p. Ξp(\y. y True p) ⇒ p x)
In English: x is a conatural if for all predicates p, if p y implies y True p, then p x. y True p can be interpreted as y = 0 or y = S n and p n.
Isn’t IΞ cool? Simple, obvious, but powerful enough to model a wide class of data (and codata). The thing I like best about it is that it is untyped at its core. Functions are just pure lambda calculus functions that we are “later” proving properties about. Type erasure comes for free (well, sortof: encoding dependent types into this system will end up passing types as parameters at runtime, even though they are never used).
Future Concerns
Bunder proved his version of IΞ consistent and complete. But the rules I gave, and that I have been using, are not his, and in fact are more powerful than his. This makes it possible that my rules are inconsistent. My system can prove LL, while his cannot. This worries me, because LL in the typical interpretation means “Type : Type”, which gives rise to the Burali-Forti paradox. However, even though I was able to encode the infrastructure for Russell’s paradox, I was unable to complete the proof because of the H rules. Maybe the same thing will happen?
I’m spending a bit of time trying to understand the Burali-Forti paradox that gives rise to the inconsistency in Girard’s System U, so that I can try to carry it out in IΞ. If IΞ does turn out to be inconsistent, I am not worried. A few universe restrictions here and there (i.e. leave U unspecified, rather than defining as K T) should do the trick, at the expense of some convenience and beauty.
Also, since I intend to compile Haskell to IΞ, I need to talk about partiality somehow (eg. prove that if a function terminates, it has this type). This has been giving me trouble, but in a good way. I found that I don’t really understand how bottoms behave, and how to talk about them without implying their semantics. I’m confident there is a way, though, maybe after adding a few axioms as a compromise. But I need to think hard and understand bottoms better, so I know what ought to be true, before I try to prove them or add them as axioms.
Jun 8, 2009
How to Read Mathematics
Mathematics says a lot with a little. The reader must participate. At every stage, he/she must decide whether or not the idea being presented is clear. Ask yourself these questions:
· Why is this idea true?
· Do I really believe it?
· Could I convince someone else that it is true?
· Why didn't the author use a different argument?
· Do I have a better argument or method of explaining the idea?
· Why didn't the author explain it the way that I understand it?
· Is my way wrong?
· Do I really get the idea?
· Am I missing some subtlety?
· Did this author miss a subtlety?
· If I can't understand the point, perhaps I can understand a similar but simpler idea?
· Which simpler idea?
· Is it really necessary to understand this idea?
· Can I accept this point without understanding the details of why it is true?
· Will my understanding of the whole story suffer from not understanding why the point is true?
Putting too little effort into this participation is like reading a novel without concentrating. After half an hour, you wake up to realize the pages have turned, but you have been daydreaming and don’t remember a thing you read.