32

If I am given a parking lot with ten thousand cars and I want to determine whether one of the cars is orange, the only way I can do this is go through the parking lot examining each car until I find one that is orange or I examine each car and conclude that there are no orange cars.

However, if I want to the determine whether there are any nontrivial integer solutions to the equation of Fermat's Last Theorem (xn + yn = zn, n > 2),

I do not have to examine every possible solution, in which there are an infinite number of them. If I am clever I can mathematically prove that there are no such solutions, just as Wiles and Taylor did in the 1990s.

So my question is what is it about mathematical problems like FLT which allow a person to bypass the brute force search of the parking lot problem?

I am really asking, "How does mathematics work?"

  • 14
    Your premise is not necessarily true. For example, you could take a picture of the entire neighbourhood from a plane, at a resolution that will capture car-sized objects, and see if it contains any orange pixels. If not, you know there are no orange cars in the neighbourhood, even though you don't even know whether or not there are any cars at all there. – alephzero Jul 21 at 18:25
  • 11
    Mathematics works because it only answers questions about what happens according to instructions we ourselves specified in advance (as Kant famously pointed out). If the lot was filled according to a set of instructions that specified colors for each spot you can find out the colors without looking at the cars at all. The "lot" of integers is filled according to just such instructions, the Peano axioms. – Conifold Jul 21 at 22:36
  • 19
    Suppose you are at a parking lot in a city that does not allow orange cars. You would then not need to examine the whole parking lot (assuming you trust the city's police force) but can immediately conclude that you will find no orange cars. Fermat's Last Theorem is stated in an environment that let's you conclude certain things about solutions to the given equation. It turns out that all solutions are outlawed by axioms in the environment. This is certainly not as trivial to conclude as my example with cars, but I hope it's clear enough what I mean. – WorldSEnder Jul 22 at 0:01
  • 13
    Your idea about the orange cars only works that way because there's no sorting, the cars are in random order, and you don't know anything about one car based on its position. You could easily search fewer cars if they're sorted already, say into ROYGBIV - if you find a red car next to a yellow car, you know there are no orange cars. – David Rice Jul 22 at 14:30
  • 4
    You could also make some assumptions, such as the year. As Henry Ford is said to have said "You can have any car color you want, as long as it is black". Then picking a timeline in sync with that you can safely say there are no orange cars because orange wasn't available as color choice then. – CrossRoads Jul 22 at 17:47

17 Answers 17

29

If you want to take a more constructive point of view, you need to reinterpret things accordingly. For example, "not P" should be interpreted as the assertion "P implies a contradiction".

Accordingly, Fermat's last theorem says:

Given any solution to xn + yn = zn, n > 2, you can deduce a contradiction

To prove this statement, you don't need to examine every possible instance — you merely need to exhibit a recipe for how you would construct a contradiction if you were given a solution.

  • 1
    So what is contradiction? Say "1=0". Why? Because it doesn't "work" And we are back to the OP question : What is "workingness" in math? – Rusi Jul 21 at 5:49
  • 13
    @Rusi "So what is contradiction? Say "1=0". Why?" I'm not sure whether you haven't studied any university-level math, but any formal mathematicial definition of "numbers" will include the statements "there are two objects called "0" and "1" with the following properties … and this is what we mean by "equality" … and as an axiom of the number system, 0 is not equal to 1". – alephzero Jul 21 at 18:32
  • 22
    @Rusi: You cannot ask for rigor and simultaneously demand high school level math. They are not doing math in high school, they are doing paint by numbers. – Kevin Jul 22 at 11:44
  • 9
    @Rusi: The fact remains that high-school-level math covers neither of those things, instead focusing on rote application of recipes such as "isolate X on one side of the equation." We never explain to students why they are solving for X in particular, or even what they are actually doing when they solve for X. So it should be unsurprising that we cannot answer a question such as this without taking a detour through math that they have not seen. – Kevin Jul 22 at 12:27
  • 4
    I wouldn't say it results in a contradiction, I'd say it results in a self-evidently false statement; it violates an axiom of our reasoning system. An "axiom" is a statement or proposition which is regarded as being self-evidently true. A violation of an axiom is self-evidently false; like 1=0. Thus, given any values of integers (x,y,z,n) with n>2, then x^n +y^n = z^n can be manipulated to produce a self-evidently false statement. – Amadeus Jul 22 at 18:25
14

The math solution is, to find out properties of the things we work with, and prove those. Then we re-search those properties for more properties we can now prove. And on those more intricate properties, we build even more complex proofs.

In the case of your parking lot, the mathematician might start by asking: What do I know about this parking lot? The answer might be that it's the staging area of a factory where the finished cars are waiting to be shipped. The natural next question would be, whether the factory actually can produce orange cars. If we find that the answer is "no", we may continue to check other possible loopholes like the question whether other cars than freshly built cars from the factory are parked there.

The result is a proof along the lines of: This parking lot only contains cars of Ford model Ts, which always comes in black, so no car on the parking lot can be orange.


Ok, slightly contrived example, but you get the idea. For a look the other way round, take for example the proof that there are infinitely many prime numbers. It goes like this:

  • I assume that there is only a finite number of primes.

  • If that's true, I can multiply them all in finite time to get a product N.

  • Consquently, N must be divisible by all primes.

  • This means that N+1 is not divisible by any prime, I always get a remainder of exactly 1 when dividing by any number that divides N.

  • Thus, N+1 is itself a prime, and my finite list of primes was not complete.

  • This is bullshit. It contradicts my assumption. Since I didn't make a mistake in deriving this bullshit, my assumption must be bullshit. I conclude that there is an infinite number of primes.

You see, all this proof really does, is to derive other facts from the given facts. It did not need to look at every integer. It did not need to look at each prime. It just assumed that the opposite was true, derived some consequences (properties of the numbers N and N+1), and used that to show that the assumption was wrong. Much in the same way that above we didn't even look at a single car, we just checked some properties of the parking lot to determine that there is no orange car on that parking lot.


The trouble with this method is, that we can never prove everything that's true. That's another property of mathematical proofs that's been proven by Gödel. We can derive some astounding properties of many things we can formalize, but in the end almost all questions that are possible to ask require an infinite amount of time and space to prove them. Math is, by its very nature, restricted to those questions that have a finite proof which is actually easy enough for humans to find.

  • 2
    “...almost all questions that are possible to ask require an infinite amount of time and space to prove them.” This is not what Gödel proved, nor do I think it’s close to an accurate statement. I’m not sure where this idea came from. What Gödel did prove is that in any axiomatic mathematical system that has enough complexity to encode basic arithmetic, there are theorems that cannot be proven. – Santana Afton Jul 24 at 12:23
  • @SantanaAfton Gödels proof was a diagonalization proof. This proof structure is the same as that of the proof that there are more real numbers (uncountably infinite) than natural numbers (countably infinite). And, I guess you'd agree if I said that almost all real numbers are neither natural nor rational (also countable). So, while the proof itself just proves the existence of a single additional true statement for which no finite proof exists, it does prove that the set of true statements has at least uncountable cardinality, and thus that almost all true statements lack a finite proof. – cmaster Jul 24 at 13:08
  • I agree that what the proof says is that the cardinality of {true statements} is higher than the cardinality of {representable statements}, but it’s not clear to me that this is equivalent to saying that “almost all questions that are possible to ask require an infinite amount of time and space to prove them.” I see what you’re going for here, though. – Santana Afton Jul 24 at 16:55
  • @SantanaAfton In math, we generally know only three classes of cardinality: Finite cardinalities (zero, one, two, ... elements), the countable cardinality (infinite amount, but you can assign a number to each element), and the uncountable cardinality (any function that associates natural numbers with elements from the set misses pretty much every element). Note the "the" in both cases. You cannot just add a countable amount to a countable set to get uncountable, you must at least add a countable number of countable sets to get an uncountable set. The result is infinitely larger. – cmaster Jul 24 at 17:42
  • 1
    There are at least countably many cardinalities that we lump into the word “uncountable.” There is no unique uncountable cardinality. Moreover, certainly a countable union of countable sets is still countable — it will never be uncountable. How is this relevant to my comment? – Santana Afton Jul 24 at 17:45
11

What makes mathematical statements about infinite domains work is a belief in realism, that is, a belief that these statements represent on face-value something real.

If they represent something real then according to Michael Dummett this implies a belief in the principle of bivalence regarding these statements. With realism each of these statements has a semantic content. They are either true or false even before one finds out by constructing a proof or disproof of the statement.

If they have this semantic content then there is no reason not to allow the inference rules used to provide proofs or disproofs of these statements to include the law of the excluded middle reflecting the principle of bivalence about these statements.

For an anti-realist the situation is different. These mathematical statements are not true until one has constructed a proof of the statements. Furthermore, the inference rules used in those proofs cannot include the law of the excluded middle since that assumes a belief that the statements are true or false prior to providing a proof.

The choice of being a realist or an anti-realist regarding mathematical statements does not carry much significance for most people. This may be another reason why such mathematics works or why such statements are culturally acceptable: there is little at stake for most people one way or the other.

However, the choice between realism and anti-realism may not involve such cultural indifference for all classes of statements. For example, consider statements about the future. Does the principle of bivalence apply to statements about the future now or do we have to wait and see what actually happens? If these statements represent a reality about the future, then there are no alternate paths for us to take, we have no free will and determinism is true. That would be a cultural motivation for rejecting realism about that class of statements.


Dummett, M. (1991). The logical basis of metaphysics. Harvard university press.

  • 2
    You should add that Dummett was an anti-realist!!! ie there's more nontriviality (and subtlety!) in what you are saying. – Rusi Jul 21 at 20:29
  • 2
    @Rusi He was an anti-realist. I don't want to suggest that he wasn't. His presentation of realism as characterized by the principle of bivalence for mathematical statements may be considered an anti-realist perspective of realism. – Frank Hubeny Jul 21 at 21:09
  • 4
    Aside: excluded middle does not imply two-valued logic; all Boolean algebras obey the law of the excluded middle. Also, one can adopt the law of noncontradiction without insisting on the excluded middle: e.g. intuitionistic logic in the form of Heyting algebra. – user6559 Jul 22 at 4:06
  • 2
    "What makes mathematical statements about infinite domains work is a belief in realism" -- does this mean that if mathematicians stopped being realists then Fermat's Last Theorem would stop working? This seems to suggest that the truth of mathematical statements depends on the subjective state of mathematicians -- which is a profoundly antirealist position. – John Coleman Jul 22 at 11:39
  • 1
    @JohnColeman If realism about mathematical statements is true, that is, the belief that mathematical statements are either true or false is true, then it would be a realist position that recognizes that. Taking a different stance would be potentially anti-realist. Noting that it depends on this belief merely notes that we have a choice regarding these statements that we don't usually consider. Considering that choice is neither realist nor anti-realist. If mathematicians stopped being realists they may assess FLT differently. – Frank Hubeny Jul 22 at 15:03
11

This question sort of leads in two directions. The first direction is proof theory, which describes how mathematical proofs work. They formalize a process of manipulating statements according to a set of rules, much like a game. Reach the statement you wish to reach, and you win the game.

There are many games out there, with different sets of rules. Some of those rule sets permit making sweeping statements about sets of objects, or even classes of objects. For example, many proofs use mathematical induction, a rule that permits a mathematician to condense an infinite number of steps into one, provided it fits the precise shape of that rule.

The more interesting question leads in the other direction: why does mathematics seem to be so darn good at being applicable in real life? Consider I may be able to prove that "OZ/H", or some equivalently fancy string of characters forming a mathematical sentence, and "prove" that it is true, but it is nothing more than a game I played with symbols unless it can be translated into real life, perhaps as "If there's an orange car here, it must be in a handicap spot."

And, frankly, mathematics has a curiously good track record for being able to be applied this way. Some of this is simply a matter of how long we've been developing it. We've had a lot of time to hone it. There's plenty of other ways to get reliable information besides mathematics. In particular, wisdom often does not rely on such games. You may find an old man who simply nods and says "Yep, there's an orange car in a handicap spot. Here, I can take you to it." (Later, you may find out that he owned the orange car... you can find the answer to your question many ways!)

Now when mathematics reaches out to the larger and larger reaches, such as dabbling with infinity, it gets harder to test it empirically. We find ways, mind you (calculus based physics being my favorite), but we start realizing that it simply may *or may not be true! Indeed there are some who play by rulesets that disagree with modern math (constructivists, in particular, play with a much more strict ruleset which does not permit as many infinite steps tucked away like we tend to do).

The final reason I'd consider for why math is so effective is known as reverse mathematics. This is the study of how little one needs to assume to make the proofs work. This looks at what happens as we refuse to make assumptions about how the universe works. We may cease to assume that multiplication is commutative (abba), or may assume Robinson Arithmetic rather than the more powerful Peano arithmetic that we are used to.

Each time we drop an assumption, we gain the ability to describe a larger set of possible operations with which to model reality. As we grasp at the faint edges of mathematics, we find its hard to come up with counterexamples showing that a model doesn't work. This, while not quite philosophical, has a bit of a self-fulfilling prophecy bit to it.

  • 2
    Nice answer. However, when you say "mathematical induction, a rule that permits a mathematician to condense an infinite number of steps into one", that's not quite right: A proof of full induction provides a receipt for constructing a finite proof for every (finite) natural number. While this receipt provides an infinite count of proofs (equal to the count of natural numbers), each of these proofs is perfectly finite in itself. I know, I'm splitting hairs here, but sometimes the fine distinctions are important (and fun), and they are always important in math. – cmaster Jul 23 at 18:30
9

We can do the same thing for a parking lot problem as we do for Fermat's Last Theorem.

Suppose we want to determine whether one of the cars is both orange and not orange (see note). I don't think anyone would need to go through the parking lot or even give so much as a cursory look to any of the cars.

We can do the same thing for a mathematical problem as we do for your parking lot problem. Suppose we want to know how many even integers there are. Well, we could just go through the set of integers. We wouldn't finish the job but we wouldn't finish a parking lot problem either if the parking lot had an infinite number of cars in it.

And, for maths problems, it is simpler for some of them to just count on our fingers than to try and solve the thing logically. For example, how many 1's in the first one hundred digits of the decimal part of π?

It is a mathematical problem since there is likely a logical solution to it, but, like your parking lot problem, it is also one you can solve using an algorithm because it is a finite problem.

However, it is precisely the method you use to solve a problem which is either mathematical or not mathematical.

Mathematics is both logical and formal. It is also fundamentally an abstraction and therefore a generalisation. The same theorem applies to an infinity of possible concrete situations. Logic isn't specific to mathematics. Any problem we solve requires some logic. Formalisation isn't specific to mathematics either. But mathematics involves these three aspects.

It is also an extreme form of generalisation. Science also relies on abstraction: a necessarily small set of observations and experiments make the basis for generalising to a particular type of phenomena. Mathematics goes well beyond that. The same mathematical theorem or theory will potentially apply to very different species of phenomena. You can count cows just as much as atoms, and the whole of arithmetic applies just as well to cows as to atoms.

This in turns requires that mathematics, unlike science, completely ignores empirical evidence (except of course, if it is applied mathematics).

So, mathematics is a discipline where people assume abstract premises, often called axioms, expressed in as rigorous a way as possible using an often specially made-up formalism and go on logically inferring from that perfectly abstract and formal conclusions, i.e. theorems, that potentially apply to many completely different types of real-world phenomena. Something only mathematics and Aristotelian logic can do.

There is also a number of mathematical problems that still don't have any known mathematical solution. One of the most well-known and perplexing example, given its apparent simplicity, is that of the prime numbers.

A prime number n is a natural number, i.e. a positive integer, which is not equal to the product of any two natural numbers other than 1 and n itself. For example, 2, 5, 17, 53 are prime numbers. 12 is not a prime since it is the product of 2 by 6, or 4 by 3, or indeed 2 by 2 by 3.

So, we can give a proper definition to the notion of prime number and assert confidently that if n is a prime number, there are no two natural numbers p and q, other than 1 and n itself, such that n = pq. However, there is as yet no known formula to identify all prime numbers. We don't know of any algorithm listing all prime numbers.

Of course, mathematicians are perfectly capable of deciding whether one particular number is or not a prime. However, what they seem interested in is a formula for listing all primes. They already have discovered various formulas to identify a number of subsets of all primes. But no general formula yet.

Existing formulas leave out an infinity of prime numbers. You have one parking lot with an infinity of cars and you also have several infinite lists of orange cars together with their location in parking lot. This is a lot of orange cars you know where they are. However, there is still an infinity of orange cars not on any of your lists, somewhere in the parking lot you don't know where.

Thus, for an infinity of cases, to know whether a number n is a prime or not, you have to use your parking lot procedure to try and see if it is or not divisible by any of the natural numbers between 1 and n.

This is a cumbersome procedure. A formula would be much more convenient, be less exhausting, give the result faster and with less risk of error. Discovering whether one number is a prime or not, however, is not the job of mathematicians. The job of mathematicians is to find the general formula once the premise of the definition of prime numbers is accepted (and given all other accepted premises relative to numbers).


Nota

Could "orange and not orange" fail to be a contradiction, voiding my point?

Cars could be painted not at all with orange paint but looking orange from a distance for example...

Yes, what colour things are is nothing like a black-and-white issue... However, I did say "orange and not orange", not something else.

So, let's assume cars may be painted with yellow and red dots all over and look orange from a distance. Even then cars will either be orange or not orange, and this whatever criterion you decide to use to assess whether a car is "orange".

The argument that red and yellow dots would make a car both orange and not orange, which would therefore make the predicate "orange and not orange" true is the fallacy of equivocation.

The equivocation is in having, if only implicitly, two different criteria to assess whether a car is orange. You can't do that. You have to use the same criterion not only for all cars but for "orange" and for "not orange". The criterion may be "looks orange to me", or "is painted with orange paint all over", or indeed anything at all, like, is painted black, or "smells good". This is how, and indeed why, logic works. But it will only work if you use it to begin with.

  • 1
    The paragraph "Thus, for an infinity of cases ..." makes no sense to me. For each single number, you can decide in principle whether it's prime; but there are infinitely many numbers. In the analogy, there are infinitely many parking lots now. Then it's not like "for infinitely many parking lots, you have to go through all cars there". Rather, you can only check finitely many parking lots anyway, with whatever method you have. – Torsten Schoeneberg Jul 22 at 17:46
  • 1
    As an aside, there are many formulae which single out primes; if you are generous, already Eratosthenes's sieve is such a formula. en.wikipedia.org/wiki/Formula_for_primes Some mathematicians are interested in deciding how efficient such formulae can be made; I think more mathematicians are interested in problems like, what's the asymptotic density of primes in a set of the form X? That would be something like: we figured out that if we only check the lots #1, #11, #21, #31, ... we are sure there will still always come another one where all cars are orange. – Torsten Schoeneberg Jul 22 at 17:53
  • 1
    Even if you changed the phrase 'both orange and not orange" to "both orange and not-at-all orange", a pointillist could paint a car in completely non-orange colors, so that from a distance the car would appear to be orange. – Jasper Jul 22 at 22:03
8

Mathematics works because mathematics has a defined set of rules for manipulating mathematical symbols and entities. If we start with a specific mathematical phrase, we apply the rules in some sequence to achieve different mathematical phrases until we reach an outcome we want (a contradiction, a scope limitation, a relation...).

If there were solid rules for how people parked cars — e.g., that no one ever parked an orange car next to another orange car; that no one ever parked an orange car on Tuesday; that orange cars always park next to blue signs — then we could do 'proofs' to try to determine whether there was an orange car in the parking lot. In other words, if we know rule #3 holds, and we know the parking lot has no blue signs, then we would know (without ever getting out of our chairs) that there are no orange cars in it. Likewise, if we do something in mathematics where we do not know an obvious rule, then we are always reduced to brute-force counting methods. If we don't know the binomial theorem, then the only way to calculate probabilities is to list out and count every possible permutation of a random event.

A 'proof' is nothing more than the logical manipulation of symbolic rules. When we have such rules, proofs are possible; when we don't, they're not. But rules of this sort are a mixed blessing. The more tightly defined rules are, the more restricted the domain of inquiry. Do we want a world in which we are always obliged to park our orange cars net to blue signs, just to make the lives of parking control officers more systematic?

4

Something that's pretty important to state is that it's not easy! Fermat's Last Theorem took a while to prove, and while what the statement means is to some extent a trivial consequence of its phrasing in first order logic, we didn't actually know whether or not it was a true statement for about 400 years before it was eventually proved.

The epistemology of Mathematics has a long and complicated literature, but broadly speaking, logical reasoning is our most important tool for apprehending its facts and objects. From foundational axioms, we apply rules of inference to derive new statements of fact about the domains we take the axioms to describe. The structure of rules and derivations we call Proof, and the new statements that we have derived are call Theorems.

If we take mathematical axioms to describe privileged domains, then our understanding of the different kinds of systems of inference we might use will be informed by how we generally observe those domains to behave, or how we want those domains to behave in order to put them to effective use.

A good example is the Dedekind-Peano axioms, which we take to describe the system of Natural Numbers. This system is useful to us because it helps us understand what we mean when we talk about finite counting, and about what it means to carry out sequential operations in a countable way.

We can often prove things about the Natural numbers as a whole by appeal to this systematic definition and through the use of logical inference. In effect, rather than directly appealing to the natural numbers as individual objects, we are actually proving new theorems about the axiom system; since the natural numbers satisfy this axiom system, we as a result get to know new things about those numbers.

However! Even this is controversial, because when you ask a question about what, exactly, we are taking the axioms to describe, you might get wildly different answers. A Platonist will say that the numbers simply exist in some abstract real way, and the axioms are our interpretation of things we currently know for sure about them. A Structuralist may say that numbers are just features of the regularity of the known scientific world, and that the axioms are fairly strongly confirmed hypotheses about how the world works. A Logicist will say that there could be many different interpretations of what the numbers are, but we can safely define what we mean using the cognitive or categorical resources we use to reason about the world in general; the axioms just define which resources we're particularly interested in exploring. And a Formalist or Fictionalist might go a step further and say that numbers might just be human constructions as a result of the regularity of our thinking and writing about maths, and the axioms may not describe anything in reality at all save for those principles we want to build our formal empires on.

There is a nice introduction to some of this thinking on the SEP article for the Philosophy of Mathematics, and it's worth noting that a diversity of approaches is probably good for stimulating creativity in mathematical practice.

4

Perhaps mathematics is more similar to your parking lot scenario than you suggest. After all, there are formulae P(x, y, z, n) in Peano arithmetic which are true for every instance of (x, y, z, n), but for which there is no finite proof, assuming consistency of course.

You could have a parking lot having an infinite number of cars whose memberships are so random and arbitrary that the only way to confirm that no orange car exists in the lot is to check each one. Thus if no orange car exists in the lot, it would be unprovable.

Peano arithmetic is incomplete. There is a so-called "Godel sentence" P(x, y, z, n) that "true but improvable."

4

I like the answers by @TedWrigley and @cmaster, and want to take them one step further with the analogy:

Mathematics does not decide whether all cars in a parking lot are orange.

Mathematics decides whether in a city which has such-and-such bylaws (and is situated in a country which has such-and-such laws and constitution), it is legally possible that all cars in that lot are orange. (Or maybe even necessary, as in: non-orange cars are illegal here.)

This can be decided without ever looking at any parking lot at all. Actually, looking at actual parking lots at best can give vague heuristic ideas to decide that question, but never actually solve it.

The question of "realism" that some other answers address is then akin to asking whether A) a city with such laws exists B) whether everyone in those cities abides by the laws. But that is outside the scope of math. (I think in the metaphor, A would be "modelling" in the sense of logic and proof theory, and B is "modelling" and doing experiments in physics/chemistry/whatever.)

