Logic

Logic

Unsolvability results also imply unprovability in logics Logics we will look at (all very briefly) – – – – – – – Aristotelian logic Euclidean geometry Propositional logic First order logic Peano axioms Zermelo Fraenkel set theory Higher order logic

This material is presented so as to require a minimum of mathematical formalism.

What is truth? Logic can infer the truth of statements in the conceptual world of mathematics, or statements about the real world. The “real” world is perceived through senses We all perceive the same real world How is the conceptual world perceived?

How do we know we perceive the same conceptual world? The symbol “1” that we see is just ink on paper (or shadow on screen) and not the same as the concept of the number one. “1” can be written different ways but the concept does not change The conceptual world is not perceived but imagined It is a world of ideas rather than objects

Why study the conceptual world? For some reason mathematics is helpful in understanding the real world Why should this be so? A possible argument for the existence of God The correspondence between mathematics and reality can be seen as an evidence that the designer of the world was a thinking being Statements may be true or false in the conceptual world

Possible Worlds Logic considers not only the world that exists but also other potential worlds, the way things could be Different statements may be true in different possible worlds. – In one world, the statement “It is raining” may be true. – In another world, this statement may be false.

There are many “possible worlds” There are also many “possible worlds” in the conceptual realm of mathematics. In a logic a possible world is called an interpretation. It assigns meanings to the symbols in the logic. Thus each interpretation makes some statements true and some statements false. Then what does it mean to say that a statement in mathematics is true?

What is truth?

We believe certain statements are true – Fermat’s last theorem – There are infinitely many primes What does it mean that such statements are true? – – – – The answer is not straightforward Primes are not physical objects They can’t be directly counted Even if you could count them you could not count infinitely many of them

How can one check the truth of a statement in the conceptual world? In the real world this is easier – Either it’s raining or it isn’t – We all perceive the same real world – The question of meaning is more straightforward A mathematical statement is logically true if it is true when the symbols in it are given their standard mathematical meaning

This is called the standard interpretation – For example, the integers are , -2, -1, 0, 1, 2, under the standard interpretation Sometimes mathematicians debate about the standard interpretation – Is the axiom of choice true or not? – Then there can be disagreement about whether a logical statement is true or not

The purpose of logic is to distinguish correct forms of argument from incorrect forms of argument This is done using only the form of the argument, independently of the subject matter

A logic consists of a set of statements (syntax), an assignment of meaning to the statements (semantics), and a method of proving statements. A logic L is sound if all statements provable in L, are true A logic L is effective if the problem of determining whether a statement A is provable in L, is partially decidable We assume all logics are sound and effective

A theorem prover for a logic is a Turing machine that tests if a statement is provable in the logic. If the statement is provable, the Turing machine halts. If not, the Turing machine either runs forever or halts in the “n” state. Thus if there is a theorem prover for a logic L, then it is partially decidable whether a statement of L is provable in L. All these logics have theorem provers.

All these logics also have interpretations of formulas. An interpretation assigns meanings to the symbols in the logic. It is a “possible world” described by the logic. A statement in L is valid if it is true in all interpretations of L.

An interpretation that makes a statement A true is called a model of A. A nonstandard model has a counterintuitive meaning. For example, it may have integers larger than infinity. We will see that any sufficiently powerful logic has nonstandard models. If a statement X is valid then it is true in standard models so it is true. A statement may be true but not valid.

Aristotelian Logic Three part statements called categorical syllogisms 256 forms of categorical syllogisms in all Validity depends only on the form of the syllogism

Example of a categorical syllogism: – All P are Q. All Q are R. Thus all P are R. An interpretation of this syllogism: – All North Carolinians are Southerners. – All Southerners are Earthlings. – Therefore all North Carolinians are Earthlings. Another interpretation: – All ducks are sponges. – All sponges are happy. – Therefore all ducks are happy.

The syllogism is true if – one of the hypotheses is false or – the conclusion is true Both interpretations make the syllogism true. This syllogism is valid. Thus it is true in all interpretations.

Another syllogism: – All P are Q. All P are R. Thus all Q are R. An interpretation: – All North Carolinians are Earthlings. – All North Carolinians are Southerners. – Therefore all Earthlings are Southerners. Another interpretation: – All students are people. – All students are mortal. – Therefore all people are mortal.

The first interpretation makes the syllogism false. The second interpretation makes the syllogism true. This syllogism is not valid. Syllogisms can be conditionally or unconditionally valid.

Aristotelian Logic Conditional validity assumes non empty sets P,Q,R et cetera Unconditional validity has no assumptions 15 unconditionally valid syllogisms 9 conditionally valid syllogisms 24 valid either way

Table 9: Valid categorical syllogisms [Hurley, 1985]. Unconditionally valid: All M are P. All S are M. Thus All S are P. No M are P. All S are M. Thus No S are P. All M are P. Some S are M. Thus Some S are P. No M are P. Some S are M. Thus Some S are not P. No P are M. All S are M. Thus No S are P. All P are M. No S are M. Thus No S are P. No P are M. Some S are M. Thus Some S are not P. All P are M. Some S are not M. Thus Some S are not P. Some M are P. All M are S. Thus Some S are P. All M are P. Some M are S. Thus Some S are P. Some M are not P. All M are S. Thus Some S are not P. No M are P. Some M are S. Thus Some S are not P. All P are M. No M are S. Thus No S are P. Some P are M. All M are S. Thus Some S are P. No P are M. Some M are S. Thus Some S are not P.

Conditionally valid: All M are P. All S are M. Thus Some S are P. (S must exist) No M are P. All S are M. Thus Some S are not P. (S must exist) All P are M. No S are M. Thus Some S are not P. (S must exist) No P are M. All S are M. Thus Some S are not P. (S must exist) All P are M. No M are S. Thus Some S are not P. (S must exist) All M are P. All M are S. Thus Some S are P. (M must exist) No M are P. All M are S. Thus Some S are not P. (M must exist) No P are M. All M are S. Thus Some S are not P. (M must exist) All P are M. All M are S. Thus Some S are P. (P must exist)

Interpretations assign meanings to symbols The meaning of S in interpretation I is a set This set is called SI. Interpretations also assign meanings to statements Let I be an interpretation of a categorical syllogism. Then I is extended to statements as follows:

All S are P means that SI is a subset of PI. Some S are P means that SI and PI have nonempty intersection. No S are P means that SI and PI have empty intersection. Some S are not P means that SI and the complement of PI have nonempty intersection. A categorical syllogism is valid if it is true in all interpretations.

Example: All M are P. All S are M. Thus all S are P. Example I: MI is {a,b,c}, SI is {a,b}, PI is {a,b,c,d}. I is a model of this syllogism if: (MI PI) (SI MI) (SI PI). This syllogism is true for this particular I. Another example I: MI is {a,b}, SI is {a,b,c}, PI is {a}. This syllogism is also true for this I.

This syllogism is true for all I, so this syllogism is valid. Example: No M are P. Some M are S. Thus some S are not P. I is a model of this syllogism if: (MI PI ) (SI MI ) (SI - PI ). This syllogism is also true for all I so this syllogism is also valid.

An invalid syllogism: All S are P. All S are Q. Thus all P are Q. An interpretation: SI {a,b}, PI {a,b,c}, QI {a,b,c,d}. This I makes the syllogism true and is thus a model of it. Another interpretation: SI {a,b}, PI {a,b,c,d}, QI {a,b,c}. This I makes the first two statements true but the conclusion false. I is not a model.

A categorical syllogism is satisfiable if there exists an interpretation I making it true. Such an interpretation I is called a model of the syllogism. It is possible to construct models of valid categorical syllogisms. It is also possible to construct models of many non-valid categorical syllogisms.

Venn diagrams can be used to check the validity of categorical syllogisms. A Turing machine could use the same idea to check whether a categorical syllogism is valid. A TM could also check that a statement followed from a set of statements by a sequence of categorical syllogisms. Thus there is a theorem prover for this logic. In fact the validity problem is decidable.

Given the assumptions – All M are P. All S are M. All P are Q. To prove: – All S are Q From the first two statements, it follows that all S are P. From “all S are P” and “all P are Q,” it follows that “all S are Q.” Thus “all S are Q” has been proved.

Geometry Euclid's Axioms and Postulates First Axiom: Things which are equal to the same thing are also equal to one another. Second Axiom: If equals are added to equals, the whole are equal. Third Axiom: If equals be subtracted from equals, the remainders are equal. Fourth Axiom: Things which coincide with one another are equal to one another. Fifth Axiom: The whole is greater than the part.

First Postulate: To draw a line from any point to any point. Second Postulate: To produce a finite straight line continuously in a straight line. Third Postulate: To describe a circle with any center and distance. Fourth Postulate: That all right angles are equal to one another. Fifth Postulate: That, if a straight line falling on two straight lines make the interior angles on the same side less than two right angles, the two straight lines, if produced indefinitely, meet on that side of which are the angles less than the two right angles.

Hilbert's Axioms of Geometry Given below is the axiomatization of geometry by David Hilbert (18621943) in Foundations of Geometry (Grundlagen der Geometrie), 1902 (Open Court edition, 1971). This was logically a much more rigorous system than in Euclid. I. Axioms of Incidence: – For every two points A, B there exists a line a that contains each of the points A, B. – For every two points A, B there exists no more than one line that contains each of the points A, B. – There exist at least two points on a line. There exist at least three points that do not lie on a line.

– For any three points A, B, C that do not lie on the same line there exists a plane [alpha] that contains each of the points A, B, C. For every plane there exists a point which it contains. – For any three points A, B, C that do not lie on one and the same line there exists no more than one plane that contains each of the three points A, B, C. – If two points A, B of a line a lie in a plane [alpha], then every point of a lies in the plane [alpha]. – If two planes [alpha], [beta] have a point A in common, then they have at least one more point B in common. – There exist at least four point which do not lie in a plane.

II. Axioms of Order: – If a point B lies between a point A and a point C, then the points A, B, C are three distinct points of a line, and B then also lies between C and A. – For two points A and C, there always exists at lest one point B on the line AC such that C lies between A and B. – Of any three points on a line there exists no more than one that lies between the other two. – Let A, B, C be three points that do not lie on a line and let a be a line in the plane ABC which does not meet any of the points A, B, C. If the line a passes through a point of the segment AB, it also passes through a point of the segment AC, or through a point of the segment BC.

III. Axioms of Congruence: – 1. If A, B are two points on a line a, and A' is a point on the same or on another line a' then it is always possible to find a point B' on a given side of the line a' through A' such that the segment AB is congruent or equal to the segment A'B'. In symbols AB A'B'. – If a segment A'B' and a segment A"B", are congruent to the same segment AB, then the segment A'B' is also congruent to the segment A"B", or briefly, if two segments are congruent to a third one they are congruent to each other. – On the line a let AB and BC be two segments which except for B have no point in common. Furthermore, on the same or on another line a' let A'B' and B'C' be two segments which except for B' also have no point in common. In the case, if AB A'B' and BC B'C' then AC A'C'.

– Let angle(h,k) be an angle in a plane [alpha] and a' a line in a plane [alpha]' and let a definite side of a' in [alpha]' be given. Let h' be a ray on the line a' that emanates from the point O'. Then there exists in the plane [alpha]' one and only one ray k' such that the angle(h,k) is congruent or equal to the angle(h',k') and at the same time all interior point of the angle(h',k') lie on the given side of a'. Symbolically angle(h,k) angle(h',k'). Every angle is congruent to itself, i.e., angle(h,k) angle(h,k) is always true. – If for two triangles ABC and A'B'C' the congruences AB A'B', AC A'C', angleBAC angleB'A'C' hold, then the congruence angleABC angleA'B'C' is also satisfied.

IV. Axiom of Parallels: – (Euclid's Axiom) Let a be any line and A a point not on it. Then there is at most one line in the plane, determined by a and A, that passes through A and does not intersect a.

V. Axioms of Continuity: – (Archimedes' Axiom or Axiom of Measure) If AB and CD are any segments, then there exists a number n such that n segments CD constructed contiguously from A, along the ray from A through B, will pass beyond the point B. – (Axiom of Line Completeness) An extension of a set of points on a line with its order and congruence relations that would preserve the relations existing among the original elements as well as the fundamental properties of line order and congruence that follow from Axioms I-III, and from V,1 is impossible.

Examples of geometry proofs

Supply the reasons for the steps in the following proof. Given: 1 and 2 are supplementary 3 and 4 are supplementary 2 4 Prove: 1 3 Statement 1) 1 and 2 are supplementary 3 and 4 are supplementary 2) m 1 and m 2 180 m 3 and m 4 180 3) m 1 and m 2 m 3 and m 4 4) 2 4 5) m 2 m 4 6) m 1 m 3 7) 1 3 QED Reason 1) Given 2) Definition of Supplementary Angles 3) Transitive Prop of Equalities (or substitution) 4)Given 5) Definition of congruent angles 6) Substitution Property 7) Definition of congruent angles

