TITLE: Understanding extension by definition
QUESTION [2 upvotes]: Definition of relation symbols
According to this wikipedia page https://en.wikipedia.org/wiki/Extension_by_definitions, an extension by definition is the following. Let $T$ be a first order theory and $\varphi(x_1,...,x_n)$ be a formula of $T$. We form a new first order theory $T'$ by adding a new $n$-ary relation symbol $R$ the logical axioms featuring $R$ and the axiom $$\forall x_1...\forall x_n( R(x_1,...x_n) \iff \varphi(x_1,...,x_n)).$$
Definition of function symbols
Let $T$ be a first order theory and $\phi(x_1,...,x_n)$ a formula of $T$ such that $y,x_1,...,x_n$ are distinct and include the variables free in $\phi(x_1,...,x_n)$. Assume that we can prove $$\forall x_1...\forall x_n \exists!y(\phi(y,x_1,...,x_n)$$ in $T$. Then we can form a new theory $T'$ from $T$ by adding a new $n$-ary function symbol $f$, the logical axioms of $f$ as well as the axiom $$\forall x_1...\forall x_n (\phi(f(x_1,...,x_n),x_1,...,x_n)).$$
As far as I understand it, the we have the following examples:
$(1)$ Consider two sets $X,Y$ as well as a function $f:X \to Y$. Then we know that for all $x \in X$ there exists exactly one $y \in Y$ such that $(x,y) \in f$. Hence we can introduce a new symbol $f(x)$ denoting this object $y$.
$(2)$ Consider two sets $A,B$. Then there exists exactly one set $X$ that satisfies $\forall x(x \in X \iff x \in A \wedge x \in B)$. We introduce a new symbol $A \cap B$ to denote this set.
Questions
$(i)$ Is the following also an example of definitional extension? Consider a function $F:X \times X \to X$  such that $X$ is a set whose elements are functions from $Y \to Z$, where $Y$ and $Z$ are sets such that the following is satisfied: For all $y \in Y$ and all $f,g \in X$ satisfying $f(y)=g(y)=z$ we have that $F(f,h)(y)=F(g,h)(y)$ and we thus define this object to be $F_z(h).$
$(ii)$ What exactly is the difference between relation and function symbols? What is an example for a "new" relation symbol?
$(iii)$ What does "the logical axioms of $f$" mean, as it is mentioned in the definition of function symbols?
$(iv)$ Why do the $y,x_1,...,x_n$ need to be distinct? What is even meant by distinct? Does this mean that they refer to distinct objects and if so, what would go wrong if they refer to the same object?

REPLY [1 votes]: Your examples are fine: in set theory we have only one "basic" binary predicate symbol: $\in$, and we introduce new symbols, like $\cap, \cup$, defining them in terms of $\in$.
A formal definition will be:

$C = A \cap B \leftrightarrow \forall x(x \in C \leftrightarrow (x \in A \land x \in B))$.

It will be a good definition provided that we prove that set $C$ exists and is unique.
To (ii) "What exactly is the difference between relation and function symbols? What is an example for a "new" relation symbol?"
A relation symbol expresses a relation between objects: $(x≤y)$ in arithmetic and "x is taller than y" in common world, while a function symbol "names" an object $(x+y), A \cap B$ and "the father of x".
Similarly to $\cap$, in the language of arithmetic usually there is no $\le$ symbol; we define it with: $(x≤y) ↔ ∃z(y=x+z)$.
To (iii), when we want to add a new symbol $f$ to a theory $T$, we "enlarge" the language of $T$ with the new symbol and we add the formula defining it as a new axiom. The resulting theory is $T′$.
About (iv), the basic fact is that if we want to add a new function symbol meaning $y=f(x)$ we have to find a suitable formula $\varphi(x,y)$ with $x$ and $y$ free that satisfies the "functionality condition": for every $x$ there is exactly one value of $y$ such that $\varphi(x,y)$ holds.


TITLE: Existence or non existence of uniformly convergent subsequence
QUESTION [0 upvotes]: Consider the sequence of functions defined from $[0,1]$ to $\mathbb{R}$, given by $$f_n(x) = \frac{2x^2}{x^2+(1-2nx)^2}~,\quad \text{where} ~~n=1,2,\dots$$
I could conclude that this sequence of functions converges pointwise to zero. But supremum of $|f_n - f|$, (here $f=0$) does not converge to zero, hence convergence is not uniform.
But I'm not able to conclude if there exist a subsequence that converges uniformly or not.  Any help would be appreciated.
Thanks in advance.

REPLY [1 votes]: The pointwise limit is  $f(0)=2, f(x)=0$ for $x \neq 0$. Every subsequence converges to the same limit. Since this limit is not continuous it follows that the convergence is not uniform.


TITLE: Eigenvalue and eigenvector $Av=λv$ , $A^{-1}v=\frac{1}{\lambda}v$
QUESTION [0 upvotes]: Suppose that $A$ is invertible, and $v$ is an eigenvector of $A$, corresponding to some
eigenvalue $λ \in \Bbb R$. Show that $v$ is an eigenvector of $A^{−1}$
, corresponding to the eigenvalue $µ = 1/λ$

REPLY [3 votes]: Once $A$ is invertible then $\lambda \ne 0$.
$$Av=\lambda v \Rightarrow A^{-1}(Av)=A^{-1}(\lambda v)\Rightarrow v=\lambda A^{-1}v \Rightarrow A^{-1}v=\frac{1}{\lambda}v$$

REPLY [0 votes]: Suppose that $v\neq 0$ and $Av=\lambda v$. Then,
$$
\frac{1}{\lambda}v=\frac{1}{\lambda}Iv=\frac{1}{\lambda}(A'A)v=\frac{1}{\lambda}A'(Av)=\frac{1}{\lambda}A'\lambda v=A'v.
$$
So $\lambda^{-1}$ is an eigenvalue of $A'$. But $A'$ and $A$ have the same eigenvalues (because $\det(I-\mu A)=\det[(I-\mu A)']=\det(I-\mu A')$ for all real $\mu$), and so $\lambda^{-1}$ is an eigenvalue of $A$.

Without the use of determinant: Suppose that $w\neq 0$ and $Aw=\lambda w$. We have
$$
\lambda^2||w||^2=(\lambda w)'(\lambda w)=(Aw)'(Aw)=w'A'Aw=w'(I)w=||w||^2.
$$
This implies $\lambda^2=1$ and so $\lambda=\pm 1$. In either case, $\lambda=\lambda^{-1}$ and so of course if $\lambda$ is an eigenvalue of $A$ then it's trivial that $\lambda^{-1}$ ($=\lambda$) is also an eigenvalue of $A$.


TITLE: Splitting fields and Galois extensions
QUESTION [5 upvotes]: Let $L/K$ be a field extension such that $L$ is a splitting field of $f\in K[X]$, i.e. $f=\prod_{i=1}^{k} (X-u_i)^{n_i}$ for some $u_i\in L$. If we denote the coefficients of $g:=\prod_{i=1}^{k} (X-u_i)$ with $v_0,\ldots,v_k$ is then
1) $L/K(v_0,\ldots,v_k)$ a Galois extension ?
2) Does $\text{Gal}(L/K(v_0,\ldots,v_k))=\text{Gal}(L/K) $ hold ?
I also have to show that $L$ is a splitting field of $g$, but this seems trivial, since $L$ contains the $u_i$'s, so if $f$ split, also $g$ has to split - or am I missing something here ?

REPLY [1 votes]: Let $E=K(v_1,\dots,v_k)$. The extension $L/E$ is normal, this follows because $L/K$ is normal. Now $L$ is the splitting field of $g$ over $E$. By definition $g$ has no repeated roots so is separable. So the extension is also separable and thereby Galois.
For the second part I assume that $\mathrm{Gal}(L/K)=\mathrm{Aut}(L/K)$.  One inclusion is clear so let $\varphi \in \mathrm{Gal}(L/K)$ and we wish to show that $\varphi$ fixes $E$. This follows from observing that $\varphi$ acts on the roots $u_1,\dots,u_k$ and $E$ is generated by the symmetric polynomials in $u_1,\dots,u_k$ so the generators of $E$ are fixed by $\varphi$. Thereby $\varphi \in \mathrm{Gal}(L/E)$.


TITLE: Counting total number of arrangements
QUESTION [1 upvotes]: Count the total number of arrangements of a,b,c,d,e,f such that
(a) a and b are side-by-side
(b) a occurring somewhere before b
For part (a), I know the answer is represented by $4!\times 10$ but I don't know the logic behind it, if someone could explain that it would be great.
For part (b), The a will occur before the b in half the cases so I can just say the following if I'm not wrong here.
$$6! \times \frac 1 2$$
Edit: something occured to me about part (a). If a and b had to appear in the order ab then it would just count as one element and the answer would be $5!$ but since a and b can also appear as ba it would just be $2 \times 5!$ which evaluates to the same thing as $4! \times 10$. Lemme know if my thinking is wrong here.

REPLY [1 votes]: For the first part consider $a,b$ together as an element. Then there are $5$ elements and the total number of arrangements of $5$ elements is $5!$ and we can write $a,b$ together in $2$ ways, $a,b$ or $b,a$. So total number is $5! \times2.$
For part b your logic is right.

REPLY [0 votes]: For a) consider {a,b} as one element. Thus, you now have effectively 5 elements: {a,b}, c, d, e, f. How many permutations of them are possible? (For instance, a possible permutation would be c{a,b}dfe). Now, pick an ordering between a and b; how many are possible now? (Edit: your thinking is right)
b) Like you said, half the arrangements will have a before b, so it is valid.

REPLY [0 votes]: For part $(b)$, you are definitely right.
For part $(a)$, stick $a$ and $b$ together and consider it as one element. Then there are $5!$ ways to arrange $ab,c,d,e,f$. And don't forget that $a$ and $b$ can switch places so there are $2\cdot5!$ such arrangements.
Edit: Now, in both parts, your answer and methodology are correct. Well done :)


TITLE: Every $L_q$ function as a product of $L_p$ and $L_r$ functions
QUESTION [0 upvotes]: Let $(X, \alpha, \mu)$ be a finite measure space. In the context of a measure theory course, I heard that every function $f \in L_q(\mu)$ can be written as a product of functions $g \in L_p(\mu)$ and $h \in L_s(\mu)$ where $$\frac{1}{q} = \frac{1}{p} + \frac{1}{s}$$ holds. I thought about how to prove that but all I know is how to estimate various inclusions, i.e. $L_q(\mu) \subseteq L_p(\mu)$, for $1\leq p < q \leq \infty $ in the case of $\mu(X) < \infty$. What is the idea here?

REPLY [1 votes]: The idea is that $|f|^q=|f|^{\frac{ps}{s+p}}$. Therefore one can define $g=f|f|^{\frac{s}{s+p}−1}$ and $h=|f|^{\frac{p}{s+p}}$. They belong respectively to $L_p$ and $L_s$ and their product is $f$.
We can also observe that the hypotesis of $X$ having finite measure was not used.


text:
section \<open>CFG and semantics conform\<close>

theory SemanticsCFG imports CFG begin

locale CFG_semantics_wf = CFG sourcenode targetnode kind valid_edge Entry
  for sourcenode :: "'edge \<Rightarrow> 'node" and targetnode :: "'edge \<Rightarrow> 'node"
  and kind :: "'edge \<Rightarrow> 'state edge_kind" and valid_edge :: "'edge \<Rightarrow> bool"
  and Entry :: "'node" ("'('_Entry'_')") +
  fixes sem::"'com \<Rightarrow> 'state \<Rightarrow> 'com \<Rightarrow> 'state \<Rightarrow> bool"
    ("((1\<langle>_,/_\<rangle>) \<Rightarrow>/ (1\<langle>_,/_\<rangle>))" [0,0,0,0] 81)
  fixes identifies::"'node \<Rightarrow> 'com \<Rightarrow> bool" ("_ \<triangleq> _" [51,0] 80)
  assumes fundamental_property:
    "\<lbrakk>n \<triangleq> c; \<langle>c,s\<rangle> \<Rightarrow> \<langle>c',s'\<rangle>\<rbrakk> \<Longrightarrow>
      \<exists>n' as. n -as\<rightarrow>* n' \<and> transfers (kinds as) s = s' \<and> preds (kinds as) s \<and>
               n' \<triangleq> c'"

end

subset_name: curated


TITLE: Is an alternating sequence never divergent?
QUESTION [0 upvotes]: My question:
lets say the sequence $\{a_n\}_{n \in \mathbb{N}}$ is alternating and not against $0$, to avoid the Leibniz criterion.
Is that said sequence always divergent then?

REPLY [3 votes]: Do you mean:

Suppose $a_n \geq 0$, and $a_n \not \rightarrow 0$. Is is true that the series $\Sigma _{n=1}^\infty (-1)^n a_n$ diverges?

Then the answer is that the series can't possibly converge to a real number, because the terms of a convergent series always converge to zero. No conclusion can be made about if it diverges to $\pm \infty$ or just doesn't converge at all.


TITLE: How should I interpret constraint $x^T u_1=0$ in a quadratic function optimization?
QUESTION [1 upvotes]: In a linear algebra book, the following is stated with proof shown, so I get it.

Let A be a symmetric matrix and so $x^TAx$ the quadratic form of a quadratic function. Arrange the eigenvalues such that $\lambda_1 > \lambda_2...>\lambda_n$.
Then Max is the largest eigenvalue, $\lambda_1$, of A and Min is the smallest eigenvalue, $\lambda_n$, of A.
Max is attained when x is a unit eigenvector $u_1$ corresponding to Max.
Min is attained when x is a unit eigenvector $u_n$ corresponding to Min.

Then it states the following without proof and interpretation discussion:

The Max of $x^TAx$ subject to constraints:
$x^Tx=1, x^Tu_1=0$
is the second largest eigenvalue $\lambda_2$ and this Max is attained when x is a unit eigenvector,$u_2$, corresponding to $\lambda_2$.

Question: How should I interpret the constraint $x^Tu_i=0$?
I see that when $A$ in $x^TAx$ is originally diagonal, $x^Tu_i=0$ says $x_i=0$ so $x^Tu_1=0$ says $x_1=0 \rightarrow \lambda_1$ unattainnable and go hunt for the next largest, which is $\lambda_2$.
How about when A is any general symmetric matrix and not neccesarily diagonal?
By having $x^Tu_1=0$, it says $x$ must be orthogonal to $u_1$, so $x\neq u_1 \rightarrow x^TAx \neq\lambda_1$. When $\lambda$ are ranked $\lambda_1 > \lambda_2...$ , constraint $x^Tu_1=0$ seems to suggest 2nd largest value. So if we want the 4th largest, then we add $x^Tu_i=0$ for $i=[1,3]$ which restricts $x$ to be in the subspace orthogonal to those $u_i$? Is that how the constraint should be interpreted?

REPLY [1 votes]: The essential fact is that the matrix $A$ is diagonal w.r.t. the basis $\{u_1,\ldots,u_n\}$. I'll give a sketch of how to see this, and how to use this to prove the claims in your text.
Fact 1: If $A$ is a symmetric matrix with two distinct eigenvalues $\lambda_1$ and $\lambda_2$, then any pair of corresponding eigenvectors $u_1$ and $u_2$ is perpendicular.
If you are not familiar with this fact, then it is a nice exercise to prove it.
Fact 2: If $A$ is an $n\times n$-matrix with distinct eigenvalues $\lambda_1>\lambda_2>\ldots>\lambda_n$, then there is an orthonormal basis of eigenvectors of $A$.
Proof. For each $i$ let $u_i$ be a unit eigenvector for the eigenvalue $\lambda_i$. By Fact 1 the $u_i$ are pairwise perpendicular, and because we have $n$ distinct eigenvalues, together they form a basis.
With respect to this basis the matrix $A$ is diagonal, with the eigenvalues on the diagonal. Explicitly:
$$A=\begin{bmatrix}
\lambda_1&0&\cdots&0\\
0&\lambda_2&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&\lambda_n
\end{bmatrix}.$$
Fact 3: For a unit vector $x$, the maximum of $x^{\top}Ax$ is $\lambda_1$ and it is attained if $x$ is a unit eigenvector of $\lambda_1$.
As you say this was already shown and you understand it, I won't show this.
The constraint $x^{\top}u_1=0$ restricts $x$ to the subspace perpendicular to $u_1$, i.e. to the subspace spanned by $\{u_2,\ldots,u_n\}$. On this subspace, with respect to this basis, we have
$$A'=\begin{bmatrix}
\lambda_2&0&\cdots&0\\
0&\lambda_3&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&\lambda_n
\end{bmatrix}.$$
Now we can use Fact 3 again; the maximum of $x^{\top}Ax$ is $\lambda_2$ and it is attained if $x$ is a unit eigenvector of $\lambda_2$.
And indeed as you conjecture, repeating this process yields the third largest, fourth largest, fifth largest, etc. eigenvalues. Simply add the constraint $x^{\top}u_2=0$, $x^{\top}u_3=0$, $x^{\top}u_4=0$, etc.


TITLE: Does Gravity Depend on Spatial Dimension?
QUESTION [3 upvotes]: Consider a line containing two point masses, $m$ and $M$. The line is a $1D$ space.
What's the gravitational force between the two masses?
Newton's formula for the gravitational force $F$ between two masses $m$ and $M$ in 3D space is
$$F=\frac{G M m}{r^2}$$
where $G$ is a constant and $r$ is the distance between the two masses.
The $r$ term is good in a $3D$ space, but in general it's $r^{n-1}$ where $n$ is the dimension of the space. So putting $n=1$ for $1D$ space we get
$$r^{1-1}=r^0=1 \Rightarrow F=GMm \, ,$$
Which means $F$ is independent of distance. Gravity has the same strength no matter how far apart the two objects are!
Of course, this calculation uses Newton's theory of gravity. Perhaps General Relativity would give a different result.

