User zzzhhh - MathOverflow

A question about the size of a L1 ball

2013-03-03T04:37:31Z

I met with a problem when I am reading a paper "On the Redundancy of Slepian-Wolf Coding" by He, DK; Lastras-Montano, LA; Yang, EH; Jagmohan, A; Chen, J, IEEE TRANSACTIONS ON INFORMATION THEORY, ISSN 0018-9448, 12/2009, Volume 55, Issue 12, pp. 5607 - 5627. The image below is an excerption of the paper where I have a question.

Here the term "type" just means pmf on $\mathcal{X}\times\mathcal{Y}$ with each entry having denominater $n$. We can think of it as a result produced by the following process: assume I have $n$ coins and want to place them on a chessboard having $|\mathcal{X}|\times|\mathcal{Y}|$ squares. After placing the coins, each square of the chessboard has $0..n$ coins and the sum of numbers of coin(s) in all squares is $n$. the type is defined to be a sequence(or matrix) of size $|\mathcal{X}|\times|\mathcal{Y}|$ with each element being the number of coins in the corresponding square devided by $n$. We can see that type is actually a pmf on $\mathcal{X}\times\mathcal{Y}$ but the denominator of each probability is $n$ (if not reduced). All of the types on $\mathcal{X}\times\mathcal{Y}$ is denoted as $\mathcal{T}_n(\mathcal{X}\times\mathcal{Y})$.

In the paper, $s$ and $s^*$ are all types on $\mathcal{X}\times\mathcal{Y}$. $s^*$ is a given fixed type; we can consider it as a constant. $s_\mathcal{X}$ means the marginal pmf on $\mathcal{X}$ (recall that $s$ is a pmf). It is required that $s_\mathcal{X}$ is a given fixed $t$. $s^*_\mathcal{X}$ is also required by the lemma mentioned to be $t$. $\kappa$ is an arbitrary positive real number. $\tau(x^n,y^n)$ is the type of the joint sequence $(x^n,y^n)$. $\|\cdot\|_1$ is the L1 norm, i.e., sum of absolute values.

My question is: How the formula (C2) comes out? Although the paper gives a hint regarding degree of freedom of movement and step size $1/n$, but I still could not understand. Thank you for any help!

Answer by zzzhhh for A question about the size of a L1 ball

2013-03-26T16:47:42Z

Since I can not find the check sign to accept an answer, I hereby declare that I accept domotorp's answer to my question, and sincerely express my appreciation to him for taking time and effort on my question. In addition, I would like to ask the administrator to help me accept domotorp's answer and in turn transfer the 200 bounty to him. Thank you.

Answer by zzzhhh for equivalence of 1-norm and relative entropy?

2013-01-27T07:08:03Z

I have found a solution, but it seems not complete (will explain at the end)

$D(p\|q)=|D(p\|q)|=|\sum p_i\log p_i-\sum p_i\log q_i|=|\sum p_i\log p_i-\sum p_i\log q_i+\sum q_i\log q_i-\sum q_i\log q_i|$ $=|H(q)-H(p)+\sum(q_i-p_i)\log q_i|\le|H(q)-H(p)|+\sum|q_i-p_i||\log q_i|$. If we denote $M_1=\max\lbrace|\log q_i|=\log\frac{1}{q_i}\rbrace$, the last equation will be $\le M_2\|p-q\|_1+M_1\|p-q\|_1=M\|p-q\|_1$ where $M=M_1+M_2$. Here I claimed that $|H(q)-H(p)|\le M_2\|p-q\|_1$ for some positive number $M_2$ due to the Mean Value Theorem extended to multi-dimensional space and concavity of entropy wrt pmf. This seems true but I am not very sure. That's why I think the proof is incomplete. Could anyone please justify this inequality (it's better to point out such a proposition in some textbook)? Thank you!

equivalence of 1-norm and relative entropy?

2013-01-27T04:37:56Z

