User péter komjáth - MathOverflow

Answer by Péter Komjáth for What is the least ordinal than cannot be embedded in $\mathbb{R}^\mathbb{R}$?

2013-05-24T19:39:03Z

One can define an eventually increasing sequence $\{f_\alpha:\alpha<\omega_1\}$ by transfinite recursion on $\alpha$. By inserting sequences in the intervals $(f_\alpha(x),f_{\alpha+1}(x))$ we can see that $\omega_1$-sums (and of course, $\omega$-sums) do not lead out of the representable ordinals. This gives that all ordinals $<\omega_2$ are representable and this is clearly sharp if CH holds, by Will's above answer. If CH fails, larger ordinals can be represented, if, e.g. Martin's Axiom holds.

Answer by Péter Komjáth for Proof of the weak Goldbach Conjecture

2013-05-14T05:54:07Z

https://plus.google.com/114134834346472219368/posts/8qpSYNZFbzC

Answer by Péter Komjáth for collapsing successor of singular

2013-05-13T04:33:57Z

I think this is a consequence of stationary forcing. See P. Larson: The Stationary Tower, p. 60.

Answer by Péter Komjáth for Examples of stationary set preserving forcings that are not semiproper?

2013-04-17T08:56:26Z

Namba forcing is stationary preserving but not semiproper unless Chang's Conjecture holds. See "Proper and Improper Forcing" of Shelah, Ch 12.

Answer by Péter Komjáth for Countable coloring of a plane

2013-04-09T06:04:57Z

This is a result of Erdos: Problems and results in chromatic graph theory, Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) , pp. 27--35, Academic Press, New York, 1969, see p. 32. Available at the Renyi Institute's collection of Erdos papers: http://www.renyi.hu/~p_erdos/1969-13.pdf

Here is the proof. Let $X$ be the graph on the plane where two points are joined iff their distance is rational. What we want to prove is that the graph has countable chromatic number. Instead, we prove that it has a well ordering in which each point is joined into finitely many smaller (by the well ordering) points. This done, it is easy to good color the vertices via a transfinite recursion along the well ordering.

We prove the above statement for every $X\subseteq R^2$, by tranfinite induction on $|X|$. The case when $X$ is countable is obvious: order $X$ as the natural numbers. Assume that $\kappa=X$ is uncountable, and the statement is proved for every set $Y$ of cardinality less than $\kappa$.

If $a\neq b$ are point of the plane, then let $F(a,b)$ denote the set of points in rational distance from both $a$ and $b$. It is easy to see that $F(a,b)$ is always countable.

We can exhibit $X$ as the increasing, continuous union of subsets $\{X_\alpha:\alpha<\kappa\}$ such that $X_0=\emptyset$, $|X_\alpha|<\kappa$ and each $X_\alpha$ is closed under $F$. One way of seeing this is to enumerate $X$ as $\{x_\alpha:\alpha<\kappa\}$ and let $X_\alpha$ be the closure of $\{x_\beta:\beta<\alpha\}$ under the operation $F$.
Now $X$ can partitioned into the difference sets $X_{\alpha+1}-X_\alpha$. Each set $X_{\alpha+1}-X_\alpha$ possesses a well ordering $\prec_\alpha$ as required and we define the well ordering of $X$ as follows: $x\prec y$ iff either $x\in X_{\alpha+1}-X_\alpha$ and $y\in X_{\beta+1}-X_\beta$ with $\alpha<\beta$ or else $x \prec_\alpha y$ for some $\alpha$.

We have to show that $\prec$ is as wanted, so let $a$ be a point. $a\in X_{\alpha+1}-X_\alpha$ for some $\alpha<\kappa$.
We count those points $x$ which are joined to $a$ and $x\prec a$. Of these, only finitely many are in the $X_{\alpha+1}-X_\alpha$, as those precede $a$ by $\prec_\alpha$. The remaining points are in $X_\alpha$. But there can be only at most one point in $X_\alpha$ in rational distance from $a$, as otherwise, if say, $p,q\in X_\alpha$ are in rational distance from $a$, then $a\in F(p,q)\subseteq X_\alpha$, a contradiction. Altogether, we get finitely many plus one=finitely many points preceding $a$ and in rational distance from it.

