Bounded treewidth implies bounded clique-width

We have a graph G of treewidth $ \operatorname{tw}(G)\leq k$ , for some $ k\in\mathbb{N}$ . I’ve seen a claim that that implies that the clique-width of the same graph is at most $ k \cdot 2^k$ . This implies that given a tree decomposition of the graph we can construct a proper expression tree using at most $ k \cdot 2^k$ labels.

I’m guessing that the $ k$ in the decomposition allows us to “construct” a node of the tree decomposition, i.e. regardless how the vertices in one bag are connected, we can easily connect them since we have $ k+1$ -ish labels at our disposal. However, I don’t quite see how we can use that fact to construct the complete expression tree (and therefore the $ k\cdot 2^k$ -expression).

How can we construct the proper expression and therefore prove that graphs of bounded treewidth are a subclass of graphs of bounded clique-width

Proving that the failure of algorithm W implies that the program is not typable

How one does prove that if algorithm W failed for a given program $ e$ and context $ \Gamma$ , then there is no substitution $ S$ and type $ \tau$ such that $ S\Gamma \vdash e : \tau$ ?

The original paper states that from the completeness proof one can derive that “it is decidable whether $ e$ has any type at all under the assumptions $ \Gamma$ “. However, I didn’t found this proof in the literature.

The algorithm W has some failures cases: the unification algorithm failed, an identifier was not found in the context, a recursive call failed, etc.

I more interested in the hard cases, the easy ones I can do myself.

One hard case seems to be the failure of the unification. In this case we know about the soundness and completeness of both recursive calls and, also, the non-existence of a unifier for $ S_2\tau_1$ and $ \tau_2\rightarrow \alpha$ . How those informations can be used to prove $ \neg \exists \tau \:S, S\Gamma \vdash e_1 \: e_2 : \tau $ ?

This part of algorithm W may be relevant here:

$ W(\Gamma, e_1\: e_2)$ =

$ (\tau_1,S_1) \leftarrow W(\Gamma, e_1)$

$ (\tau_2,S_2) \leftarrow W(S_1\Gamma, e_2)$

$ S \leftarrow unify(S_2\tau_1, \tau_2\rightarrow \alpha)$ where $ \alpha$ is fresh

return $ (S\alpha, S_\circ S_1 \circ S_2)$

There are other hard cases, but I will be accepting an answer if it is about at least this one.

What are the sets on which norm-closedness implies weakly closedness?

Let $ X$ be a Banach space. Let $ C$ be a convex, and normed-closed subset of $ X$ . It is well-known that $ C$ becomes weakly closed subset of $ X$ . I want to know is there any well-know class of non convex sets which has this property?

i.e., a class of sets in $ X$ , not necessary convex on which, norm-closed implies weakly-closed.

Find the cocycle condition in fppf descent implies Galois descent

I tried to give a proof that fppf (faithfully flat) descent implies Galois descent purely at the level of modules and I stumble to obtain the Galois cocycle condition. I’m interested to consider some questions of twisted sheaves with a Galois cohomological description and understanding how to obtain the former would be useful to me.

I obtained the following the following conditions: Given a finite Galois extension $ L/K$ of Galois group $ G$ and $ M$ an $ L$ -vector space $ M$ , we have for each $ \sigma \in G$ an isomorphism of $ L$ -vector spaces $ \psi_\sigma : M \to M^\sigma$ satisfying $ \psi_\sigma(am) = \sigma(a) \psi_\sigma(m)$ , where $ a \in L$ and $ m \in M$ and such that for every pair $ (\sigma, \tau) \in G \times G$ we have

$ $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \sigma } \circ \psi_{ ( \sigma, \tau), (\sigma, \tau), \tau } = \psi_{ ( \sigma, \tau), (\sigma, \tau), \sigma \tau } $ $

as isomorphisms of $ L$ -modules. The $ L$ -module structure of $ M^\sigma$ is twisted by $ \sigma$ , i.e given by $ a \cdot m:= \sigma(a)m$ .

