XKCD’s NP-Complete

Opening paragraph:

“I was reading XKCD along with a friend and we came across a comic. He wanted to continue reading but I wanted to solve it! [...]“

Extensive mathematical symbols necessitates a PDF file.

XKCD’s NP-Complete

ETA: Some of the data in the PDF is missing it seems. I do not have a backup.

Induction and a probability formula

I thought about how induction relates to the probability of something, and I came up with this formula. Induction is here taken as repeated confirming observations of some theory or hypothesis.

Formula. When the amount of confirmed observations, O, of a hypothesis goes towards infinity, then the probability of the hypothesis given the observations, Pr(H|O), goes towards 1 unless defeated by other evidence.

The last clause ‘unless defeated by other evidence’ is important, as without it the conditional would be false. It could be that some hypothesis correctly predicted an increasing amount of observations but that it also mistakenly predicted an increasing amount of other observations. These mistaken predictions would be very strong evidence against the hypothesis (falsification), and the probability of the hypothesis would not rise even though there was more and more evidence in form of confirmed observations for it.

It is said that a single false prediction of a hypothesis disproves it. (It is a counter-example to a universal (i.e. A-type) proposition.) That’s correct but if we have very strong evidence for some hypothesis and we think we have found some evidence against it (i.e. a false prediction) then it is very probably that the evidence against it is bogus in some way (i.e. is not evidence against it at all). This sounds like Hume’s maxim doesn’t it? It’s more probably that the observation (‘testimony’) against the hypothesis is bogus than the hypothesis being bogus.

Of course, if we were to find more and more evidence against the hypothesis, then at some point the probability that the hypothesis would be false will be greater than the probability that all the evidence is bogus (or misleading, as it is also called).

Mathematical representation

If anyone knows how to properly formalize this formula in mathematic symbols, then please inform me. I tried using a limit function but couldn’t figure it out. Basically I want to express the idea that when the amount of O goes toward infinity, then the probability of H given O goes toward 1. The ‘given O’ here is the set of all the observations. The clause about ‘unless defeated by other evidence’ can be expressed in propositional logic by including it into the antecedent proposition in the conditional; “If there is no other defeating evidence and the amount of confirmed observations goes toward…, then …”

Some different deterministic theses

Determinism is a fairly broad thesis, and some formulations of it does not “work” with Swartz’s regularity theory. Below I have outlined some different deterministic theses.

Minimal Causal Determinism (MCD): All events are caused.

Necessarian Causal Determinism (NCD): “[G]iven a specified way things are at a time t, the way things go thereafter is fixed as a matter of natural law.”[i]

Predictability Causal Determinism (PCD): Given complete knowledge of the present situation and the laws of physics the future can in principle be calculated with 100% certainty.

The first is what I usually mean when I talk about determinism.

The second is, apparently, what is often meant with determinism when others use it. The second formulation is incompatible with regularity theory as it implies that laws of physics (or nature, or natural law etc.) necessitate the outcome which regularity theory denies.

The last is just an idea I had that might be useful. For instance, it implies that nature is not probabilistic which I think some claim it is. People sometimes mistakenly think that since our theory of some phenomenon is probabilistic, then the phenomenon is probabilistic.


[i] This is what the Stanford Encyclopedia of Philosophy writes as the definition (simple) of determinism. plato.stanford.edu/entries/determinism-causal/

Worldviews and mistaken beliefs, a paradox

Here’s a little paradox that I’ve come across while thinking. It’s about worldviews and knowing that at least one thing I currently believe to be true is actually false.

The argument

1.      For all x, if x is a belief in my worldview, then I hold that belief. [Premise]

2.      If for all x, if x is a belief in my worldview, then I hold that belief, then I don’t believe that my worldview contains a mistaken belief. [Premise]

3.      Thus, I don’t believe that my worldview contains a mistaken belief. [from 1, 2, MP]

4.      There is at least one proposition such that I believe it and it is false. [Premise]

5.      If there is at least one proposition such that I believe it and it is false, then my worldview contains a mistaken belief. [Premise]

6.      Thus, my worldview contains a false belief. [From 4, 5, MP]

7.      Thus, my worldview contains a mistaken belief and I don’t believe that my worldview contains a mistaken belief. [3, 6, Conj.][1]

