Solving Conundrums Part 2

- Hints (including clarifications) to Solving Conundrums Part 1

The First Conundrum

Restatement of the problem:

How many of the alternatives in this question is/are correct?

A) 1 of the alternatives

B) 2 of the alternatives

C) 0 of the alternatives

D) 1 of the alternatives

The Second Conundrum

This solution is supposed to only use a question referring twice to the brother who is alive. This one is connected to the third conundrum.

The Third Conundrum

This question is related to the post on Limitations of Logic

The Fourth Conundrum

The wikipedia-page on this (unexpected hanging paradox) is the worst I have seen. It is a lot simpler than that. Start with defining surprised.

If you think something (H) will happen (or not), there are four possible outcomes with respect to your information:

You said H would happen, and it does -> you're right

You said H would not happen, and it does not -> you're right

You said H would happen, but it does not happen -> False Positive

You said H would not happen, but it does happen -> False Negative

Are you surprised when you do a false negative, or are you surprised whenever you do either a false negative or a false positive?

Gambling All Of Mathematics

"A chess-master may gamble a piece, or even the entire game; but a mathematician writing an ad absurdum argument is gambling all of mathematics." - Couldn't find the source.

- This post can also be considered a hint to Solving Conundrums.

What is an ad absurdum argument? As always, you can see wikipedia, but let me take one of the most famous examples, and then give an explanation. Essentially the argument goes like this: Assume the opposite of what you want to show, arrive at a contradiction, conclude the opposite of what you assumed.

Example of an ad absurdum ("to the absurd") argument:

Are there a finite or infinite number of primes? (Primes are numbers p that cannot be factored into any other factors but p and 1. Primes per definition are > 1.)

Well, assume the statement Q to be true:

Q: 'There is a finite number of primes'

Then there are exactly n primes for some number n, and we can number these primes p_1, p_2, p_3 ... to p_n. Then we make a new number s by multiplying all these primes, and then adding 1 (s = p_1*p_2*...*p_n +1). This new number s will not be divisible by any of our primes, so the only possible factors of s are itself and 1. Hence there is at least n+1 primes. But this is impossible as n is the total number of primes.

We assumed Q and ended up with a contradiction, so Q must be wrong. Hence there is an infinite number of primes.

Example end.

So how does this work? I assume that we agree on what Logic is (the axioms and rules), as it would be far too cumbersome to write it out. Last time we talked about consistency of logic. This can be represented by the following axiom:

((P) and (not P)) equivalent to false

What we got in the proof was that the number of primes was exactly n and n+1, that is, exactly n and not n. What we got was equivalent to false by the above axiom. We showed that:

Q implies false

Now we want to use something called the rule of transposition:

(A implies B) is equivalent to ((not B) implies (not A))

In total we get

(not false) implies (not Q), which gives

true implies (not Q), which gives

not Q, which is

'There is an infinite number of primes'

“Once you eliminate the impossible, whatever remains, no matter how improbable, must be the truth.” - Sherlock Holmes

Have Mercy on my Implication

There is some sayings that irritates me. Like, "this is a quantum leap" (Norwegian: "Dette er et kvantesprang"). A quantum leap is the smallest possible leap in nature, in everyday life a quantum leap is the same as a continuous increase, as it is extremely small. That can be remedied, however, by thinking of the quantum leap as a leap in understanding. Physics at the scale of atoms were poorly understood until the concept of a quantum (the world is not continuous, but fundamentally quantized).

And then there are some that have no valid interpretation, some phrases that want me to knock someone's teeth out: "Yes, that implies truth."

It is common to confuse the following three words:

Correlation: Often when there is sun and rain we see a rainbow.

Causation: If you hit me on the head, I will feel pain.

Implication: If the moon is made of cheese, then I am eating chocolate right now.

(Since the moon is not made of cheese, the implication is true whether I am eating chocolate or not. Note also that moon and chocolate have nothing to do with each other.)

See Wikipedia's three pages for a more thorough explanation. Some may argue that implication is an abstract model for causation, but let us avoid philosophy right now.

Back to business: Instead of saying "X is true" some people say "X implies truth" to sound more wise. (In Norwegian: "X medfører riktighet"). This is completely bollocks! If you know that X implies truth, then you know nothing at all about X. ANYTHING implies truth! (Can you feel my frustration?) On the other hand, if someone were to say "Truth implies X", then you would know that X was true.