My issue is that because of what one obtains for sheaves of modules ( I would expect the cocycle condition for modules to also have a twisting in the formula.

Translating what is done in stacks project into modules is certainly possible but I wasn’t able to do so. Instead I will present a (somehow long) sketch of what I did. I can provide more details upon request and I apologize if there are too many. My difficulty is on Step 5.

The context: Let $ L/K$ be a finite Galois extension and let $ M$ be an $ L$ -module together we an isomorphism of $ L \otimes_K L$ -modules $ \phi: M \otimes_K L \to L \otimes_K M$ satisfying the cocyle condition $ p_{13}^* \phi = p_{23}^* \phi \circ p_{12}^* \phi$ as isomorphisms of $ L \otimes_K L \otimes_K L$ -modules.

What I did:

Step 1: Describing some isomorphisms We have an isomorphism of $ K$ -algebras $ L \otimes_K L \to \prod_{\sigma \in G} L$ given by $ a \otimes 1 \mapsto ( a )_{\sigma \in G}$ and $ 1 \otimes a \mapsto ( \sigma(a) )_{\sigma \in G}$

and another one $ L \otimes_K L \otimes_K L \to \prod_{\sigma \in G} \Big( \prod_{\tau \in G} L \Big)$ given by

$ $ a \otimes 1 \otimes 1 \mapsto \Big( (a)_{\tau \in G} \Big)_{\sigma \in G}, $ $

$ $ 1 \otimes a \otimes 1 \mapsto \Big( (\tau(a)_{\tau \in G} \Big)_{\sigma \in G}, $ $

$ $ 1 \otimes 1 \otimes a \mapsto \Big( \tau\sigma(a)_{\tau \in G} \Big)_{\sigma \in G}. $ $

We can then describe the above isomorphisms as

$ $ (1_L \coprod \sigma) : L \otimes_K L \to \prod_{\sigma \in G} L $ $


$ $ (1_L \coprod \tau \coprod \tau \sigma): L \otimes_K L \otimes_K L \to \prod_{\sigma \in G} \Big( \prod_{\tau \in G} L \Big). $ $

Step 2: Obtain some $ \prod_{\sigma \in G} L$ -module structures

We then have a commutative diagram of modules.

$ $ \begin{array}{ccccc} M \otimes_K L & \xrightarrow{} & \prod_{\sigma \in G} \Big( M \otimes_K L \Big) & \xrightarrow{} & \prod_{\sigma \in G} M\ \downarrow & & \downarrow & & \downarrow \ L \otimes_K M & \xrightarrow{} & \prod_{\sigma \in G} \Big( L\otimes_K M \Big) & \xrightarrow{} & \prod_{\sigma \in G} M^\sigma \end{array} $ $

where the left most vertical arrow is $ \phi$ and we denote by $ \psi$ the induced the right most vertical arrow.

Using Step 1 we have ring morphisms $ L \xrightarrow{1_L} L$ and $ L \xrightarrow{\sigma} L$ for each $ \sigma \in G$ . Tensoring $ M$ with these morphisms give $ L$ -module structures for $ M \otimes_K L$ by $ a \cdot ( m \otimes c ) = m \otimes ac$ and for $ L \otimes_{L,\sigma} M$ by $ a \cdot (c \otimes m) = \sigma(a)c \otimes m$ . Now the isomorphism of $ L$ -modules $ \mu: M \otimes_L L \to M: m \otimes c \mapsto cm$ then gives to $ M$ the $ L$ -module structure $ a \otimes m = am$ . We also have the composite diagram

$ $ L \otimes_{L,\sigma} M \xrightarrow{ \sigma^{-1} \otimes 1_M } L \otimes_L M \xrightarrow{\mu’} M : c \otimes m \mapsto \sigma^{-1}(c) \otimes m \mapsto \sigma^{-1}(c)m. $ $

Then this $ M$ has $ L$ -module structure given by $ a \cdot m := \sigma(a)m$ and we denote it by $ M^\sigma$ (We can relabel to get $ M^\sigma$ instead of $ M^{\sigma^{-1}}$ .).

Now a structure of $ \prod_{\sigma \in G} L$ -module on $ \prod_{\sigma \in G} M$ (resp. on $ \prod_{\sigma \in G} M^\sigma$ ) is determined by an $ L$ -module structure on $ M$ (resp. on $ M^\sigma$ ) for each $ \sigma \in G$ . Therefore, if $ (a_\sigma)_{\sigma \in G} \in \prod_{\sigma \in G}$ and $ (m_\sigma)_{\sigma \in G} \in \prod_{\sigma \in G} M$ (resp. in $ \prod_{\sigma \in G} M^\sigma$ ), then

$ $ (a_\sigma)_{\sigma \in G} \bullet (m_\sigma)_{\sigma \in G} = (~a_\sigma m_\sigma)_{\sigma \in G} ( \text{ resp. } (a_\sigma)_{\sigma \in G} \circ (m_\sigma)_{\sigma \in G} = ( \sigma(a)_\sigma m_\sigma)_{\sigma \in G}~). $ $

Step 3: Determine for each $ \sigma \in G$ the isomorphisms of $ L$ -modules $ \psi_\sigma$ .

The isomorphism $ \psi$ induced by $ \phi$ must then satisfy

$ $ \psi \big( a_\sigma m_\sigma)_{\sigma \in G} ) = (a_\sigma)_{\sigma \in G} \circ \psi( ( m_\sigma)_{\sigma \in G} ). $ $

For each $ \sigma \in G$ we have an isomorphism of $ L$ -modules

$ $ M \xrightarrow{\iota_\sigma} \prod_{\sigma \in G} M \xrightarrow{\psi} \prod_{\sigma \in G} M^\sigma \xrightarrow{\pi_\sigma} M^\sigma $ $

given by

$ $ am \mapsto (0, \cdots, 0, am, 0, \cdots, 0) \mapsto \big( \sigma(a) \pi_\sigma \Big( \psi( \iota_\sigma(m) \Big) \big)_{\sigma \in G} \mapsto \sigma(a)\pi_\sigma \Big( \psi(m) \Big). $ $

So for each $ \sigma \in G$ we have an isomorphism $ \psi_\sigma : M \to M^\sigma$ defined by $ \psi_\sigma(m):=\pi_\sigma( \psi(m) )$ and such that $ \psi_\sigma(am) = \sigma(a)\psi_\sigma(m)$ .

Step 4: Determine some $ \prod_{\sigma \in G} \prod_{\tau \in G} L$ -module structures

I will skip some details, which I can provide upon request. I use the cocycle condition to determine three $ \prod_{\sigma \in G} \prod_{\tau \in G} L$ -module structures.

Consider $ p_{12}^* p_1^* M$ (or equivalently $ p_{13}^*p_1^*M$ ).

The $ \prod_{(\sigma,\tau) \in G \times G } L$ -module $ \prod_{(\sigma,\tau) \in G \times G } M$ is

$ $ (a_{g,h}) \cdot ( m_{g,h} ) = ( a_{g,h} m_{g,h} ). $ $

Consider $ p_{12}^* p_2^* M$ (or equivalently $ p_{23}^*p_1^*M$ ).

The $ \prod_{(\sigma,\tau) \in G \times G } L$ -module $ \prod_{(\sigma,\tau) \in G \times G } M^\tau$ is

$ $ (a_{\sigma,\tau}) \cdot ( m_{\sigma,\tau} ) = ( \tau(a_{\sigma,\tau}) m_{\sigma,\tau} ). $ $

Consider $ p_{13}^* p_2^* M$ (or equivalently $ p_{23}^*p_2^*M$ ).

The $ \prod_{(\sigma,\tau) \in G \times G } L$ -module $ \prod_{(\sigma,\tau) \in G \times G } M^{\sigma \tau}$ is

$ $ (a_{\sigma,\tau}) \cdot ( m_{\sigma,\tau} ) = ( (\sigma \circ \tau)(a_{\sigma,\tau}) m_{\sigma,\tau} ). $ $

Step 5: Determine the cocycle condition

Finally, for each pair $ (\sigma, \tau) \in G \times G$ we have three composite maps given as follows:

$ $ M_{(\sigma, \tau)} \xrightarrow{ \iota_{(\sigma,\tau)}} \prod_{(\sigma,\tau) \in G \times G} M \xrightarrow{ p_{12}^* \psi } \prod_{(\sigma,\tau) \in G \times G} M^\tau \xrightarrow{ \pi_{\sigma,\tau}} M_{(\sigma, \tau)}^\tau $ $

defining an $ L$ -module isomorphism $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \tau } : M_{(\sigma,\tau)} \to M_{(\sigma,\tau)}^\tau$ satisfying

$ $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \tau }(am) = \tau(a)\psi_{ ( \sigma, \tau), (\sigma, \tau), \tau }(m) $ $

$ $ M_{(\sigma, \tau)} \xrightarrow{ \iota_{(\sigma,\tau)}} \prod_{(\sigma,\tau) \in G \times G} M \xrightarrow{ p_{13}^* \psi } \prod_{(\sigma,\tau) \in G \times G} M^{\sigma \tau} \xrightarrow{ \pi_{\sigma,\tau}} M_{(\sigma, \tau)}^{\sigma\tau} $ $

defining an $ L$ -module isomorphism $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \sigma \tau } : M_{(\sigma,\tau)} \to M_{(\sigma,\tau)}^{\sigma \tau}$ satisfying

$ $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \tau }(am) = (\sigma \circ \tau)(a)\psi_{ ( \sigma, \tau), (\sigma, \tau), \tau }(m) $ $


$ $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \tau }(am) = \tau(a)\psi_{ ( \sigma, \tau), (\sigma, \tau), \tau }(m) $ $

$ $ M_{(\sigma, \tau)}^\tau \xrightarrow{ \iota_{(\sigma,\tau)}} \prod_{(\sigma,\tau) \in G \times G} M^\tau \xrightarrow{ p_{23}^* \psi } \prod_{(\sigma,\tau) \in G \times G} M^{\sigma \tau} \xrightarrow{ \pi_{\sigma,\tau}} M_{(\sigma, \tau)}^{\sigma \tau} $ $

defining an $ L$ -module isomorphism $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \sigma } : M_{(\sigma,\tau)}^\tau \to M_{(\sigma,\tau)}^{\sigma \tau}$ satisfying

$ $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \sigma }(am) = \sigma(a)\psi_{ ( \sigma, \tau), (\sigma, \tau), \tau }(m). $ $

Indeed, $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \sigma }$ sends $ \tau(a)m$ to $ (\sigma \circ \tau)(a)m$ and so sends $ am = \tau(\tau^{-1}(a))m$ to $ \sigma( am )$ .

Since $ p_{23}^* \phi \circ p_{12}^*\phi = p_{13}^* \phi$ , we have $ p_{23}^* \psi \circ p_{12}^*\psi = p_{13}^* \psi$ and therefore for each pair $ (\sigma, \tau) \in G \times G$ we have

$ $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \sigma } \circ \psi_{ ( \sigma, \tau), (\sigma, \tau), \tau } = \psi_{ ( \sigma, \tau), (\sigma, \tau), \sigma \tau } $ $

as isomorphisms of $ L$ -modules.

Remarks: The map $ \psi_{ ( \sigma, \tau), (\sigma, \tau), \sigma }$ is from $ M^\tau$ to $ M^{\sigma \tau}$ and it is not clear to me how to re-express it as starting from $ M$ and twisting it by $ \tau$ . Another problem is that the maps I found on Step 3 are not in an obvious way related to those of Step 5 and there might be a need to twick something here as well.