3

Math is a toolkit, nothing more or less. If we have a problem, perhaps we can find some mathematical tools that will help.

For example we are given a parking lot containing 10,000 cars. We are asked to determine whether one of them is orange, without inspecting every car.

Consider a related problem. Given a throw of a pair of dice, what are the probabilities that various sums will occur? It's even worse than the cars because not only are the facts of the next roll unknown, they can't even be examined as we can at least examine the cars.

Yet, Fermat and Pascal worked out the mathematical theory of probability. Since then, probabilistic and statistical methods have been part of math and also physical science. Statistical mechanics in physics, statistics in the social sciences.

https://en.wikipedia.org/wiki/History_of_probability

Perhaps we can apply some statistical thinking to the parking lot. We could make some assumptions, that there are n colors with such and such a distribution, so many red, so many blue, so many orange. Based on that, we could determine how likely it is that there's at least one orange car; and we can even determine how likely our estimate is to be true.

We can improve the accuracy of our estimate by obtaining some outside knowledge about our assumptions. Perhaps the parking lot belongs to a car factory and consists of newly manufactured units. Then we can ask the plant manager how many orange cars are out there. Or we can refer to car industry literature about the popularity of various car colors.

This is how a lot of science works these days. Statistical mechanics and quantum physics for example.

The field of AI works that way. How do we teach a machine to play chess? These days they just program in the rules, let the machine play billions or trillions of games against itself, keep track of which moves lead to wins and which don't, and then turn it loose. This literally knowledge-free computing strategy plays at an advanced grandmaster level. It turns out that in some problem domains, you literally don't need to know anything ... just do what statistically works.