For two pmf $p=\lbrace p_i\rbrace$ and $q=\lbrace q_i\rbrace$ on the same finite alphabet, we know that relateive entropy $D(p\|q)=\sum p_i\log\frac{p_i}{q_i}$ and 1-norm $\|p-q\|_1=\sum |p_i-q_i|$ are both measures of their distance. But it is unfortunate that relative entropy is not a norm. My question is: even so, do we still have equivalence between these two measure of distance? To be specific, assume $\|p-q\|_1\le C$ for some positive constant $C$, do we have $D(p\|q)\le MC$ for some positive $M$? If have, how to prove? Thanks a lot!

The sets in mathematical logic

2011-04-24T08:57:46Z

It is well known that intuitive set theory (or naive set theory) is characterized by having paradoxes, e.g. Russell's paradox, Cantor's paradox, etc. To avoid these and any other discovered or undiscovered potential paradoxes, the ZFC axioms impose constraints on the existense of a set. But ZFC set theory is build on mathematical logic, i.e., first-order language. For example, the axiom of extensionality is the wff $\forall A B(\forall x(x\in A\leftrightarrow x\in B)\rightarrow A=B)$. But mathematical logic also uses the concept of sets, e.g. the set of alphabet, the set of variables, the set of formulas, the set of terms, as well as functions and relations that are in essence sets. However, I found these sets are used freely without worrying about the existence or paradoxes that occur in intuitive set theory. That is to say, mathematical logic is using intuitive set theory. So, is there any paradox in mathematical logic? If no, why not? and by what reasoning can we exclude this possibility? This reasoning should not be ZFC (or any other analogue) and should lie beyond current mathematical logic because otherwise, ZFC depends on mathematical logic while mathematical logic depends on ZFC, constituting a circle reasoning. If yes, what we should do? since we cannot tolerate paradoxes in the intuitive set theory, neither should we tolerate paradoxes in mathematical logic, which is considered as the very foundation of the whole mathematics. Of course we have the third answer: We do not know yes or no, until one day a genius found a paradox in the intuitive set theory used at will in mathematical logic and then the entire edifice of math collapse. This problem puzzled me for a long time, and I will appreciate any answer that can dissipate my apprehension, Thanks!

what method can I employ to solve this optimization problem which involves \min?

2012-07-04T08:17:08Z

The optimization problem is:

maximize $$\min(\sum\limits_{i=1}^N \log\left(a_{1,i}+\frac{b_{1,i}}{c_{1,i}+d_{1,i}x_i}\right),\sum\limits_{i=1}^N \log\left(a_{2,i}+\frac{b_{2,i}}{c_{2,i}+d_{2,i}x_i}\right))$$ subject to $x_i\ge0, i=1,...,N$ and $\sum\limits_{i=1}^N x_i=C$, where $x_i$ are variables, $a_{1,i}, b_{1,i}, c_{1,i}, d_{1,i}, a_{2,i}, b_{2,i}, c_{2,i}, d_{2,i}$ and $C$ are constants.

Kuhn–Tucker conditions can only optimize one $\sum$ alone. but I don't know how to handle optimization problem involving $\min$ operation as above. Could you please tell me what method can I employ to solve it (I would greatly appreciate if you can refer me to a textbook containing exposition of the method)? Thank you very much!

Ask for recommendations for textbook on mathematical logic

2011-04-15T12:54:05Z

I studied mathematical logic using a book not written in English. I would now like to study it again using a textbook in English. But I hope I can read a text that is similar to the one I used before, so I ask here for recommendations. Any recommendation will be appreciated. The characters of the mathematical logic book I used before is as follows:

1, Formal.

