×

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.

MSC:

03B48 Probability and inductive logic
03F30 First-order arithmetic and fragments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Billingsley, P., Probability and Measure (1986), New York: Wiley, New York · 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 · doi:10.2307/2273587
[3] Gold, E. M., Limiting recursion, J. Symb. Logic, 30, 28-18 (1965) · Zbl 0203.01201 · doi:10.2307/2270580
[4] Hájek, P., Experimental logics and Π_3^0 theories, J. Symb. Logic, 42, 515-522 (1977) · Zbl 0428.03043 · doi:10.2307/2271872
[5] Jeroslow, R. G., Experimental logics and δ_2^0 theories, J. Philosoph. Logic, 4, 253-267 (1975) · Zbl 0319.02024
[6] Jockush, C. G., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc., 131, 420-436 (1968) · Zbl 0198.32402 · doi:10.2307/1994957
[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 · doi:10.2307/2270581
[10] Rogers, H., Theory of Recursive Functions and Effective Computability (1967), New York: McGraw-Hill, New York · Zbl 0183.01401
[11] Scott, D.; Krauss, P.; Hintikka, J.; Suppes, P., Assigning probabilities to logical formulas, Aspects of inductive logic, 219-264 (1966), Amsterdam: North-Holland, Amsterdam · Zbl 0202.29905 · doi:10.1016/S0049-237X(08)71672-0
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.