Transcript 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
(1862-1943) 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.
11) Complete the proof.
Given: AC  BC
3 is comp to 1
Prove: 3  2
Statement
1) AC  BC
3 is comp to 1
2) m ACB = 90
3) m1 + m2 = mACB
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
QED
Reason
1) Given
2) Def  lines
3)  add postulate
4) transitive prop. =
5) def comp ’s
6) trans prop =
7) reflexive prop =
8) subtraction prop of =
9) def of congruent angles
• 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
Statement
1)
m1 = m2
m3 = m4
2) mSYX + mSYZ = 180
3) m1 + m3 = mSYX
m2 + m4 = mSYZ
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SYX = 90
9) YS  XA
QED
Reason
1) Given
2)  add post
3)  add post
4) substitution
5) substitution
6) substitution
7) division prop of =
8) substitution
9) Def 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.