The Experts below are selected from a list of 14178 Experts worldwide ranked by ideXlab platform
Ludovic Patey - One of the best experts on this subject based on the ideXlab platform.
-
Computing sets from all Infinite Subsets
arXiv: Logic, 2020Co-Authors: Noam Greenberg, Ludovic Patey, Matthew Harrison-trainor, Daniel TuretskyAbstract:A set is introreducible if it can be computed by every Infinite Subset of itself. Such a set can be thought of as coding information very robustly. We investigate introreducible sets and related notions. Our two main results are that the collection of introreducible sets is $\Pi^1_1$-complete, so that there is no simple characterization of the introreducible sets; and that every introenumerable set has an introreducible Subset.
-
The weakness of the pigeonhole principle under hyperarithmetical reductions
Journal of Mathematical Logic, 2020Co-Authors: Benoit Monin, Ludovic PateyAbstract:The Infinite pigeonhole principle for 2-partitions ($\mathsf{RT}^1_2$) asserts the existence, for every set $A$, of an Infinite Subset of $A$ or of its complement. In this paper, we study the Infinite pigeonhole principle from a computability-theoretic viewpoint. We prove in particular that $\mathsf{RT}^1_2$ admits strong cone avoidance for arithmetical and hyperarithmetical reductions. We also prove the existence, for every $\Delta^0_n$ set, of an Infinite low${}_n$ Subset of it or its complement. This answers a question of Wang. For this, we design a new notion of forcing which generalizes the first and second-jump control of Cholak, Jockusch and Slaman.
-
Pigeons do not jump high
Advances in Mathematics, 2019Co-Authors: Benoit Monin, Ludovic PateyAbstract:Abstract The Infinite pigeonhole principle for 2-partitions asserts the existence, for every set A, of an Infinite Subset of A or of its complement. In this paper, we develop a new notion of forcing enabling a fine analysis of the computability-theoretic features of the pigeonhole principle. We deduce various consequences, such as the existence, for every set A, of an Infinite Subset of it or its complement of non-high degree. We also prove that every Δ 0 3 set has an Infinite low3 solution and give a simpler proof of Liu's theorem that every set has an Infinite Subset in it or its complement of non-PA degree.
-
Somewhere over the rainbow Ramsey theorem for pairs
2018Co-Authors: Ludovic PateyAbstract:The rainbow Ramsey theorem states that every coloring of tuples where each color is used a bounded number of times has an Infinite subdomain on which no color appears twice. The restriction of the statement to colorings over pairs (RRT22) admits several characterizations: it is equivalent to finding an Infinite Subset of a 2-random, to diagonalizing against Turing machines with the halting set as oracle... In this paper we study principles that are closely related to the rainbow Ramsey theorem, the Erd\H{o}s Moser theorem and the thin set theorem within the framework of reverse mathematics. We prove that the thin set theorem for pairs implies RRT22, and that the stable thin set theorem for pairs implies the atomic model theorem over RCA. We define different notions of stability for the rainbow Ramsey theorem and establish characterizations in terms of Ramsey-type K\"onig's lemma, relativized Schnorr randomness or diagonalization of Delta2 functions.
-
Pigeons do not jump high
arXiv: Logic, 2018Co-Authors: Benoit Monin, Ludovic PateyAbstract:The Infinite pigeonhole principle for 2-partitions asserts the existence, for every set $A$, of an Infinite Subset of $A$ or of its complement. In this paper, we develop a new notion of forcing enabling a fine analysis of the computability-theoretic features of the pigeonhole principle. We deduce various consequences, such as the existence, for every set $A$, of an Infinite Subset of it or its complement of non-high degree. We also prove that every $\Delta^0_3$ set has an Infinite low${}_3$ solution and give a simpler proof of Liu's theorem that every set has an Infinite Subset in it or its complement of non-PA degree.
Alireza Abdollahi - One of the best experts on this subject based on the ideXlab platform.
-
RINGS WITH A SETWISE POLYNOMIAL-LIKE CONDITION
Bulletin of The Iranian Mathematical Society, 2012Co-Authors: Ali Tavakoli, Alireza Abdollahi, Howard E. BellAbstract:Let R be an Infinite ring. Here, we prove that if 0R be- longs to {x1x2 ···xn | x1,x2,...,xn 2 X} for every Infinite Subset X of R, then R satisfies the polynomial identity x n = 0. Also, we prove that if 0R belongs to {x1x2 ···xn xn+1 | x1,x2,...,xn,xn+1 2 X} for every Infinite Subset X of R, then x n = x, for all x 2 R.
-
A permutability problem in Infinite groups and Ramsey's theorem
Bulletin of the Australian Mathematical Society, 2001Co-Authors: Alireza Abdollahi, Aliakbar Mohammadi HassanabadiAbstract:We use Ramsey's theorem to generalise a result of L. Babai and T.S. Sós on Sidon Subsets and then use this to prove that for an integer n > 1 the class of groups in which every Infinite Subset contains a rewritable n-Subset coincides with the class of groups in which ever Infinite Subset contains n mutually disjoint non-empty Subsets X1,…,Xn such that X1…Xn∩Xσ(1) …xσ(n) ≠ θ for some non-identity permutation σ on the set {1,…,n}.
-
SOME ENGEL CONDITIONS ON Infinite SubsetS OF CERTAIN GROUPS
Bulletin of The Australian Mathematical Society, 2000Co-Authors: Alireza AbdollahiAbstract:Let k be a positive integer. We denote by Ek(oo) the class of all groups in which every Infinite Subset contains two distinct elements x, y such that (X,ky) = 1. We say that a group G is an EZ-group provided that whenever X, Y are Infinite Subsets of G, there exists x E X, Y E Y such that (X,ky) = 1. Here we prove that: (1) If G is a finitely generated soluble group, then G E E3(00) if and only if G is finite by a nilpotent group in which every two generator subgroup is nilpotent of class at most 3. (2) If G is a finitely generated metabelian group, then G E Ek(oo) if and only if G/Zk(G) is finite, where Zk(G) is the (k + l)-th term of the upper central series of G. (3) If G is a finitely generated soluble Edoo)-group, then there exists a positive integer t depending only on k such that G/ Zt (G) is finite. (4) If G is an Infinite EZ-group in which every non-trivial finitely gener- ated subgroup has a non-trivial finite quotient, then G is k-Engel. In particular, G is locally nilpotent.
-
Finitely generated soluble groups with an Engel condition on Infinite Subsets
Rendiconti del Seminario Matematico della Università di Padova, 2000Co-Authors: Alireza AbdollahiAbstract:In this note, we prove that, in every finitely generated soluble group G, G/Z2 (G) is finite if and only if in every Infinite Subset X of G there exist different x, y such that [x, y, y] = 1. B. H. Neumann proved in [9] that a group G is centre-by-finite if and only if every Infinite Subset X of G contains two different commuting elements. This answered a question posed by Paul Erdos. Extensions of problems of this type are studied in [1], [4], [5], [8] and [11]. We denote by E( 00) (respectively, N( 00» the class of groups G such that, every Infinite Subset X of G, contains different elements x and Y EX such that [X,kY] = 1 (respectively, (x, y) is nilpotent of class at most k) for some k = k( x, Y) ~ 1. If the integer k is the same for all Infinite Subsets of G, we say that G is in the class E k ( 00) (respectively, N k ( 00 ) ) • It is easy to see that the above classes are closed with respect to forming subgroups and homomorphic images. In [6] J. C. Lennox and J. Wiegold studied the class N( 00) and proved that a finitely generated soluble group is in N( 00 ) if and only if it is finite-by-nilpotent. Also, in [7] P. Longobardi and M. Maj studied the class E( 00) and proved that a finitely generated soluble group is in E( 00 ) if and only if it is finite-by-nilpotent. Moreover, they proved that a finitely generated soluble group G is in E2( 00) if and only if G/R(G) is finite, where R(G) is (*) Indirizzo dell'A: Department of Mathematics, University of Isfahan, Isfahan-Iran. ""
-
Some Engel conditions on Infinite Subsets of certain groups
Bulletin of the Australian Mathematical Society, 2000Co-Authors: Alireza AbdollahiAbstract:Let k be a positive integer. We denote by ɛk(∞) the class of all groups in which every Infinite Subset contains two distinct elements x, y such that [x,k y] = 1. We say that a group G is an -group provided that whenever X, Y are Infinite Subsets of G, there exists x ∈ X, y ∈ Y such that [x,k y] = 1. Here we prove that:(1) If G is a finitely generated soluble group, then G ∈ ɛ3(∞) if and only if G is finite by a nilpotent group in which every two generator subgroup is nilpotent of class at most 3.(2) If G is a finitely generated metabelian group, then G ∈ ɛk(∞) if and only if G/Zk (G) is finite, where Zk (G) is the (k + 1)-th term of the upper central series of G.(3) If G is a finitely generated soluble ɛk(∞)-group, then there exists a positive integer t depending only on k such that G/Zt (G) is finite.(4) If G is an Infinite -group in which every non-trivial finitely generated subgroup has a non-trivial finite quotient, then G is k-Engel. In particular, G is locally nilpotent.
Lu Liu - One of the best experts on this subject based on the ideXlab platform.
-
Avoid Schnorr randomness
arXiv: Logic, 2019Co-Authors: Lu LiuAbstract:We prove that every finite partition of $\omega$ admit an Infinite Subset that does not compute a Schnorr random real. We use this result to answer two questions of Brendle, Brooke-Taylor, Ng and Nies and strength a result of Khan and Miller.
-
Extracting randomness within a Subset is hard
European Journal of Mathematics, 2019Co-Authors: Bjørn Kjos-hanssen, Lu LiuAbstract:The tree forcing method of Liu enables the cone avoiding of bounded enumeration of a given tree, within Subsets or co-Subsets of an arbitrary given set, provided the given tree does not admit computable bounded enumeration. Using this result, he settled and reproduced a series of problems and results in reverse mathematics and the theory of algorithmic randomness, including showing that every 1-random set has an Infinite Subset or co-Subset which computes no 1-random set. In this paper, we show that for any given 1-random set A, there exists an Infinite Subset G of A such that G does not compute any set with positive effective Hausdorff dimension. In particular, we answer in the affirmative Kjos-Hanssen’s 2006 question whether each 1-random set has an Infinite Subset which computes no 1-random set. The result is surprising in that the tree forcing technique seems to heavily rely on Subset co-Subset combinatorics, whereas this result does not.
-
Constructing a weak Subset of a random set
arXiv: Logic, 2016Co-Authors: Lu LiuAbstract:The tree forcing method given by (Liu 2015) enables the cone avoiding of strong enumeration of a given tree, within a Subset or co-Subset of an arbitrary given set, provided the given tree does not admit computable strong enumeration. Using this result, we settled and reproduced a series of problems in reverse mathematics. In this paper, we demonstrate cone avoiding results within an Infinite Subset of a given 1-random set. We show that for any given 1-random set $X$, there exists an Infinite Subset $Y$ of $X$ such that $Y$ does not compute any real with positive effective Hausdorff dimension, thus answering negatively a question posed by Kjos-Hanssen that whether there exists a 1-random set of which any Infinite Subset computes some 1-random real. The result is surprising in that the tree forcing technique used on the Subset or co-Subset seems to heavily rely on Subset co-Subset combinatorics, whereas this result does not.
-
$\mathsf{RT}_2^2$ does not imply $\mathsf{WKL}_0$
arXiv: Logic, 2016Co-Authors: Lu LiuAbstract:We prove that $\mathsf{RCA}_0+\mathsf{RT}_2^2\not\rightarrow \mathsf{WKL}_0$ by showing that for any set $C$ not of PA-degree and any set $A$, there exists an Infinite Subset $G$ of $A$ or $\bar{A}$, such that $G\oplus C$ is also not of PA-degree.
Bjørn Kjos-hanssen - One of the best experts on this subject based on the ideXlab platform.
-
Extracting randomness within a Subset is hard
European Journal of Mathematics, 2019Co-Authors: Bjørn Kjos-hanssen, Lu LiuAbstract:The tree forcing method of Liu enables the cone avoiding of bounded enumeration of a given tree, within Subsets or co-Subsets of an arbitrary given set, provided the given tree does not admit computable bounded enumeration. Using this result, he settled and reproduced a series of problems and results in reverse mathematics and the theory of algorithmic randomness, including showing that every 1-random set has an Infinite Subset or co-Subset which computes no 1-random set. In this paper, we show that for any given 1-random set A, there exists an Infinite Subset G of A such that G does not compute any set with positive effective Hausdorff dimension. In particular, we answer in the affirmative Kjos-Hanssen’s 2006 question whether each 1-random set has an Infinite Subset which computes no 1-random set. The result is surprising in that the tree forcing technique seems to heavily rely on Subset co-Subset combinatorics, whereas this result does not.
-
A strong law of computationally weak Subsets
Journal of Mathematical Logic, 2011Co-Authors: Bjørn Kjos-hanssenAbstract:We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an Infinite Subset that computes no random set. That is, there is an almost sure event $\mathcal{A}$ such that if $X \in \mathcal{A}$ then X has an Infinite Subset Y such that no element of $\mathcal{A}$ is Turing computable from Y.
-
Infinite Subsets of random sets of integers
Mathematical Research Letters, 2009Co-Authors: Bjørn Kjos-hanssenAbstract:There is an Infinite Subset of a Martin-L\"of random set of integers that does not compute any Martin-L\"of random set of integers. To prove this, we show that each real of positive effective Hausdorff dimension computes an Infinite Subset of a Martin-L\"of random set of integers, and apply a result of Miller.
Patey Ludovic - One of the best experts on this subject based on the ideXlab platform.
-
The weakness of the pigeonhole principle under hyperarithmetical reductions
World Scientific Publishing House Ltd, 2020Co-Authors: Monin Benoit, Patey LudovicAbstract:29 pagesInternational audienceThe Infinite pigeonhole principle for 2-partitions ($\mathsf{RT}^1_2$) asserts the existence, for every set $A$, of an Infinite Subset of $A$ or of its complement. In this paper, we study the Infinite pigeonhole principle from a computability-theoretic viewpoint. We prove in particular that $\mathsf{RT}^1_2$ admits strong cone avoidance for arithmetical and hyperarithmetical reductions. We also prove the existence, for every $\Delta^0_n$ set, of an Infinite low${}_n$ Subset of it or its complement. This answers a question of Wang. For this, we design a new notion of forcing which generalizes the first and second-jump control of Cholak, Jockusch and Slaman
-
Somewhere over the rainbow Ramsey theorem for pairs
HAL CCSD, 2018Co-Authors: Patey LudovicAbstract:31 pagesThe rainbow Ramsey theorem states that every coloring of tuples where each color is used a bounded number of times has an Infinite subdomain on which no color appears twice. The restriction of the statement to colorings over pairs (RRT22) admits several characterizations: it is equivalent to finding an Infinite Subset of a 2-random, to diagonalizing against Turing machines with the halting set as oracle... In this paper we study principles that are closely related to the rainbow Ramsey theorem, the Erd\H{o}s Moser theorem and the thin set theorem within the framework of reverse mathematics. We prove that the thin set theorem for pairs implies RRT22, and that the stable thin set theorem for pairs implies the atomic model theorem over RCA. We define different notions of stability for the rainbow Ramsey theorem and establish characterizations in terms of Ramsey-type K\"onig's lemma, relativized Schnorr randomness or diagonalization of Delta2 functions