This conclusion seems paradoxical to me. It’s not a contradiction at it stands, it’s just fishy. If I form the belief as a result of this argument, that my worldview contains a mistaken belief, then I hold two contradictory beliefs. It seems that I have to reject a premise, but I don’t find any of them weak. In fact, three of them are logical tautologies, and the last is proven by induction. I’ll discuss the premises below.

Premise one

This one may seem a little unnecessary. I had no luck formulating the argument without this premise. I think it is a logical tautology, that is, true per definition. Let me first define worldview as I use it here.

Worldview =df The (complete) set of beliefs a person has.

Then, given the above definition, it is clear that if a belief is part of a person’s worldview, then that person holds that belief.

When I wrote this article and when I was thinking of the paradox, I noticed that it is easy to make a category error and call a worldview false. But that doesn’t make sense. ‘True’ and ‘false’ are meaningful in relation to propositions and not to beliefs. We may instead say that a worldview is mistaken which just means that the worldview contains at least one mistaken belief. A mistaken belief is a belief in a false proposition.

Common language may be broader in the use of ‘true’ and ‘false’ but here I will restrict myself for the sake of clarity of thought.

Premise two

This one is similar to the first, as it seems unnecessary and is a logical tautology.

One could argue it with a reductio. Assume that I believe that my worldview contains a mistaken belief. If I believe that, then I don’t hold the belief that is mistaken. (Since if I did, I would have two contrary beliefs.) If I don’t hold that belief, then it isn’t part of my worldview. But from the assumed we can deduce that it is part of my worldview. Thus, contradiction, and the assumption is, thus, false.

Premise three

This one is not a tautology for a change, but I think it is uncontroversial. I have a large number of beliefs, all grown-ups do, and in the past it has always been the case that a belief I had turned out to be false. Similar behavior has been observed in other humans. By induction we have good reason to believe that some of my current beliefs are false. The trouble is that I don’t know which of them it is!

Premise four

This is another tautology. By definition my worldview is the set of beliefs that I have, and if I hold a mistaken belief then it follows that my worldview contains at least one mistaken belief.

Solution?

I don’t know. I haven’t found one, if there is one.


[1] The argument is valid in propositional logic but some of the propositions are formulated in predicate logic for extra clarity.

Meaning, propositions, category errors

I quote Swartz:

“What sort of thing is my pen’s  being on my desk? We are inclined to say such things as “My pen’s being on my desk is true,” which would suggest that my pen’s being on my desk is a proposition; but we are also inclined to say such things as “My pen’s being on my desk annoyed my wife who was looking for my pen in the bureau drawer,” which, on one reading, would suggest that my pen’s being on my desk is a physical state or an event that has causal consequences. (No proposition has causal consequences; they are not the sorts of things that do.)”[i]

I have a few things to say about meaning, cognitive meaning, propositions, statements, impossibilities and category errors.

Meaningfulness

This predicate applies to statements (in this context). Broadly, if a statement is meaningful that means it is understandable for someone. The someone has to know the correct language (e.g. English), sometimes the context it is used in etc. Consider this example:

E1. KLskjn asdkasdkasdjknjab 2ksdan.

E1 is not meaningful (for me or anyone else). It is also grammatically ill-formed. Note that statements can be meaningless even though they are grammatically well-formed. Consider:

E2.  Colorless green ideas sleep furiously.[ii]

So, as we can see this statement does not mean anything but it is grammatically correct. This is because that even though the words are used grammatically correct they do not convey any meaning in the relation they are used in. Philosophers call this a category mistake or category error.

Keep in mind that the meaningfulness I’m concerned about here is in relation to semantics and language, and not, say, actions. Sometimes we say that an action was meaningless, and by that we mean that it had no purpose.

Cognitive meaningfulness

Cognitive meaningfulness is different from meaningfulness itself but it is a proper subset. So, all cognitively meaningful statements are meaningful, but not conversely. A statement is cognitive meaningful iff it conveys a proposition. A statement expresses or conveys a proposition iff it is descriptive. Consider this example:

E3. Go clean the dishes!

E3 is not the kind of statement that describes something, thus it’s not descriptive. And, thus, it is not cognitively meaningful. Some philosophers have thought that moral or ethical statements were statements of this kind, that is, that they didn’t convey propositions. Instead they thought that they had other purposes such as conveying information about the feelings of the speaker, or served as orders.[iii]

Propositions

Propositions are not the statements themselves. No statement is true or false but we usually speak of them like this because it’s easier. Consider this example:

E4. The sky is blue.

E4 is a meaningful statement, and it is a cognitively meaningful statement. Thus, E4 conveys a proposition. It is the proposition that it either true or false.

Meaningless impossibilities?

Consider this example:

E5. There exists a four-sided triangle.

People tend to have different intuitions or opinions about this example. Is it cognitively meaningless? Some think it is. I think it is not. The same people that think it is cognitively meaningless also sometimes think that four-sided triangles are impossible. I contend that these two claims are incompatible in a broad sense.

Recall that if a statement is cognitively meaningless, then it does not convey a proposition. So, I’m curious as to what exactly these people think is impossible. ‘Impossible’ and ‘possible’ are propositional properties, i.e. they are about propositions. But since there is, according to these people, no proposition conveyed by E5 and similar statements, there is nothing relevant that can have the property of being impossible. Perhaps they think that it is the statement itself that is impossible, but this would be a category error. Their position thus implies giving nothing a predicate (or property) or the category error of ascribing ‘impossible’ to a statement.

I contend that E5 conveys a proposition and that that proposition is impossible (and thus false). All triangles have precisely three sides. If a figure has precisely three sides, then it does not have four sides. Thus, the triangle both has four sides and has not. Impossible.

Ambiguity

Consider this example:

E6. He ate the cookies on the couch.[iv]

Suppose we were to assess this statement (i.e. the proposition that it conveys). What are we to make of it? This statement is ambiguous and could mean either of the propositions conveyed by these:

E6a. He ate the cookies that were on the couch.

E6b. He ate the cookies when he was sitting on the couch.

So, an ambiguous statement is a statement that conveys more than one proposition. Usually we use ambiguous language because it is shorter, and the meaning can usually be inferred from the context.

Category errors again

Recall the quote in the beginning of this article. The reason I quoted it was this: In the last part of it Swartz writes that “[n]o proposition has causal consequences”. However, does this make sense? Not really, as much as it does not make sense to say that propositions have causal power, it does not make sense to deny it either. There is no proposition conveyed that can be affirmed or denied. What can be affirmed and denied is that the two words convey a meaning in the relation they are used in. This was what Swartz meant with the second statement “they [i.e. propositions] are not the sorts of things that do”.

We should be very careful when we talk about propositions and meaning. We are inclined to respond “No cars are hungry.” to a person if a person says that his car is hungry, but when we think of it, that statement does not make sense. “My car is hungry” is meaningless and conveys no proposition. Thus, there is nothing we can deny.

We should also not take language completely literal for sometimes people use language non-literally. In the example from above the person might mean that his car needs gas.

An approach to cognitive meaning of statements

It has been suggested that statements are meaningful iff they describe a possible state of the world. But I think this is a bad analysis. First, what kind of possible are we talking about? I will suppose it is logical. Given the thesis above, any statement that describes (more on this) an impossible state of the world is not cognitively meaningful. So, there is no proposition that claims that something is impossible that is true. This is false so the thesis is wrong.

Furthermore, it does not make sense to say that statements describe anything. Propositions describe things. Going by the thesis, if a statement conveys a proposition that describes some impossible statement of world, then the statement is not cognitively meaningful. If the statement is not cognitively meaningful, then it does not convey a proposition, but this contradicts that previous claim that it does, and therefore the thesis is false.


[i] Norman Swartz, The Concept of Physical Law, p. 47, www.sfu.ca/philosophy/physical-law

[ii] It is a well known example. en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously

[iii] en.wikipedia.org/wiki/Noncognitivism . See emotivism for the theory about emotions and perscriptivism for the theory about orders.

[iv] Taken from en.wikipedia.org/wiki/Ambiguity#Linguistic_forms

The recent controversy about Hume's Maxim against justified belief in miracles

Contrary to what I normally do I’m not going to argue anything in this article. My goal is to spread useful information, mostly in form of links about Hume’s maxim.

Hume’s maxim

Hume mentions this in his essay An Enquiry Concerning Human Understanding.[i]:

