Category: Epistemology

Introduction to Mathematical Logic (Part 3: Reconciling Gödel’s Completeness And Incompleteness Theorems)

~ ~ Leave a comment

Last time we saw that no first-order theory could successfully pin down the natural numbers as a unique model. We also saw that in fact no sound and complete theory with the property of finite provability could pick out ℕ; any such theory has a Compactness Theorem, from which you can prove the existence of nonstandard models of numbers that include infinities of numbers larger than any of the naturals.

Worse, we saw that due to the Löwenheim-Skolem theorem, any first-order theory of the naturals has uncountable models, as well as models of every infinite cardinality. What followed from this was that try as we might, any first-order theory will fail to prove elementary facts about the natural numbers, like that there are a countable infinity of them or that no number is larger than 0, 1, 2, 3, and all the rest of the standard naturals.

Now, with the limitations in our ability to prove all true facts about the natural numbers firmly established, I want to talk about a theorem that seems to be in contradiction with this. This is the Completeness Theorem, proven by the same Kurt Gödel who later discovered the Incompleteness Theorems.

In a few words, the Completeness Theorem says that in any first-order theory, that which is semantically entailed is also syntactically entailed. Or, said differently, the Completeness Theorem says that a first order theory can prove everything that is true in all its models.

This sounds great! It’s the dream of mathematicians to be able to construct a framework in which all truths are provable, and Gödel appears to be telling us that first order logic is just such a framework.

But hold on, how do we reconcile this with what we just said: that there are true facts about the natural numbers that can’t be proven? And how do we reconcile this with what Gödel later proved: the Incompleteness Theorems? The First Incompleteness Theorem shows that that in any axiomatic system of mathematics, there will be true statements about arithmetic that cannot be proven within the system. These seem to be in stark contradiction, right? So which is right; Completeness or Incompleteness? Can we prove everything in first-order logic or not?

It turns out that there is no contradiction here. The Completeness Theorem is true of first order logic, as is the Incompleteness Theorem. What’s required is a subtle understanding of exactly what each theorem is saying to understand why the apparent conflict is only apparent.

There are two senses of completeness. One sense of completeness refers to theories in a particular logic. In this sense, a theory is complete if it can prove the truth or falsity of every well-formed formula. Gödel’s Incompleteness Theorems are about this sense of completeness: no theory rich enough to talk about the natural numbers can prove all statements about the natural numbers.

The second sense of completeness refers to logical frameworks themselves. A logical framework is complete if for every theory in that logic, all the semantically valid statements can be proven. Gödel’s Completeness Theorem is about this sense of completeness. In first-order logic, any theory’s semantic consequences are syntactic consequences.

Let’s go a little deeper into this.

What Gödel showed in his First Incompleteness Theorem is that one can encode the statements of any logical theory (first order or second order) as natural numbers. Then, if your theory is expressive enough to talk about the natural numbers, you produce a type of circularity: Your theory makes statements about the natural numbers, and the natural numbers encode statements from the theory. Gödel exploited this circularity to produce a sentence whose interpretation is something like “This sentence has no proof in T” (where T is your chosen theory). This sentence corresponds to some complicated fact about the properties of the natural numbers, because all sentences are encoded as natural numbers. If it’s false, then that means that the sentence does have a proof, so it’s true. And if it’s true, then it has no proof. The conclusion is that for any theory T, there are true statements about the natural numbers that cannot be proven by T.

The Incompleteness Theorem plays out slightly differently in first and second order logic. In first-order logic, anything that’s true in all models is provable. It’s just that there is no theory that has the natural numbers as a unique model. The best you can do in first-order logic is develop a theory that has the natural numbers as one out of many models. But this means that there is no first-order theory whose semantic consequences are all the truths about the natural numbers! (This is a neat way to actually prove the inevitability of nonstandard models of arithmetic, as a necessary consequence of the combination of the Completeness and Incompleteness theorems.)

And as it happens, any theory that has a model of the natural numbers is also going to have models in which Gödel’s statement is actually false! Remember that Gödel’s statement, if false, says that it is provable, which is to say that some number encodes a proof of it. In nonstandard models of arithmetic, there will be nonstandard numbers that encode a “proof” of Gödel’s statement, using Gödel’s encoding. It’s just that these “proofs” are not actually going to be things that we recognize as valid (for example, nonstandard numbers can represent infinitely long proofs). They’re proofs according to Gödel’s encoding, but Gödel’s encoding only represents valid proofs insofar as we assume that only natural numbers are being used in the encoding. So since Gödel’s statement is not true in all models of any first-order theory of arithmetic, it’s not provable from the axioms of the theory. And this is totally consistent with any first-order theory being complete! All that completeness means is that anything that is true in all models of a theory is also provable!

Now, how does this play out in second-order logic? Well, in second-order logic, you can uniquely pin down the natural numbers with a second-order theory. This is where the Incompleteness Theorem swoops in and tells you that the semantic consequences are not all syntactic consequences. Since there are second-order theories whose semantic consequences are all the truths about the natural numbers, these theories must have as semantic consequences the truth of the Gödel statement, which by construction means that they cannot have the Gödel statement as a syntactic consequence.

So either way you go, first or second order, you’re kinda screwed. In first-order, you can prove all the semantic consequences of a theory. It’s just that no theory has the full set of semantic consequences that we want, because first-order logic doesn’t have the expressive power to pin down the types of mathematical structures that we are interested in. And in second-order theories, you do have the expressive power to pin down the types of mathematical structures we care about, but as a consequence lose the property that all semantic consequences can be proved.

Regardless, there are fundamental limitations in our ability to prove all the facts that we want to prove as mathematicians. Hilbert’s program has crumbled. You can choose a theory that guarantees you the ability to prove all its semantic consequences, but lacks the expressive power to uniquely pin down the natural numbers. Or you can choose a theory that has the expressive power to uniquely pin down the natural numbers, but guarantees you the inability to prove all its semantic consequences.

Introduction to Mathematical Logic (Part 1)

~ ~ 3 Comments

Mathematical logic is the study of the type of reasoning we perform when we do mathematics, and the attempt to formulate a general language as the setting in which all mathematics is done. In essence, it is an attempt to form a branch of mathematics, of which all other branches of mathematics will emerge as special cases.

You might sort of think that when speaking at this level of abstraction, there will nothing general and interesting to say. After all, we’re trying to prove statements not within a particular domain of mathematics, but theorems that are true across a wide swath of mathematics, potentially encompassing all of it.

The surprising and amazing thing is that this is not the case. It turns out that there are VERY general and VERY surprising things you can discover by looking at the logical language of mathematics, a host of results going by names like the Completeness Theorem, the Incompleteness Theorem, the Compactness Theorem, the Löwenheim-Skolem Theorem, and so on. These results inevitably have a great deal of import to our attitudes towards the foundations of mathematics, being that they generally establish limitations or demonstrate eccentricities in the types of things that we can say in the language of mathematics.

My goal in this post is to provide a soft introduction to the art of dealing in mathematics at this level of ultimate abstraction, and then to present some of the most strange things that we know to be true. I think that this is a subject that’s sorely missing this type of soft introduction, and hope I can convey some of the subject’s awesomeness!

— — —

To start out with, why think that there is any subject matter to be explored here? Different branches of mathematics sometimes appear to be studying completely different types of structures. I remember an anecdote from an old math professor of mine, who worked within one very narrow and precisely defined area of number theory, and who told me that when she goes to talks that step even slightly outside her area of specialty, the content of the  lectures quickly incomprehensible to her. Why think that there is such a common language of mathematics, if specialists in mathematics can’t even understand each other when talking between fields?

The key thing to notice here is that although different fields of mathematics are certainly wildly different in many ways, there nevertheless remain certain fundamental features that are shared in all fields. Group theorists, geometrists, and number theorists will all accept the logical inference rule of modus ponens (if P is true and P implies Q, then Q is true), but none of them will accept its converse (if Q is true and P implies Q, then P is true). No matter what area of mathematics you study, you will accept that if P(x) is true for all x, then it is true for any particular x you choose. And so on. These similarities may seem obvious and trivial, but they HAVE to be obvious and trivial to be things that every mathematician agrees on. The goal, then, is to formalize a language that has these fundamental inference rules and concepts built in, and that has many special cases to account for the differences between domains of math, specified by some parameters that are freely chosen by any user of the system.

There are actually several distinct systems that attempt to accomplish this task. Generally speaking, there are three main branches, in order of increasing expressive power: propositional logic, first order (predicate) logic, and second order logic.

Reasoning In Zeroth Order

Let’s start with propositional logic, sometimes called “zeroth order logic.” Propositional logic is the framework developed to deal with the validity of the following types of arguments:

Argument 1

  1. 2+2=4.
  2. If 2+2=4, then 1+3=4.
  3. So 1+3=4.

Argument 2

  1. The Riemann hypothesis is false and P = NP.
  2. So P = NP.

Notice that it doesn’t matter if our premises are true or not. Logical validity doesn’t care about this, it just cares that the conclusions really do follow from the premises. This is a sign of the great generality at which we’re speaking. We’re perfectly fine with talking about a mathematical system in which the Riemann hypothesis is false, or in which 2+2 is not 4, just so long as we accept the logical implications of our assumptions.

Propositional logic can express the validity of these arguments by formalizing rules about valid uses of the concepts ‘and’, ‘if…then…’, ‘or’, and so on. It remains agnostic to the subject matter being discussed by not fully specifying the types of sentences that are allowed to be used in the language. Instead, any particular user of the language can choose their set of propositions that they want to speak about.

To flesh this out more, propositional logic fulfills the following three roles:

  1. Defines an alphabet of symbols.
  2. Specifies a set of rules for which strings are grammatical and which are not.
  3. Details rules for how to infer new strings from existing strings.

In more detail:

  1. The set of symbols in propositional logic are split into two categories: logical symbols and what I’ll call “fill-in-the-blank” symbols. The logical symbols are (, ), ∧, ∨, ¬, and →. The fill-in-the-blank symbols represent specific propositions, that are specified by any particular user of the logic.
  2. Some strings are sensible and others not. For example, the string “P∧∧” will be considered to be nonsensical, while “P∧Q” will not. Some synonyms for sensible strings are well-formed formulas (WFFs), grammatical sentences, and truth-apt sentences. There is a nice way to inductively generate the set of all WFFs: Any proposition is a WFF, and for any two WFFs F and F’, the following are also WFFs: (F∧F’), (F∨F’), ¬F, (F→F’).
  3. These include rules like modus ponens (from P and P→Q, derive Q), conjunction elimination (from P∧Q, derive P), double negation elimination (from ¬¬P, derive P), and several more. They are mechanical rules that tell you how to start with one set of strings and generate new ones in a logically valid way, such that if the starting strings are true than the derived ones must also be true. There are several different but equivalent formulations of the rules of inference in propositional logic.

A propositional language fills in the blanks in the logic. Say that I want to talk about two sentences using propositional logic: “The alarm is going off”, “A robber has broken in.” For conciseness, we’ll abbreviate these two propositions as A for alarm and R for robber. All I’ll do to specify my language is to say “I have two propositions: {A, R}”

The next step is to fill in some of the details about the relationships between the propositions in my language. This is done by supplementing the language with a set of axioms, and we call the resulting constrained structure a propositional theory. For instance, in my example above we might add the following axioms:

  1. A→R
  2. A∨R

In plain English, these axioms tell us that (1) if the alarm is going off, then a robber has broken in, and (2) an alarm is going off or a robber has broken in.

Finally, we talk about the models of our theory. Notice that up until now, we haven’t talked at all about whether any statements are true or false, just about syntactic properties like “The string P∨¬ is not grammatical” and about what strings follow from each other. Now we interpret our theory by seeing what possible assignments of truth values to the WFFs in our language are consistent with our axioms and logical inference rules. In our above example, there are exactly two interpretations:

Model 1: A is true, R is true
Model 2: A is false, R is true

These models can be thought of as the possible worlds that are consistent with our axioms. In one of them, the alarm has gone off and a robber has broken in, and in the other, the alarm hasn’t gone off and the robber has broken in.

Notice that R turns out true in both models. When a formula F is true in all models of a theory, we say that the theory semantically entails F, and write this as T ⊨ F. When a formula can be proven from the axioms of the theory using the rules of inference given by the logic, then we say that the theory syntactically entails F, and write this as T ⊢ F.

This distinction between syntax and semantics is really important, and will come back to us in later discussion of several important theorems (notably the completeness and incompleteness theorems). To give a sneak peek: above we found that R was semantically entailed by our theory. If you’re a little familiar with propositional logic, you might have also realized that R can be proven from the axioms. In general, syntactic truths will always be semantic truths (if you can prove something, then it must be true in all models, or else the models would be inconsistent. But a model is by definition a consistent assignment of truth values to all WFFs). But a natural question is: are all semantic consequences of a theory also syntactic consequences? That is, are all universal truths of the theory (things that are true in every model of the theory) provable from the theory?

Summary of mathematical logic meeting

If the answer is yes, then we say that our logic is complete. And it turns out that the answer is yes, for propositional logic. Whether more complex logics are complete turns out to be a more interesting question. More on this later.

This four-step process I just laid out (logic to language to theory to model) is a general pattern we’ll see over and over again. In general, we have the following division of labor between the four concepts:

  1. Logic: The logic tells us the symbols we may use (including some fill-in-the-blank categories of symbols), the rules of grammar, and a set of inference rules for deriving new strings from an existing set.
  2. Language: The language fills in the blanks in our logic, fully specifying the set of symbols we will be using.
  3. Theory: The theory adds axioms to the language.
  4. Model: A model is an assignment of truth values to all WFFs in the language, consistent with the axioms and the inference rules of our logic.

It’s about time that we apply this four-step division to a more powerful logic. Propositional logic is pretty weak. Not much interesting math can be done in a purely propositional language, and it’s wildly insufficient to capture our notion of logically valid reasoning. Consider, for example, the following argument:

  1. Socrates is a man.
  2. All men are mortal.
  3. So, Socrates is mortal.

This is definitely a valid argument. No rational agent could agree that 1 and 2 are true, and yet deny the truth of 3. But can we represent the validity of this argument in propositional logic? No!

Consider that the three sentences “Socrates is a man”, “All men are mortal”, and “Socrates is mortal” are distinct propositions, and the relationships between them are too subtle for propositional logic to capture. Propositional logic can’t see that the first proposition is asserting the membership of Socrates to a general class of things (“men”), and that the second proposition is then making a statement about a universal property of things in this class. It just sees two distinct propositions. To propositional logic, this argument just looks like

  1. P
  2. Q
  3. Therefore, R

But this is not logically valid! We could make it valid by adding as a premise the sentence (P∧Q)→R, which corresponds to the English sentence “If Socrates is a man and all men are mortal, then Socrates is mortal.” But this should be seen as a tautology, something that is provable in any first order theory that contains the propositions P Q and R, not a required additional assumption. Worse, if somebody came along and stated the proposition A = “Aristotle is a man”, then we would need a whole ‘nother assumption to assert that Aristotle is also mortal! And in general, for any individual instance of this argument, we’d need an independent explanation for its validity. This is not parsimonious, and indicative that propositional logic is missing something big.

Missing what? To understand why this argument is valid, you must be able to reason about objects, properties, and quantification. This is why we must move on to an enormously more powerful and interesting logic: first order logic.

Reasoning In First Order

First order logic is a logic, so it must fill the same three roles as we saw propositional logic did above. Namely, it must define the alphabet, the grammar, and the inference rules.

Symbols
Logical: ∧ ∨ ¬ → ( ) ∀ ∃ =
Variables: x y z w …
Constants: ______
Predicates: ______
Functions: ______

That’s right, in first order we have three distinct categories of fill-in-the-blank symbols. Intuitively, constants will be names that refer to objects, predicates will be functions from objects to truth values, and functions will take objects to objects. To take an everyday example, if the objects in consideration are people, then we might take ‘a’ to be a constant referring to a person named Alex, ’T’ to be a predicate representing ‘is tall’, and ‘f’ to be a function representing “the father of”. So T(a) is either true or false, while f(a) doesn’t have a truth value (it just refers to another object). But T(f(a)) does have a truth value, because it represents the sentence “Alex’s father is tall.”

Next, we define well-formed formulas. This process is more complicated than it was for propositional logic, because we have more types of things than we did before, but it’s not too bad. We start by defining a “term”. The set of terms is inductively generated by the following scheme: All constants and variables are terms, and any function of terms is itself a term. Intuitively, the set of terms is the set of objects that our language is able to “point at”.

With the concept of terms in hand, we can define WFFs through a similar inductive scheme: Any predicate of terms is a WFF. And for any WFFs F and F’, (F∧F’), (F∨F’), (¬F), (F→F’), ∀x F, ∃x F are all WFFs. The details of this construction are not actually that important, I just think it’s nice how you can generate all valid first order formulas from fairly simple rules.

Good! We have an alphabet, a grammar, and now all we need from our logic is a set of inference rules. It turns out that this set is just going to be the inference rules from propositional logic, plus some new ones:

Quantifier elimination: From ∀x P(x) derive P(t) (for any term t and predicate P)
Quantifier introduction: From P(t) derive ∃x P(x) (for any term t and predicate P)

That’s it, we’ve defined first order logic! Now let’s talk about a first order language. Just like before, the language is just obtained by filling in the blanks left open by our logic. So for instance, we might choose the following language:

Constants: a
Functions: f
Predicates: none

In specifying our function, we have to say exactly what type of function it is. Functions can take as inputs a single object (“the father of”) or multiple objects (“the nearest common ancestor of”), and this will make a difference to how they are treated. So for simplicity, let’s say that our function f just takes in a single object.

A first order theory will simply be a language equipped with some set of axioms. Using our language above, we might have as axioms:

  1. ∀x (f(x) ≠ x)
  2. ∀x (f(x) ≠ a)

In plain English, we’re saying that f never takes any object to itself or to a.

And lastly, we get to the models of a first order theory. There’s an interesting difference between models here and models in propositional logic, which is that to specify a first order model, you need to first decide on the size of your set of objects (the size of the ‘universe’, as it’s usually called), and then find a consistent assignment of truth values to all propositions about objects in this universe.

So, for instance, we can start searching for models of our theory above by starting with models with one object, then two objects, then three, and so on. We’ll draw little diagrams below in which points represent objects, and the arrow represents the action of the function f on an object.

  1. No 1-element universe.
    Summary-of-mathematical-logic-meeting-1.png
  2. No 2-element universe.
    Summary-of-mathematical-logic-meeting-2.png
  3. 3-element universe
    Summary-of-mathematical-logic-meeting-3.png
  4. 4 element universes
    Summary-of-mathematical-logic-meeting-5.pngSummary-of-mathematical-logic-meeting-4.pngSummary-of-mathematical-logic-meeting-7.pngSummary of mathematical logic meeting (6)
  5. And so on…

It’s a fun little exercise to go through these cases and see if you can figure out why there are no models of size 1 or 2, or why the one above is the only model of size 3. Notice, by the way, that in the last two images, we have an object for which there is no explicit term! We can’t get there just using our constant and our functions. Of course, in this case we can still be clever with our quantifiers to talk about the Nameless One indirectly (for instance, in both of these models we can refer to the object that is not equal to a, f(a), or f(f(a))) But in general, the set of all things in the universe is not going to be the same as the set of things in the universe that we can name.

Here’s a puzzle for you: Can you make a first order sentence that says “I have exactly four objects”? That is, can you craft a sentence that, if added as an axiom to our theory, will rule out all models besides the ones that have exactly four elements?

(…)

(Think about it for a moment before moving on…)

(…)

Here’s how to do it for a universe with two objects (as well as a few other statements of interest). The case of four objects follows pretty quickly from this.

  • “I have at most two objects” = ∃x∃y∀z (z=x ∨ z=y)
  • “I have exactly two objects” = ∃x∃y (x≠y ∧ ∀z(z=x ∨ z=y))
  • “I have at least two objects” = ∃x∃y (x≠y)

Another puzzle: How would you say “I have an infinity of objects”, ruling out all finite models?

(…)

(Think about it for a moment before moving on…)

(…)

This one is trickier. One way to do it is to introduce an infinite axiom schema: “I have at least n objects” for each n.

This brings up an interesting point: theories with infinite axioms are perfectly permissible for us. This is a choice that we make that we could perfectly well deny, and end up with a different and weaker system of logic. How about infinitely long sentences? Are those allowed? No, not in any of the logics we’re talking about here. A logic in which infinite sentences are allowed is called an infinitary logic, and I don’t know too much about such systems (besides that propositional, first, and second order logics are not infinitary).

Okay… so how about infinitely long derivations? Are those allowed? No, we won’t allow those either. This one is more easy to justify, because if infinite derivations were allowed, then we could prove any statement P simply by the following argument “P, because P, because P, because P, because …”. Each step logically follows from the previous, and in any finite system we’d eventually bottom out and realize that the proof has no basis, but in a naive infinite-proof system, we couldn’t see this.

Alright, one last puzzle. How would you form the sentence “I have a finite number of objects”? I.e., suppose you want to rule out all infinite models but keep the finite ones. How can you do it?

(…)

(Think about it for a moment before moving on…)

(…)

This one is especially tricky, because it turns out to be impossible! (Sorry about that.) You can prove, and we will prove in a little bit, that no first order axiom (or even infinite axiom schema) is in general capable of restricting us to finite models. We have run up against our first interesting expressive limitation of first-order logic!

Okay, let’s now revisit the question of completeness that I brought up earlier. Remember, a logic is complete if for any theory in that logic, the theory’s semantic implications are the same as its syntactic implications (all necessary truths are provable). Do you think that first order logic is complete?

The answer: Yes! Kurt Gödel proved that it is in his 1929 doctoral dissertation. Anything that is true in all models of a first order theory, can be proven from the axioms of that theory (and vice versa). This is a really nice feature to have in a logic. It’s exactly the type of thing that David Hilbert was hoping would be true of mathematics in general. (“We must know. We will know!”) But this hope was dashed by the same Kurt Gödel as above, in his infamous incompleteness theorems.

There will be a lot more to say about that in the future, but I’ll stop this post for now. Next time, we’ll harness the power of first order logic to create a first order model of number theory! This will give us a chance to apply some powerful results in mathematical logic, and to discover surprising truths about the logic’s limitations.

The Central Paradox of Statistical Mechanics: The Problem of The Past

~ ~ 2 Comments

This is the third part in a three-part series on the foundations of statistical mechanics.

  1. The Necessity of Statistical Mechanics for Getting Macro From Micro
  2. Is The Fundamental Postulate of Statistical Mechanics A Priori?
  3. The Central Paradox of Statistical Mechanics: The Problem of The Past

— — —

What I’ve argued for so far is the following set of claims:

  1. To successfully predict the behavior of macroscopic systems, we need something above and beyond the microphysical laws.
  2. This extra thing we need is the fundamental postulate of statistical mechanics, which assigns a uniform distribution over the region of phase space consistent with what you know about the system. This postulate allows us to prove all the things we want to say about the future, such as “gases expand”, “ice cubes melt”, “people age” and so on.
  3. This fundamental postulate is not justifiable on a priori grounds, as it is fundamentally an empirical claim about how frequently different micro states pop up in our universe. Different initial conditions give rise to different such frequencies, so that a claim to a priori access to the fundamental postulate is a claim to a priori access to the precise details of the initial condition of the universe.

 There’s just one problem with all this… apply our postulate to the past, and everything breaks.

 Notice that I said that the fundamental postulate allows us to prove all the things we want to say about the future. That wording was chosen carefully. What happens if you try to apply the microphysical laws + the fundamental postulate to predict the past of some macroscopic system? It turns out that all hell breaks loose. Gases spontaneously contract, ice cubes form from puddles of water, and brains pop out of thermal equilibrium.

 Why does this happen? Very simply, we start with two fully time reversible premises (the microphysical laws and the fundamental postulate). We apply it to present knowledge of some state, the description of which does not specify a special time direction. So any conclusion we get must as a matter of logic be time reversible as well! You can’t start with premises that treat the past as the mirror image of the future, and using just the rules of logical equivalence derive a conclusion that treats the past as fundamentally different from the future. And what this means is that if you conclude that entropy increases towards the future, then you must also conclude that entropy increases towards the past. Which is to say that we came from a higher entropy state, and ultimately (over a long enough time scale and insofar as you think that our universe is headed to thermal equilibrium) from thermal equilibrium.

Let’s flesh this argument out a little more. Consider a half-melted ice cube sitting in the sun. The microphysical laws + the fundamental postulate tell us that the region of phase space consisting of states in which the ice cube is entirely melted is much much much larger than the region of phase space in which it is fully unmelted. So much larger, in fact, that it’s hard to express using ordinary English words. This is why we conclude that any trajectory through phase space that passes through the present state of the system (the half-melted cube) is almost certainly going to quickly move towards the regions of phase space in which the cube is fully melted. But for the exact same reason, if we look at the set of trajectories that pass through the present state of the system, the vast vast vast majority of them will have come from the fully-melted regions of phase space. And what this means is that the inevitable result of our calculation of the ice cube’s history will be that a few moments ago it was a puddle of water, and then it spontaneously solidified and formed into a half-melted ice cube.