The diagram is an interpretation of the assumptions. The two lines in the diagram are the meaning of the symbol 1 in the assumption. Other diagrams would be other interpretations of these assumptions.

1 1 )C o m p leteth ep ro o f. BC G iv en : AC 3isc o m pto 1 P ro v e: 3 2

Statem ent BC 1) AC 3iscom pto 1 2)m A C B 90 3)m 1 m 2 m A C B 4)m 1 m 2 90 5)m 3 m 1 90 6)m 3 m 1 m 1 m 2 7)m 1 m 1 8)m 3 m 2 9) 3 2 Q E D R eason 1)G iven 2)D ef lines 3) addpostulate 4)transitiveprop. 5)defcom p ’s 6)transprop 7)reflexiveprop 8)subtractionpropof 9)defofcongruentangles

The line in the diagram is the meaning of the symbol AC in the hypotheses. Thus the diagram is an interpretation of the hypotheses of the theorem.

Given: m 1 m 2 m 3 m 4 Prove: YS XZ

Statem ent 1) m 1 m 2 m 3 m 4 2) m SY X m SY Z 180 3)m 1 m 3 m SY X m 2 m 4 m SY Z 4)m 1 m 3 m 2 m 4 180 5)m 1 m 3 m 1 m 3 180 6)2m 1 2m 3 180 7)m 1 m 3 90 8)m SY X 90 XA 9) YS Q E D R eason 1)G iven 2) addpost 3) addpost 4)substitution 5)substitution 6)substitution 7)divisionpropof 8)substitution 9)D ef of lines

A Turing machine could generate all possible proofs in an attempt to prove a theorem in geometry. Thus there is a theorem prover for geometry.

Propositional (Boolean) Logic Formulae are composed of Boolean variables p,q,r, and Boolean connectives: (conjunction, “and”) (disjunction, “or”) (negation, “not”) (implication, “if then”) (equivalence, “if and only if”)

Example formula –p q p Interpretation: – “It is raining” and “It is Tuesday” implies “It is raining. Another interpretation: – “All birds are green” and “All fish are purple” implies “All birds are green.” Both interpretations make the formula true. The formula is valid (true in all interps.)

Another example formula: –p q p Interpretation: – 2 2 3 3 2 2 Another interpretation: – 2 2 3 3 2 2 The first interpretation makes the formula false. The second makes it true. The formula is not valid.

Validity can be determined by truth tables.

Truth Tables 1st Conjunct A true true false false Truth Table for Conjunctions 2nd Conjunct B true false true false Statement A B true false false false 1st Disjunct A true true false false Truth Table for Disjunctions 2nd Disjunct B true false true false Statement A B true true true false

Antacedent A true true false false Truth Table for Conditionals Consequent B true false true false Statement A B true false true true Antacedent A true true false false Truth Table for Equivalences Consequent B true false true false Statement A B true false false true Truth Table for Negations Statement A true false Negation A false true

Interpretations assign meanings to symbols. In Boolean logic interpretations assign truth values (true, false) to the symbols. An interpretation in Boolean logic is called a valuation. Thus a valuation I is an assignment of truth values (true or false) to each variable in a formula

Example: Consider the formula (X Y) X. An example of an interpretation of this formula assigns true to X and false to Y. This interpretation makes the formula true. Another example interpretation assigns false to X and true to Y. This interpretation makes the formula false.

If X is a formula then I(X) is the value of X with truth values assigned as in I. Thus I(X1 X2) true iff I(X1) true and I(X2) true, et cetera. A formula X is satisfiable if for some I, I(X) is true. Such an I is called a model of X. A formula is valid if for all I, I(X) is true.

A valid formula P T T F F Q T F T F P Q T F F F P Q P T T T T A satisfiable invalid formula P T T F F Q T F T F P Q T F F F (P Q) Q T F T F

An unsatisfiable formula: P P P P P P T F F F T F

Valid formulas are also called tautologies. Unsatisfiable formulas are contradictions. One can test validity of a formula with n variables by 2n evaluations. Thus a Turing machine can test validity of propositional formulae. So there is a theorem prover for Boolean logic. The validity problem for Boolean logic is decidable.