https://en.wikipedia.org/wiki/AlphaZero

There are even probabilistic proofs of mathematical theorems. Feynman I recall had a probabilistic proof of Fermat's last theorem.

http://www.lbatalha.com/blog/feynman-on-fermats-last-theorem

Bitcoin and cryptocurrencies work using probabilistic reasoning. In truth we can never be certain that a transaction is valid. We are certain beyond statistical reason; but never certainty. Likewise computer security. The probabilities are built into the crypto algorithms.

So in fact your example illustrates a shift in scientific viewpoint. These days we care about probabilities and not absolute truth. The world is run by probability and statistics, not certainties. And math has a toolkit for that.

3

First of all, you do not need infinite entities to state your problem.

The Traveling Salesman Problem would be a good example. In many popular texts people claim that you need to check all the n! possibilities to find the minimal length tour of a "traveling salesman".

This is not true. There are many algorithms which find the optimal solution and prove it, without going through all the possibilities.

An even simpler example: You can find the shortest road trip from New York to Boston without considering every possible trip on the road network. You can prove it. The key here is the triangle inequality. When you start building a road trip and you have gone from New York to California you know that all road trips starting that way are longer than the one you already know, so you can skip a very large number of road trips without ever considering them explicitly.

The key here is structure. The million cars in your parking lot are completely unstructured. The road network has a lot of structure. A trip does not get shorter when you add a road or changes its value in a pseudo-random matter.