Everything is formal, introduced from very beginning, such as (I'm not clear if my expression is correct in English, that's why I need an English book to remedy this deficiency) basic bricks of mathematical logic (symbol, formulas, predicate word, logic word, constrained variable, etc.), the formation rules of propositional/predicate logic (how well-formed formula is constructed recursively), differnt systems of propositional/predicate logic such as P, P*. F, F* and their relation, formal reasoning rules in these systems(e.g., in P, there are five formal reasoning rules: $(\in),(\tau),(\neg),(\to_-) and (\to_+)$).

2, comprehensive

In addition to the conceptions in 1, It introduces also Sheffer vertical, function word and equality word. calculus of propositional/predicate logic including replacement of equal formula, the replacement theorem, normal forms, Skolem normal forms, Gentzen normal forms, non-embedding normal forms, reduction of logic calculus. Reliability. Assignment. Completeness of propositional/predicate (with equality word) logic. Compactness theorem and Lowenheim-Skolem theorem. Independency.

3, many examples

in this book, there are many examples of calculus of propositional/predicate logic using the formal reasoning rules of a specified system. It also introduces actual formal mathematical systems such as elementary algebra, natural numbers, definition of formal symbols, etc. It used a "diagonal" form of proof to prove things.

I hope to have a book in English similar to this one, that is, possesses these charactors. Could you please recommendate one? It would be better if the recommendated textbook can also contain some motivations and some modern things(the book I read was written 30 years ago). Thanks!

A question about regular signed or complex Borel measure under LRN decomposition

2011-03-20T09:13:07Z

Suppose $\nu$ is a regular signed or complex Borel measure on $\mathbb R^n$, m is the Lebesgue measure on the class of Borel sets $\mathcal B_{\mathbb R^n}$ and the Lebesgue-Radon-Nikodym decomposition of $\nu$ is $d\nu=d\lambda+fdm$ where f is an extended m-integrable function when $\nu$ is a signed measure or $\in L^1(m)$ when $\nu$ is a complex measure and $\lambda\bot m$. Prove that $d|\nu|=d|\lambda|+|f|dm$ where the notation $|\bullet|$ represents total variation.

PS: A Borel measure $\nu$ on $\mathbb R^n$ is regular if $\nu(K)<\infty$ for every compact K. From this definition we have $\nu(E)=\inf \{\nu(U)|U{\;\rm{ open},}U\supseteq E\}$. A signed or complex Borel measure on $\mathbb R^n$ is regular if $|\nu|$ is regular.

Thanks!

Is total variation continuous?

2011-02-19T07:44:41Z

Given a sequence of signed measures $<\nu_j>$, if it happens that $\nu=\sum\limits_{j = 1}^\infty \nu_j$ is still a valid signed measure (then it can be proved that each partial sum $\nu_n=\sum\limits_{j = 1}^n \nu_j$ is valid signed measure), do we have $\lim\limits_{n\to \infty}|\sum\limits_{j = 1}^n \nu_j|=|\sum\limits_{j = 1}^\infty \nu_j|$ ($=|\lim\limits_{n\to \infty} \sum\limits_{j = 1}^n \nu_j|$)? Thanks!

A question in a proof on approximating n-dimensional Lebesgue measurable set by open set

2010-12-27T09:43:56Z