NP completeness: What is the fastest algorithm to test satisfiability of Boolean formulae? The answer is not known. But all known algorithms take exponential time in the worst case.

First Order Logic Formulae may contain Boolean connectives and also variables x, y, z, , predicates P,Q,R, , function symbols f,g,h, , and quantifiers and meaning “for all” and “there exists.” Example: x(P(x) yQ(f(x),y))

Individual Constants Formulae can also contain constant symbols like a,b,c which can be regarded as functions of no arguments. Example: x(P(x) Q(x,c))

Interpretations assign meanings to the symbols in a logic. First-order formulae have interpretations that interpret predicate symbols as predicates, function symbols as functions, variables as elements of a nonempty set (the domain) and individual constants as particular elements of the domain. Boolean connectives and quantifiers are given the expected interpretations.

Interpreting first order formulae To translate a first order formulae into English, – choose a set of objects (people, integers for example) as the domain – choose a meaning (interpretation) for the predicate and function symbols Translate xA as “for all x, A” Translate xA as “there exists x such that A”

Translate Boolean connectives as follows: – – – A B as “A and B” A B as “A or B” A B as “if A then B” A as “not A” – A B as “A if and only if B” Translate predicate symbols in English – P(x,y) as “x loves y”, “x is a child of y”, et cetera. This assigns a meaning to P. – f(x) as “the age of x,” “the father of x”, et cetera. This assigns a meaning to f.

If the domain is the set of people and P(x,y) is interpreted as “x is a child of y” then the formula x yP(x,y) is translated as “for all x there exists y such that x is a child of y.” It can also be translated as “for all persons x there exists a person y such that person x is a child of person y.” In other words, everyone is a child of someone. This formula is true under this interpretation.

If the domain is the set of people and P(x,y) is interpreted as “x is a parent of y” then the formula x yP(x,y) is translated as “for all x there exists y such that x is a parent of y.” In other words, everyone has a child. This formula is false under this interpretation. Thus this formula is true under at least one interpretation but not true in all interpretations.

A formula X that is true under at least one interpretation I is satisfiable. Such an I is called a model of X. A formula that is true under all interpretations is said to be valid.

Consider the formula y xP(x,y) x yP(x,y). Let the domain be the set of people, and let P(x,y) be “x loves y”. The formula then is interpreted as “if there exists y such that for all x, x loves y, then for all x, there exists y such that x loves y.” In other words, if there is someone that everyone loves, then everyone loves someone. The formula is true under this interpretation.

In fact this formula is true under all interpretations, and is a valid formula. Consider this formula: x yP(x,y) y xP(x,y). Under the same interpretation, this formula becomes “If for all x, there exists y such that x loves y, then there exists y such that for all x, x loves y.” In other words, if everyone loves someone, then there is someone that everyone loves. This formula is false under this interpretation and is not a valid formula.

The validity problem for first-order logic has the set of first-order formulae as the base set. The right answer is “yes” if the formula is valid and “no” otherwise. The validity problem for first-order logic is undecidable (unsolvable). But it is partially decidable. Therefore there is a Turing machine theorem prover for first-order logic.

Peano axioms There is a natural number 0. Every natural number a has a successor, denoted by a 1. There is no natural number whose successor is 0. Distinct natural numbers have distinct successors: if a b, then a 1 b 1. If a property is possessed by 0 and also by the successor of every natural number it is possessed by, then it is possessed by all natural numbers.

Peano Axioms in Higher Order Logic Nat(0) x(Nat(x) Nat(s(x))) x(Nat(x) s(x) 0) x y(Nat(x) Nat(y) x y s(x) s(y)) P[P(0) x(P(x) Nat(x) P(s(x))) x(Nat(x) P(x))]

Induction in Peano Arithmetic Using the last axiom, to show that x(Nat(x) P(x)) it suffices to show – P(0) and x(P(x) Nat(x) P(s(x))) This is mathematical induction

Many proofs about integers can be done in Peano arithmetic but not first-order logic. The quantification over P is not allowed in firstorder logic. To get an effective logic, properties can be restricted to those that are expressible by a firstorder formula. This makes Peano arithmetic into an infinite set of first-order formulas, but still much more powerful than first-order logic.