2

You use words like determine, examine, prove. And assume that the objects of those verbs are somehow same or related. That (implied) object is...

Law

The word law has 3 distinct usages:

  1. Empirical laws are verified /falsified
  2. Mathematical1 laws are discovered and applied
  3. Legal laws2 are enforced and broken

In different terms

  • Empirical (physical) laws are properties of the world
  • Math laws are properties of our brains
  • Legal laws are ossifications of societal dos and donts

In other words your question is more linguistic even though it has a venerable philosophical pedigree. Just imagine the word "law" which in English is 3-way pun to instead have 3 different words and there is no question!

Further readings/study

  • Analytic vs synthetic
  • a priori vs a posteriori
  • logicism/formalism vs intuitionism
  • rationalism vs empiricism

1 I've written the above from the pov that math and logic are largely the same field. Not all mathematicians agree.

2 Rupert Sheldrake makes an interesting point that using "law" for Mosaic law as well as Newton's law is peculiar (ethnocentricity??)

2

But, as a mathematician would, you also made an assumption: that as you are walking around the lot no new cars arrive which may be orange changing the state of the system (parking lot). Brute force is an impossibility in any dynamic system due to the nature of cognitive reasoning. Anchoring assumptions must be made in all cases. Sometimes they are subtle. It’s rather physiological limitations of our brains. Perhaps a future General AI will break these shackles as a brute force chess player goes down every state permutation.

  • 2
    I am not sure how adding the assumption that no new orange cars arrive affects the problem of finding one orange car among the ten thousand already in the lot. One still has to check each car. Also I don't see how brute force is an impossibility in this case. It would just take a long time. – Frank Hubeny Jul 22 at 18:08
