Infinitary logic

Infinitary logic

:"Those unfamiliar with mathematical logic or the concept of ordinals are advised to consult those articles first."

An infinitary logic is a logic that allows infinitely long statements and/or infinitely long proofs. Some infinitary logics may have different properties from those of standard first-order logic. In particular, infinitary logics may fail to be compact or complete. Notions of compactness and completeness that are equivalent in finitary logic sometimes are not so in infinitary logic. So for infinitary logics the notions of strong compactness and strong completeness are defined. In this article we shall be concerned with Hilbert-type infinitary logics, as these have been extensively studied and constitute the most straightforward extensions of finitary logic. These are not, however, the only infinitary logics that have been formulated or studied.

Considering whether a certain infinitary logic named Omega-logic is complete promises to throw light on the continuum hypothesis.

A word on notation and the axiom of choice

As we are presenting a language with infinitely long formulae it is not possible to write expressions down as they should be written. To get around this problem we use a number of notational conveniences which strictly speaking are not part of the formal language we are defining. We use cdots to indicate an expression that is infinitely long. Where it is not clear the length of the sequence is noted afterwards. Where this notation becomes ambiguous or confusing we use suffixes such as lor_{gamma < delta}{A_{gamma to indicate an infinite disjunction over a set of formulae of cardinality delta. The same notation may be applied to quantifiers for example forall_{gamma < delta}{V_{gamma}:}. This is meant to represent an infinite sequence of quantifiers for each V_{gamma} where gamma < delta.

All usage of suffices and cdots are not part of formal infinitary languages. We assume the axiom of choice (as is often done when discussing infinitary logic) as this is necessary to have sensible distributivity laws.

Definition of Hilbert-type infinitary logics

A first-order infinitary logic L_{alpha ,eta} ,alpha in regular ,eta = 0 or omega < eta < alpha has the same set of symbols as a finitary logic and may use all the rules for formation of formulae of a finitary logic together with some additional ones:
*If we have a set of variables V={V_gamma | gamma< delta < eta } and a formulae A_0 then forall V_0 :forall V_1 cdots (A_0) and exists V_0 :exists V_1 cdots (A_0) are formulae (In each case the sequence of quantifiers has length delta).
*If we have a set of formulae A={A_gamma | gamma < delta then (A_0 lor A_1 lor cdots) and (A_0 and A_1 and cdots) are formulae (In each case the sequence has length delta).

The concepts of bound variables apply in the same manner to infinite sentences. Note that the number of brackets in these formulae is always finite. Just as in finitary logic, a formula all of whose variables are bound is referred to as a "sentence".

A theory T in infinitary logic L_{alpha , eta} is a set of statements in the logic. A proof in infinitary logic from a theory T is a sequence of statements of length gamma which obeys the following conditions: Each statement is either a logical axiom, an element of T, or is deduced from previous statements using a rule of inference. As before, all rules of inference in finitary logic can be used, together with an additional one:

*If we have a set of statements A={A_gamma | gamma < delta which have occurred previously in the proof then the statement and_{gamma < delta}{A_{gamma can be inferred.

We give only those logical axiom schemata specific to infinitary logic. For each delta and gamma such that 0 < alpha < delta we have the following logical axioms:
*((and_{epsilon < delta}{(A_{delta} implies A_{epsilon})}) implies (A_{delta} implies and_{epsilon < delta}{A_{epsilon))
*For each gamma < delta we have ((and_{epsilon < delta}{A_{epsilon) implies A_{gamma})
*Chang's distributivity laws (for each gamma): (lor_{mu < gamma}{(and_{delta < gamma}{A_{mu , delta)}) where forall mu : forall delta : exists epsilon < gamma:A_{mu , delta} = A_{epsilon} and forall g in gamma^{gamma} : exists epsilon < gamma: {A_{epsilon} , eg A_{epsilon}} subseteq {A_{mu , g(mu)} : mu < gamma}
*For gamma < alpha we have ((and_{mu < gamma}{(lor_{delta < gamma}{A_{mu , delta)}) implies (lor_{epsilon < gamma^{gamma{(and_{mu < gamma}{A_{mu ,gamma_{epsilon))) where gamma_{epsilon} is a well ordering of gamma^{gamma}The last two axiom schemata require the axiom of choice because certain sets must be well orderable. The last axiom schema is strictly speaking unnecessary as Chang's distributivity laws imply it, however it is included as a natural way to allow natural weakenings to the logic.

Completeness, compactness and strong completeness

A theory is any set of statements. The truth of statements in models are defined by recursion and will agree with the definition for finitary logic where both are defined. Given a theory T a statement is said to be valid for the theory T if it is true in all models of T.

A logic L_{alpha , eta} is complete if for every sentence S valid in every model there exists a proof of S. It is strongly complete if for any theory T for every sentence S valid in T there is a proof of S from T. An infinitary logic can be complete without being strongly complete.

A logic is compact if for every theory T of cardinality alpha if all subsets S of T have models then T has a model. A logic is strongly compact if for every theory T if all subsets S of T, where S has cardinality< alpha, have models then T has a model. If a logic is strongly compact, and complete, then it is strongly complete.

The cardinal kappa eq omega is weakly compact if L_{kappa , kappa} is compact and kappa is strongly compact if L_{kappa , kappa} is strongly compact.

Concepts expressible in infinitary logic

In the language of set theory the following statement expresses foundation:

:forall_{gamma < omega}{V_{gamma}:} eg and_{gamma < omega}{V_{gamma +} in V_{gamma.,

Unlike the axiom of foundation, this statement admits no non-standard interpretations. The concept of well foundedness can only be expressed in a logic which allows infinitely many quantifiers in an individual statement. As a consequence many theories, including Peano arithmetic, which cannot be properly axiomatised in finitary logic, can be in a suitable infinitary logic. Other examples include the theories of non-archimedean fields and torsion-free groups. These three theories can be defined without the use of infinite quantification; only infinite junctions are needed.

Complete infinitary logics

Two infinitary logics stand out in their completeness. These are L_{omega , omega} and L_{omega_1 , omega}. The former is standard finitary first-order logic and the latter is an infinitary logic that only allows statements of countable size.

L_{omega , omega} is also strongly complete, compact and strongly compact.

References

*citation|authorlink=Carol Karp|first=Carol R. |last=Karp|title=Languages with expressions of infinite length|id=MR|0176910
publisher= North--Holland Publishing Co.|publication-place= Amsterdam |year=1964

*citation|authorlink=Jon Barwise|first=Kenneth Jon |last=Barwise
id=MR|0406760
title=Infinitary logic and admissible sets
journal=J. Symbolic Logic|volume= 34 |year=1969|issue= 2|pages=226-252


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Logic — For other uses, see Logic (disambiguation). Philosophy …   Wikipedia

  • Infinitary combinatorics — In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. Some of the things studied include continuous graphs and trees, extensions of Ramsey s theorem, and Martin s axiom …   Wikipedia

  • First-order logic — is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic (a less… …   Wikipedia

  • Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… …   Wikipedia

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • List of topics in logic — This is a list of topics in logic.See also: List of mathematical logic topicsAlphabetical listAAbacus logic Abduction (logic) Abductive validation Affine logic Affirming the antecedent Affirming the consequent Antecedent Antinomy Argument form… …   Wikipedia

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

  • List of basic topics in logic — For a more comprehensive list, see the List of logic topics. Logic, a branch of both philosophy and mathematics, is the study of criteria for the evaluation of arguments. The task of the logician is to advance an account of valid and fallacious… …   Wikipedia

  • Predicate logic — In mathematical logic, predicate logic is the generic term for symbolic formal systems like first order logic, second order logic, many sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulas… …   Wikipedia

  • Ω-logic — Not to be confused with ω logic. In set theory, Ω logic is an infinitary logic and deductive system proposed by W. Hugh Woodin (1999) as part of an inquiry into non specific large cardinal axioms and the determinacy of corresponding… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”