Answer by Péter Komjáth for Why does $\aleph_{\omega}$ have more than $\aleph_{\omega}$ countable subsets?

2012-08-01T05:54:45Z

Let $\{A_\alpha:\alpha<\omega_\omega\}$ be all countable subsets of $\omega_\omega$. We build one that is not among them, giving the contradiction. Pick $x_0\in\omega_1$ wich is not in $\bigcup\{A_\alpha:\alpha<\omega\}$ . Then choose $\omega_1\leq x_1<\omega_2$ which is not in $\bigcup\{A_\alpha:\alpha<\omega_1\}$ , etc. Eventually we get a countable set $\{x_0,x_1,\dots\}$ different from each $A_\alpha$. (This is essentially the argument for proving Konig's inequality.)

Answer by Péter Komjáth for Is every set class generic over a given inner model?

2012-07-10T19:47:06Z

Isn't it Theorem 15.46 in Jech's Set Theory (Springer 2003) book? Perhaps one can reformulate it as follows: every set is in some generic extension of HOD.

Answer by Péter Komjáth for Minimal blocks for a family of finite sets

2012-07-05T06:43:32Z

Dear Martin: I think you can easily extend the result for systems of infinite sets, where there is a set $A$ intersecting all sets in finitely many but at least 1 point. The latter property was investigated by Erdos and Hajnal in On a property of families of sets, Acta Math. Acad. Sci. Hungar. 12 (1961), 87--123, see http://www.renyi.hu/~p_erdos/1961-11.pdf Perhaps I also had some papers on this. Does this make any sense?

Answer by Péter Komjáth for Sum of the reciprocal of perfect numbers

2012-06-23T20:22:08Z

There is, indeed a simple argument to show that the sum of the reciprocals of perfect numbers converges. It suffices to show that the number of perfect numbers up to $x$ is $O(\sqrt{x})$. As the number of even perfect numbers is less than $\log x$, it is enough to consider odd perfect numbers. Assume that $n\leq x$ is an odd perfetc number. If $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$, then $2n=(p_1^{\alpha_1}+p_1^{\alpha_1-1}+\cdots+1)(p_2^{\alpha_2}+p_2^{\alpha_2-1}+\cdots+1)\cdots(p_r^{\alpha_r}+p_r^{\alpha_r-1}+\cdots+1)$. As $n$ is odd, exactly one factor on the right hand side is even. As each $p_i$ is odd, the parity of the factor corresponding to $p_i$ is the same as the parity of $\alpha_i+1$, i.e., exactly one $\alpha_i$ is odd. That is, $n=p^\alpha N^2$, where $p$ does not divide $N$. It suffices to show that $N$ determines the prime power $p^\alpha$ and therefore for each $N^2\leq x$ there is only one odd perfect number of the above form. Now $$2=\frac{\sigma(n)}{n}=\left(1+\frac{1}{p}\cdots+\frac{1}{p^\alpha}\right)\frac{\sigma(N^2)}{N^2}$$ and so $$1+\frac{1}{p}+\cdots+\frac{1}{p^\alpha}=\frac{a}{b}$$ where $a/b$ is $2N^2/\sigma(N^2)$ in reduced form. As the denominator of the L.H.S. is $p^\alpha$, we must have $p^\alpha=b$.

Answer by Péter Komjáth for Sum of the reciprocal of perfect numbers

2012-06-10T16:48:51Z

I think that Erdos proved in 1934 that the sum of the reciprocals of primitive abundant numbers is convergent. A number $n$ is abundant if $\sigma(n)\geq 2n$ and is primitive aboundant if it is aboundant but none of its proper divisor is. It is easy to see that perfect numbers are primitive aboundant and so is the result. P. Erdõs: On the density of the abundant numbers, J. London Math. Soc. 9 (1934), 278--282. Available as http://www.renyi.hu/~p_erdos/1934-04.pdf .

Answer by Péter Komjáth for "Ill-founded Recursion" without Fund

2012-05-14T13:30:29Z

Let $x_0>x_1>\cdots$ be a strictly decreasing sequence in $(X,<)$. We can define an $F$ which gives two solutions: $f_0$ which is 0 everywhere, and $f_1$, which has $f_1(y)=0$ if $y\le x_n$ for every $n$ and $f_1(y)=1$ if $y\ge x_n$ for some $n$.

Answer by Péter Komjáth for Hales Jewett Theorem

2012-03-26T14:37:40Z

A simple application of the Hales-Jewett theorem give the following result: if $r$, $k$ are natural numbers, then there is a finite set $S$ of natural numbers which does not contain a $(k+1)$-AP, yet every coloring with $r$ colors gives a monochromatic $k$-AP.

Let $N$ be sufficiently large. The HJ theorem says that if we color all sequences of length $N$, consisting of numbers between 0 and $k-1$, with $r$ colors, there is a monocolored combinatorial line, that is, a configuration of the form $f_0,\dots,f_{k-1}$, such that for a nonempty subset $T\subseteq \{0,\dots,N-1\}$ $f_i$ is $i$ in $T$, and the same outside it. Now the set $S$ above consists of the sums $x_0+x_1M+x_2M^2+\cdots+x_{N-1}M^{N-1}$, ($0\leq x_j\leq k-1$), where $M$ is very large. That is, we map the HJ-hypercube via the mapping $(x_0,x_1,\dots,x_{N-1})\mapsto x_0+x_1M+x_2M^2+\cdots+x_{N-1}M^{N-1}$. If $M$ is large enough, then no linear combination with small ($\lt k$) coefficients that gives 0, unless the same linear combination gives 0 in the left hand side, i.e., in the hypercube, in which there is no $(k+1)$-AP.

Answer by Péter Komjáth for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T14:32:55Z

Lovasz told me the following interesting story. He had read a paper containing a long list of computer generated conjectures, did not like most them, but suddenly found one, which turned out to be an interesting and deep question. Then he realized that the same question had been asked earlier by humans. See http://oldwww.cs.elte.hu/~lovasz/berlin.pdf.

Answer by Péter Komjáth for The history of Proper Forcing

2012-03-18T14:19:26Z

What I remember is that first Laver solved the Borel conjecture by an countable support iteration which added a real at every stage (1976). That such an iteration can be of any use, was very surprising at the time. Then Baumgartner introduced the very general notion of property A, which included most (all?) standard forcings known then which added reals and showed that countable support iteration of them behaves nicely (1978). Then came Shelah, who gave the proper definition (1980). This was again a surprising thing, as Baumgartner's definition was combinatorial (containing combinatorial properties of the poset, eh, almost) while Shelah simply required that P should preserve all stationary subsets of all sets of the form $[A]^{\aleph_0}$, that is, a semantic definition. Notice that Shelah's new theory gave new and elegant proofs to old theorems, as Baumgartner's consistency of that any two $\aleph_1$-dense sets of reals are isomorphic or Mitchell's consistency of the tree property of $\aleph_2$.

Answer by Péter Komjáth for TP($\omega_2$) and the continuum

2012-03-15T14:49:52Z

I think Spencer Unger in "Fragility and indestructibility of the tree property" proves that if one adds an arbitrary number of Cohen reals to Mitchell's model, then the tree property survives (see http://www.math.cmu.edu/~sunger/).

Answer by Péter Komjáth for Is there any sequence $a_n$ of nonnegative numbers for which $\sum_{n \geq 1}a_n^2 <\infty$ and $\sum_{n \geq 1}\left(\sum_{k \geq 1}\frac{a_{kn}}{k}\right)^2=\infty$?

2012-01-13T07:07:57Z

In the recent issue of Matematikai Lapok, the report on the Schweitzer contest attributes the problem to Zoltan Buczolich and Julien Bremont.

Answer by Péter Komjáth for Well-ordered cofinal subsets

2011-12-05T13:45:40Z

Nice argumant. BTW Hausdorff's name must be mentioned, who proved a stronger form of the statement and who started the investigation of ordered sets in general.

Answer by Péter Komjáth for Forcing the nonexistence of a certain set

2011-10-31T12:43:54Z

Jech's book has a current reprint, so it can be bought.

Answer by Péter Komjáth for "name" for the ground model

2011-10-21T13:45:23Z

In most cases, however, you can get rid of the problem of referring to $\check{M}$. Andreas' formula above, for example, can be written as $$ (\forall D)((D\in \check{X})\Longrightarrow (D\cap \dot{G}\neq\emptyset)). $$ where $X$ is the set of dense subsets of $P$ (as defined in $M$).

Another standard trick to ensure that $M$ is a definable class in $M[G]$ is to force over $L$ (whenever one can, this clearly rules out the use of some large cardinals).

Answer by Péter Komjáth for Forcing over models without the axiom of choice

2011-09-26T17:54:21Z

Arnie Miller's "Long Borel hierarchies" specifically pp 8-12 may be of interest for you. See here

Answer by Péter Komjáth for Partitioning $\mathbb{R}$ into $\aleph_1$ Borel sets

2011-08-07T07:17:00Z

There is a Hausdorff gap, a sequence $\{f_\alpha,g_\alpha:\alpha\lt\omega_1\}$ of $\omega\to\omega$ functions such that $f_\alpha\lt^*f_\beta<^*g_\beta<^*g_\alpha$ hold for $\alpha\lt\beta\lt\omega_1$ (here $f\lt^* g$ denotes eventual dominance, i.e., that $f(n)\lt g(n)$ holds for large $n\lt\omega$) and there is no function $f:\omega\to\omega$ such that $f_\alpha\lt^* f\lt^* g_\alpha$ holds for $\alpha\lt\omega_1$. If we identify the reals with ${}^\omega\omega$ and set $H_\alpha=\{f:f_\alpha\lt^* f \lt^* g_\alpha\}$ then $\{H_\alpha:\alpha\lt\omega_1\}$ is a decreasing sequence of nonempty $F_\sigma$ with empty intersection.

Answer by Péter Komjáth for More on Lebesgue non-measurability

2011-08-03T13:06:32Z

I have a construction which is probably overkill, but may be flexible enough to answer the "real" question (whatever that is). Let $A$ be a measure-zero planar set which meets all lines in continuum many points. (It is easy to find, e.g., take the union of countably many products of the interval and the Cantor-set) We select a subset $B\subseteq A$ such that all projections of $B$ are Bernstein sets (a set on a line is Bernstein if neither it nor its complement contains a perfect set). Enumerate all pairs consisting of a line $L$ and a perfect set $P$ on $L$ as $\{(L_\alpha,P_\alpha):\alpha<2^\omega\}$ . At step $\alpha$ we choose a point $x_\alpha$ and a line $M_\alpha$ with the intention of promising $x_\alpha\in B$ and $B\cap M_\alpha=\emptyset$. Assume we arrived at step $\alpha$. We have some less than continuum many points $\{x_\beta:\beta<\alpha\}$ which are promised into $B$, and some less than continuum many lines, which are promised to be disjoint from $B$. We are given a line $L_\alpha$ and a perfect set $P_\alpha$ on it. Choose a point $z$ in $P_\alpha$ which is not the projection of some $x_\beta$ (possible, as $P_\alpha$ has cardinality continuum, and less than that many points have been chosen). Erect a line on $z$, perpendicular to $L_\alpha$, that will be $M_\alpha$. Next, choose an element $y\neq z$, $y\in P_\alpha$ such that the line $K$ throu $y$, perpendicular to $L_\alpha$ is not one of the $M_\beta$'s ($\beta<\alpha$). Then we can choose $x_\alpha\in K$ such that it is not in any of the lines $L_\beta$ ($\beta\leq\alpha$). Finally, $B={x_\alpha:\alpha<2^\omega}$ is as required.

Answer by Péter Komjáth for Size of stationary sets

2011-07-31T18:54:24Z

Shelah proved using his pcf theory that the least cardinality of a stationary subset of $P_\kappa(\lambda)$ is equal to the least cardinality of a cofinal subset of $P_\kappa(\lambda)$. See here: M. Shioya: A proof of Shelah's strong covering theorem for $P_\kappa(\lambda)$, Asian J. Math, 12(2008), 83-98.

Answer by Péter Komjáth for On the independence of the Kurepa Hypothesis

2011-07-31T18:34:37Z

This paper contains several results of the kind: Keith Devlin: $\aleph _{1}$-trees, Ann. Math. Logic 13(1978), 267–330.

Answer by Péter Komjáth for Dual covering theorem

2011-07-31T09:39:18Z

Perhaps Magidor's covering lemma may be mentioned: if $0^\sharp$ does not exist and $A$ is a set of ordinals which is closed under the primitive recursive set functions, then $A$ is the union of countably many constructible sets. M. Magidor: Representing sets of ordinals..., Transactions of the AMS, 317(1990), 91-126.

Answer by Péter Komjáth for Partition calculus question

2011-07-29T12:45:22Z

I think that the general conjecture $\omega_1\to(\alpha,n)^3$ goes back to Erdos and Rado.

Answer by Péter Komjáth for Successive nth powers mod p?

2011-07-16T05:31:13Z

I think van der Waerden's theorem gives at least an arithmetic progression (not consecutive elements) consisting of $n$-th powers. Let $k,n$ be given and $p$ a sufficiently large prime. If $g$ is a primitive root mod $p$, then consider the following coloring of the reduced residue system: $x\mapsto c$ if $x\equiv g^{ny+c}\pmod{p}$ for some $y$ and $0\leq c \lt n$ . This is a coloring of $0,1,\dots,p-1$ with $n$ colors. By van der Waerden's theorem, there is an AP of length $k$, i.e., $y,y+H,\dots,y+(k-1)H$ get the same color, $c$. If we divide by $g^c$, we get an AP $z,z+h,\dots,z+(k-1)h$ of length $k$, consisting $n$-th powers.

Answer by Péter Komjáth for About solvable groups

2011-03-26T18:19:05Z

The minimal non-solvable group surely has the property that all proper subgroups are solvable.

Answer by Péter Komjáth for Is there always, for a given prime $p$, a prime $\ell
2011-01-18T06:38:36Z

Erdos conjectured that for any sufficiently large prime $p$ there is a primitive root $q<p$ for $p$ which is prime.

Answer by Péter Komjáth for Determine the (N-1)th fibonacci number from a given extremely large Nth ?

2010-12-26T16:38:41Z

The n-th Fibonacci number can be calculated in log n steps, see, e.g., here

Comment by Péter Komjáth

2013-05-20T13:39:52Z

Good point. .

Comment by Péter Komjáth

2013-05-16T03:41:54Z

I just heard this nice result from Fred Galvin a few weeks ago. My understanding is that he proved it without knowing a reference.

Comment by Péter Komjáth

2013-04-23T05:08:23Z

Did you try Dickson's "Theory of Numbers"?

Comment by Péter Komjáth

2013-01-21T09:50:36Z

Similarly to Andrej's argument above, one can give an AC-free proof of the following result: if $X$ is a countable graph, every finite subgraph of $X$ has a good coloring with $k$ colors ($k$ is finite) then so has $X$.

Comment by Péter Komjáth

2013-01-15T12:41:57Z

Hindman's theorem has a proof using Zorn's lemma. See, e.e., here: math.toronto.edu/lgoldmak/Hindman.pdf

Comment by Péter Komjáth

2012-09-14T21:34:53Z

The above "joke" is a famous comment made by Erdos on the above diagonal Ramsey numbers (somewhat loosely told).

Comment by Péter Komjáth

2012-08-24T19:10:48Z

This problem, with the above solution, can be found in my book: Problems and solutions in classical set theory with Totik, in the chapter on Hamel bases as problem 15.23.

Comment by Péter Komjáth

2012-07-27T12:45:38Z

Erdos rather called it "the transfinite book". He was certainly aware that proofs cannot be compared by elegance, that sometimes an ugly proof is "the right one", that there is no such thing as the ultimate proof of a theorem. This was just a figure of speech used mostly when somebody gave a surprising new proof of a theorem.

Comment by Péter Komjáth

2012-07-10T20:01:41Z

Sorry, I don't know.

Comment by Péter Komjáth

2012-05-15T04:36:19Z

Does $2^\alpha\geq\alpha^{+n}$ qualify?

Comment by Péter Komjáth

2012-04-24T19:09:50Z

What exactly are your questions?

Comment by Péter Komjáth

2012-03-26T18:04:28Z

The fact that no zeta roots have zero as real part follows from that no roots have 1 as real part via the functional equation.

Comment by Péter Komjáth

2012-03-26T15:56:51Z

Thanks, Andres. I could never figure that out...

Comment by Péter Komjáth

2012-03-26T05:23:05Z

Yes, exactly that one.

Comment by Péter Komjáth

2012-03-25T06:04:49Z

The conjecture does not claim that $A$ is entirely composed of arithmetic progressions (unless we allow APs of length 1 or 2).

User péter komjáth - MathOverflow

Answer by Péter Komjáth for What is the least ordinal than cannot be embedded in $\mathbb{R}^\mathbb{R}$?

Answer by Péter Komjáth for Proof of the weak Goldbach Conjecture

Answer by Péter Komjáth for collapsing successor of singular

Answer by Péter Komjáth for Examples of stationary set preserving forcings that are not semiproper?

Answer by Péter Komjáth for Countable coloring of a plane

Answer by Péter Komjáth for Why does $\aleph_{\omega}$ have more than $\aleph_{\omega}$ countable subsets?

Answer by Péter Komjáth for Is every set class generic over a given inner model?

Answer by Péter Komjáth for Minimal blocks for a family of finite sets

Answer by Péter Komjáth for Sum of the reciprocal of perfect numbers

Answer by Péter Komjáth for Sum of the reciprocal of perfect numbers

Answer by Péter Komjáth for "Ill-founded Recursion" without Fund

Answer by Péter Komjáth for Hales Jewett Theorem

Answer by Péter Komjáth for Interesting conjectures "discovered" by computers and proved by humans?

Answer by Péter Komjáth for The history of Proper Forcing

Answer by Péter Komjáth for TP($\omega_2$) and the continuum

Answer by Péter Komjáth for Is there any sequence $a_n$ of nonnegative numbers for which $\sum_{n \geq 1}a_n^2 <\infty$ and $\sum_{n \geq 1}\left(\sum_{k \geq 1}\frac{a_{kn}}{k}\right)^2=\infty$?

Answer by Péter Komjáth for Well-ordered cofinal subsets

Answer by Péter Komjáth for Forcing the nonexistence of a certain set

Answer by Péter Komjáth for "name" for the ground model

Answer by Péter Komjáth for Forcing over models without the axiom of choice

Answer by Péter Komjáth for Partitioning $\mathbb{R}$ into $\aleph_1$ Borel sets

Answer by Péter Komjáth for More on Lebesgue non-measurability

Answer by Péter Komjáth for Size of stationary sets

Answer by Péter Komjáth for On the independence of the Kurepa Hypothesis

Answer by Péter Komjáth for Dual covering theorem

Answer by Péter Komjáth for Partition calculus question

Answer by Péter Komjáth for Successive nth powers mod p?

Answer by Péter Komjáth for About solvable groups

Answer by Péter Komjáth for Is there always, for a given prime $p$, a prime $\ell 2011-01-18T06:38:36Z Erdos conjectured that for any sufficiently large prime $p$ there is a primitive root $q<p$ for $p$ which is prime.

Answer by Péter Komjáth for Determine the (N-1)th fibonacci number from a given extremely large Nth ?

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Comment by Péter Komjáth

Answer by Péter Komjáth for Is there always, for a given prime $p$, a prime $\ell
2011-01-18T06:38:36Z

Erdos conjectured that for any sufficiently large prime $p$ there is a primitive root $q<p$ for $p$ which is prime.