2

It seems like you're asking how we can "know" things about a set S of values when there is not an algorithm which can explicitly verify the property for each element of S (at least not in a finite amount of time). We can imagine that this might occur with an infinite set.

Let me provide an example:

How do we know that every multiple of 4 is even? That is, how do we know that for every s in the set S = {x: x = 4·k, k} it is the case that s = 2·m, m?

Consider an arbitrary s in S. Then s = 4·k for some integer k by the definition of S. And 4 = 2·2. Then s = 4·k = 2·2·k = 2(2·k), which is an even number.

Since s was an arbitrary element of S, and s was even, via a law of logic called universal generalization, we may conclude that every element of S is even (even though S has infinitely many elements).

Now, a next question is, how do we know universal generalization works for sure? Well, by an incredible result called Godel's Incompleteness Theorem mathematics/logic can't be used to prove its own correctness (roughly speaking). This is partly which mathematics relies on axioms, which are statements which can't be proven. See this question on axioms in mathematics. The philosophical implications of Godel's Incompleteness Theorem are massive and beyond what I can really address here. Given that mathematics cannot prove its correctness, you may find this question on the unreasonable effectiveness of mathematics interesting.

2

Part of the problem may be you jumped to a complicated mathematical proof and compared it against a brute-force real world proof.

In many ways, they can be more similar. For example, I can look at the historical record and tell you there were no Ford cars built before Henry Ford's birth in 1863. I don't have to check the year of manufacture of every Ford car in the entire world. I could come up with a logical argument for this; akin to a Ford car is a car made by the Ford motor company; a car is a type of product; products made by a company necessarily are made after the company was started; a company is started necessarily after the birth of its founders. With a basic concept of time that nothing can be made by X before X exists, you can prove this. To get somewhere in logic you may have to define some unproveable definitions and axioms that you can build up on.