This argument generalizes! What’s the most likely past history of you, according to statistical mechanics? It’s not that the solar system coalesced from a haze of gases strewn through space by a past supernova, such that a planet would form in the Goldilocks zone and develop life, which would then gradually evolve through natural selection to the point where you are sitting in whatever room you’re sitting in reading this post. This trajectory through phase space is enormously unlikely. The much much much more likely past trajectory of you through phase space is that a little while ago you were a bunch of particles dispersed through a universe at thermal equilibrium, which happened to spontaneously coalesce into a brain that has time to register a few moments of experience before dissipating back into chaos. “What about all of my memories of the past?” you say. As it happens the most likely explanation of these memories is not that they are veridical copies of real happenings in the universe but illusions, manufactured from randomness.

Basically, if you buy everything I’ve argued in the first two parts, then you are forced to conclude that the universe is most likely near thermal equilibrium, with your current experience of it arising as a spontaneous dip in entropy, just enough to produce a conscious brain but no more. There are at least two big problems with this view.

Problem 1: This conclusion is, we think, extremely empirically wrong! The ice cube in front of you didn’t spontaneously form from a puddle of water, uncracked eggs weren’t a moment ago scrambled, and your memories are to some degree veridical. If you really believe that you are merely a spontaneous dip in entropy, then your prediction for the next minute will be the gradual dissolution of your brain and loss of consciousness. Now, wait a minute and see if this happens. Still here? Good!

Problem 2: The conclusion cannot be simultaneously believed and justified. If you think that you’re a thermal fluctuation, then you shouldn’t credit any of your memories as telling you anything about the world. But then your whole justification to coming to the conclusion in the first place (the experiments that led us to conclude that physics is time-reversible and that the fundamental postulate is true) is undermined! Either you believe it without justification, or you don’t believe despite justification. Said another way, no reflective equilibrium exists at an entropy minimum. David Albert calls this peculiar epistemic state cognitively unstable, as it’s not clear where exactly it should leave you.

Reflect for a moment on how strange of a situation we are in here. Starting from very basic observations of the world, involving its time-reversibility on the micro scale and the increase in entropy of systems, we see that we are inevitably led to the conclusion that we are almost certainly thermal fluctuations, brains popping out of the void. I promise you that no trick has been pulled here, this really is the state of the philosophy of statistical mechanics! The big issue is how to deal with this strange situation.

One approach is to say the following: Our problem is that our predictions work towards the future but not the past. So suppose that we simply add as a new fundamental postulate the proposition that long long ago the universe had an incredibly low entropy. That is, suppose that instead of just starting with the microphysical laws and the fundamental postulate of statistical mechanics, we added a third claims: the Past Hypothesis.

The Past Hypothesis should be understood as an augmentation of our Fundamental Postulate. Taken together, the two postulates say that our probability distribution over possible microstates should not be uniform over phase space. Instead, it should be what you get when you take the uniform distribution, and then condition on the distant past being extremely low entropy. This process of conditioning clearly preferences one direction of time over the other, and so the symmetry is broken.

 It’s worth reflecting for a moment on the strangeness of the epistemic status of the Past Hypothesis. It happens that we have over time accumulated a ton of observational evidence for the occurrence of the Big Bang. But none of this evidence has anything to do with our reasons for accepting the Past Hypothesis. If we buy the whole line of argument so far, our conclusion that something like a Big Bang occurred becomes something that we are forced to believe for deep logical reasons, on pain of cognitive instability and self-undermining belief. Anybody that denies that the Big Bang (or some similar enormously low-entropy past state) occurred has to contend with their view collapsing in self-contradiction upon observing the physical laws!

Is The Fundamental Postulate of Statistical Mechanics A Priori?

~ ~ 6 Comments

This is the second part in a three-part series on the foundations of statistical mechanics.

  1. The Necessity of Statistical Mechanics for Getting Macro From Micro
  2. Is The Fundamental Postulate of Statistical Mechanics A Priori?
  3. The Central Paradox of Statistical Mechanics: The Problem of The Past

— — —

The fantastic empirical success of the fundamental postulate gives us a great amount of assurance that the postulate is good one. But it’s worth asking whether that’s the only reason that we should like this postulate, or if it has some solid a priori justification. The basic principle of “when you’re unsure, just distribute credences evenly over phase space” certainly strikes many people as highly intuitive and justifiable on a priori grounds. But there are some huge problems with this way of thinking, one of which I’ve already hinted at. Here’s a thought experiment that illustrates the problem.

There is a factory in your town that produces cubic boxes. All you know about this factory is that the boxes that they produce all have a volume between 0 m3 and 1 m3. You are going to be delivered a box produced by this factory, and are asked to represent your state of knowledge about the box with a probability distribution. What distribution should you use?

Suppose you say “I should be indifferent over all the possible boxes. So I should have a uniform distribution over the volumes from 0 m3 to 1 m3.” This might seem reasonable at first blush. But what if somebody else said “Yes, you should be indifferent over all the possible boxes, but actually the uniform distribution should be over the side lengths from 0 m to 1 m, not volumes.” This would be a very different probability distribution! For example, if the probability that the side length is greater than .5 m is 50%, then the probability that the volume is greater than (.5)3 = 1/8 is also 50%! Uniform over side length is not the same as uniform over volume (or surface area, for that matter). Now, how do you choose between a uniform distribution over volumes and a uniform distribution over side lengths? After all, you know nothing about the process that the factory is using to produce the boxes, and whether it is based off of volume or side length (or something else); all you know is that all boxes are between 0 m3 and 1 m3.

The lesson of this thought experiment is that the statement we started with (“I should be indifferent over all possible boxes”) was actually not even well-defined. There’s not just one unique measure over a continuous space, and in general the notion that “all possibilities are equally likely” is highly language-dependent.

The exact same applies to phase space, as position and momentum are continuous quantities. Imagine that somebody instead of talking about phase space, only talked about “craze space”, in which all positions become positions cubed, and all momentum values become natural logs of momentum. This space would still contain all possible microstates of your system. What’s more, the fundamental laws of nature could be rewritten in a way that uses only craze space quantities, not phase space quantities. And needless to say, being indifferent over phase space would not be the same as being indifferent over craze space.

Spend enough time looking at attempts to justify a unique interpretation of the statement “All states are equally likely”, when your space of states is a continuous infinity, and you’ll realize that all such attempts are deeply dependent upon arbitrary choices of language. The maximum information entropy probability distribution is afflicted with the exact same problem, because the entropy of your distribution is going to depend on the language you’re using to describe it! The entropy of a distribution in phase space is NOT the same as the entropy of the equivalent distribution transformed to craze space.

Let’s summarize this section. If somebody tells you that the fundamental postulate says that all microstates compatible with what you know about the macroscopic features of your system are equally likely, the proper response is something like “Equally likely? That sounds like you’re talking about a uniform distribution. But uniform over what? Oh, position and momentum? Well, why’d you make that choice?” And if they point out that the laws of physics are expressed in terms of position and momentum, you just disagree and say “No, actually I prefer writing the laws of physics in terms of position cubed and log momentum!” (Substitute in any choice of monotonic functions).

If they object on the grounds of simplicity, point out that position and momentum are only simple as measured from a standpoint that takes them to be the fundamental concepts, and that from your perspective, getting position and momentum requires applying complicated inverse transformations to your monotonic transformation of the chosen coordinates.

And if they object on the grounds of naturalness, the right response is probably something like “Tell me more about this ’naturalness’. How do you know what’s natural or unnatural? It seems to me that your choice of what physical concepts count as natural is a manifestation of deep selection pressures that push any beings whose survival depends on modeling and manipulating their surroundings towards forming an empirically accurate model of the macroscopic world. So that when you say that position is more natural than log(position), what I hear is that the fundamental postulate is a very useful tool. And you can’t use the naturalness of the choice of position to justify the fundamental postulate, when your perception of the naturalness of position is the result of the empirical success of the fundamental postulate!”

In my judgement, none of the a priori arguments work, and fundamentally the reason is that the fundamental postulate is an empirical claim. There’s no a priori principle of rationality that tells us that boxes of gases tend to equilibrate, because you can construct a universe whose initial microstate is such that its entire history is one of entropy radically decreasing, gases concentrating, eggs unscrambling, ice cubes unmelting, and so on. Why is this possible? Because it’s consistent with the microphysical laws that the universe started in an enormously low entropy configuration, so it’s gotta also be consistent with the microphysical laws for the entire universe to spend its entire lifetime decreasing in entropy. The general principle is: If you believe that something is physically possible, then you should believe its time-inverse is possible as well.

Let’s pause and take stock. What I’ve argued for so far is the following set of claims:

  1. To successfully predict the behavior of macroscopic systems, we need something above and beyond the microphysical laws.
  2. This extra thing we need is the fundamental postulate of statistical mechanics, which assigns a uniform distribution over the region of phase space consistent with what you know about the system. This postulate allows us to prove all the things we want to say about the future, such as “gases expand”, “ice cubes melt”, “people age” and so on.
  3. This fundamental postulate is not justifiable on a priori grounds, as it is fundamentally an empirical claim about how frequently different microstates pop up in our universe. Different initial conditions give rise to different such frequencies, so that a claim to a priori access to the fundamental postulate is a claim to a priori access to the precise details of the initial condition of the universe.

There’s just one problem with all this… apply our postulate to the past, and everything breaks.

Up next: Why does statistical mechanics give crazy answers about the past? Where did we go wrong?

A Cognitive Instability Puzzle, Part 2

~ ~ 4 Comments

This is a follow of this previous post, in which I present three unusual cases of belief updating. Read it before you read this.

I find these cases very puzzling, and I don’t have a definite conclusion for any of them. They share some deep similarities. Let’s break all of them down into their basic logical structure:

Joe
Joe initially believes in classical logic and is certain of some other stuff, call it X.
An argument A exists that concludes that X can’t be true if classical logic is true.
If Joe believes classical logic, then he believes A.
If Joe believes intuitionist logic, then he doesn’t believe A.

Karl
Karl initially believes in God and is certain of some other stuff about evil, call it E.
An argument A exists that concludes that God can’t exist if E is true.
If Karl believes in God, then he believes A.
If Karl doesn’t believe in God, then he doesn’t believe A.

Tommy
Tommy initially believes in her brain’s reliability and is certain of some other stuff about her experiences, call it Q.
An argument A exists that concludes that hat her brain can’t be reliable if Q is true.
If Tommy believes in her brain’s reliability, then she believes A.
If Tommy doesn’t believe in her brain’s reliability, then she doesn’t believe A.

First of all, note that all three of these cases are ones in which Bayesian reasoning won’t work. Joe is uncertain about the law of the excluded middle, without which you don’t have probability theory. Karl is uncertain about the meaning of the term ‘evil’, such that the same proposition switches from being truth-apt to being meaningless when he updates his beliefs. Probability theory doesn’t accommodate such variability in its language. And Tommy is entertaining a hypothesis according to which she no longer accepts any deductive or inductive logic, which is inconsistent with Bayesianism in an even more extreme way than Joe.

The more important general theme is that in all three cases, the following two things are true: 1) If an agent believes A, then they also believe an argument that concludes -A. 2) If that agent believes -A, then they don’t believe the argument that concludes -A.

Notice that if an agent initially doesn’t believe A, then they have no problem. They believe -A, and also happen to not believe that specific argument concluding -A, and that’s fine! There’s no instability or self-contradiction there whatsoever. So that’s really not where the issue lies.

The mystery is the following: If the only reason that an agent changed their mind from A to -A is the argument that they no longer buy, then what should they do? Once they’ve adopted the stance that A is false, should they stay there, reasoning that if they accept A they will be led to a contradiction? Or should they jump back to A, reasoning that the initial argument that led them there was flawed?

Said another way, should they evaluate the argument against A from their own standards, or from A’s standards? If they use their own standards, then they are in an unstable position, where they jump back and forth between A and -A. And if they always use A’s standards… well, then we get the conclusion that Tommy should believe herself to be a Boltzmann brain. In addition, if they are asked why they don’t believe A, then they find themselves in the weird position of giving an explanation in terms of an argument that they believe to be false!

I find myself believing that either Joe should be an intuitionist, Karl an atheist, and Tommy a radical skeptic, OR Joe a classical-logician, Karl a theist, and Tommy a reliability-of-brain-believer-in. That is, it seems like there aren’t any significant enough disanalogies between these three cases to warrant concluding one thing in one case and then going the other direction in another.

Logic, Theism, and Boltzmann Brains: On Cognitively Unstable Beliefs

~ ~ 7 Comments

First case

Propositional logic accepts that the proposition A∨-A is necessarily true. This is called the law of the excluded middle. Intuitionist logic differs in that it denies this axiom.

Suppose that Joe is a believer in propositional logic (but also reserves some credence for intuitionist logic). Joe also believes a set of other propositions, whose conjunction we’ll call X, and has total certainty in X.

One day Joe discovers that a contradiction can be derived from X, in a proof that uses the law of the excluded middle. Since Joe is certain that X is true, he knows that X isn’t the problem, and instead it must be the law of the excluded middle. So Joe rejects the law of the excluded middle and becomes an intuitionist.

The problem is, as an intuitionist, Joe now no longer accepts the validity of the argument that starts at X and concludes -X! Why? Because it uses the law of the excluded middle, which he doesn’t accept.

Should Joe believe in propositional logic or intuitionism?

Second case

Karl is a theist. He isn’t absolutely certain that theism is correct, but holds a majority of his credence in theism (and the rest in atheism). Karl is also 100% certain in the following claim: “If atheism is true, then the concept of ‘evil’ is meaningless”, and believes that logically valid arguments cannot be made using meaningless concepts.

One day somebody presents the problem of evil to Karl, and he sees it as a crushing objection to theism. He realizes that theism, plus some other beliefs about evil that he’s 100% confident in, leads to a contradiction. So since he can’t deny these other beliefs, he is led to atheism.

The problem is, as an atheist, Karl no longer accepts the validity of the argument that starts at theism and concludes atheism! Why? Because the arguments rely on using the concept of ‘evil’, and he is now certain that this concept is meaningless, and thus cannot be used in logically valid arguments.

Should Karl be a theist or an atheist?

Third case

Tommy is a scientist, and she believes that her brain is reliable. By this, I mean that she trusts her ability to reason both deductively and inductively. However, she isn’t totally certain about this, and holds out a little credence for radical skepticism. She is also totally certain about the content of her experiences, though not its interpretation (i.e. if she sees red, she is 100% confident that she is experiencing red, although she isn’t necessarily certain about what in the external world is causing the experience).

One day Tommy discovers that reasoning deductively and inductively from her experiences leads her to a model of the world that entails that her brain is actually a quantum fluctuation blipping into existence outside the event hole of a black hole. She realizes that this means that with overwhelmingly high probability, her brain is not reliable and is just producing random noise uncorrelated with reality.

The problem is, if Tommy believes that her brain is not reliable, then she can no longer accept the validity of the argument that led her to this position! Why? Well, she no longer trusts her ability to reason deductively or inductively. So she can’t accept any argument, let alone this particular one.

What should Tommy believe?

— — —

How are these three cases similar and different? If you think that Joe should be an intuitionist, or Karl an atheist, then should Tommy believe herself to be a black hole brain? Because it turns out that many cosmologists have found themselves to be in a situation analogous to Case 3! (Link.) I have my own thoughts on this, but I won’t share them for now.

Philosophers of religion are religious. Why?

~ ~ 5 Comments

In 2009, David Chalmers organized a massive survey of over 3000 professional philosophers, grad students, and undergrads, asking them questions about all things philosophical and compiling the results. The results are broken down by area of specialization, age, race, gender, and everything else you might be interested in.

Here’s a link to the paper, and here to a listing of all survey results.

This is basically my favorite philosophy paper to read, and I find myself going back to look at the results all the time. I’d love to see an updated version of this survey, done ten years later, to see how things have changed (if at all).

There’s a whole lot I could talk about regarding this paper, but today I’ll just focus on one really striking result. Take a look at the following table from the paper:

Screen Shot 2019-09-11 at 1.36.13 PM.png

What’s shown is the questions which were answered most differently by specialists and non-specialists. At the very top of the list, with a discrepancy more than double the second highest, is the question of God’s existence. 86.78% of non-specialists said yes to atheism, and by contrast only 20.87% of philosophers of religion said yes to atheism. This is fascinating to me.

Here are two narratives one could construct to make sense of these results.

Narrative One

Philosophers that specialize in philosophy of religion probably select that specialization because they have a religious bias. A philosophically-minded devout Catholic is much more likely to go into philosophy of religion than, say, philosophy of language. And similarly, an atheistic philosopher would have less interest in studying philosophy of religion, being that they don’t even believe in the existence of the primary object of study, than a religious philosopher. So the result of the survey is exactly what you’d expect by the selection bias inherent in the specialization.

Narrative Two

Philosophers, like everybody else, are vulnerable to a presumption in favor of the beliefs of their society. Academics in general are quite secular, and in many quarters religion is treated as a product of a bygone age. So it’s only natural that philosophers that haven’t looked too deeply into the issue come out believing basically what the high-status individuals in their social class believe. But philosophers of religion, on the other hand, are those that have actually looked most closely and carefully at the arguments for and against atheism, and this gives them the ability to transcend their cultural bias and recognize the truth of religion.

