J.-M. Kuczynski Introduction The propositional calculus: Definitions Propositional calculus: Theorems Predicate calculus, Set Theory, and Boolean Algebra: Definitions Predicate Calculus: Derived definitions Predicate calculus: Theorems Boolean Algebra: Theorems Modality Set Theory: Axioms and basic theorems Advanced Set Theory: Definitions Advanced Set Theory: Principles and Derived Definitions Advanced Set Theory: Recursivity Recursivity in relation toN A recursive definition ofQ No recursive definitions ofR [PK]>[K] No recursive definition of the class of recursive definitions Formal languages: introductory points Natural languages as recursive sentence-classes Formal languages as recursive sentence-classes Definition of "formal truth" No formal characterization of the property of formal truth Function-theoretic Characterizations of Logical Operations Arithmetic Two set-theoretic interpretations of arithmetic Von Neumann's set-theoretic interpretation of arithmetic J.-M. Kuczynski Von Neumann arithmetic (continued) Frege's set-theoretic interpretation of arithmetic Fregean formalizations of the previously mentioned recursive definitions of +, ×, and ζ General definition of cardinal number Isomorphism The concept of a mathematical model Recursivity as categoricity Incompleteness (non-recursivity) identical with non-categoricity Introduction In the present volume, I state, as clearly and concisely as possible, the central tenets of settheory and mathematical logic. In Part 2, I identify the model-theoretic underpinnings of the contents of this volume. In Part 3, I discuss the philosophical underpinnings of the contents of Part 2. The propositional calculus: Definitions P⋁Q P or Q P⋀Q P and Q ¬P Not P P→Q ¬(P⋀¬Q) P↛Q J.-M. Kuczynski ¬(P→Q) P↔Q (P→Q)⋀(Q→P) P/Q ¬P⋀¬Q P↛Q ¬(P→Q) ¬P→Q P unless Q Propositional calculus: Theorems (¬P∨Q)↔¬(P⋀¬Q) (P→Q)↔(¬P∨Q) ¬(P⋀Q) ↔(¬P∨¬Q) ¬(P∨Q) ↔(¬P⋀¬Q) P→P Self-entailment P↔¬¬P J.-M. Kuczynski Double Negation P∨¬P Excluded Middle ¬(P⋀¬P) Non-contradiction (P∨Q)↔(Q∨P) Interchange (P⋀Q)↔(Q⋀P) Interchange (¬P∨Q)↔(P→Q) (P⋀(P→Q))→Q Modus Ponens ((P→Q)⋀¬Q)→¬P Modus Tollens ((P∨Q)⋀¬P)→Q DeMorgan's (P→¬P)→¬P Statements are false that self-refute. (¬P→P)→P Statements are true that self-verify. J.-M. Kuczynski (P⋀¬P)→Q Nothing doesn't follow from a contradiction. P→(Q∨¬Q) Nothing doesn't entail a tautology. (P→(Q⋀¬Q))→¬P No contradiction follows from a truth. ((Q∨¬Q)→P)→P No falsehood follows from a tautology. P→(P∨Q) Logical Addition (P⋀Q)→P Simplification ((P→Q)⋀(Q→R))→(P→R) Transitivity (P→Q)→((Q→R)→(P→R)) Transitivity P→Q→((P⋀R)→Q) Monotony P↔(P⋁P) Precursor of n+0=n P↔(P⋀P) J.-M. Kuczynski Precursor of nx1=n (P⋁(Q⋀¬Q))↔P Absorption (P⋀(Q⋁¬Q))↔P Absorption P⋁(Q⋀R)↔((P⋁Q)⋀P⋁R)) P⋀(Q⋁r)↔((P⋀Q)⋁(P⋀R)) ¬(P⋁Q)↔(¬P⋀¬Q) ¬(P⋀Q)↔(¬P⋁¬Q) P/ Q↔DF(¬P⋀¬Q) (P/P)/( P/P) P ((P/P)/(P/P))/(Q/Q) P⋀¬Q ¬(P→Q) (((P/P)/(P/P))/(Q/Q))/(((P/P)/(P/P))/(Q/Q)) ¬(P⋀¬Q) P→Q J.-M. Kuczynski Predicate calculus, Set Theory, and Boolean Algebra: Definitions {x: φx} The extension of φ. φ The intension of {x: φx} x∈k x is a member of k x∉k ¬x∈k ∀xφx For all x, φx ∃xφx For some x, φx k⋃k* {x: x∈k⋁x∈k*} k⋂k* {x: x∈k⋀x∈k*} Ck The complement of k {x: x∉k} J.-M. Kuczynski V The universal class {x: x=x} [k] The number of objects in k k's cardinal number k≈k* [k]=[k*] Predicate Calculus: Derived definitions ¬∀xφx It is not the case that, for all x, φx For some x, ¬φx ¬∃xφx Nothing has φ ∀x¬φx Everything is a non-phi. ¬∃xφx↔∀x¬φx ∃x(φx⋀ψx) For some x, φx and ψx ∀x(φx→ψx) All φ's are ψ's. J.-M. Kuczynski ∃x(φx⋀¬ψx) Not all φ's are ψ's. Predicate calculus: Theorems φx↔x∈{y:φy} ∃xφx↔¬∀x¬φx ∀xφx⋀∀xψx↔∀x(φx⋀ψx) ∃x(φx⋀ψx)→(∃xφx⋀∃xψx) (∃xφx⋀∃xψx)↛∃x(φx⋀ψx) ∀xφx→(∀xφx∨∀xψx) α=β→(φα↔φβ) Indiscernibility of identicals. (φα↔φβ)→α=β Identity of indiscernibles. ((α∈k1→α∈k2)⋀(α∈k2→α∈k3))→(α∈k1→α∈k3) Transitivity α∈k↔ α∈CCk Double Negation J.-M. Kuczynski α∈k→(α∈k⋁α∈k*) Logical Addition (α∈k⋀α∈k*)→α∈k Simplification (α∈k⋀α∈k*)↔(α∈k*⋀α∈k) ((α∈k⋁α∈k*)⋀α∉k)→α∈k* ((α∈k→α∈k*)⋀α∈k))→α∈k* ((α∈k→α∈k*)⋀α∉k*)→α∉k ¬∃xφx→∀x(φx→ψx) ¬∃xφx→∀x(φx→¬ψx) P↔∀xP P↔∃xP Boolean Algebra: Theorems k1⋃(k2⋂k3)=(k1⋃k2)⋂(k1⋃k3) Analogue of (p⋁(q⋀r))↔((p⋁q)⋀(p⋁r)) k1⋂(k2⋃k3)=(k1⋂k2)⋃(k1⋂k3) Analogue of (p⋀(q⋁r))↔((p⋀q)⋁(p⋀r)) J.-M. Kuczynski k1=k1⋃k1 Analogue of P→P⋁P k1= k1⋂k1 Analogue of P→P⋀P k⋃∅=k k⋂V=k k1⋃(k1⋂k2)=k1 Absorption k1⋂(k1⋃k2)=k1 Absorption CCk=k Ck=∅↔k=V Modality □P Necessarily P ◊P Possibly P A truth is necessary if it follows from any given statement-set. □P↔∀Q(Q→P) J.-M. Kuczynski A truth is necessary if its negation does entails a contradiction. □P↔∃Q(¬P→ ( Q⋀¬Q)) A truth is possible if it does not entail a contradiction. ◊P↔¬∃Q(P→(Q⋀¬Q)) A truth is possible if its negation is not necessary. ◊P↔¬□¬P A truth is necessary if its negation is not possible. □P↔¬◊¬P What is necessary is actual. □P→P What is actual is possible. P→◊P (□P⋀□Q)↔□(P⋀Q) ◊(P⋀Q)→(◊P⋀◊Q) (◊P⋀◊Q)↛◊(P⋀Q) Set Theory: Derived Definitions ∀x∀y(φx⋀φy↔x=y) At most one thing has φ. ∃x(φx⋀∀y(φy→x=y)) J.-M. Kuczynski Exactly one thing has φ. ∃x∀y(φx⋀(φy→x=y)) Exactly one thing has φ. ∃x∀y(φy↔x=y) Exactly one thing has φ. ∃x∃y(φx⋀φy⋀x≠y) At least two things have φ. ∀x∀y∀z(φx⋀φy⋀(φz↔y=z)) At most two things have φ. ∃x∃y(φx⋀φy⋀x≠y⋀∀z(φz→(x=z⋁y=z))) Exactly two things have φ ∃x∃y∀z(φx⋀φy⋀x≠y⋀(φz→(x=z⋁y=z))) Exactly two things have φ k=k*↔∀x(x∈k↔x∈k*) Set Theory: Axioms and basic theorems Classes are identical when membership-identical (Axiom of Extensionality) k=k*↔(α∈k↔α∈k*) Any given property generates a class (Axiom of Comprehension) ∀φ∃k∀x(x∈k↔φx) J.-M. Kuczynski There is at most one empty class. ∀k∀x(x∉k→k=∅)) There is exactly one empty class ∃k∀x(k=∅↔x∉k) [k]=0↔k≈∅ [k]=1↔k≈{∅} [k]=2↔k≈{{∅},∅} [k]=3↔k≈{{{∅},∅},{∅},∅} [k]=n+1↔∃k*([k*]=n⋀k≈{x:x∈k*⋁x=k}) [k]=0↔¬∃x(x∈k) [k]=0↔∀x(x∉k) [k]=1↔∃x∀y(y∈k ↔x=y) [k]=2↔∃x∃y∀z(x∈k⋀y∈k⋀x≠y⋀(z∈k→(x=z⋁y=z)) [k]=n+1↔∀k*∃x∀y((x∈k⋀x∉k*⋀(x≠y→y∈k*))→[k*]=n) k has n+1 members exactly if k* has n members, where k* is any class such that, for some x, x∈k and x∉k* and such that k and k* are otherwise membership-identical. [k]=1↔∀k*(([k*]=0⋀α∉k*)→[k*⋃α]=[k]) J.-M. Kuczynski [k]=n+1↔∀k*(([k*]=n⋀α∉k*)→[k*⋃α]=[k]) Advanced Set Theory: Definitions CP(k⋃k*)={α:∃β∃γ(β∈k⋀γ∈k*⋀(α=(β,γ)⋁ α=(γ,β))) The Cartesian Product of k and k* is the smallest class K such that, whenever x belongs to k and y belongs to k*, (x,y)∈K and (y,x)∈K k=ΣK k is a selection from K k is a selection from K, where K is a class of classes, if, whenever k* belongs to K, exactly one member of k* is a member of k. k=ΣK↔DF∀k*(k*∈K→[k⋂k*]=1) k=ΣK↔DF∀k*(k*∈K→∃x(x∈k*⋀x∈k⋀∀y((x≠y⋀y∈k*)→y∉k))) A function is a rule that assigns exactly one object (an ordered n-tuple, in the case of functions of more than variable) to each member of some class of objects. φ(x)=y→(φ(x)=z→y=x) φ is a one-one function if, for some function ψ, ψ(y)=x whenever φ(x)=y. φ is a one-one function from k to k* if there some function ψ such that, for any element x of k, there is some element y of k* such that φ(x)=y↔ ψ(y)=x. k and k* are bijected by a function φ just in case φ is a one-one function from k to k*. [k]=[k*] iff there is a one-one function from k to k*. [k]=[k*]↔∃φ∃ψ∀x∃y (x∈k →(y∈k*⋀φ(x)=y⋀ ψ(y)=x)) J.-M. Kuczynski For any class K, PK is the class of all subsets of K PK={k: k⊂K} [Pk]=2[k] Proof by induction First suppose that k=∅. In that case, [Pk]=1. Therefore, if [k]=0, then [Pk]=2[k]. Lemma: If [Pk]=2n, then 2[k∪α]=2n+1, whenever α∉k. Proof of lemma ∀k*(k*∈Pk⟶α∉k*) For each subset of k that does not contain α, there is exactly one subset of k that does contain α. Symbolically,∀k#(k#∈Pk⋃α∧α∉k#)⟶∃1k^(k^∈Pk∧α∈k^) Therefore, [Pk⋃α]=[Pk]×2. Therefore, when α∉k, 2[k∪α]=2[k] × 2. Therefore, when α∉k, 2[k∪α]=2[k]+1. Therefore, if [k]=n and [Pk]=2n, then [Pk⋃α]= 2n+1, whenever α∉k. Therefore, [Pk]=2[k]. Q.E.D. Advanced Set Theory: Principles and Derived Definitions Cardinal Number: The number of elements in a class. When you ask "how many?", you are asking for a cardinal number. (When you ask 'how many dogs does Jim have?', you are asking 'how large is k?', where k is the class of Jim's dogs). Ordinal number: An ordinal number is position. In the series 0,1,2,3...n...,1's ordinal number is 2. In the series, 1,2,3...n..,1's ordinal number is 1. Signed Integer: +x is the relation that n bears to m when n-x=m, and -x is the relation that n bears to m when n+x=m. J.-M. Kuczynski For example, +4 is the relation that n bears to m when n-4=m, and -4 is the relation that n bears to m when n+4=m. Rational: m/n is the relation that x bears to y when x×n=y×m. For example, 3⁄4 is the relation that x bears to y when x×4=y×3. Real Number: Real numbers are degrees, a degree being a position in a continuous series. Therefore, a real number is a position in a one-dimensional space. Complex Number: A complex number is a pair of real numbers. Therefore, a complex number is a position in a two-dimensional space. (A,B)={A, {A, B}} An ordered pair is identical with a suitably membered unordered pair. Explanation: When we talk about (3,5), we say that 3 is the "first" member and 5 is the "second." When we talk about {3, {3,5}}, we say that 3 is the "uncoupled" member and 5 is the "coupled" member. It is obviously a matter of indifference whether we distinguish them by using the terms "first" and "second" or "coupled" and "uncoupled". It is necessary only that there be some way of marking the difference between the two. (A,B,C)={A,{A,B,},{A,B,C}} An ordered triple is identical with a suitably membered unordered triple. (A1...An-1, B)={(A1...An-1),{ A1...An-1, B}} An ordered n-tuple is identical with a suitably membered unordered n-tuple. (1,2,3)={1, {1,2}, {1,2,3}} (1,2,3,4)={1, {1,2}, {1,2,3}, {1,2,3,4}} (1,2,3,...n)={1, {1,2}, {1,2,3}, {1,2,3,4},...{1,2,3,...n}} J.-M. Kuczynski A n-membered sequence is an ordered n-tuple and, therefore, a suitably membered unordered n-tuple. R strictly orders k exactly if, whenever x,y,z∈k, (i) ¬xRx (R is non-reflexive) (ii) xRy→¬yRx (R is asymmetric) (iii) (xRy⋀yRz)→xRz (R is transitive) N The class of all cardinal numbers N=DF{x: x=0⋁∃y(y∈N⋀x=y+1)} x is a number just in case x=0 or x=y+1, for some number y. We have just given a recursive definitionofN. It is classes that are recursively defined, a recursive definition of a class k being one of the form: (i) α∈k, and (ii) γ∈k, whenever, for some β such that β∈k, β bears R to γ, where R is a relation that strictly orders k. Z The class of signed integers Z=DF{x:∃y(y∈N⋀(x=+y⋁x=−y))} Q The class of rational numbers J.-M. Kuczynski Q=DF{x:∃p∃q(p∈N⋀q∈N⋀x=p/q)} K is an initial segment ofQ just in case K is a non-empty proper subset of the class of rationals such that x doesn't belong to K unless, whenever y<x, y also belongs to K. SG(K) K is an initial segment ofQ Given some initial segment K ofQ, x is the least upper bound of K just in case (i) x<y, where y is any member of K and (ii) x<z, z is any non-member, other than x itself, of K. L(K)=x x is K's least upper bound. R The class of real numbers. R=DF{x:∃k(SG(k)⋀x=L(k))} C The class of complex numbers C=DF{x:∀y(y∈R⋀((y<0→∃z(z<0⋀z2=y))⋀(y>0→∃w(w<0⋀w2=y))) Series: An ordered pair (k, R), where k is a class and R is a relation that strictly orders k. Progression: A function fromN to k, for some class k. Sequence: The initial part of a progression. (Note: In the present paper, "progression" and "sequence" are used interchangeably.) J.-M. Kuczynski k≈N↔DF[k]=א0 [N]=DFא0 [Q]=א0 k is finite iff k has finitely many members; and k has finitely many members iff [k]=n, where n∈N. k is infinite iff k has infinitely many members; and k has infinitely many members if [k]>n, whenever n∈N. n is an inductive cardinalif n∈N. n is a non-inductive cardinalif, for some k, n=[k] and, whenever m∈N, n>m. k is infinitely large if [k] is a non-inductive cardinal. [k] is transfinite whenever k is infinitely large. A discrete seriesis a sequence, a sequence being a series each of whose non-terminal members has an immediate successor. (N, <) is a discrete series. A compact series is a series that is not discrete; equivalently, a series is compact if there is a member between any two members. (Q, <) is a compact series. A continuous series is a compact series that contains each of its own limiting points. (R, <) is a continuous series. J.-M. Kuczynski L is a sequence-limit iff there is some sequence α1, α2, α3,... αn,...such that, for any ε, there is some ν such that the difference between αν and L is less than ε. Thus, 1 is the limit of 1⁄2, 3⁄4, 7/8, 15/16,... L is a series-limit iff there is some compact series S such that L is the least upper bound of S, meaning that if R is the relation that generates S, then (i) Anything that bears R to L belongs to S, and (ii) Anything to which L bears R does not belong to S. Thus, 1 is the least upper bound, and therefore the limit, of (κ,<), where κ is the class of proper fractions; and √2 is the least upper bound, and therefore the limit, of (κ#,<), where κ# is the class of rationals p/q such that (p/q)2<2. R=DFThe class of limiting points of segments of (Q,<). Continuous series: S is a continuous series if S is a compact series that contains all of its own limiting points. (R,<) is a continuous series. (Q,<) is not a continuous series. This is because no irrational belongs to (Q,<) even though any given irrational is a limiting point of subseries of (Q,<). Advanced Set Theory: Recursivity A function is a relation R such that if x bears R to each of y and z, then y=z. Thus +1 is a function since, if x+1=y and x+1=z, then y=z. A recursive function is one that is defined for each of its own outputs. Thus +1 is a function since 1 can be added to n+1, for any n. A recursion may loop. Cf. When x<9, F(x)=x+1, and x=9, F(x)=1. J.-M. Kuczynski A non-looping recursion is a serial relation. A relation R is serial just in case R is transitive (meaning that if x bears R to y and y bears R to z, then x bears R to z), non-reflexive (meaning that x does not bear R to x), and anti-symmetric (meaning that if x bears R to y, then y does not bear R to x). A class k can be recursively defined just in case k is the posterity with respect to O of α, for arbitrary α, where O is a recursive function. If k is a recursively defined class, then (k, R) is a progression (a non-looping series each of whose members has an immediate successor), where R is the function that generates k. Thus, (N, +1) is a progression. A progression is a non-looping, never-ending sequence. A sequence is the initial part of a progression. (Although I shouldn't do so, I tend to use "progression" and "sequence" interchangeably.) k is recursively defined just in case, for some α and some recursion R, k is the smallest set containing R and containing x whenever, for some y belonging to k, y bears R to x. In other words, k is recursively defined just in case it is the posterity with respect to α of R, where α∈k and where, if x∈k and x bears R to y, then y∈k. Recursivity in relation toN N is recursively defined, given the class of natural numbers is the posterity of 0 with respect to +1. N=DF{x: x=0∨∃y(y∈ N ∧x=y+1). If [k]=N, then k is recursively defined. Proof : Any two progressions can be bijected; two sets are equinumerous if they can be bijected. Explanation of proof:N is recursively defined. If a class C is recursively defined, then C is the posterity of α with respect to R, for some α and some recursion R. Thus, 0 can be associated with α and, if x is associated with n and x bears R to y, n+1 is associated with y. J.-M. Kuczynski If k is recursively defined, then, for arbitrary α, k∪α is recursively defined. Proof: Supposing that k is the posterity of ζ with respect to R, then k∪α is the posterity of R* with respect to α, where ζ bears R* to α but R* is otherwise just like R. A recursive definition ofQ Qis given by the following recursion: n∈Q just in case either (i) n=1/1 or (ii) n∈{α:∃β∃γ∃m(m∈N⋀m>1⋀β+γ=m+1⋀ α=β/γ)}. This definition generates the series: 1/1, 1⁄2, 2/1, 1/3, 3/1, 2/2, 1⁄4, 4/1, 2/3, 3/2, 1/5, 5/1, 2/4, 4/2, 3/3,.... There is no rational that does not occur on this series. Sequences are recursively defined infinite series. Given thatN is recursively definable, it follows that any given infinitely long sequence is recursively definable and also that any recursively definable class can be represented as a sequence. Any two infinite sequences equipollent with each other. Given that any given infinite sequence can be bijected withN, it follows that, if k is recursively definable,N≈k and, consequently, [N]=[k]. This entails that [N]=[Q]. No recursive definitions ofR There is no recursive definition ofR. J.-M. Kuczynski Proof: Let L be an arbitrary list (sequence) of rationals, where each rational is represented as an infinite decimal. In that case, (i) D(L)∈R and (ii) D(L)∉L, where D(L) is generated by (a) Replacing x with x+1, when x<9, and (b) Replacing x with 0, when x=9, where x is the figure in the nth decimal place of the nth member of L. Therefore, there is no sequence, and therefore no recursively definable class, that contains every real number. Q≤R, given that each element ofQcorresponds to some element ofR, andQ<R, given thatR cannot be recursively defined. Qcan be identified with the class of all pairs of cardinals, since any given ordered pair of cardinals determines a unique element ofQ. Similarly,R can be identified with the class of all subsets ofN, since any subset ofNdetermines a unique element ofR. Obviously the class of all integer-pairs can be bijected withN. ButRcannot be bijected with the class of al subsets ofR, since no class can be bijected with the class of its subsets. It follows thatR>Q. And this is the reason whyR>Q, as opposed to a mere proof of the same. [PK]>[K] [PK]>[K], for all K. A set has more subsets than members. Proof: Assume that [PK]=[K]. In that case, there is a function φ that bijects K and PK. Let k be a subset of K such that x∈k just in case x∉φ(x). Let α be a member of K such that φ(α)=k. J.-M. Kuczynski If α∉k, then α∉φ(α), and if α∉φ(α), then α∈k. Therefore, if α∉k, then α∈k. If α∈k, then α∈φ(α), and if α∈φ(α), then α∉k. Therefore, if α∈k, then α∉k. Therefore, φ(α)=k, then α∈k↔ α∉k. Therefore, there is no such that φ(α)=k. In other words, there is no element of K that can be correlated with k. [PK]≥[K], since {x}∈PK whenever x∈K. Therefore, [PK]>[K]. No recursive definition of the class of recursive definitions This last theorem is extremely important; for in it lies the raison d'être for every single incompleteness proof. An incompleteness proof is simply a proof that, for some class C, there is no recursive definition of C. For example, the non-recursivity ofR is really a consequence of the fact that [PK]>[K]. To say that [PK]>[K] is to say that, if R is the recursion that generates K, then R does not generate PK. Let R* be the recursion that generates an arbitrary list (or class) L of real numbers. In that case, R* does not generate PL (the power-set of L), even though, given that L is recursive, so is PL. That said, the union of the elements of PL itself defines a real number. Hence, the nonrecursivity ofR. The non-recursivity ofR is a consequence of the fact that there is no recursive definition of the class of all logically true statements. Explanation/proof: A statement-class is a class of true statements. A logic is a recursively defined class of true statements. I.e. a logic is the posterity of S with respect to Φ, where S is a true statement and Φ is a truth-transmissive operation, meaning that Φ(σ) is true, for any true statement σ. Kurt Gödel's celebrated (1931) incompleteness proof is to the effect that the class of all arithmetical truths is incomplete. A truth of arithmetic is one concerning such interrelations between integers as can be expressed in terms of the following concepts: 0, +, ×, some, all, negation, set-membership, and property. Gödel's theorem is really a special case of a more comprehensive principle, namely, that the class of recursive definitions is not itself recursively defined. Given any class k, there is an J.-M. Kuczynski associated statement-class s(k). If k is itself a statement-class, then k=s(k). If k is not a statement-class, then s(k) is the smallest class of truths of the form x∈k. k is recursive just in case s(k) is recursive, and there is a one-one correspondence between K and S(K), where K is the class of recursive definitions and S(K) is the class of recursively There is a one-one correspondence between the class of recursively defined classes and the class of recursively defined statement-classes. Therefore, supposing that K is not recursively definable, it follows that S(K) is not recursively definable, i.e. it follows that the class of logics is not recursively definable, i.e. it follows that logic is incomplete. And given that [PK]>[K], it follows that, indeed, K is not recursively definable. For if k is a recursively defined class, Pk (the class of all subsets of k) is also a recursively defined class, but the recursion that generates k fails to generate Pk. Therefore, if k is a statement-class-if k is a logic, in other words-then Pk is also a logic, since Pk is a recursively generated statementclass and is ipso facto a logic, but the recursion that generates k fails to generate Pk. Thus, the class of logics is incomplete. In other words, there is no formal procedure by which, when given an arbitrary statement S, to determine whether or not S is a truth of logic. More plainly, the class of logical truths is non-recursive. Gödel's theorem is to the effect that the class of arithmetical truths is non-recursive. Formal languages: introductory points For now, let us regard a language as a class of sentences, a sentence being an expression that expresses a proposition. Languages obviously contain subsentential expressions, but subsentential expressions are of interest only to the extent that they can be absorbed into sentences. Also, in this context, we will set aside the fact that, in English and other natural languages, sentences tend to contain context-sensitive expressions, such as demonstratives (e.g. "that fellow", "this cow") and tense-markers (e.g. the "s" in "John plays rugby"), in virtue of which it is sentence-tokens, not sentences per se, that are true or false. ("It is raining" per se is neither true nor false, it being tokens (specific utterances or inscriptions) of that sentence that are true or false.) J.-M. Kuczynski In order to understand the concept of a formal language, we must introduce two new concepts: the concept of strict or actual entailment and the concept of syntactic entailment. P strictly entails Q if Q is a logical consequence of P. Q is a logical consequence of P if there is no possible world where P is true and Q is false. P⟹Q≡DF Q is a logical consequence of P. S1↦S2≡DF S2 is a syntactic consequence of S1. Strict entailment is a relation between propositions (a proposition being a truth or a falsehood). Propositions are not symbols. The proposition that snow is white can be expressed by symbols of different languages; it is not itself a symbol. Syntactic entailment is a relation between symbols. Sm syntactically entails Sn (i.e. Sm↦Sn) if the following four conditions are satisfied: (i) Sm and Sn both belong to some language L, (ii) L the posterity with respect to S1 (this being a sentence or class of sentences) of some recursion Φ, (iii) Sn is in the Φ-posterity of Sm, and (iv) Sm is not in the Φ-posterity of Sn, except in the case where Sn=Sm. Natural languages as recursive sentence-classes A language is a recursively defined class of sentences. Explanation: It is a datum that English and Spanish and other so-called natural languages are, indeed, languages. Any given natural language contains infinitely many sentences. This is because any given sentence or n-tuple of sentences belonging to a given natural language can be combined into a new sentence, e.g. "snow is not white" can be converted into "John is happy about the fact that snow is which", which in turn can converted into "John is happy about the fact that John is happy about the fact that snow is white", and so on. Therefore, a 'language' that contains only finitely many expressions is but a caricature of a bona fide language. J.-M. Kuczynski At the same time, no natural language, and therefore no language in legitimate sense of the word, contains non-denumerably many expressions. A language is a class of comprehensible expressions. (Indeed, "incomprehensible expression" is a veritable oxymoron.) If L is an infinitely large expression-class, it is not possible to memorize the meanings of L's members. Therefore, L-expressions, if understood, are understood on the basis of other L-expressions. To say that one expression S2 is understood on the basis of some other expression S1 is to say that, for some recursion Φ, it is already known that: (i) Φ(S1)=S2, and (ii) if σα means such and such, then, if Φ(σα)= σβ, then σβ means thus and such. Formal languages as recursive sentence-classes In the expression "formal language", the word "language" has the same meaning that it has in the expression "natural language." In fact, there is no intrinsic difference between a formal language and a natural language. The class of natural languages is a proper subset of the class of formal languages. When a language L is described as "formal", what is meant is that it can be immediately be said exactly what Φ and Ψ are, where Φ is L's syntax is and Ψ is L's semantics. This condition is obviously met where artificial languages are concerned, simply because, given any such language, we stipulate what those values are. This condition is not met where natural languages are concerned, since we don't stipulate what those values are and therefore have to figure out what those values are. And given how expressively rich natural languages are, it cannot be readily figured out what Φ and Ψ are. But their approximate values can be determined quickly but non-immediately, and their specific values can be determined non-immediately and non-quickly. That said, there is one intrinsic difference between formal (artificial) and natural languages, namely, that any given natural language is really hierarchy of languages. What this means, and why it is true, will presently be made clear. J.-M. Kuczynski Definition of "formal truth" Logic is often described as the study of "formal truth." Depending on how it is taken, this characterization is either meaningless or false. An individual logic L is a recursively defined class of true sentences. To say that a given a sentence Sn is formally true is to say that that Sn belongs to the posterity of S1 with respect to φ, where S1 is a true statement (or class of true statements) and φ is a truth-transmissive function. If that condition is met, then Sn is formally true with respect to (S1, φ). But given any true statement σn, there are infinitely many pairs (σ1, Φ), where σ1 is a true sentence and Φ is a truth-transmissive function, such that σn is not formally true with respect to (σ1, Φ). Thus, the concept of formal truth is a relative notion. The class of recursive statement-classes is non-recursive. We proved this earlier. It follows that the class of logics is non-recursive. We also proved this earlier, but here is another proof. No formal characterization of the property of formal truth Proposition: The class of logics is non-recursive. Proof: If an expression-class L is expressively rich enough to be described as a language, then L is negation-complete, meaning that whenever SL belongs to L, so does not-SL. A logic is simply a language---that is, a recursively defined sentence-class---that has been purged of its false members. Given any sentence-pair (SL, not-SL), each of whose members belongs to L, exactly one member of that pair is true. Let L* be the class of true members of L. There obviously exists a one-one function that assigns each member SL* of L* to (SL, notSL). Therefore, there is a one-one correspondence between the class of negation-complete languages and the class of logics. J.-M. Kuczynski Therefore, the class of logics is recursive exactly if the class of languages is recursive, and the class of logics is recursive exactly if the class of languages is non-recursive. The class of languages is non-recursive. A language is simply a recursively defined statement-class, and it has already been proved that the class of recursively defined statementclasses is non-recursive. Therefore, the class of logics is non-recursive. Therefore, there is no recursive definition of the class of logical truths. Therefore, if S is formally true with respect to (σ1, Φ1), there is some other pair (σ2, Φ2) with respect to which S is not formally true. In other words, there is no formal characterization (no recursive definition) of the class formal truths (the class of logics, i.e. of recursively defined classes of true sentences). Function-theoretic Characterizations of Logical Operations ¬ (negation) is a function that assigns truth to P when P is false; otherwise, falsity. ∧ (conjunction) is a function that assigns truth to (P,Q) when P is true and Q is true; otherwise, falsity. ∨(disjunction) is a function that assigns truth to (P,Q) when (¬P∧¬Q) is false; otherwise, falsity. A given property φ is a function that assigns truth to each of its instances and falsity to everything else. ∃x (there exists and an x such that...) is a function that assigns truth to φ when φ is instantiated; otherwise, falsity. (x) (for all x...) is a function that assigns truth to φ when ¬ φ is uninstantiated; otherwise, falsity. / is a function that assigns truth to P/Q exactly if P is false and Q is false. ⟹ (sign of the consequence-relation) is a function that assigns truth to (P,Q) whenever it is impossible that Q should be false if P is true. A truth is a class of a properties p1...pn such that, for all i (1≤i≤n), pi is instantiated. A falsehood is class of a properties p1...pn such that, for some i (1≤i≤n), pi is not instantiated. J.-M. Kuczynski 0 is a function φ that assigns T to∅. n+1 is a function φ that assigns T to k∪{x}, where x∉k, when φ assigns T to k. Arithmetic An operation is a function from ordered n-tuples to ordered n-tuples. All functions are operations and vice versa, with the qualification that the term "operation" is usually reserved for explanatorily significant functions, such as +, ×, and ζ (exponentiation), these being the three primary arithmetical operations. Arithmetic is the smallest class of truths that can be expressed in terms of the following concepts: 0 1 + × ∃ ∀ ¬ → Function Class ∈ Property Relation This list can be compressed, given that ∀xφx is equivalent with ¬∃x¬φx and given also that m×n=0 is a compressed way of saying that o is the nth iterate of the operation of adding m to 0. +, ×, and ζ (exponentiation) are given by the following recursions: J.-M. Kuczynski α+0=α; α +(β+1)=(α+β)+1 α ×0=0; α×(β +1)=(α ×β)+α αβ =1; αβ+1= αβ×α Two set-theoretic interpretations of arithmetic We will now show how to formalize arithmetical truths. The first formalization is due to John von Neumann (1920). The second is due to Gottlob Frege (1884). To formalize a class of truths is simply to express them in such a way that their logical properties can be read off of their syntax. Let us start by defining three functors "S" (short for "sum"), "P" (short for "product"), "E" (short for "exponent"), which express, respectively, addition, multiplication, and exponentiation; and we then express the recursions in question in our new notation: S0(α)=α; Sβ+1(α)=Sβ(α)+1 P0(α)=0; Pβ+1(α)=Sα(Pβ(α)) E0(α)=0; Eβ+1(α)=Pα(Eβ(α)) Let us now identify entities that can be identified with 0 and the successor-operation: J.-M. Kuczynski ∅=DF0 {α}=DFα+1 Let us now assimilate these identities into our new notation: S∅(α)=α; S{β}(α)=Sβ({α}) P∅(α)=∅; P{β}(α)= Sα(Pβ(α)) E∅(α)={∅}; E{β}(α)= Pα(Eβ(α)) And, of course, α+β=γ α×β=γ, and αβ=γ, are equivalent with, respectively: Sβ(Sα(∅))=Sγ(∅) Pβ(Sα(∅))=Sγ(∅)), and Eβ(Sα(∅))=Sγ(∅)). These equivalencies are the foundation of Von Neumann's construction of arithmetic, which we will now state. Von Neumann's set-theoretic interpretation of arithmetic J.-M. Kuczynski If k is the class of Jim's houses, then (a) Jim has 0 houses is equivalent with (a*) k≈∅, suggesting that 0 may be identified with∅. And (b) Jim has 1 house, (c) Jim has 2 houses, and (d) Jim has 3 houses, are equivalent with, respectively, (b*) k≈{∅}. (c*) k≈{{∅},∅}, and (d*) k≈{{{∅},∅}, {∅},∅} suggesting that, if 0 is identified with∅, then n may be identified with {m: m∈n}. Taking n to be identical with {m: m∈n}, it follows that n+1={m: m=n∨m∈n}. Hence the equivalence of: (e) Jim has n+1 houses, J.-M. Kuczynski with (e*)∀k*(k≈k*∪α↔([k*]=1⋀α∉k*)), where the meaning of (e*) is: If k* has n members and α is not an element of k*, then k has the same number of members as k*∪α. There are no number-expressions in (a*)-(d*). Thus, all of the number-expressions in (a)- (d) have been successfully eliminated. There are number-expressions in (e*), but we are about to see how to produce an equivalent statement that contains no such expressions.) Given obvious generalizations of the fact that (a)-(d) are equivalent with (a*)-(d*),Nmay be identified with the posterity of∅with respect to Φ, where Φ is the relation that {n: nεα} bears to {n: n∈α∨n=α}. (In other words, 1={∅}, and 2={{∅},∅}, and so on.) Stated formally, n is a cardinal iff either (i) n=∅ or (ii) n=β, where Φ(γ)=β, where γ∈N. And given thatNmay be identified with the posterity of∅ with respect to ρ, it follows that (e*) is equivalent with: (e#)∀k*∀x(x∈{α: α=∅∨∃β(Φ(β)=α)}⋀k*≈x)→∃y(Φ(x)=y⋀k≈y)), which, unlike each of (e) and (e*), contains no number-expressions. Von Neumann arithmetic (continued) It follows that, for any number α, J.-M. Kuczynski (+V1) α+1={n: n=α or n∈α}, and α=β+1 exactly if α ={n: n=β⋁n∈β}. Given (+V1), it follows that the following definitions are both consistent with one another and otherwise admissible: (+) {n: n∈α}+0=DF{n: n∈α}; and {n: nεα}+n+1=DF{n: n=α or n∈α}+n. (×){n: n∈α}×0=DF∅; and {n: n∈α}×n+1=DF{{n: n∈α}×n}+α, and (ζ) {n: n∈α}ζ0=DF{∅}; and {n: n∈α}ζn+1=DF{n: n∈α}ζn}×α. (+), (×), and (ζ) are equivalent with, respectively: (A) α+0=α; and α+(β+1)= (α+β)+1, (B) α×0=0; and α×(β+1)= (α×β)+ α, (C) α0=1; αn+1= αn×α. these being the recursions that define +, ×, and ζ, respectively. Relative to this construction of arithmetic, the meanings of (I) α+β=γ (II) α×β=γ, and (III) αβ=γ are, respectively, (IV) {n: n∈α}+β={n: n∈ γ}, (IIV) {n: n∈α}×β={n: n∈ γ}, and (IIIV) {n: n∈α} ζβ={n: n∈ γ}. J.-M. Kuczynski Frege's set-theoretic interpretation of arithmetic For Frege, n is the class of all n-tuples. Thus, 0={k:∀x(x∉k)}=∅ n+1=DF{k:∀x(x∈k→[k⋂C{x}]=n)} α+1=β ∀k∀k*∀x(([k]=α⋀x∉k)→[k⋃x]=β) α+β=γ The union of an α-tuple and a non-overlapping β-tuple is a γ-tuple ∀k∀k*((k⋂k*=∅⋀k∈Kα⋀k*∈Kβ)→(k⋃k*)∈Kγ) α×β=γ The Cartesian Product of an α-tuple and a β-tuple is a γ-tuple ∀k∀k*(([k]=α⋀[k*]=β)→[CP(k,k*)]=γ) αβ=γ The class of all selections from an α-tuple whose members are β-tuples is a γ-tuple ∀k∀k*([k]=α⋀∀x((x∈k→[x]=β)→[{k: k= ΣK}]= γ)) Fregean formalizations of the previously mentioned recursive definitions of +, ×, and ζ ∀k([k]=α →[k⋃∅]=α); ∀k∀k*∀x(k⋂k*=∅⋀[k]=α⋀[k*]=β⋀x∉k⋀x∉k*)→([k⋃(k*⋃x)]= [(k⋃k*)⋃x)])) ∀k([k]=α →[CP(k,∅)]=∅); J.-M. Kuczynski ∀k∀k*∀x(([k]= α⋀[k*]=β⋀x∉k⋀x∉k*)→[CP(k, k*⋃x)]=[CP(k⋃k*)]+α) ∀k([k]=α⋀∀x((x∈k→[x]=∅) →∃k*([k*]=1⋀k*={∅}⋀ Σk=k*)); ∀k1∀k2∀k3∀k4 (([k1]=α⋀(k2∈k→[k2]= β)⋀([k3]=α→(Σk3=[CP(Σk1,k1)]→(k4∈k3))))→[k4]=β+1) General definition of cardinal number Although Frege and Von Neumann seem to have differing views as to what n is identical with, they do not. Von Neumann does not really identify n with {m: m∈n}. Rather, he identifies n with the pair ({m: m∈n}, ≈), where ≈ is the relation of set to equipollent set. And Frege does not identify n with Kn (this being the class of all n-tuples) Rather, he identifies n with the pair (Kn,∈). Each of ({m: m∈n}, ≈) and (Kn,∈) is an instance of the structure individuative of n. Thus, n per se is the class Ν of all pairs (k, R), where k is a class, not necessarily an n-tuple, and R is a relation such that a given class k* is an n-tuple exactly if k* bears R with respect to k. It is readily seen that no non-instance of n is an element of Ν and also that any instance of Ν is an instance of n. Therefore, n=Ν, there being no other entity with which n can possibly be identified. In order to see why this is so, we must acquaint ourselves with the concept of isomorphism and also with the concept of a mathematical model. Isomorphism Two classes k and k* are isomorphic with each other if there is a one-one function Φ such that, for any elements x and y of k such that φ(x)=y, there exist elements x* and y* of k* such that Φ(x,y)=(x*,y*). If, with respect to Φ, k and k* are isomorphic with each other, then the one class is a transformation of the other. Co-cardinality (the property, had by pairs of classes, of having the same number of elements) is one-dimensional isomorphism. J.-M. Kuczynski The concept of a mathematical model Let P be an arbitrary progression such that (i) α1 is P's first member, and (ii) φ(αn)=αn+1. We may identify α1 with 0 and we may be identify φ with +1. Any two progressions are isomorphic. Therefore, any given progression is no less adequate a model of arithmetic than any other progression. M is a model of N if (i) N is a class of sentences or of open-sentences (expressions that contain free-variables, and are therefore neither true nor false, but are otherwise sentence-like), (ii) M is a sentence-class that results when the expressions belonging to N are uniformly replaced with other expressions, Φ(N)=M, where Φ is a function from expressions to expressions, and (iii) If Sn is sentence of N and Sm is the corresponding sentence of M, then Sn is true just in case Sm is true, i.e. Sn↔Φ(Sn). Recursivity as categoricity A statement class N is categorical if, whenever M and M* are models of N, M is isomorphic with M*. 1. N is complete iff N is recursive. 2. N is recursive iff, supposing that each of M and M* is a model of N, M and M* are isomorphic with each other. 3. N is incomplete if non-recursive. J.-M. Kuczynski 4. N is non-recursive if, for any model M of N, there is a mode M* of N such that M is not isomorphic with M*. 1 and 3 are definitional points. 2 and 4 are immediate consequences of two facts, namely: (i) Any two progressions are isomorphic, and (ii) No progression is isomorphic with any non-progression. We have already proved (i), and (ii) is a corollary of (i). An isomorphism is a one-one function. If a sequence either loops or otherwise has finitely many members, then the elements of that sequence cannot be paired off with elements of a progression. Let us now prove that, given (i) and (ii), it follows that recursive statement-classes are categorical and non-recursive statement-classes are non-categorical. Incompleteness (non-recursivity) identical with non-categoricity If k is a recursively defined class and φ is the recursion that generates k, then (k, φ) is a progression. Therefore, (k, φ) is isomorphic with (k*, φ*), for any class k* that is a recursively generated by φ*. If N is recursive, then N=(k, φ), for some k and some φ. In other words, if N is recursive, then N is a progression. Therefore, if N* is non-recursive, then N* is a non-progression and is therefore nonisomorphic with N. Therefore, if N is recursive and N* is non-recursive, then, supposing that each of N and N* is a model of some third class M, it follows that M is not a progression and therefore that M is non-recursive. J.-M. Kuczynski End of Part