REPLY [0 votes]: Yes, it depends on the spatial dimensions, as discussed above. This has implications for the physical theories that claim that spacetime is higher dimensional than 4 (and space more than 3). This is to tell you something about the consequences and implications of higher dimensions for gravity.
In fact, for n (spatial) dimensions the force would decrease as $1/r^{n-1}$, with r the distance, as noted in the answer by @ccc. No problem. But that also indicates that as r becomes smaller, the force of gravity can be stronger, at least relatively speaking. Simplistically, if you take $F = k/r^{n-1}$, for two given masses, then we have, for n = 3, n= 4, and n = 10 respectively (and doing it in arbitrary units),
*FOR n=3

For n=3 and r= 1 you get F = k
For n=3 and r= 2 you get F= k/4
For n=3 and r = 1/2 you get F = 4k

*FOR n=4
-For n=4 and r= 1 you get F = k
-For n=4 and r = 2 you get F = k/8
-For n=4 and r = 1/2 you get F= 8k
*FOR n=10
-For n=10 and r=1 you get F = k
-For n=10 and r = 2 you get F= k/1024
-For n= 10 and r = 1/2 you get F = 1024k
So, as the dimensions get to be more, the force of gravity "dilutes" over all the dimensions as you increase distance, whereas at smaller distances you can get a relatively stronger effect. Gravity has been measured down to about a millimeter and this effect has not been observed.
This tends to be similarly true, also for General Relativity, although it is not about forces then but curvature, and the numerical answers are not as simple. But the concept generally holds. Dimensions also make a difference in String Theory.
However, it turns out, see below, that those extra dimensions (besides our 3 known spatial dimensions) cannot be too small (String Theory in some versions claims those extra dimensions are very small, Planck sized)  -- in fact at least one or two have to be large dimensions if gravity is to be diluted by them. Meaning, they need to encompass non-microscopic sizes. How much?
From http://www.eurekalert.org/features/doe/2001-10/dbnl-gil053102.php:   "How big would extra dimensions have to be? For gravity to equal the other forces at a hundred-thousandth of a trillionth of an inch (the electroweak scale), one extra dimension would have to be as big as the distance between the Earth and the sun. Two extra dimensions need extend only about a millimeter, however, and the more extra dimensions there are, the smaller they can be".
Now, CAREFUL, for even in those higher dimensional theories -- WHICH BY THE WAY HAVE NOT BEEN PROVED IN ANY WAY, AND NO EXTRA DIMENSIONS HAVE BEEN FOUND -- whether it works the way I described or not depends on a) whether those extra dimensions, besides our known 3 dimensions, are small or large, and b) whether gravity is constrained to only propagate in 3D (called a 3D brane in String Theory), or propagate in all 10 dimensions.
String and Superstring theory (really, M-theory, see https://en.wikipedia.org/wiki/M-theory, and https://en.wikipedia.org/wiki/String_theory#Extra_dimensions), require a minimum of 10 spatial dimensions. If those, or some of those are big dimensions, then the weakness of gravity might be explained, and then if we then look at smaller and smaller distances, gravity is (relatively) stronger. It is also one reason there are attempts to measure the strength of gravity at smaller and smaller distances -- to see if it does not go as $1/r^2$. So far, as I said above, it's only been down to about 1 millimeter, and nothing strange has been found.
String Theory mostly has it (because the strings that cause gravity were thought to be able to extend in all dimensions, whereas normal forces like nuclear and electromagnetism strings are constrained to move in our 3D brane) that gravity propagates in the 10 spatial dimensions. String Theory also assumed that the other dimensions are small, microscopic and we can't see them. Then you need to calculate how much it dilutes gravity.  But some String Theory developments assume 1 or more large extra dimensions, and then it dilutes (and gets relatively stronger in the much smaller domain).
You really need a quantum gravity theory to determine any of it, and dimensions and their sizes makes a difference. String Theories remain possibilities, but have lost some luster because the majority of them depend on supersymmetry being true, but there has not been any superparticle found at the LHC, so far. Still, there remains both a theoretical and experimental interest in the higher dimensions.