Making Peano axioms first order Only the last axiom is the problem For all first order formulae A with one free (unquantified) variable, have the axiom – A[0] x(A[x] Nat(x) A[s(x)]) x(Nat(x) A[x]) This gives an infinite set of first-order axioms and makes Peano arithmetic effective. Some expressivity is lost.

Instance of last axiom Let A[x] be y(x y y x). Then the first-order instance of the last axiom is y(0 y y 0) x ( y(x y y x) Nat(x) y(s(x) y y s(x))) x(Nat(x) y(x y y x)) Different formulas A generate different instances of this axiom

Proofs in Peano Arithmetic Peano arithmetic permits mathematical induction Do some proofs of properties of the integers in Peano arithmetic, possibly defining addition and showing it is commutative Maybe also prove the distributive law Such proofs require induction and cannot be done in first-order logic

Nonstandard models of integers The compactness theorem: a set of first-order sentences is satisfiable, i.e., has a model, if and only if every finite subset of it is satisfiable. Applies to infinite sets of axioms. Consequence: any theory that has an infinite model has models of arbitrary large cardinality. So, for instance, there are nonstandard models of Peano arithmetic with uncountably many natural numbers.

Zermelo-Fraenkel set theory The ten axioms of ZFC are listed below. (Strictly speaking, the axioms of ZFC are just strings of logical symbols. What follows should therefore be viewed only as an attempt to express the intended meaning of these axioms in English. Moreover, the axiom of separation, along with the axiom of replacement, is actually an infinite schema of axioms, one for each formula.) The axioms of choice and regularity are still controversial today among a minority of mathematicians.

Axiom of extensionality: Two sets are the same if and only if they have the same elements. Axiom of empty set: There is a set with no elements. We will use {} to denote this empty set. Axiom of pairing: If x, y are sets, then so is {x,y}, a set containing x and y as its only elements. Axiom of union: For any set x, there is a set y such that the elements of y are precisely the elements of the elements of x. Axiom of infinity: There exists a set x such that {} is in x and whenever y is in x, so is the union y U {y}. Axiom of separation (or subset axiom): Given any set and any proposition P(x), there is a subset of the original set containing precisely those elements x for which P(x) holds.

Axiom of replacement: Given any set and any mapping, formally defined as a proposition P(x,y) where P(x,y) and P(x,z) implies y z, there is a set containing precisely the images of the original set's elements. Axiom of power set: Every set has a power set. That is, for any set x there exists a set y, such that the elements of y are precisely the subsets of x. Axiom of regularity (or axiom of foundation): Every nonempty set x contains some element y such that x and y are disjoint sets. Axiom of choice: (Zermelo's version) Given a set x of mutually disjoint nonempty sets, there is a set y (a choice set for x) containing exactly one element from each member of x.

First order forms of ZFC axioms A, B, A B ( C, C A C B) (extensionality) A, B, (B A) (empty set) A, B, C, D, D C (D A D B) (pairing) A, B, C, C B ( D, D A C D) (union) ω, {} ω ( x, x ω x {x} ω) (infinity) A, B, C, C B (C A P(C)) (specification)

( X, ! Y, P(X,Y)) A, B, C, C B ( D, D A P(D,C)) (replacement) A, B, C, C B ( D, D C D A) (power set) S, ( S {} a, (a S a S {})) (regularity) Let X be a collection of non-empty sets. Then we can choose a member from each set in that collection. That is, there exists a function f defined on X such that for each set S in X, f(S) is an element of S. (axiom of choice)

The specification and replacement axioms are axiom schemata, and represent infinitely many first-order formulas. The elememts of ω in the infinity axiom can be regarded as integers. ZFC set theory is an infinite set of first-order axioms. Thus it also has nonstandard models of the integers. ZFC can be used to define the real numbers, imaginary numbers, continuous functions, integration, and differentiation.

We have seen a number of logics: Aristotelian logic, geometry, propositional calculus, first order logic, Peano axioms, and ZFC set theory. All these logics have Turing machine theorem provers. This permits one to show incompleteness of the Peano axioms and ZFC using the halting problem.

One can also show that “nonstandard models” exist because of the incompleteness of these logics. True statements in a logic L are true in all standard models Provable statements in L are true in all standard and nonstandard models. Thus if there is a statement that is true but not provable, then L has a nonstandard model.