In Folland's "real_analysis: modern techniques and their applications", second edition, page 70, line 4 of proof of Theorem 2.40 (a), the author asserts the inequality $m(U_j) < m(T_j)+\epsilon2^{-j}$. I think this comes from $m(i$-th side of $U_j)\leq m(i$-th side of $T_j)+$a small number, $i=1,...,n$, by Theorem 1.18. But I find if one of the sides of $T_j$ (assume $T_{j_1}$) has measure 0 and another side (assume $T_{j_2}$) has measure $+\infty$, $m(T_j)$ would still be 0 by the convention $0\cdot\infty=0$, but on the other hand the measure of the side $U_{j_1}$ coresponding to the null side may be nonzero since the elements can be all nonzero even if the infimum is 0, and the side $U_{j_2}$ corresponding to the infinite side satisfies $m(U_{j_2})=\infty$, thus $m(U_j)$ would be $\infty$, then the inequality can never hold. I can not amend this problem by, say, simply discarding this special kind of rectangles. This conclusion is right, but so far as I am concerned, it was established by a rather complicated process, as in Bartle's "The Elements of Integration and Lebesgue Measure"([B]) for example, first build up from cells ([B]P132,Definition 12.1), then reduce from general cells to open cells([B]P133, Remarks 12.2(b)), then prove that this construction is identical to the product measure approach as Folland ([B]P149 Lemma 14.1 and uniqueness of extension) and finally prove it using the similar method([B]P155-156 Lemma 15.1(a)). So my question is, 1)if it is an error? 2)if it is, how to amend it? do we have to use the complicated process mentioned above? Thanks! The following image is a snapshot of the proof, there are a few typoes in it: the "$R_j$" and "$F_j$" in line 3 and 4, respectly, are actually "$T_j$".

A question on the cardinality of sigma-algebra generated by aleph_0 or aleph_1 class

2010-09-23T12:25:31Z

This question comes from notes to section 1.2 in page 40-41 of Folland's "real analysis: modern techniques and their applications", 2nd edition. At the end of this note, the author asserts that card(M(E))=c, i.e., aleph_1, if E has cardinality aleph_0 or aleph_1, using Proposition 0.14. But in order for Proposition 0.14 to be applicable, each E_alpha in Proposition 1.23 must has cardinality less than or equal to aleph_1. I don't know how to obtain it from its construction. could you please help me with this problem? Thanks! This part of note is pasted below, together with Proposition 0.14.

terminology about ring/algebra in abstract algebra and measure theory

2010-04-27T04:08:06Z

Both in abstract algebra and measure theory is there term ring/algebra, but their definition are different and we can not deduce one from the other, the only requirement in definition they share is that they be closed under two operations: addition and multiplication in abstract algebra while difference and union in measure theory. Why we use the same term for these two different notions in two different branches of mathematics? Is there any connection between them? Thanks!

To be more specific, my intention is to compare "ring in measure theory" with "ring in abstract algebra", not "ring" with "algebra". I use notation "ring/algebra" in the post because the term algebra has the same situation, that is, compare "algebra in measure theory" with "algebra in abstract algebra".

A problem regarding definition of p-norm

2010-06-04T01:24:03Z

Let ${\bf x}=(x_1,...,x_n)$, the p-norm of x is $(|x_1|^p+...+|x_n|^p)^{1/p}$. If one of the components of x is 0, there will be exponential of the form $0^p$. If p is an irrational, $x^p$ is only definable for x>0 (see e.g. page 181 of baby Rudin), that is, $0^p$ is not defined. So how do we handle this problem when working with p-norm? Assume that p does not take irrational value, or prescribe that $0^p$ means 0 when it occurs? Thanks!

two questions about Theorem 22.E in Halmos' "Measure Theory"

2010-05-20T09:57:03Z

This theorem can be found here: Th 22.E

Question 1): I think "fundamental a.e." in the second line of the proof should be "converges a.e.", because I can not derive from almost uniformly Cauchy to Cauchy a.e.. Am I right?

Question 2) Since $f_{n_k}(x)$ is not necessarily convergent for all x, the f defined in the 3rd line may not definable on the whole X and therefore can not be used in the definition of convergence in measure. I think we should extend its definition as follows: if $\lim\limits_{k \to \infty } f_{n_k}(x)$ exists, then f (x)=this limit as the text indicates, otherwise, f (x)=0. I can prove that this f (x) defined on the whole X is measurable, so we can apply Theorem 22.B to obtain that $f_{n_k}$ converges in measure to this f. Am I right? The definition of convergence in measure in Halmos' book is here: link text

Thanks!

questions from Halmos' "Measure Theory"

2010-05-11T01:52:58Z

These questions comes from theorem 19.C, page 81-82, in Halmos' "Measure Theory", as the image below shows.

Question 1): The 4th line of the proof says "we restrict our attention to finite valued functions" and the proof is carried out for finite f and g. Why can we "restrict our attention to finite valued functions"? How to extend the conclusion from finite case to extended real valued case?

Question 2): measurable functions, by definition in page 76-77, are defined on the whole X. But it is possible that f + g has no definition at some point x of X, e.g. $f(x)=+\infty$ but $g(x)=-\infty$. The product fg has the same situation. Of course we can assume in advance that f + g must be defined on the whole X in order for the theorem to hold, but violation of such an assumption occurs immediately: in the equation in the last line of the proof, $fg=[(f+g)^2-(f-g)^2]/4$, even if we assume f + g is defined on the whole X, we cannot guarantee that f - g and $(f+g)^2-(f-g)^2$ is meaningful for all x in X; in the paragraph that follows the proof, $f^+=f\cup 0=(f+|f|)/2$, if $f(x)=-\infty$ for some x, we cannot apply the theorem to obtain the measurability of (f+|f|)/2 and in turn of $f^+$ because f+|f| is not definable on whole X. So we have to allow that f + g (and fg) has domain smaller than X, but this violates the definition of measurable function in page 76-77. What, then, does the conclusion of the theorem "so also are f + g and fg" mean exactly on earth? and how to apply it to $fg=[(f+g)^2-(f-g)^2]/4$ and $f^+=(f+|f|)/2$?

Thanks!

Answer by zzzhhh for questions from Halmos' "Measure Theory"

2010-05-11T09:20:31Z

too long to be a comment, so I have to post it as an answer.

@Arturo Magidin: Do you mean: by "throw away" points where f and g are not defined or take infinite value, we do not need to abide by the requirement in the definition of measurable function in page 76-77 of this book that the domain of f be the whole X? We only need to grasp the essential idea that $N(f)\cap f^{-1}(M)$ is measurable for all extended Borel set M, that is, in particular, $f^{-1}(\{+\infty\}), f^{-1}(\{-\infty\})$ and $N(f)\cap f^{-1}(M)=f^{-1}(M-\{0\})$ is measurable for all real Borel set M, without caring if f + g and fg are definable on whole X. I think this is what I should learn from this theorem. So, denoting $F=[(f+g)^2-(f-g)^2]/4$ from the last line of the proof or (f+|f|)/2 for $f^+$, after checking inverse images of $\{+\infty\}$ and $\{-\infty\}$ , since for any real subset E we have $(fg)^{-1}(E)$ or $(f^+)^{-1}(E)=F^{-1}(E)$ which lie in the subset of X where both f (x) and g (x) are defined and finite (note this subset is contained in the actual domain of F which may be smaller than X), we have $(fg)^{-1}(M-\{0\})$ and $(f^+)^{-1}(M-\{0\})=F^{-1}(M-\{0\})$ are measurable. For product fg, this is what we want, although fg is not necessarily definable for the whole X. For $f^+$, this completes the proof that $f^+$ is a measurable function. Then my second question is therefore answered. Is the above words what your reply intended and correct, Prof Magidin?

PS: Note that $(f+g)^{-1}(\{+\infty\})=[f^{-1}(\{+\infty\})\cap g^{-1}((-\infty,+\infty])]\cup[g^{-1}(\{+\infty\})\cap f^{-1}((-\infty,+\infty])]$ which is measurable by the 3rd paragraph in page 77. We also need to prove that $N(f+g)=[N(f)\cup N(g)]-C$ where $C=\{x|f(x)=-g(x)\}$ is measurable to apply Theorem 19.A. Because $C\subseteq N(f)\cup N(g)$, so $C=[N(f)\cup N(g)]\cap C$ which is measurable by Theorem 19.A, so N (f + g) is measurable. Note that C may contain (all) points that f + g is not meaningful.