The Limitations of Logic

- Consistency, completeness, and Gödel's theorems.

- This is not really a hint to SolvingConundrums, but it is a prerequisite for understanding some of the solutions properly.

What is a logic? What is a mathematics? It is a set of axioms and some rules for deducing true statements.

Logic is the set of rules and axioms we have agreed to use. I will assume that we agree on these. (I refer to the mainstream choice, I know there are other candidates, like fuzzy logic, and I may come back to that later.)

A consistent system is one in which not both 'P' and 'not P' is true. In other words, a system where there is no statement P that is both true and false. Why is it so bad to have one such statement in our logic? Well, assume that we have one such statement, and call it P. Then for any other statement Z we get that P implies Z, because P is false. Then, since P is true, we can deduce that Z is true. The conclusion is that every statement in our logic is true (including 'not Z'). This is senseless – there is no difference between true and false anymore!

A statement-complete system is one in which every statement is either true or false, so that there is no unknowable thing. Having an incomplete system means that we can't know everything, even in principle, and that is bad. (When doing science we often think that there is just a matter of time and patience before we understand something.) This concept, I just made up, and it is a bad concept. What is truth, really, in a logical system? We still want to avoid epistemology (philosophy), so what then is truth? It is something that can be proved by using the axioms and logical rules.

In Logic/Mathematics we desire proofs. If something is true (say 'P'), then we want there to exist a string of logical arguments showing that 'P' is true. If something is true, but there is no way of knowing that it is true, that is bad. Our definition of truth in a logical system is that which can be proved within the system. A system where every statement (which can be constructed in the system) is either provably true, or provably false, is known as a complete system. Wikipedia calls this syntactically complete, and gives a nice reformulation: A system is complete if and only if "no unprovable axiom can be added to it as an axiom without introducing an inconsistency."

Let me be clear: We will only use one concept, so that truth and provability is the same thing in Logic. It is possible to make a distinction between the two, but I don't want to do that.

What Gödel tellsus is that we can never have a complete system (given that it includes basic number theory and some extra technicalities). If humanity some day decides on a logical system to use for all eternity, then either that system is inconsistent or incomplete according to Gödel's proof. In other words, since we require our system to be consistent, there will be statements that are neither true nor false in our system.

What do we call these statements that are neither true or false in our logical system? We call them independent or undecidable. Examples of these are the axiom of choice (independent in ZF-logic), and the continuum hypothesis (independent in ZFC-logic). These examples are (to mathematicians) interesting statements, so the problem that Gödel found is not some weird technicality, but something we have to deal with.

What can be done with an independent statement? We can choose to add it as an axiom, or we can choose to add its negation as an axiom. Logic does not care which we choose, it will still be consistent regardless of our choice! If we want to model observable reality, however, we might care about which is "true", as in which choice results in the best model of reality.

When we have added our axiom (or its negation), then our logic is a new and more powerful logic, where more statements are provable (also known as 'theorems'), and where more statements can be constructed. Again Gödel's proof works, and we can find new (and possibly interesting) statements that are independent in this new logical system. And so on, and so on.

Here, those who are familiar with mathematics might want to try to cheat, and add an infinite sequence of axioms, each based on a previous level's known independent statements. Even this (and generalizations of this) will not work at all. The logic you end up with is either incomplete or inconsistent.

Gödels general examples that always work in a logical system T (not true nor false):

(A Gödel number is a proof translated to a number in number theory.)

"There is no Gödel number to this statement using the logical rules of system T"

(i.e.: There is no proof of this statement.)

"The logical system T is complete"

Solving Conundrums Part 1

[I was a little unsatisfied with my last post, the second part of Q.M. logic, so to the next theme I will take a different approach; starting with a problem to solve, and, within two weeks, give hints, and within four weeks, the solutions.]

I have a conundrum for you (that word tastes like soft thunder rolling over the horizon on a warm summer day). Well, I have several. All in the form of seemingly innocent questions, that soon become quite frustrating logical puzzles. I promise that I will solve all of them in a very concrete way; I am, after all, a mathematician (I do not, however, promise that you will like the solutions, as I am not a politician).

The First Conundrum

You sit down to have your exam in [logic-something-course], and get the following multiple-choice question:

"If you were to answer this question randomly what is the probability that you would be correct?

A) 25%

B) 50%

C) 0%

D) 25%

"

What is the correct answer?

The Second Conundrum

Suppose you are at a crossroads, and there are two paths, one will lead to riches, and the other to death. In the old days there were two brothers; one who always speak the truth and another who always lie. They were, of course, identical twins. The solution was to ask both of them, which road would your brother tell me to go to get riches, and then go the opposite way.

Sadly, one of the brothers was killed by an angry customer. As they were twins, noone knows who died and who still lives on. The only thing you know about the person in front of you is that he always either speaks the truth, or he always lies. What do you ask him? Will you get rich?

The Third Conundrum

Is the following statement true?

"This sentence is false."

What about the two next sentences, are any of them true?

"The next sentence is false.

The previous sentence is true."

The Fourth Conundrum

Once upon a time, there was a proud king. His throne was usurped by a maniac, and the king was to be executed. The maniac said: "I will execute you this week, on Tuesday, Wednesday, Thursday or Friday. I will come and get you early in the morning, and it will surprise you!" The proud king then answered: "Well, fool, you cannot kill me on Friday, because then I will know it Thursday evening, so it will not be a surprise! Since you are unable to kill me come Friday, on Wednesday evening I will know it if you plan to kill me on Thursday, hence you cannot kill me on Thursday. Now, only Tuesday and Wednesday remains. So if I am not executed on Tuesday, I will know that you plan to kill me on Wednesday. Hence only Tuesday remains. But I know this, so there are no possible day when you can kill me!"

The maniac thought about this for a while, then answered "We will see". On Wednesday, the proud king was, to his surprise, executed (he had, after all, predicted that he would not be executed). Where was the flaw in his logic?

The Cat That Killed De Morgan

According to google (number of hits), it's supposed to be "the cat who killed", does anyone know for sure?

• Part two of Quantum Mechanical Logic. (Part one here).

In logic (classical/ordinary logic) we have something known as De Morgan's laws:

Let P be the statement 'It's raining outside', or any logical statement

Let Q be the statement 'The sun is shining', or any other logical statement

Then saying 'not(P and Q)' is the same as saying '(not P) or (not Q)', in words:

'It can't be both raining outside and sunny' is the same as

'It isn't raining outside, or It isn't sunny'

(yes, none of the sentences are necessarily true, but they are equivalent)

(in logic, 'A or B' means 'either A, or B, or both')

Does this work in Quantum Mechanics? No. Remember our perfectly grey cat. If you ask the cat

P: Are you black

Q: Are you grey

The statement 'not(P and Q)' [not both black and grey] is true. In the Quantum Mechanical sense, you cannot observe that it's grey and black at the same time (that is not a legal outcome). Hence (grey and black) is false, and 'not(grey and black)' is true.

The statement '(not P) or (not Q)' [not black or not grey] is true in 50% of the experiments. The part (not grey) is never true, as it starts out with being perfectly grey, and you cannot then observe it to be not grey. The statement 'not black', however, is true 50% of the time as it is a 50% chance that when we measure it to be 'not black' the cat will spontaneously become white. In total '(not P) or (not Q)' is true 50% of the time, and false the other 50% of the time.

So in Quantum Mechanical logic De Morgan's laws are not valid, the two statements are not equivalent. But in logic we require this law, so what to do? Well, even though I have called it Quantum Mechanical logic, it isn't really logic, but something else that has a strong similarity to ordinary logic; and it has some differences as we just saw.

To be fair to any mathematically inclined readers I want to add a comment. The "logical" 'or'-statement in Q.M. is usually taken to be a join of subspaces (the least subspace containing both the subspaces of Q and P), instead of a 'or' between two experimental outcomes, so that in our example the most natural thing to say is that (not black) or (not grey) is the linear span of the two, namely the whole 2-dimensional black/white subspace. Observing whether it is in this subspace would give a 'yes' with a 100% probability. It was, after all, grey. This seems to make my point moot, but alas, even with this more refined notion of "logical 'or'" you can find contradictions to De Morgan's laws (where meet and complement of subspaces is not the same as complement and join), see for example this page.