As an atheist, it’s perhaps not surprising that my immediate reaction to seeing this result was something like Narrative One. And upon reflection, that still seems like the more likely explanation to me. But to a religious person, I’m sure that Narrative Two would seem like the obvious explanation. This, by the way, is what should happen from a Bayesian perspective. If two theories equally well explain some data, then the one with a higher prior should receive a larger credence bump than the one with a lower prior (although their odds ratio should stay fixed).

Ultimately, which of these stories is right? I don’t know. Perhaps both are right to some degree. But I think that it illustrates the difficulty of adjudicating expertise questions. Accusations of bias are quite easy to make, and can be hard to actually get to the bottom of. That said, it’s definitely possible to evaluate the first narrative, just by empirically looking at the reasons that philosophers of religion entered the field. If somebody knows of such a study, comment it or send me a message please! The results of a study like this could end up having a huge effect on my attitude towards questions of religion’s rationality.

Imagine that it turned out that most philosophers of religion were atheists when they entered the field, and only became religious after diving deep into the arguments. This is not what I’d expect to find, but if it was the case, it would serve as a super powerful argument against atheism for me.

x^5 – x – 1

~ ~ 2 Comments

One of the strange and wonderful facts of mathematics is the general unsolvability of quintic polynomials. If you haven’t heard about this, prepare to have your mind pleasantly blown. Most people memorize the quadratic equation, the general expression for the roots of any quadratic polynomial, in high school:

Screen Shot 2019-08-27 at 11.19.54 AM.png
Screen Shot 2019-08-27 at 11.14.31 AM.png

And even though very few people learn it in school, it turns out that we know a general solution to any cubic polynomial as well. It’s a little cumbersome to write, but just like the quadratic equation, it expresses the zeroes of any cubic polynomial as a function of its coefficients.

ax3 + bx2 + cx + d = 0
x = (some big complicated function of a, b, c, and d)

And in fact we have a general solution for any quartic polynomial as well, even more cumbersome.

ax4 + bx3 + cx2 + dx + e = 0
x = (some even bigger and more complicated function of a, b, c, d, and e)

Mathematicians struggled for a long time to find a general solution for the roots of quintic polynomials (ax5 + bx4 + cx3 + dx2 + ex + f = 0). Eventually, some mathematicians began to suspect that no such general solution existed. And then in the first few decades of the 1800s, a few mathematicians put out proofs to that effect. The most complete of these proofs was provided by Évariste Galois before he died in a duel at the age of 20 (we really need a big Hollywood movie about Galois’ life).

I recently found a fantastic 15-minute video sketching the proof of the unsolvability of the quintic. The approach taken in this proof is different from any of the original proofs, and it’s much simpler in a bunch of ways.

Here’s the video:

And briefly, here’s a summary of the proof:

  1. The roots of any quintic polynomial obviously depend on the coefficients of the polynomial.
  2. If you imagine taking a particular quintic polynomial (ax5 + bx4 + cx3 + dx2 + ex + f), and making small continuous changes in the coefficients (a, b, c, d, e, f), then the set of zeroes of this polynomial should make similar continuous changes.
  3. If you move each coefficient in a loop in the complex plane, ending at the same value it started at, then you should end up with the same set of zeroes as you started with (the same set, by the way, which doesn’t guarantee that each solution ends at the same place it started).
  4. However, moving each coefficient in a loop in the complex plane sometimes ends up with the solutions switching places. (Illustration below)
  5. For any “ordinary” function of the coefficients (a function that can be written using a finite number of rational numbers and the symbols +, -, ×, /, exp(), log(), √, and so on), you can find loops that don’t cause the solutions to switch places.
  6. But for some quintic polynomials, you can always finds one of these loops that does cause the roots to switch places.
  7. So there are quintic polynomials whose roots cannot be written as any ordinary function of the coefficients (since you can find a loop that permutes the solutions of the quintic but don’t permute the values of any ordinary function).

There are obviously holes in this proof that need to be filled. (1) through (3) should be pretty self-explanatory. And (4) can be illustrated by thinking about functions that involve square roots… on the complex plane, taking a square root of an expression means halving the angle to the expression. So rotating an expression around the complex plane by 2π only ends up rotating its square root by π (and thus bringing it to a different point). Observe:

Square Roots of 2
Red dots are the square roots of the white dot, which starts and ends at 2.

And in general, a function involving an nth root of some ordinary expression will take n rotations around the complex plane to return each solution to its starting point. Take a look for n = 3:

Cube Roots of 2
Red dots are the cube roots of the white dot, which starts and ends at 2.

For (5), you can prove this by using commutator loops (which are formed from two smaller loops L1 and L2 by putting them together as follows: L1 L2 L1-1 L2-1). Ultimately, this works for expressions with roots in them because solutions switch places exactly when you circle the origin of the complex plane, and commutators circle the origin a net zero times. For expressions with one nested root, you actually need to use commutators of commutators (first to return the inner root to its starting value, and then to return the outer root to its starting value). And with two nested roots, you use commutators of commutators of commutators. And so on. In this way, you can construct a loop in the complex plane for any expression you construct from roots and ordinary functions that will bring all values back to their starting points.

And finally, (6) is a result of the structure of the permutation group on five elements (S5). If you look at all commutators of permutations of five elements, you are looking at the commutator subgroup of S5, which is A5 (the set of even permutations of five elements). And the commutator subgroup of A5 is just A5 itself. This means that you can find always find some commutator, or some commutator of commutators, or some commutator of commutators of commutators, (and so on) that is not equal to the identity permutation! (After all, if all commutators of commutators of commutators ended up just being the identity permutation, then the group of commutators of commutators of commutators would just be the trivial group {e}. But we already know that the group of commutators of commutators of commutators is just the commutator subgroup of the commutator subgroup of the commutator subgroup of S5. I.e. the commutator subgroup of A5, which is A5.

And that’s the proof! You can see the whole thing sketched out in much more detail here.

Now, notice that the conclusion was that there are quintic polynomials whose roots cannot be written as any ordinary function of the coefficients. Not that all quintic polynomials’ roots can’t be written as such. Obviously, there are some quintics whose solutions can be written easily. For example…

x5 – 1 = 0
Solutions: x = e2πik/5 for k = 0, 1, 2, 3, 4

But there also exist many quintic polynomials whose roots just have no way of being finitely expressed through ordinary functions! An example of this is the real root of x5 – x – 1.

x5 – x – 1 = 0
at x ≈ 1.167304…

Screen Shot 2019-08-27 at 11.24.41 AM
Plot of x5 – x – 1

There is no way to write this number using a finite number of the symbols +, -, ×, /, exp(), log(), √, sin(), cos(), and rational numbers. And this is the case even though this number is an algebraic number! I don’t know if there’s a name for this category of “algebraic numbers that cannot be explicitly expressed using ordinary functions” but there should be.

Of course, you can define a function into existence that just returns the solutions of the quintic (which is what the Bring radical allows one to do). And you can also write the solution with ordinary functions if you’re allowed to use an infinity of them. For example, you can use a repeated fifth root:

x5 – x – 1 = 0
x5 = x + 1
x = (1 + x)1/5
x = (1 + (1 + x)1/5)1/5
x = (1 + (1 + (1 + x)1/5)1/5)1/5
x = (1 + (1 + (1 + (…))1/5)1/5)1/5

But while an infinity of symbols suffices to express this 1.167304…, no finite number cuts it!

Extending Cauchy’s Theorem

~ ~ Leave a comment

Here I present an extension of Cauchy’s theorem that I haven’t seen anywhere else.

In our earlier proof of Cauchy’s theorem, we saw that r, the number of p-tuples (g,g,…,g) of elements of G whose product is e, had to be a multiple of p. Since (e,e,…,e) was one such p-tuple, we knew that r was greater than zero, and therefore concluded that there must be at least one other element g in G such that gp = e. And that was how we got Cauchy’s theorem. But in our final step, we weakened our state of knowledge quite a bit, from “r = pn (for some positive n)” to “r > 1”. We can get a slightly stronger result than Cauchy’s theorem by just sticking to our original statement and not weakening it.

So, we know that r = pn for some n. Does this mean that there are pn elements of order p? Not quite. One of these p-tuples is just (e,e,…,e), and e is order 1, not p. So there are really (pn – 1) elements of order p.

Furthermore, each of these elements forms a subgroup of size p. Every non-identity element in any of these subgroups is also order p. So this tells us that the number of elements of order p must be k(p – 1), where k is the number of subgroups of order p.

Putting these together, we see that (pn – 1) = k(p – 1). Crucially, this equation can’t be satisfied for all n and p! In particular, for k to be an integer, the value of n must be such that pn – 1 is divisible by p – 1. Let’s look at some examples.

p = 2

2n – 1 must be divisible by 1. This is true for all n.
So k, the number of subgroups of order 2, is 2n – 1 for any positive n.
k = 1, 3, 5, 7, …

p = 3

3n – 1 must be divisible by 2. This is only true for odd n.
So k, the number of subgroups of order 3, is (3n – 1)/2 for any odd n.
k = 1, 4, 7, 10, …

p = 5

5n – 1 must be divisible by 4. This is only true for n = 1, 5, 9, 14, …
So k = 1, 6, 11, 16, …

See the pattern? In general, the number of subgroups of order p can only be 1 + mp for any m ≥ 0. And the number of elements of order p is therefore mp2 – (m – 1)p – 1.

Needless to say, this is a much stronger result than what Cauchy’s theorem tells us!

An Application

Say we have a group G such that |G| = 15 = 3⋅5. By Cauchy, we know that there’s at least one subgroup of size 3 and one of size 5. But now we can do better than that! In particular we know that:

Number of subgroups of size 3 = 1, 4, 7, 10, …
Number of subgroups of size 5 = 1, 6, 11, 16, …

For each subgroup of size 3, we have 2 unique elements of order 3. And for each subgroup of size 5, we have 4 unique elements of order 5.

Number of elements of order 3 = 2, 8, 14, …
Number of elements of order 5 = 4, 24, 44, 64, …

But keep in mind, we only have 15 elements to work with! This immediately rules out a bunch of the possibilities:

Number of subgroups of size 3 = 1, 4, or 7
Number of subgroups of size 5 = 1

So we know that there is exactly one subgroup of size 5, which means that 4 of our 15 elements are order 5. This leaves us with only 10 non-identity elements left, ruling out 7 as a possible number of subgroups of size 3. So finally, we get:

Number of subgroups of size 3 = 1 or 4
Number of subgroups of size 5 = 1

This is as far as we can go using only our extended Cauchy theorem. However, we can actually go a little further using Sylow’s Third Theorem. This allows us to rule out there being four subgroups of size 3 (since 4 doesn’t divide 5). So the “subgroup profile” of G is totally clear: G has one subgroup of size 3 and one of size 5. You can use this fact to show that there is exactly one group of size 15, and it is just ℤ15.

ℤ15 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}
Subgroup of size 3 = <5> = {0, 5, 10}
Subgroup of size 5 = <3> = {0, 3, 6, 9, 12}
All other elements generate the whole group.

All About Adultery, BDSM, and Divorce

~ ~ Leave a comment

I recently came across a whole bunch of crazy historical trivia, involving the laws around adultery, BDSM, and divorce. Here are some of the quotes that made me gasp (mostly from Wikipedia):

On Adultery

As of 2019, adultery remains a criminal offense in 19 states, but prosecutions are rare. Although adultery laws are mostly found in the conservative states (especially Southern states), there are some notable exceptions such as New York, Idaho, Oklahoma, Michigan, and Wisconsin consider adultery a felony, while in the other states it is a misdemeanor.

Penalties vary from a $10 fine (Maryland) to four years in prison (Michigan). In South Carolina, the fine for adultery is up to $500 and/or imprisonment for no more than one year (South Carolina code 16-15-60), and South Carolina divorce laws deny alimony to the adulterous spouse.

In Florida adultery (“Living in open adultery”, Art 798.01) is illegal; while cohabitation of unmarried couples was decriminalized in 2016.

Under South Carolina law adultery involves either “the living together and carnal intercourse with each other” or, if those involved do not live together “habitual carnal intercourse with each other” which is more difficult to prove.

In Alabama “A person commits adultery when he engages in sexual intercourse with another person who is not his spouse and lives in cohabitation with that other person when he or that other person is married.”

In some Native American cultures, severe penalties could be imposed on an adulterous wife by her husband. In many instances she was made to endure a bodily mutilation which would, in the mind of the aggrieved husband, prevent her from ever being a temptation to other men again. Among the Aztecs, wives caught in adultery were occasionally impaled, although the more usual punishment was to be stoned to death.

The Code of Hammurabi, a well-preserved Babylonian law code of ancient Mesopotamia, dating back to about 1772 BC, provided drowning as punishment for adultery.

Amputation of the nose – rhinotomy – was a punishment for adultery among many civilizations, including ancient India, ancient Egypt, among Greeks and Romans, and in Byzantium and among the Arabs.

In England and its successor states, it has been high treason to engage in adultery with the King’s wife, his eldest son’s wife and his eldest unmarried daughter. The jurist Sir William Blackstone writes that “the plain intention of this law is to guard the Blood Royal from any suspicion of bastardy, whereby the succession to the Crown might be rendered dubious.”

Adultery was a serious issue when it came to succession to the crown. Philip IV of France had all three of his daughters-in-law imprisoned, two (Margaret of Burgundy and Blanche of Burgundy) on the grounds of adultery and the third (Joan of Burgundy) for being aware of their adulterous behaviour. The two brothers accused of being lovers of the king’s daughters-in-law were executed immediately after being arrested.

Until 2018, in Indian law, adultery was defined as sex between a man and a woman without the consent of the woman’s husband. The man was prosecutable and could be sentenced for up to five years (even if he himself was unmarried) whereas the married woman cannot be jailed.

In Southwest Asia, adultery has attracted severe sanctions, including death penalty. In some places, such as Saudi Arabia, the method of punishment for adultery is stoning to death. Proving adultery under Muslim law can be a very difficult task as it requires the accuser to produce four eyewitnesses to the act of sexual intercourse, each of whom should have a good reputation for truthfulness and honesty. The criminal standards do not apply in the application of social and family consequences of adultery, where the standards of proof are not as exacting.

Adultery is no longer a crime in any European country. Among the last Western European countries to repeal their laws were Italy (1969), Malta (1973), Luxembourg (1974), France (1975), Spain (1978), Portugal (1982), Greece (1983), Belgium (1987), Switzerland (1989), and Austria (1997).

In most Communist countries adultery was not a crime. Romania was an exception, where adultery was a crime until 2006, though the crime of adultery had a narrow definition, excluding situations where the other spouse encouraged the act or when the act happened at a time the couple was living separate and apart; and in practice prosecutions were extremely rare.

English common law defined the crime of seduction as a felony committed “when a male person induced an unmarried female of previously chaste character to engage in an act of sexual intercourse on a promise of marriage.” A father had the right to maintain an action for the seduction of his daughter (or the enticement of a son who left home), since this deprived him of services or earnings.

In more modern times, Frank Sinatra was charged in New Jersey in 1938 with seduction, having enticed a woman “of good repute to engage in sexual intercourse with him upon his promise of marriage. The charges were dropped when it was discovered that the woman was already married.”

Buddhist Pali texts narrate legends where the Buddha explains the karmic consequences of adultery. For example, states Robert Goldman, one such story is of Thera Soreyya. Buddha states in the Soreyya story that “men who commit adultery suffer hell for hundreds of thousands of years after rebirth, then are reborn a hundred successive times as women on earth, must earn merit by “utter devotion to their husbands” in these lives, before they can be reborn again as men to pursue a monastic life and liberation from samsara.

According to Muhammad, an unmarried person who commits adultery or fornication is punished by flogging 100 times; a married person will then be stoned to death. A survey conducted by the Pew Research Center found support for stoning as a punishment for adultery mostly in Arab countries; it was supported in Egypt (82% of respondents in favor of the punishment) and Jordan (70% in favor), as well as Pakistan (82% favor), whereas in Nigeria (56% in favor) and in Indonesia (42% in favor) opinion is more divided, perhaps due to diverging traditions and differing interpretations of Sharia.

The Roman Lex Julia, Lex Iulia de Adulteriis Coercendis (17 BC), punished adultery with banishment. The two guilty parties were sent to different islands (“dummodo in diversas insulas relegentur”), and part of their property was confiscated. Fathers were permitted to kill daughters and their partners in adultery. Husbands could kill the partners under certain circumstances and were required to divorce adulterous wives.

Durex’s Global Sex Survey found that worldwide 22% of people surveyed admitted to have had extramarital sex. In the United States Alfred Kinsey found in his studies that 50% of males and 26% of females had extramarital sex at least once during their lifetime. Depending on studies, it was estimated that 26–50% of men and 21–38% of women, or 22.7% of men and 11.6% of women, had extramarital sex. Other authors say that between 20% and 25% of Americans had sex with someone other than their spouse. Three 1990s studies in the United States, using nationally representative samples, have found that about 10–15% of women and 20–25% of men admitted to having engaged in extramarital sex.

The Standard Cross-Cultural Sample described the occurrence of extramarital sex by gender in over 50 pre-industrial cultures. The occurrence of extramarital sex by men is described as “universal” in 6 cultures, “moderate” in 29 cultures, “occasional” in 6 cultures, and “uncommon” in 10 cultures. The occurrence of extramarital sex by women is described as “universal” in 6 cultures, “moderate” in 23 cultures, “occasional” in 9 cultures, and “uncommon” in 15 cultures.

Traditionally, many cultures, particularly Latin American ones, had strong double standards regarding male and female adultery, with the latter being seen as a much more serious violation.

Adultery involving a married woman and a man other than her husband was considered a very serious crime. In 1707, English Lord Chief Justice John Holt stated that a man having sexual relations with another man’s wife was “the highest invasion of property” and claimed, in regard to the aggrieved husband, that “a man cannot receive a higher provocation” (in a case of murder or manslaughter).

The Encyclopedia of Diderot & d’Alembert, Vol. 1 (1751), also equated adultery to theft writing that, “adultery is, after homicide, the most punishable of all crimes, because it is the most cruel of all thefts, and an outrage capable of inciting murders and the most deplorable excesses.”

On BDSM

The United States Federal law does not list a specific criminal determination for consensual BDSM acts. Some states specifically address the idea of “consent to BDSM acts” within their assault laws, such as the state of New Jersey, which defines “simple assault” to be “a disorderly persons offense unless committed in a fight or scuffle entered into by mutual consent, in which case it is a petty disorderly persons offense”.

Mutual combat, a term commonly used in United States courts, occurs when two individuals intentionally and consensually engage in a fair fight, while not hurting bystanders or damaging property. There is not an official law that forbids mutual combat in the United States. There have been numerous cases where this concept was successfully used in defense of the accused. In some cases, mutual combat may nevertheless result in killings.

Oregon Ballot Measure 9 was a ballot measure in the U.S. state of Oregon in 1992, concerning sadism, masochism, gay rights, pedophilia, and public education, that drew widespread national attention. It would have added the following text to the Oregon Constitution:

All governments in Oregon may not use their monies or properties to promote, encourage or facilitate homosexuality, pedophilia, sadism or masochism. All levels of government, including public education systems, must assist in setting a standard for Oregon’s youth which recognizes that these behaviors are abnormal, wrong, unnatural and perverse and they are to be discouraged and avoided.

Dildos or any object used for “the stimulation of human genital organs” cannot be made or sold in Alabama. The Anti-Obscenity Enforcement Act says that anyone caught with such tools could face a fine up to $20,000, a one-year jail sentence or 12-months doing hard labor.

Florida bans “lewd and lascivious behavior,” which is defined as a situation where “any man and woman, not being married to each other, lewdly and lasciviously associate and cohabit together.” The misdemeanor is punishable by a fine of up to $500. In Mississippi, an unmarried couple caught living together “whether in adultery or fornication” can face up to six months in jail and/or a $500 fine.

In 2003, the U.S. Supreme Court deemed a Texas state law that banned the practice of anal and oral sex between same-sex couples as unconstitutional. Despite the ruling, a sizable list of states, including Texas, still have anti-sodomy laws on the books.

Louisiana’s “crime against nature” statute prohibits the “the unnatural carnal copulation by a human being with another of the same sex or opposite sex or with an animal.” The state legislature in April failed to pass a bill that would have repealed the law except for human-on-animal relations.

Other states that have some form of anti-sodomy laws include Kansas, Oklahoma, Alabama, Florida, Idaho, Louisiana, Mississippi, North Carolina, South Carolina, and Utah, according to the Human Rights Campaign. Virginia repealed its ban in March.

On Divorce

Today, every state plus the District of Columbia permits no-fault divorce, though requirements for obtaining a no-fault divorce vary. California was the first U.S. state to pass a no-fault divorce law. Its law was signed by Governor Ronald Reagan, a divorced and remarried former movie actor, and came into effect in 1970. New York was the last state to pass a no-fault divorce law; that law was passed in 2010.

Prior to the advent of no-fault divorce, a divorce was processed through the adversarial system as a civil action, meaning that a divorce could be obtained only through a showing of fault of one (and only one) of the parties in a marriage. This required that one spouse plead that the other had committed adultery, abandonment, felony, or other similarly culpable acts. However, the other spouse could plead a variety of defenses, like recrimination (essentially an accusation of “so did you”). A judge could find that the respondent had not committed the alleged act or the judge could accept the defense of recrimination and find both spouses at fault for the dysfunctional nature of their marriage. Either of these two findings was sufficient to defeat an action for divorce, which meant that the parties remained married.

Before no-fault divorce was available, spouses seeking divorce would often allege false grounds for divorce. Removing the incentive to perjure was one motivation for the no-fault movement.

In the States of Wisconsin, Oregon, Washington, Nevada, Nebraska, Montana, Missouri, Minnesota, Michigan, Kentucky, Kansas, Iowa, Indiana, Hawaii, Florida, Colorado and California, a person seeking a divorce is not permitted to allege a fault-based ground (e.g. adultery, abandonment or cruelty).

In some states, requirements were even more stringent. For instance, under its original (1819) constitution, Alabama required not only the consent of a court of chancery for a divorce (and only “in cases provided for by law”), but equally that of two-thirds of both houses of the state legislature. This requirement was dropped in 1861, when the state adopted a new constitution at the outset of the American Civil War. The required vote in this case was even stricter than that required to overturn the governor’s veto in Alabama, which required only a simple majority of both houses of the General Assembly.

These requirements could be problematic if both spouses were at fault or if neither spouse had committed a legally culpable act but both spouses desired a divorce by mutual consent. Lawyers began to advise their clients on how to create legal fictions to bypass the statutory requirements. One method popular in New York was referred to as “collusive adultery”, in which both sides deliberately agreed that the wife would come home at a certain time and discover her husband committing adultery with a “mistress” obtained for the occasion. The wife would then falsely swear to a carefully tailored version of these facts in court (thereby committing perjury). The husband would admit a similar version of those facts. The judge would convict the husband of adultery, and the couple could be divorced. Specifically, they report that “states that adopted no-fault divorce experienced a decrease of 8 to 16 percent in wives’ suicide rates and a 30 percent decline in domestic violence.”

The Code of Hammurabi (1754 BC) declares that a man must provide sustenance to a woman who has borne him children, so that she can raise them:

If a man wish to separate from a woman who has borne him children, or from his wife who has borne him children: then he shall give that wife her dowry, and a part of the usufruct of field, garden, and property, so that she can rear her children. When she has brought up her children, a portion of all that is given to the children, equal as that of one son, shall be given to her. She may then marry the man of her heart.

In the 1970s, the United States Supreme Court ruled against gender bias in alimony awards and, according to the U.S. Census Bureau, the percentage of alimony recipients who are male rose from 2.4% in 2001 to 3.6% in 2006. In states like Massachusetts and Louisiana, the salaries of new spouses may be used in determining the alimony paid to the previous partners.

Some of the possible factors that bear on the amount and duration of the support are:

Factor

Description

Length of the marriage or civil union

Generally, alimony lasts for a term or period. However, it will last longer if the marriage or civil union lasted longer. A marriage or civil union of over 10 years is often a candidate for permanent alimony.

Time separated while still married

In some U.S. states, separation is a triggering event, recognized as the end of the term of the marriage. Other U.S. states do not recognize separation or legal separation. In a state not recognizing separation, a 2-year marriage followed by an 8-year separation will generally be treated like a 10-year marriage.

Age of the parties at the time of the divorce

Generally, more youthful spouses are considered to be more able to ‘get on’ with their lives, and therefore thought to require shorter periods of support.

Relative income of the parties

In U.S. states that recognize a right of the spouses to live ‘according to the means to which they have become accustomed’, alimony attempts to adjust the incomes of the spouses so that they are able to approximate, as best possible, their prior lifestyle.

Future financial prospects of the parties

A spouse who is going to realize significant income in the future is likely to have to pay higher alimony than one who is not.

Health of the parties

Poor health goes towards need, and potentially an inability to support oneself. The courts are disinclined to leave one party indigent.

Fault in marital breakdown

In U.S. states where fault is recognized, fault can significantly affect alimony, increasing, reducing or even nullifying it. Many U.S. states are ‘no-fault‘ states, where one does not have to show fault to get divorced. No-fault divorce spares the spouses the acrimony of the ‘fault’ processes, and closes the eyes of the court to any and all improper spousal behavior. In Georgia, however, a person who has an affair that causes the divorce is not entitled to alimony.