Does weak Convergence in $H^1$ implies strong convergence in $H^1_0$?

I’m reading proof which begins with a statement that confuses me:

Prop: Let $ u \in H^1(\Omega)$ and suppose that $ $ \sup_{\partial \Omega} u = M = \inf \{m\in \mathbb{R} : u \leq m \text{ on } \partial \Omega \text{ in } H^1(\Omega)\} < \infty$ $ Then for any $ k \geq M$ , $ \max(u-k,0) \in H^1_0(\Omega)$ and $ \max(u-k,0)\geq 0$ on $ \Omega$ in the $ H^1$ sense (this means there’s a non-negative sequence of Lipsichtz continuous functions converging to $ \max(u-k,0)$ .)

The proof starts:

To show $ \max(u-k,0) \in H^1_0(\Omega)$ it suffices to prove the existance of a sequence $ v_n \in H^{1,\infty}_0(\Omega)$ (i.e. lipschitz continuous functions) such that $ $ v_n \rightharpoonup \max(u-k,0) \in H^1(\Omega)$ $

Why does it suffice to show weak convergence in $ H^1$ ?? Also why weak convergence in $ H^1$ not $ H^1_0$ ?

Conditions on matrices implies that 3 divides $n$

A quite popular exercise in linear algebra is the following (or very related exercises, see for example and

Let $ K$ be a field of characteristic different from 3 and $ X$ and $ Y$ two $ n\times n$ -matrices with $ X^2+Y^2+XY=0$ and $ XY-YX$ invertible. Then 3 divides $ n$ .

A proof can be given as in the answer of Mariano Suárez-Álvarez in .

Question: Is this also true for fields of characteristic 3?

Question about Jech’s proof of V = L implies GCH

On pg 190 of Jech’s Set Theory, he proves V = L implies GCH. I understand it all except the following:

Thus let X ⊂ $ ω_α$ . There exists a limit ordinal δ>$ ω_α$ such that X ∈ $ L_δ$ . Let M be an elementary submodel of $ L_δ$ such that $ ω_α$ ⊂ M and X ∈ M, and $ |M| = \aleph_{\alpha}$ .

I think this uses the Lowenheim Skolem theorem to get the model of size $ \aleph_{\alpha}$ , but why should $ \omega_{\alpha} \subset M$ and why should $ X \in M$ , or how do we construct such an M?

I know there are other proofs of this theorem which uses a version of the reflection principle which gives you this directly, but the version of the reflection principle I know is the more basic one which doesn’t deal with the cardinality of the sets for which the formulas are absolute (the beginning reflection theorems in Kunen).

Basically, I would prefer an explanation that uses the Lowenheim Skolem theorem instead. How is this done?

$G$ is a non-abelian group of order 6 $ \implies G \approx S_3 $. Simpler proof?

I’ve seen some proofs of this fact but they seemed more complicated than necessary, so I’ve tried to come up with my own, which is hopefully simpler. Can you kindly tell me if it’s correct?

Proof. $ G$ cannot have an element of order 6, else it would be cyclic and thus abelian. So the elements of $ G$ different from $ e$ can only have order 3 or 2. If all $ g \in G$ have order 2 then $ G$ is abelian, so there must be at least one element $ a \in G$ of order 3. The subgroup $ H= \langle a \rangle$ is normal in $ G$ because its index is 2. $ G/H$ is a cyclic group of order 2. Let $ b \not \in H$ . We have $ (bH)^2=H \implies b^2 \in H$ . If $ o(b)=3$ , then $ b=b^4=b^2b^2 \in H$ , a contradiction. So we must conclude that every $ g \in bH$ has order 2. Therefore $ G= H \cup bH = \{e, a, a^2, b, ba, ba^2 \}$ . Moreover, $ ab \in Hb$ so $ (ab)^2=e$ . Then $ ab=b^{-1}a^{-1}=ba^2$ , which is exactly the relation in $ S_3$ . $ \square$