91. The plain consequence is (and it is a general maxim worthy of our attention), “That no testimony is sufficient to establish a miracle, unless the testimony be of such a kind, that its falsehood would be more miraculous, than the fact, which it endeavours to establish; and even in that case there is a mutual destruction of arguments, and the superior only gives us an assurance suitable to that degree of force, which remains, after deducting the inferior.” When anyone tells me, that he saw a dead man restored to life, I immediately consider with myself, whether it be more probable, that this person should either deceive or be deceived, or that the fact, which he relates, should really have happened. I weigh the one miracle against the other; and according to the superiority, which I discover, I pronounce my decision, and always reject the greater miracle. If the falsehood of his testimony would be more miraculous, than the event which he relates; then, and not till then, can he pretend to command my belief or opinion. (Section X, part 1, 91)

John Earman’s critique

Recently a professor has been arguing against Hume’s maxim.[ii] The first thing to find our is whether he is a waste of time or not. So, I looked him up on Wikipedia:

John Earman (born 1942) is a philosopher of physics. He is currently a professor in the History and Philosophy of Science department at the University of Pittsburgh. He has also taught at UCLA, the Rockefeller University, and the University of Minnesota,[1] and is president of the Philosophy of Science Association.[2] He received his PhD from Princeton in 1968.[3] [iii]

He doesn’t seem like a waste of time. But people who are not a waste of time sometimes write books that are a waste of time. So, let’s check some reviews of his book. There are six reviews on Amazon. All of them are positive. Five reviews with five stars and one with four. One of the reviews is an alleged professor (of what?) and one is a Christian nutcase.

David Johnson’s critique

Also somewhat recently another professor has challenged Hume’s maxim.[iv] Again, let’s see if he is worth our time. Wikipedia writes:

David A. Johnson (born 1952) is Associate Professor of Philosophy at Yeshiva University and has previously taught at UCLA and Syracuse University. Raised in Nebraska, he earned his BA from the University of Nebraska, where he studied under Robert Audi, and his PhD from Princeton University. His areas of concentration are Philosophy of Religion, Metaphysics, and Epistemology. His brother, Edward, is Professor of Philosophy at University of New Orleans.[v]

The answer is therefore probably yes. Is his book worth our time? Amazon has one positive review of it, giving it four stars. So, maybe. Not enough data.

Jordan Howard Sobel’s defense

Sobel defends Hume’s maxim.[vi] There is no Wikipedia article on Sober, but one can read his persona CV. He’s a doctor of philosophy and a professor of philosophy.[vii] His book has a single five star positive review on Amazon, and Theodore M. Drange (also a professor) has written a positive review of his book.[viii]

Robert J. Fogelin’s defense

In the most recent book mentioned in this article Fogelin defends Hume’s Maxim against the criticism of the aforementioned authors.[ix] Fogelin has no Wikipedia article, but he is mentioned on a list of philosophers.[x] One his personal homepage one can read that:

Robert J. Fogelin is Professor of Philosophy and Sherman Fairchild Professor in the Humanities at Dartmouth College.[xi]

The book has two positive five star reviews on Amazon.

A combined review

A review of Earman’s, Johnson’s and Fogelin’s books can be found here.[xii]

Sean’s writings on Hume’s maxim

Sean has written four articles on Hume’s maxim that I have been allowed to reprint here, so to speak.

hume_maxim
bayes-theorem-cards-and-miracles

Warning: These have been converted from the original HTML version and may contain errors and dead links.


[i] David Hume, An Enquiry Concerning Human Understanding, 1748, Section X. “Of Miracles”, www.infidels.org/library/hist…rstanding.html

[ii]John Earman, Hume’s Abject Failure: The Argument Against Miracles, 2000 www.amazon.com/Humes-Abject-Failure-Argument-Miracles/dp/0195127382

[iii] en.wikipedia.org/wiki/John_Earman

[iv] David Johnson, Hume, Holism, and Miracles, 1999, www.amazon.com/Miracles-Corne…ref=pd_sim_b_2

[v] en.wikipedia.org/wiki/David_Alan_Johnson

[vi] Logic and Theism: Arguments for and against Beliefs in God, Cambridge University Press, 2004 (xix + 652).

[vii] www.utsc.utoronto.ca/~sobel/cv.pdf

[viii] www.infidels.org/library/modern/theodore_drange/sobel.html

[ix] Robert J. Fogelin, A Defense of Hume on Miracles, 2005, www.amazon.com/Defense-Miracl…ref=pd_sim_b_7

[x] en.wikipedia.org/wiki/List_of_philosophers_(D%E2%80%93H)

[xi] www.robertfogelin.com/

[xii] philreview.dukejournals.org/c…17/1/142?rss=1 (starting at page 142, or 24 in the document)