Obstruction Theory

Obstruction is a concept in homotopy theory where an invariant equals zero if a corresponding problem is solvable and is non-zero otherwise. Let Y be a space, and assume for convenience that Y is n-simple for every n, that is, the action of π₁(y) on π_n(y) is trivial for every n. Under this hypothesis we can forget about base points for homotopy groups, and any map ƒ: S → Y determines an element of π_n(Y).

Let B be a complex and A a subcomplex. Write Xⁿ for A U Bⁿ, where Bⁿ denotes the n-skeleton of B. Let σ be an (n + I)-cell of B which is not in A. Let g = g_σ be the attaching map σ^. = Sⁿ → Xⁿ ⊂ B.

Given a map ƒ: Xⁿ → Y, denote by c(ƒ) the cochain in Cⁿ⁺¹ (B, A; π_n(Y)) given by c(ƒ): σ → [f º g_σ]. Then it is clear that ƒ may be extended over Xⁿ ∪ _gσ σ iff f º g_σ is null-homotopic, that is, iff c(ƒ)(σ) = 0, and therefore that ƒ can be extended over Xⁿ⁺¹ = A ∪ Bⁿ⁺¹ if the cochain c(ƒ) is the zero cochain. It is a theorem of obstruction theory that c(ƒ) is a cocycle. It is called the obstruction cocycle or “the obstruction to extending ƒ over Bⁿ⁺¹“

There are two immediate applications. First, any map of an n-dimensional complex K into an n-connected space X is null-homotopic.

Take (B, A) = (K x I, K x i) and define ƒ:A → X by the given map K → X on one piece and a constant map on the other piece; then ƒ can be extended over B because the obstructions lie in the trivial groups π_i(X).

Second, as a particular case, a finite-dimensional complex K is contractible iff π_i(K) is trivial for all i < dim K.

Suppose ƒ, g are two maps Xⁿ → Y which agree on X^n-1. Then for each n-cell of B which is not in A, we get a map Sⁿ → Y by taking ƒ and g on the two hemispheres. The resulting cochain of Cⁿ(B, A; π_n(Y)) is called the difference cochain of ƒ and g, denoted d(ƒ, g).

Advertisement

Hilbert’s Walking the Rope Between Real and Ideal Propositions. Note Quote.

If the atomic sentences of S have a finitistic meaning, which is the case, for instance, when they are decidable, then so have all sentences of S built up by truth-functional connectives and quantifiers restricted to finite domains.

Quantifiers over infinite domains can be looked upon in two ways. One of them may be hinted at as follows. Let x range over the natural numbers, and let A(x) be a formula such that A(n) expresses a finitary proposition for every number n. Then a sentence ∀xA(x) expresses a transfinite proposition, if it is understood as a kind of infinite conjunction which is true when all of the infinitely many sentences A(n), where n is a natural number, hold.

Similarly, a sentence ∃xA(x) expresses a transfinite proposition, if it is understood as a kind of infinite disjunction which is true when, of all the infinitely many sentences A(n), where n is a natural number, there is one that holds. There is a certain ambiguity here, however, depending on what is meant by ‘all’ and ‘there is one’. To indicate the transfinite interpretation one should also add that the sentences are understood in such a way that it is determined, regardless of whether this can be proved or not, whether all of the sentences A(n) hold or there is some one that does not hold.

If instead an assertion of ∀xA(x) is understood as asserting that there is a method which, given a specific natural number n, yields a proof of A(n), then we have to do with a finitary proposition. Similarly, we have a case of a finitary proposition, when to assert ∃xA(x) is the same as to assert that A(n) can be proved for some natural number n.

It is to be noted that the ‘statement’ “In the real part of mathematics, either in the real part of S or in some extension of it, that for each A ∈ R, if ⌈_S A, then A is true” is a universal sentence. Hence, the possibility of giving a finitary interpretation of the universal quantifier is a prerequisite for Hilbert’s program. Does the possibility of interpreting the quantifiers in a finitary way also mean that one may hope for a solution of the problem stated in the above ‘statement’ when all quantified sentences interpreted in that way are included in R?

A little reflection shows that the answer is no, but that R may always be taken as closed under universal quantification. For it can be seen (uniformly in A) that if we have established the ‘statement’ when R contains all instances of a sentence ∀xA(x), then the ‘statement’ also holds for R+ = R U {∀xA(x)}. To see this let ∀xA(x) be a formula provable in S whose instances belong to R, and let a method be given which applied to any formula in R and a proof of it in S yields a proof of its truth. We want to show that ∀xA(x) is true when interpreted in a finitistic way, i.e. that we have a method which applied to any natural number n yields a proof of A(n). The existence of such a method is obvious, because, from the proof given of ∀xA(x), we get a proof of A(n), for any n, and hence by specialization of the given method, we have a method which yields the required proof of the truth of A(n), for any n.

Having included universal sentences ∀xA(x) in R such that all A(n) are decidable, it is easy to see that one cannot in general also let existentially quantified sentences be included in R, if the ‘statement’ is still to be possible. For let S contain classical logic and assume that R contains undecidable sentences ∀xA(x) with A(n) decidable; by Gödel’s theorem there are such sentences if S is sufficiently rich. Then one cannot allow R to be closed under existential quantification. In particular, one cannot allow formulas ∃y(∀xA(x) V ¬ A(y)) to belong to R ∀ A: the formulas are provable in S but all of them cannot be expected to be true when interpreted in a finitistic way, because then, for any A, we would get a proof of ∀xA(x) V ¬ A(n) for some n, which would let us decide ∀xA(x).

In accordance with these observations, the line between real and ideal propositions was drawn in Hilbert’s program in such a way as to include among the real ones decidable propositions and universal generalizations of them but nothing more; in other words, the set R in the ‘statement’ is to consist of atomic sentences (assuming that they are decidable), sentences obtained from them by using truth-functional connectives, and finally universal generalizations of such sentences.

Given that R is determined in this way and that the atomic sentences in the language of S are decidable and provable in S if true (and hence that the same holds for truth-functional compounds of atomic sentences in S), which is normally the case, the consistency of S is easily seen to imply the statement in the ‘statement’ as follows. Assume consistency and let A be a sentence without quantifiers that is provable in S. Then A must be true, because, if it were not, then ¬ A would be true and hence provable in S by the assumption made about S, contradicting the consistency. Furthermore, a sentence ∀xA(x) provable in S must also be true, because there is a method such that for any given natural number n, the method yields a proof of A(n). By applying the decision method to A(n); by the consistency and the assumption on S, it must yield a proof of A(n) and not of ¬A(n).

Conjuncted: Gross Domestic Product. Part 2.

Conjuncted here.

The topology of the World Trade, which is encapsulated in its adjacency matrix a_ij defined by

a_ij(t) ≡ 1 if f_ij(t) > 0

a_ij(t) ≡ 0 if f_ij(t) = 0

, strongly depends on the GDP values w_i. Indeed, the problem can be mapped onto the so-called fitness model where it is assumed that the probability p_ij for a link from i to j is a function p(x_i, x_j) of the values of a fitness variable x assigned to each vertex and drawn from a given distribution. The importance of this model relies in the possibility to write all the expected topological properties of the network (whose specification requires in principle the knowledge of the N² entries of its adjacency matrix) in terms of only N fitness values. Several topological properties including the degree distribution, the degree correlations and the clustering hierarchy are determined by the GDP distribution. Moreover, an additional understanding of the World Trade as a directed network comes from the study of its reciprocity, which represents the strong tendency of the network to form pairs of mutual links pointing in opposite directions between two vertices. In this case too, the observed reciprocity structure can be traced back to the GDP values.

The probability that at time t a link exists from i to j (a_ij = 1) is empirically found to be

p_t [x_i(t), x_j(t)] = [α(t) x_i(t) x_j(t)]/[1 + β(t) x_i(t) x_j(t)]

where x_i is the rescaled GDP and the parameters α(t) and β(t) can be fixed by imposing that the expected number of links

L_exp(t) = ∑_i≠j p_t [x_i(t), x_j(t)]

equals its empirical value

L(t) = ∑_i≠j a_ij(t)

and that the expected number of reciprocated links

L^↔_exp(t) = ∑_i≠j p_t[x_i(t), x_j(t)] p_t[x_j(t), x_i(t)]

equals its observed value

L^↔(t) = ∑_i≠j a_ij(t) a_ji(t)

This particular structure of the World Trade topology can be tested by comparing various expected topological properties with the empirical ones. For instance, we can compare the empirical and the theoretical plots of vertex degrees (at time t) versus their rescaled GDP x_i(t). Note that since p_t [x_i(t), x_j(t)] is symmetric under the exchange of i and j, at any given time the expected in-degree and the expected out-degree of a vertex i are equal. We denote both by k^exp_i, which can be expressed as

k^exp_i(t) = ∑_j≠i p_t[x_i(t), x_j(t)]

Since the number of countries N(t) increases in time, we define the rescaled degrees

k ^̃_i(t) ≡ k_i(t)/[N(t) − 1]

that always represent the fraction of vertices which are connected to i (the term −1 comes from the fact that there are no self-loops in the network, hence the maximum degree is always N − 1). In this way, we can easily compare the data corresponding to different years and network sizes. The results are shown in the figure below for various snapshots of the system.

Figure: Plot of the rescaled degrees versus the rescaled GDP at four different years, and comparison with the expected trend. 

The empirical trends are in accordance with the expected ones. Then we can also compare the cumulative distribution P^exp_>(k ^̃exp) of the expected degrees with the empirical degree distributions Pⁱⁿ_>(k ^̃in) and P^out_>(k ^̃out). The results are shown in the following figure and are in conformity to a good agreement between the theoretical prediction and the observed behavior.

Figure: Cumulative degree distributions of the World Trade topology for four different years and comparison with the expected trend. 

Note that the accordance with the predicted behaviour is extremely important since the expected quantities are computed by using only the N GDP values of all countries, with no information regarding the N² trade values. On the other hand, the empirical properties of the World Trade topology are extracted from trade data, with no knowledge of the GDP values. The agreement between the properties obtained by using these two independent sources of information is therefore surprising. This also shows that the World Trade topology crucially depends on the GDP distribution ρ(x).

Gross Domestic Product. Part 1.

The Gross Domestic Product wi of a country i is defined as the “total market value of all final goods and services produced in a country in a given period, equal to total consumer, investment and government spending, plus the value of exports, minus the value of imports”. In other words, there are two main terms contributing to the observed value of the GDP w_i of a country i: an endogenous term I_i (also konwn as internal demand) determined by the internal spending due to the country’s economic process and an exogenous term F_i determined by the trade flow with other countries. The above definition can then be rephrased as

w_i(t) ≡ I_i(t) + F_i(t) —– (1)

where F_i(t), the total trade value of exports and imports by i to/from all other countries will be denoted by fⁱⁿ_i(t) and f^out_i(t) respectively, and it can be expressed as

fⁱⁿ_i(t) ≡ ∑_j=1^N(t) f_ji(t) —– (2)

f^out_i(t) ≡ ∑_j=1^N(t) f_it(t) —– (3)

The net amount of incoming money due to the trading activity is therefore given by

F_i(t) ≡  f^out_i(t) – fⁱⁿ_i(t) —– (4)

The above definition anticipates that the GDP is strongly affected by the structure of the World Trade topology. Looking at some empirical properties of the GDP:

A fundamental macroeconomic question is: how is the GDP distributed across world countries? To address this point we consider the distribution of the rescaled quantity

x_i(t) ≡ w_i(t) /〈w(t)〉—– (5)

where ⟨w⟩ ≡ w_T/N is the average GDP and w_T(t) ≡ ∑_i=1^N(t) w_i(t) is the total one. In the figure below, is the cumulative distribution

ρ_> (x) ≡ ∫_x^∞ ρ(x’) dx’ —– (6)

Figure: Normalized cumulative distribution of the relative GDP x_i(t) ≡ w_i(t)/⟨w⟩(t) for all world countries at four different snapshots. Inset: the same data plotted in terms of the rescaled quantity y_i(t) ≡ w_i(t)/w_T(t) = x_i(t)/N(t) for the transition region to a power-law curve.

for four different years in the time interval considered. The right tail of the distribution roughly follows a straight line in log-log axes, corresponding to a power-law curve

ρ_> (x) ∝ x^1−α —– (7)

with exponent 1 − α = −1, which indicates a tail in the GDP probability distribution ρ(x) ∝ x^−α with α = 2. This behaviour is qualitatively similar to the power-law character of the per capita GDP distribution.

Moreover, it can be seen that the cumulative distribution departs from the power-law behaviour in the small x region, and that the value x^∗ where this happens is larger as time increases. However, if x_i(t) is rescaled to

y_i(t) ≡ w_i(t)/w_T(t) = x_i(t)/N(t) —– (8)

then the point y^∗ = x^∗/N ≈ 0.003 where the power-law tail of the distribution starts is approximately constant in time (see inset of figure). This suggests that the temporal change of x^∗ is due to the variation of N(t) affecting ⟨w(t)⟩ and not to other factors. This is because the temporal variation of N(t) affects the average-dependent quantities such as x: note that, while for a system with a fixed number N of units w_T would be simply proportional to the average value ⟨w⟩. In particular, the average values of the quantities of interest may display sudden jumps due to the steep increase of N(t) rather than to genuine variations of the quantities themselves…..

Conjuncted: Operations of Truth. Thought of the Day 47.1

Conjuncted here.

Let us consider only the power set of the set of all natural numbers, which is the smallest infinite set – the countable infinity. By a model of set theory we understand a set in which  – if we restrict ourselves to its elements only – all axioms of set theory are satisfied. It follows from Gödel’s completeness theorem that as long as set theory is consistent, no statement which is true in some model of set theory can contradict logical consequences of its axioms. If the cardinality of p(N) was such a consequence, there would exist a cardinal number κ such that the sentence the cardinality of p(N) is κ would be true in all the models. However, for every cardinal κ the technique of forcing allows for finding a model M where the cardinality of p(N) is not equal to κ. Thus, for no κ, the sentence the cardinality of p(N) is κ is a consequence of the axioms of set theory, i.e. they do not decide the cardinality of p(N).

The starting point of forcing is a model M of set theory – called the ground model – which is countably infinite and transitive. As a matter of fact, the existence of such a model cannot be proved but it is known that there exists a countable and transitive model for every finite subset of axioms.

A characteristic subtlety can be observed here. From the perspective of an inhabitant of the universe, that is, if all the sets are considered, the model M is only a small part of this universe. It is deficient in almost every respect; for example all of its elements are countable, even though the existence of uncountable sets is a consequence of the axioms of set theory. However, from the point of view of an inhabitant of M, that is, if elements outside of M are disregarded, everything is in order. Some of M because in this model there are no functions establishing a one-to-one correspondence between them and ω₀. One could say that M simulates the properties of the whole universe.

The main objective of forcing is to build a new model M[G] based on M, which contains M, and satisfies certain additional properties. The model M[G] is called the generic extension of M. In order to accomplish this goal, a particular set is distinguished in M and its elements are referred to as conditions which will be used to determine basic properties of the generic extension. In case of the forcing that proves the undecidability of the cardinality of p(N), the set of conditions codes finite fragments of a function witnessing the correspondence between p(N) and a fixed cardinal κ.

In the next step, an appropriately chosen set G is added to M as well as other sets that are indispensable in order for M[G] to satisfy the axioms of set theory. This set – called generic – is a subset of the set of conditions that always lays outside of M. The construction of M[G] is exceptional in the sense that its key properties can be described and proved using M only, or just the conditions, thus, without referring to the generic set. This is possible for three reasons. First of all, every element x of M[G] has a name existing already in M (that is, an element in M that codes x in some particular way). Secondly, based on these names, one can design a language called the forcing language or – as Badiou terms it – the subject language that is powerful enough to express every sentence of set theory referring to the generic extension. Finally, it turns out that the validity of sentences of the forcing language in the extension M[G] depends on the set of conditions: the conditions force validity of sentences of the forcing language in a precisely specified sense. As it has already been said, the generic set G consists of some of the conditions, so even though G is outside of M, its elements are in M. Recognizing which of them will end up in G is not possible for an inhabitant of M, however in some cases the following can be proved: provided that the condition p is an element of G, the sentence S is true in the generic extension constructed using this generic set G. We say then that p forces S.

In this way, with an aid of the forcing language, one can prove that every generic set of the Cohen forcing codes an entire function defining a one-to-one correspondence between elements of p(N) and a fixed (uncountable) cardinal number – it turns out that all the conditions force the sentence stating this property of G, so regardless of which conditions end up in the generic set, it is always true in the generic extension. On the other hand, the existence of a generic set in the model M cannot follow from axioms of set theory, otherwise they would decide the cardinality of p(N).

The method of forcing is of fundamental importance for Badious philosophy. The event escapes ontology; it is “that-which-is-not-being-qua-being”, so it has no place in set theory or the forcing construction. However, the post-evental truth that enters, and modifies the situation, is presented by forcing in the form of a generic set leading to an extension of the ground model. In other words, the situation, understood as the ground model M, is transformed by a post-evental truth identified with a generic set G, and becomes the generic model M[G]. Moreover, the knowledge of the situation is interpreted as the language of set theory, serving to discern elements of the situation; and as axioms of set theory, deciding validity of statements about the situation. Knowledge, understood in this way, does not decide the existence of a generic set in the situation nor can it point to its elements. A generic set is always undecidable and indiscernible.

Therefore, from the perspective of knowledge, it is not possible to establish, whether a situation is still the ground-model or it has undergone a generic extension resulting from the occurrence of an event; only the subject can interventionally decide this. And it is only the subject who decides about the belonging of particular elements to the generic set (i.e. the truth). A procedure of truth or procedure of fidelity (Alain Badiou – Being and Event) supported in this way gives rise to the subject language. It consists of sentences of set theory, so in this respect it is a part of knowledge, although the veridicity of the subject language originates from decisions of the faithful subject. Consequently, a procedure of fidelity forces statements about the situation as it is after being extended, and modified by the operation of truth.

Impasse to the Measure of Being. Thought of the Day 47.0

The power set p(x) of x – the state of situation x or its metastructure (Alain Badiou – Being and Event) – is defined as the set of all subsets of x. Now, basic relations between sets can be expressed as the following relations between sets and their power sets. If for some x, every element of x is also a subset of x, then x is a subset of p(x), and x can be reduced to its power set. Conversely, if every subset of x is an element of x, then p(x) is a subset of x, and the power set p(x) can be reduced to x. Sets that satisfy the first condition are called transitive. For obvious reasons the empty set is transitive. However, the second relation never holds. The mathematician Georg Cantor proved that not only p(x) can never be a subset of x, but in some fundamental sense it is strictly larger than x. On the other hand, axioms of set theory do not determine the extent of this difference. Badiou says that it is an “excess of being”, an excess that at the same time is its impasse.

In order to explain the mathematical sense of this statement, recall the notion of cardinality, which clarifies and generalizes the common understanding of quantity. We say that two sets x and y have the same cardinality if there exists a function defining a one-to-one correspondence between elements of x and elements of y. For finite sets, this definition agrees with common intuitions: if a finite set y has more elements than a finite set x, then regardless of how elements of x are assigned to elements of y, something will be left over in y precisely because it is larger. In particular, if y contains x and some other elements, then y does not have the same cardinality as x. This seemingly trivial fact is not always true outside of the domain of finite sets. To give a simple example, the set of all natural numbers contains quadratic numbers, that is, numbers of the form n², as well as some other numbers but the set of all natural numbers, and the set of quadratic numbers have the same cardinality. The correspondence witnessing this fact assigns to every number n a unique quadratic number, namely n².

Counting finite sets has always been done via natural numbers 0, 1, 2, . . . In set theory, the concept of such a canonical measure can be extended to infinite sets, using the notion of cardinal numbers. Without getting into details of their definition, let us say that the series of cardinal numbers begins with natural numbers, which are directly followed by the number ω₀, that is, the size of the set of all natural numbers , then by ω₁, the first uncountable cardinal numbers, etc. The hierarchy of cardinal numbers has the property that every set x, finite or infinite, has cardinality (i.e. size) equal to exactly one cardinal number κ. We say then that κ is the cardinality of x.

The cardinality of the power set p(x) is 2ⁿ for every finite set x of cardinality n. However, something quite paradoxical happens when infinite sets are considered. Even though Cantor’s theorem does state that the cardinality of p(x) is always larger than x – similarly as in the case of finite sets – axioms of set theory never determine the exact cardinality of p(x). Moreover, one can formally prove that there exists no proof determining the cardinality of the power sets of any given infinite set. There is a general method of building models of set theory, discovered by the mathematician Paul Cohen, and called forcing, that yields models, where – depending on construction details – cardinalities of infinite power sets can take different values. Consequently, quantity – “a fetish of objectivity” as Badiou calls it – does not define a measure of being but it leads to its impasse instead. It reveals an undetermined gap, where an event can occur – “that-which-is-not being-qua-being”.