Tag Archives: Logic

Consistency in the Hierarchy

When writing on this blog, I try to share nuggets here and there of phenomena, experiments, sociological observations and other peoples’ opinions I find illuminating. Unfortunately, this format can leave readers wanting when it comes to some sort of coherent message. Precisely because of this, I would like to revisit a few blog posts I’ve written in the past and highlight the common vein running through them.

Condensed matter physicists of the last couple generations have grown up ingrained with the idea that “More is Different”, a concept first coherently put forth by P. W. Anderson and carried further by others. Most discussions of these ideas tend to concentrate on the notion that there is a hierarchy of disciplines where each discipline is not logically dependent on the one beneath it. For instance, in solid state physics, we do not need to start out at the level of quarks and build up from there to obtain many properties of matter. More profoundly, one can observe phenomena which distinctly arise in the context of condensed matter physics, such as superconductivity, the quantum Hall effect and ferromagnetism that one wouldn’t necessarily predict by just studying particle physics.

While I have no objection to these claims (and actually agree with them quite strongly), it seems to me that one rather (almost trivial) fact is infrequently mentioned when these concepts are discussed. That is the role of consistency.

While it is true that one does not necessarily require the lower level theory to describe the theories at the higher level, these theories do need to be consistent with each other. This is why, after the publication of BCS theory, there were a slew of theoretical papers that tried to come to terms with various aspects of the theory (such as the approximation of particle number non-conservation and features associated with gauge invariance (pdf!)).

This requirement of consistency is what makes concepts like the Bohr-van Leeuwen theorem and Gibbs paradox so important. They bridge two levels of the “More is Different” hierarchy, exposing inconsistencies between the higher level theory (classical mechanics) and the lower level (the micro realm).

In the case of the Bohr-van Leeuwen theorem, it shows that classical mechanics, when applied to the microscopic scale, is not consistent with the observation of ferromagnetism. In the Gibbs paradox case, classical mechanics, when not taking into consideration particle indistinguishability (a quantum mechanical concept), is inconsistent with the idea the entropy must remain the same when dividing a gas tank into two equal partitions.

Today, we have the issue that ideas from the micro realm (quantum mechanics) appear to be inconsistent with our ideas on the macroscopic scale. This is why matter interference experiments are still carried out in the present time. It is imperative to know why it is possible for a C60 molecule (or a 10,000 amu molecule) to be described with a single wavefunction in a Schrodinger-like scheme, whereas this seems implausible for, say, a cat. There does again appear to be some inconsistency here, though there are some (but no consensus) frameworks, like decoherence, to get around this. I also can’t help but mention that non-locality, à la Bell, also seems totally at odds with one’s intuition on the macro-scale.

What I want to stress is that the inconsistency theorems (or paradoxes) contained seeds of some of the most important theoretical advances in physics. This is itself not a radical concept, but it often gets neglected when a generation grows up with a deep-rooted “More is Different” scientific outlook. We sometimes forget to look for concepts that bridge disparate levels of the hierarchy and subsequently look for inconsistencies between them.

Transistors, Logic and Abstraction

A general theme of science that manifests itself in many different ways is the concept of abstraction. What this means is that one can understand something at a higher level without having to understand a buried lower level. For instance, one can understand the theory of evolution based on natural selection (higher level) without having to first comprehend quantum mechanics (lower level), even though the higher level must be consistent with the lower one.

To my mind, this idea is most aptly demonstrated with transistors, circuits and logic. Let’s start at the level of transistors and build a NAND gate in the following way:

NANDCircuit

NAND Circuit

The NAND gate has the following truth table:

NANDTruthTable

If you can’t immediately see why the transistor circuit above yields the corresponding truth table, it helps to appeal to the “water analogy”, where one imagines the current flow as water. Imagine that water is flowing from Vcc. If A and B are high, the “dams” (transistors) are open, the current will flow to ground and X will be low. If either A or B is low (closed), the water will flow to X, and X will be high.

Why did I choose the NAND circuit instead of other logic gates? It turns out that all other logic gates can be built from the NAND alone, so it makes sense to choose it as a fundamental unit.

Let’s now abstract away the circuit and draw the NAND gate like so:

NANDgate

NAND Gate

Having abstracted away the transistor circuit, we can now play with this NAND gate and build other logic gates out of it. For instance, let’s think about how to build an OR gate. Well, an OR gate is just a NOT gate applied to the two inputs of a NAND gate. Therefore, we just need to build a NOT gate. One way to do this would be:

NOTgate

NOT from NAND

Notice that whenever A is high, X is low and vice versa. Let us now abstract this circuit away and draw the NOT gate as:

 

NOTabstract

NOT Gate

And now the OR gate can be made in the following way:

ORGate

OR from NOT and NAND

 

and abstracted away to look like:

ORAbstract

OR Gate

Now, although building an OR gate from NAND gates is totally unnecessary, and it actually would just be easier to do this by working with the transistors directly, one can already start to see the power of abstracting away the underlying circuit. We can just work at higher levels, build the component we want and put the transistors back in at the end. Our understanding of what is going on is not compromised in any way and is in fact probably enhanced since we don’t have to think about the water analogy any more!

Let’s work now with an example that actually is much easier at the level of NANDs and NOTs to really demonstrate the power of this technique. Let’s make what is called a multiplexer. A multiplexer is a three input-one output circuit with the following truth table:

MultiplexorTruthTabl

Multiplexor Truth Table

Notice that in this truth table, the X serves as a selector. When X is 0, it selects B as the output (Y), whereas when X is 1, it selects A as the output. The multiplexer can be built in the following way:

MultiplexorCircuit

Multiplexer from NOT and NANDs

and is usually abstracted in the following way:

MultiplexorAbstract

Multiplexer Gate

At this level, it is no longer a simple task to come up with a transistor circuit that will operate as a multiplexer, but it is relatively straightforward at the level of NANDs and NOTs. Now, armed with the multiplexer, NAND, NOT and OR gates, we can build even more complex circuit components. In fact, doing this, one will eventually arrive at the hardware for a basic computer. Therefore, next time you’re looking at complex circuitry, know that the builders used abstraction to think about the meaning of the circuit and then put all the transistors back in later.

I’ll stop building circuits here; I think the idea I’m trying to communicate is becoming increasingly clear. We can work at a certain level, abstract it away and then work at a higher level. This is an important concept in every field of science. Abstraction occurs in every realm. This is even true in particle physics. In condensed matter physics, we use this concept everyday to think about what happens in materials, abstracting away complex electron-electron interactions into a quasi-particle using Fermi liquid theory or abstracting away the interactions between the underlying electrons in a superconductor to understand vortex lattices (pdf!).