zbMATH — the first resource for mathematics

Logic and probabilistic systems. (English) Zbl 0854.03020
The notion of a probabilistic system, based on the two predicates of the form \(R (\varphi, q) =\) “the probability value of \(\varphi\) is eventually \(\leq q\)” and \(S (\varphi, q) = \) “the probability value of \(\varphi\) is eventually \(\geq q\)”, can be defined as a pair \(\langle R,S \rangle\) of relations between sentences and rational numbers satisfying certain axioms which formalize these predicates. The authors connect trial and error probabilistic functions with probabilistic systems and show that, although every trial and error probabilistic function generates a probabilistic system, there exist probabilistic systems that are not generated by any trial and error probabilistic function. It is also shown that, for a given probabilistic system \(\langle R,S \rangle\), if \(\pi_{R,S}\) is defined on all sentences, then \(\pi_{R,S}\) is the limit of a trial and error probabilistic function, where the partial function \(\pi_{R,S}\) satisfies properties of measure and can be presented by means of the inner and the outer probability of \(\varphi : \underline \pi_{R,S} (\varphi) = \sup \{q \mid S (\varphi, q)\}\) and \(\overline \pi_{R,S} (\varphi) = \inf \{q \mid R (\varphi, q)\}\), as their common value, when they coincide. It is proved that the relations \(R\) and \(S\) corresponding on a trial and error probabilistic function can be \(\Sigma_2 \)-complete and that the set of sentences whose limit probability value is 1 is always \(\Pi_3\) and can be \(\Pi_3\)-complete, but for any probabilistic system \(\langle R,S \rangle\), the set of sentences \(\varphi\) for which \(\pi_{R,S} (\varphi) = 1\) can not contain all the \(\Pi_2\) true sentences. One of the interesting results of the paper is that, under reasonable conditions, no probabilistic system can be improved, where improving a probabilistic system \(\langle R,S \rangle\) would mean to find a probabilistic system \(\langle R', S' \rangle\) such that, for any true sentence \(\varphi\), \(\underline \pi_{R,S} (\varphi) \leq \underline \pi_{R',S'} (\varphi)\) and \(\overline \pi_{R,S} (\varphi) \leq \overline \pi_{R',S'} (\varphi)\), but, for some true \(\varphi\), \(\pi_{R,S} (\varphi) < \pi_{R',S'} (\varphi)\). The paper is self-contained so that no special background in probability or measure theory is needed.

03B48 Probability and inductive logic
03F30 First-order arithmetic and fragments
Full Text: DOI
[1] Billingsley, P.: Probability and Measure. New York: Wiley 1986 · Zbl 0649.60001
[2] Gaifman, H., Snir, M.: Probabilities over rich languages, testing and randomness. J. Symb. Logic 47, 495–548 (1982) · Zbl 0501.60006
[3] Gold, E.M.: Limiting recursion. J. Symb. Logic 30, 28–18 (1965) · Zbl 0203.01201
[4] Hájek, P.: Experimental logics and {\(\Pi\)} 3 0 theories. J. Symb. Logic 42, 515–522 (1977) · Zbl 0428.03043
[5] Jeroslow, R.G.: Experimental logics and {\(\delta\)} 2 0 theories. J. Philosoph. Logic 4, 253–267 (1975) · Zbl 0319.02024
[6] Jockush, C.G.Jr.: Semirecursive sets and positive reducibility. Trans. Amer. Math. Soc. 131, 420–436 (1968) · Zbl 0198.32402
[7] Magari, R.: Su certe teorie non enumerabili. Ann. Mat. Pura Appl. 48, 119–152 (1974) · Zbl 0286.02051
[8] Mostowski, A.: Examples of sets definable by means of two and three quantifiers. Fund. Math. 42, 259–270 (1957) · Zbl 0066.26201
[9] Putnam, H.: Trial and error predicates and the solution of a problem of mostowski. J. Symb. Logic 30, 49–57 (1965) · Zbl 0193.30102
[10] Rogers, H.Jr.: Theory of Recursive Functions and Effective Computability. New York: McGraw-Hill 1967 · Zbl 0183.01401
[11] Scott, D., Krauss, P.: Assigning probabilities to logical formulas. In: Hintikka, J., Suppes, P. (eds) Aspects of inductive logic, pp. 219–264. Amsterdam: North-Holland 1966 · Zbl 0202.29905
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.