Answer by zzzhhh for what is the associated Borel set of a Borel measurable function on the extended real line?

2010-05-08T11:18:32Z

Two definitions of the extended Borel set:

Top-down: The class of extended Borel sets (extended Borel algebra) is the $\sigma$-ring generated by the class of all open sets of the extended real number system $\mathbb R^*$.

Bottom-up: Let B be the class of all real Borel sets (Borel algebra); then the class of extended Borel sets is the union of B with classes of the form ${\bf E}_1=\{E\cup\{+\infty\}|E\in\bf B\}, E_2=\{E\cup\{-\infty\}|E\in\bf B\}$ and ${\bf E}_3=\{E\cup\{+\infty,-\infty\}|E\in\bf B\}$ .

These two definitions are equivalent.

Proof: Let $\bf U^*$ denotes the class of all open sets of the extended real number system $\mathbb R^*$ , $\bf S(U^*)$ the $\sigma$-ring generated by $\bf U^*$ and $\bf S^*=B\cup E_1\cup E_2\cup E_3$ as in the Bottom-up definition; we propose to prove $\bf S(U^*)=S^*$ . The basis of $\mathbb R^*$ in order topology consists of nonempty bounded open intervals $(a,b), [-\infty,a)=(-\infty,a)\cup\{-\infty\}$ and $(a,+\infty]=(a,+\infty)\cup\{+\infty\}$ [1], so any open sets in $\mathbb R^*$ , as an arbitrary union of these basis elements, has a form of a union of an open set in $\mathbb R$ with possibly $\{+\infty\}$ or $\{-\infty\}$ or $\{+\infty,-\infty\}$ . Since any real open set is a real Borel set, $\bf S^*$ contains $\bf U^*$ . It is clear $\bf S^*$ is a $\sigma$-ring (actually a $\sigma$-algebra), so we get $\bf S^*\supseteq S(U^*)$ .

Since every real open set is also open in $\mathbb R^*$ , we have $\bf U\subseteq U^*$ where U is the class of all real open sets, and in turn $\bf B=S(U)\subseteq S(U^*)$ . Note in addition that $\{+\infty\}=\bigcap \limits_{n = 1}^\infty (n,+\infty]$ , so $\{+\infty\}$ is a member of the $\sigma$-ring $\bf S(U^*)$ . As a result, each element of $\bf S^*$ , being a union of real Borel set with possibly inifinities, is still an element of the ring $\bf S(U^*)$ , that is, $\bf S^*\subseteq S(U^*)$ , which establishes the converse inclusion and completes the whole proof.

If there is any error in the proof, please kindly point out. Thanks!

[1]Munkres' "Topology", page 84.

[2]Apostol's "Mathematical Analysis", page 51.

what is the associated Borel set of a Borel measurable function on the extended real line?

2010-05-07T07:21:12Z

This question comes from Theorem 19.B in page 81 of Halmos' "Measure Theory", as the image below shows.

In this theorem, we are given a function $\phi$ which is a Borel measurable function on the extended real line $\mathbb R^*$. But I can't figure out what the associated Borel set is with regard to which $\phi$ becomes a Borel measurable function. Related definitions of this book are as follows:

1)measurable space and measurable set (page 73):

That is, we must make sure two conditions are met: a)S is a sigma-ring, b)$\bigcup{\bf S}=X$

2)measurable function (page 76-77):

This definition shows that a measurable function must be defined on a measurable space, that is, a whole space X together with a sigma-ring S, otherwise we cannot check if $N(f)\cap f^{-1}(M)$ is measurable or not.

3)Borel measurable function (page 77-78):

In 3), Borel measurable function is defined only for the real line $\mathbb R$, but in Theorem 19.B, $\phi$ is a Borel measurable function on the extended real line $\mathbb R^\ast$. What is the sigma-ring of the measurable space involved in the above definitions? If it is just the real Borel set $\bf B$, we do not have $\bigcup\bf B=\mathbb R^*$, which violates the definition of measurable space in 1). If it is $\bf B$ along with $\{+\infty\}$ and $\{-\infty\}$ , that is, ${\bf B'=B}\cup \{\{+\infty\}\}\cup\{\{-\infty\}\}$ , ${\bf B'}$ is not a sigma-ring since, e.g. $[a,+\infty]=[a,+\infty)\cup\{+\infty\}$ is not in ${\bf B'}$. How to solve this problem? Thanks!

disjointlize an arbitrary sequence in a ring?

2010-04-27T04:30:54Z

In a ring R (nonempty class of sets closed under difference and finite union), any sequence (here means a function on natural numbers $\mathbb N$) {$E_i$} in R can be disjointlized to a disjoint sequence {$F_i$} such that $\bigcup E_i=\bigcup F_i$ by traditional induction using the equation $F_i=E_i-\bigcup \limits_{j < i}E_j$. But for arbitrary uncountable sequence {$E_\alpha$} in R, I either do not know if it is still possible to turn {$E_\alpha$} into a disjoint sequence with the same union or have no idea how to use transfinite induction to prove it if disjointlization is possible, can you help me with this problem? Thanks!

A question about sigma-ring

2010-04-01T02:09:05Z

This question comes from the 4th line of the proof of Theorem E of Halmos' "Measure Theory", in page 25, which says that C is a sigma-ring. Because this website does not allow new users to link images, I rephrase it as follows: Suppose A is any subset of the whole space X, E is any collection of subsets of X, S(E) denotes the sigma-ring generated by E, $E\cap A$ means the collection formed by all intersections of elements from E with A. Then the collection of all sets of the form $B\cup(C-A)$ where B is from S($E\cap A$) and C is from S(E) is a sigma-ring.

I just can not prove this because I can not make up the difference $[B1\cup(C1-A)]-[B2\cup(C2-A)]$ into a form of $B\cup(C-A)$. Could you please help me prove this statement? Thanks!

Comment by zzzhhh

2013-03-24T23:01:54Z

Thank you so much for your reply. For question (1), could you please explain in more detail why $\sum\limits_{b=0}^{\sqrt{n}}b^{|\mathcal{X}|-1}$ is approximately equal to $\sqrt{n}\cdot\sqrt{n}^{|\mathcal{X}|-1}$?

Comment by zzzhhh

2013-03-24T06:57:48Z

The third question is here: (3)For the new answer, since the number of balls in any entry of the matrix, including those in the last column, should not be negative, we can not pick any number freely from $[-\sqrt{n},\sqrt{n}]$. So the number of actual pmfs in $\mathcal{T}_{s^*}$ is less than $\sqrt{n}^{(|\mathcal{Y}|-1)\cdot|\mathcal{X}|}$. Therefore, under this constraint, how to understand the new answer?

Comment by zzzhhh

2013-03-24T06:55:41Z

Thank you very much for your answer. But I have three questions as follows: (1) in your old answer, when putting at most $\kappa\sqrt{n}$ balls to $|\mathcal{X}|$ bins and summing for the number of balls from 0 to $\sqrt{n}$ if omitting $\kappa$, I think the total possibilities should be $\sum\limits_{b=0}^{\sqrt{n}}b^{|\mathcal{X}|-1}$. Why you say it is $\sqrt{n}\cdot\sqrt{n}^{|\mathcal{X}|-1}$? (2)Why does "in most cases this distribution will be quite even" so that the number of balls for each row can be obtained by dividing the total balls $\kappa\sqrt{n}$ by $|\mathcal{X}|$?

Comment by zzzhhh

2013-03-03T05:48:21Z

$\mathcal{X}$ is the alphabet of symbols for $X$. $\mathcal{X}^n$ is all the sequence of length $n$ drawn from $\mathcal{X}$.

Comment by zzzhhh

2013-01-27T07:21:31Z

Yes, you are right. I should have considered the circumstances that $q_i=0$ for some symbol. But what if I put a restriction on $q$ that all $q_i$'s are positive?

Comment by zzzhhh

2012-07-04T09:23:58Z

I see. Thank you very much for the enlightening answer!

Comment by zzzhhh

2011-04-24T21:18:16Z

but today we are still studying and applying it regardless of this threat. Maybe the only thing we can do is to warn students of this threat, and then to assure them that this threat will not show up in the exam and future work, so can be safely ignored. Am I right?

Comment by zzzhhh

2011-04-24T21:18:11Z

It now seems that every theory is inconsistent, that is, "there is no way to be absolutely certain that mathematics is free from contradiction." from Timothy Chow's answer. But inconsistent theory is also meaningful for the most part. For example, principle mathematical analysis can be built on naive set theory which is still meaningful, at least for the most part. Of course we may possibly in the future find a paradox in mathematical analysis due to the inconsistency nature of the meta-theory on which it develops, (to be continued)

Comment by zzzhhh

2011-04-24T20:47:34Z

I should restate my question as follows: "Will inconsistency in meta-theory go into the theory built on it?" Here the meta-theory is naive set theory and the theory built is mathematical logic. I should express my thanks to kakaz and other people who answers and comments in this thread. Only after interaction with them can I formulate my question in a clear form. Now I wonder if the answer is still unknown. It seems that treating infinite sets as a proper class as suggested by Stefan Geschke works. Is that method will possibly produce paradox too?

Comment by zzzhhh

2011-04-24T20:23:19Z

To restate my question: Will inconsistency in meta-theory go into the theory built on it? Here the meta-theory is naive set theory and the theory built is mathematical logic. No formalization is involved in my question.

Comment by zzzhhh

2011-04-24T19:52:03Z

To avoid divergence, please let me rephrase part of your idea as follows: Any theory must be built on meta-theory. We should separate them. Here the meta-theory is "naive set theory" and the theory built is "mathematical logic". If so, my question is: "Will inconsistency in meta-theory go into the theory built on it?" I offered three answers to this question in my original post, the item 1 of your answer denies my second answer "if yes". Do you mean "if no" is also not certain, so there is not a must, as my third answer in my post indicates -- the answer is unknown, maybe yes, maybe no?

Comment by zzzhhh

2011-04-24T19:16:20Z

The question is not formalization, but consistency(paradox), so let's temporarily forget ZFC and consider only the consistency problem. First we need the concept of set in mathematical logic, for example, the justification of proof by induction on structure of wffs relies on the concept of set. Second, we are using the concept of set in mathematical logic freely as we do in naive set theory. Third, there exists paradox in naive set theory in meta-universe, so by analogy I'm afraid there are also paradoxes in the naive set theory used in mathematical logic. This is why I post this thread.

Comment by zzzhhh

2011-04-24T18:59:37Z

So the axioms of set theory used in mathematical logic is: only finite set is set (can be an element), while other infinite set (we should call them class) is not a set (can not be an element), even if it is allowed to be a set in ZFC, right?

Comment by zzzhhh

2011-04-24T17:19:11Z

Do you mean by "class" an object that can not be an element of some class or set? If so, can a class be a subset or subclass of another set or class? I think no, which would, however, makes induction by structure of wffs impossible. For example, in propositional logic, the class of all propositional wffs (it's infinite) is defined as a smallest subset of words satisfying ....

Comment by zzzhhh

2011-04-24T16:59:27Z

Then "formal" is "non-naive", but the first-order logic expressed in the meta-theory as you mentioned in the next-to-last line of your answer is naive, for we can find abusive use of the notion of set almost everywhere in mathematical logic, e.g., the set of alphabet, the set of variables, the set of formulas, the set of terms, as well as functions and relations that are in essence (naive) sets, etc.