Similarly, I could construct an argument that there are no even prime numbers greater than 2. I can define that a prime number is a natural number greater than 1 that has only itself and 1 as factors, and can also define even numbers as numbers that are divisible by 2. I can then come up with a proof by contradiction that if there was a even prime number greater than 2, it would have 1, itself, and 2 as at least three distinct factors and hence couldn't be prime. I don't have to check the infinite number of potential even prime numbers that are greater than 2.

  • 1
    I suspect the OP's example shows that there exists problems that require us to do an exhaustive search of each case, not that all problems are like this. Some like FLT are not given the proof. – Frank Hubeny Jul 23 at 22:07
1

Math Doesn't Work.

We build complex systems, and then we can prove that they cannot be proven sound using proof systems we trust.

Then we keep using them.

In effect, we keep using Math because it keeps on working. We have no strong reason to assume that our infinitely large constructs we build in Mathematics are not nonsense, and that the theories we build around them can distinguish truth from falsehood, once we pass really simple Mathematics.

We have lots of weak reasons; we have these complex systems, and they haven't collapsed. And when we use these complex systems to reason about concrete things, they surprisingly often give results that can be tested concretely.

So, Math as a source of absolute truth doesn't work, but Math as a source of practical predictions about concrete experience works. So we keep using Math because

