Vengono proposte alcune teorie base dei Fondamenti della Matematica che assumono come concetti primitivi i concetti di numero naturale, collezione, qualità, operazione e relazione; le operazioni e le relazioni considerate possono essere più o meno complesse: il numero naturale che indica il grado di complessità è detto arietà. Nelle teorie considerate è raggiunto un alto grado di autoreferenza.

We propose a "natural" axiomatic theory of the Foundations of Mathematics (Theory Q) where, in addition to the membership relation (between elements and classes), pairs, sets, natural numbers, n-tuples and operations are also introduced as primitives by means of suitable ground classes. Moreover, the theory Q allows an easy introduction of other mathematical and logical entities. The theory Q is finitely axiomatized in § 2, using a first-order language with a binary relation $\in$ (membership) and five...

The aim of this paper is to review the different operators defined in the Theory of Evidence. All of them are presented from the same point of view. Special attention is given to the logical operators: conjunction (Dempster's Rule), disjunction and negation (defined by Dubois and Prade), and the operators changing the level of granularity on the set of possible states (partitions, fuzzy partitions, etc.).

We show that uncountable cardinals are indistinguishable by sentences of the monadic second-order language of order of the form (∀X)ϕ(X) and (∃X)ϕ(X), for ϕ positive in X and containing no set-quantifiers, when the set variables range over large (= cofinal) subsets of the cardinals. This strengthens the result of Doner-Mostowski-Tarski [3] that (κ,∈), (λ,∈) are elementarily equivalent when κ, λ are uncountable. It follows that we can consistently postulate that the structures $(2^{\kappa },{\left[2^{\kappa }\right]}^{>\kappa },<)$, $(2^{\lambda },{\left[2^{\lambda }\right]}^{>\lambda },<)$ are indistinguishable...

We formulate a Covering Property Axiom $CP{A}_{cube}^{game}$, which holds in the iterated perfect set model, and show that it implies the existence of uncountable strong γ-sets in ℝ (which are strongly meager) as well as uncountable γ-sets in ℝ which are not strongly meager. These sets must be of cardinality ω₁ < , since every γ-set is universally null, while $CP{A}_{cube}^{game}$ implies that every universally null has cardinality less than = ω₂. We also show that $CP{A}_{cube}^{game}$ implies the existence of a partition of ℝ into ω₁ null compact sets....

The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231–245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO–Theor. Inf. Appl. 40 (2006) 551–557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju’s construction. So we prove that ωPCP is undecidable for domain alphabets...

The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231–245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO–Theor. Inf. Appl. 40 (2006) 551–557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju’s construction. So we prove that ωPCP is undecidable for domain alphabets...

In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word ω such that h(ω) = g(ω). This problem was shown to be undecidable by Ruohonen (1985) in general. Recently Blondel and Canterini (Theory Comput. Syst.36 (2003) 231–245) showed that this problem is undecidable for domain alphabets of size 105. Here we give a proof that the infinite Post Correspondence Problem is undecidable...

We prove that for every countable ordinal $\alpha$ one cannot decide whether a given infinitary rational relation is in the Borel class ${\Sigma }_{\alpha }^{\mathbf{0}}$ (respectively ${\Pi }_{\alpha }^{\mathbf{0}}$). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a ${\Sigma }_{\mathbf{1}}^{\mathbf{1}}$-complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide whether...

We prove that for every countable ordinal α one cannot decide whether a given infinitary rational relation is in the Borel class ${\Sigma }_{\alpha }^{\mathbf{0}}$ (respectively ${\Pi }_{\alpha }^{\mathbf{0}}$). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a ${\Sigma }_{\mathbf{1}}^{\mathbf{1}}$-complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide...