𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Effective Enumerations of Families of Finite Sets of Natural Numbers

✍ Scribed by Angel V. Ditchev

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
301 KB
Volume
37
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

We construct a universal r.e. set in the following manner: For any (n, x) we construct a set Un,, E 8 such that the set of all (z, n, x ) such that z E U,,,, is r.e. We construct the set Un,x by steps, and on step s we build a finite approximation U,,.x,s of U,,,,, and finally we take Let us describe the construction of the set lJ,,x., on step s for any R, x E N. We consider two Case I. V y ( y 5 s + G(F(n), x, y ) = 0). Take Un,x.s = E F ( n ) .

Case 11. 3 y ( y 5 s + G ( F ( n ) , x, y ) * 0). Now take U n , x , s = Wn,yn)).s.

Thus the construction is completed.

Obviously, the predicate u E U,,x,s is r.e. relatively to z, n, x, s. We fix Un,, = USE N Un,x.s.

First of all, we shall see that Un, E 8 for all natural numbers n and x. We consider two Case 1. V y ( G ( F ( n ) , x, y ) = 0). Then F(n) E Z, i.e. EF(,,) E 8 and for any s, U,,,,, = Case 11. 3 y ( G ( F ( n ) , x, y ) * 0). Let y o be the least y such that G ( F ( n ) , x, y ) * 0. Then

πŸ“œ SIMILAR VOLUMES

Enumeration of Special Sets of Polynomia
Enumeration of Special Sets of Polynomials over Finite Fields
✍ Astrid Reifegerste πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 379 KB

In this paper we consider squarefree polynomials over finite fields whose gcd with their reciprocal and Frobenius conjugate polynomial is trivial, respectively. Our focus is on the enumeration of these special sets of polynomials, in particular, we give the number of squarefree palindromes. These in

Refined Stirling Numbers: Enumeration of
Refined Stirling Numbers: Enumeration of Special Sets of Permutations and Set-Partitions
✍ J. Katriel πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 110 KB

The refined Stirling numbers of the first kind specify the number of permutations of n indices possessing m i cycles whose lengths modulo k are congruent to i; i ΒΌ 0; 1; 2; . . . ; k Γ€ 1: The refined Stirling numbers of the second kind are similarly defined in terms of set-partitions and the cardi

On Infinite Sum-free Sets of Natural Num
On Infinite Sum-free Sets of Natural Numbers
✍ Tomasz Ε‚uczak; Tomasz Schoen πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 346 KB

A subset of the natural numbers is k-sum-free if it contains no solutions of the equation x 1 + } } } +x k = y, and strongly k-sum-free when it is l-sum-free for every l=2, ..., k. It is shown that every k-sum-free set with upper density larger than 1Γ‚(k+1) is a subset of a periodic k-sum-free set a

Families of arcs disconnected by finite
Families of arcs disconnected by finite sets I
✍ M. Rochowski πŸ“‚ Article πŸ“… 1975 πŸ› John Wiley and Sons 🌐 English βš– 140 KB

By M. ROCHOWSKI of Katowice (Eingegangen am 5 . 12. 1973) 1. Introduction. I n this paper a generalization (theorem C,) of theorem Ci proved in [3] shall be formulated and as a consequence of it we prove MENOER'S n-Beinsatz (see [l], [2], [4]). The proof of theorem C, shall be published separately i

On Sets of Natural Numbers Whose Sumset
On Sets of Natural Numbers Whose Sumset is Free of Squares
✍ Tomasz Schoen πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 78 KB

Let A be a set of natural numbers such that the set A+A contains no perfect squares. We prove that if the density d(A) exists, it is not larger than 2Γ‚5. ## 1999 Academic Press In this note we are concerned with a problem of Erdo s and Silverman (see ) who asked about the maximal density d max of