Math Just Works.

Let us look at your parking lot problem. We'll do a variant, because your problem isn't all that interesting.

Instead of "Orange" how about "There is a car that can be arranged as the tallest car in the parking lot, such that all of the other cars can be arranged in order, where all of the cars 'earlier' in the order are at least 1 inch shorter than the cars later".

This has some structure we can exploit. Now, the classic way to prove this would be to take each car, then look at all the possible ways to arrange the other cars, and determine if the property we want is satisfied. This will take a while, as there are 10000! (10000 factorial) ways to arrange all of the cars in the parking lot, which is a big number (you'll die before you finish).

Math lets us take that structure, and state "well, if a car is the tallest in that order, it must be 1 inch taller than the previous, which must be 1 inch taller than its previous, all the way down", and state the tallest car in the order must be at least 10,000 inches tall.

Now we have reduced the problem. Instead of having to examine every order of car in the parking lot, we can show that no order can exist unless there is a car that is 10,000 inches tall.

In fact, this can be generalized with math -- given a lot with N cars and the requirement, it can only be satisfied if there is a car that is at least N inches tall.

The "cheating" part here is that one of our axioms of counting numbers in mathematics explicitly states what we need to do in order to make a statement about all counting numbers; typically the principle of (mathematical) induction is used. (This, together with some relatively basic mathematical options, results in a system that cannot be proven both sound and complete in itself; ie, Math Doesn't Work).

If we know our parking lot is in a parking garage, and there isn't 10,000 inches of height, we can even skip looking at the cars!

So we've solved the "ordered car" problem without having to examine every car. What more, we generated a statement about "ordered cars" in arbitrary sized lots.

Now, suppose a parking lot is defined to have a fixed max height, or cars are defined as things no taller than 6' tall. Then using that, plus the above solutions, we can show that no parking lot with more than 72 cars has the "ordered car" property.

There are a finite number of lots with 72 or fewer cars; we simply examine all of them, and then we can claim (without looking at larger lots) that there are no parking lots that satisfy the "ordered car" problem.

This is reasonably similar to how FLT was proven. They created some really complex mathematical structures that relate back, in extremely obscure ways, to the integer solutions of FLT. They then showed that (a) any such solution to FLT would imply a structure with certain properties must exist (equivalent to "a car ordering would imply a 10,000 inch car"), and (b) no such structure can exist (equivalent to "no car is 10,000 inches tall")

Similar to the "small lot" subproblem, often such mappings are not complete; if you can reduce the uncovered cases to a finite amount, those can be checked "manually". This, roughly, is how the 4-color mapping problem was solved; they reduced it down to many many many remaining cases, then got a computer to check those manually.

0

Maybe there is a shorter answer. I've been puzzled by this very question myself all of my life (I am almost 50), until very recently, when I run into this beautiful insight by a Russian internet blogger (Torvald). Let's see if I can do it justice retelling/translating: all mathematicians do is reason about mathematical objects that they themselves create to abstract different notions. So, to answer your question, math consists of creating proofs, and to arrive at one a mathematician creates abstractions, or "notation", which is used to represent the problem and reason about it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.