An Introduction To Mathematical Reasoning Answer Key

Systems of Logic Based on Ordinals

S. Barry Cooper , ... A.M. Turing , in Alan Turing: His Work and Impact, 2013

11 The purpose of ordinal logics.

Mathematical reasoning may be regarded rather schematically as the exercise of a combination of two faculties ^‡ , which we may call intuition and ingenuity. The activity of the intuition consists in making spontaneous judgments which are not the result of conscious trains of reasoning. These judgments are often but by no means invariably correct (leaving aside the the question what is meant by "correct"). Often it is possible to find some other way of verifying the correctness of an intuitive judgment. We may, for instance, judge that all positive integers are uniquely factorizable into primes; a detailed mathematical argument leads to the same result. This argument will also involve intuitive judgments, but they will be less open to criticism than the original judgment about factorization. I shall not attempt to explain this idea of "intuition" any more explicitly.

The exercise of ingenuity in mathematics consists in aiding the intuition through suitable arrangements of propositions, and perhaps geometrical figures or drawings. It is intended that when these are really well arranged the validity of the intuitive steps which are required cannot seriously be doubted.

The parts played by these two faculties differ of course from occasion to occasion, and from mathematician to mathematician. This arbitrariness can be removed by the introduction of a formal logic. The necessity for using the intuition is then greatly reduced by setting down formal rules for carrying out inferences which are always intuitively valid. When working with a formal logic, the idea of ingenuity takes a more definite shape. In general a formal logic, will be framed so as to admit a considerable variety of possible steps in any stage in a proof. Ingenuity will then determine which steps are the more profitable for the purpose of proving a particular proposition. In pre-Gödel times it was thought by some that it would probably be possible to carry this programme to such a point that all the intuitive judgments of mathematics could be replaced by a finite number of these rules. The necessity for intuition would then be entirely eliminated.

In our discussions, however, we have gone to the opposite extreme and eliminated not intuition but ingenuity, and this in spite of the fact that our aim has been in much the same direction. We have been trying to see how far it is possible to eliminate intuition, and leave only ingenuity. We do not mind how much ingenuity is required, and therefore assume it to be available in unlimited supply. In our metamathematical discussions we actually express this assumption rather differently. We are always able to obtain from the rules of a formal logic a method of enumerating the propositions proved by its means. We then imagine that all proofs take the form of a search through this enumeration for the theorem for which a proof is desired. In this way ingenuity is replaced by patience. In these heuristic discussions, however, it is better not to make this reduction.

In consequence of the impossibility of finding a formal logic which wholly eliminates the necessity of using intuition, we naturally turn to "non-constructive" systems of logic with which not all the steps in a proof are mechanical, some being intuitive. An example of a non-constructive logic is afforded by any ordinal logic. When we have an ordinal logic, we are in a position to prove number-theoretic theorems by the intuitive steps of recognizing formulae as ordinal formulae, and the mechanical steps of carrying out conversions. What properties do we desire a non-constructive logic to have if we are to make use of it for the expression of mathematical proofs? We want it to show quite clearly when a step makes use of intuition, and when it is purely formal. The strain put on the intuition should be a minimum. Most important of all, it must be beyond all reasonable doubt that the logic leads to correct results whenever the intuitive steps are correct ^† . It is also desirable that the logic shall be adequate for the expression of number-theoretic theorems in order that it may be used in metamathematical discussions (cf. §5).

Of the particular ordinal logics that we have discussed, Λ _H and Λ _P certainly will not satisfy us. In the case of Λ _H we are in no better position than with a constructive logic. In the case of Λ _H (and for that matter also Λ _H ) we are by no means certain that we shall never obtained any but true results, because we do not know whether all the number-theoretic theorems provable in the system P are true. To take Λ _P as a fundamental non-constructive logic for metamathematical arguments would be most unsound. There remains the system of Church which is free from these objections. It is probably complete (although this would not necessarily mean much) and it is beyond reasonable doubt that it always leads to correct results ^‡ . In the next section I propose to describe another ordinal logic, of a very different type, which is suggested by the work of Gentzen and which should also be adequate for the formalization of number-theoretic theorems. In particular it should be suitable for proofs of metamathematical theorems (cf. §5).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B978012386980750006X

Handbook of Proof Theory

Pavel Pudlák , in Studies in Logic and the Foundations of Mathematics, 1998

5.3

The question whether mathematical reasoning as represented by Zermelo-Fraenkel set theory is consistent has intrigued a lot of mathematicians and philosophers. The approach of finitists is to discard it as meaningless and ask instead whether there is a feasible proof of contradiction from our axioms of set theory. We shall say more about this modified question in the next section. Now we only want to show that there are theories, not quite unnatural, which are inconsistent but in which no feasible proof of contradiction exists. Such theories have been considered by several researchers including Parikh [1971], Dragalin [1985], Gavrilenko [1984] and Orevkov [1990]; the first and the most influential was the paper of Parikh.

Let T be any fragment of arithmetic (it can be even the set of all true sentences in the standard model). Let t be a closed term whose value m is so large that no proof of size m can be ever constructed. Note that t can be quite simple, say 2¹⁰⁰. Extend T to T' by adding axioms

$\begin{array}{l}I\left(0\right),\\ I\left(x\right)\to I\left(S\left(x\right)\right),\\ \neg I\left(2_t^0\right).\end{array}$

Clearly T' is not consistent. We shall show, however, that there is no feasible contradiction in T'.

Suppose we can derive a contradiction in T' of size less than n. Then, by the bound on cut-elimination, there is a cut-free proof of contradiction of size less than $2_n^0$ . This means that we have such a proof of   →   ¬ ∧ T ₀, for a finite fragment T₀ of T′. Let T ₁ be a Skolemization of T ₀. Then the proof of   →   ¬ ∧ T ₁ is at most polynomially larger than $2_n^0$ (since each sentence has a polynomial size proof from its Skolemization). Thus by taking m, hence also t, only slightly larger than n, we get an upper bound $2_m^0$ to the open theory T ₁. Then we use the same "interpretation" argument as in the lower bound proof above to show that such a proof cannot exist.

Let us note that we can add also other closure properties such as $I\left(x\right)\wedge I\left(y\right)\to I\left(x+y\right)$ and the same for multiplication, if we take t a little larger, since we can interpret such a theory in T' using small formulas and short proofs (see 3.5).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S0049237X98800232

Fuzzy Sets and Systems

In Mathematics in Science and Engineering, 1980

d Generality of the Extension Principle

Given this principle, it is possible to fuzzify any domain of mathematical reasoning based on set theory. As in Gaines (Reference from III.1, 1976b), "the fundamental change is to replace the precise concept that a variable has a value with the fuzzy concept that a variable has a degree of membership to each possible value."

However, using the extension principle is not the only way of fuzzifying mathematical structures. Another way is just to replace ordinary sets by fuzzy sets (or the family of their α-cuts) in the framework of a given theory. For instance, fuzzy groups were defined in the previous chapter; their setting did not require an extension principle: a fuzzy group is nothing but a subgroup without sharp boundary. The group operation is still performed on the elements of the universe. Using the extension principle, however, we can extend the group operation to have it acting on fuzzy sets of the universe. The extended operation is not necessarily a group operation. This latter way of "fuzzifying a group" is radically different from Rosenfeld's (Reference from II.1) and will be investigated in Section B of this chapter.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S0076539209601387

Modal Logics and mu-Calculi: An Introduction

Julian Bradfield , Colin Stirling , in Handbook of Process Algebra, 2001

5.3. Decidable model-checking for infinite processes

The infinite-state tableau system just described makes no claims for decidability: it allows arbitrary mathematical reasoning to be used in establishing the termination and success conditions. An obvious question is to ask what can be done for infinite processes while retaining decidability; the answer is quite limited.

Clearly model-checking is undecidable for any Turing-powerful class of processes, since μZ.[−]Z expresses the halting property. It turns out to be easy to code halting in the modal mu-calculus, or even in small fragments of linear temporal logic, for many classes that are not Turing-powerful by themselves. For example, if we try to model a register machine as a Petri net, we need to test for zero, which nets cannot do; but if d is a transition that can fire when a particular place is non-empty, then [d]ff expresses the emptiness of that place, and so one can write a mu-calculus formula which says 'the net halts, if we look at those "honest" computations where a branch-on-zero is only taken when the corresponding counter really is zero'. Similarly, it is unnecessary for the registers actually to synchronize with the finite-state control, as we can encode the synchronization into the formula. The upshot of this is that model-checking, even with just one fixpoint, is undecidable for BPP, Basic Parallel Processes – a result which might be surprising, given the decidability of bisimulation for BPP.

On the other hand, for BPA, Basic Process Algebra, and for its generalization pushdown processes, model-checking is decidable. This follows from a classical result of Muller and Schupp [48] on the monadic second-order theory of pushdown graphs; but it has been shown by a direct and elegant argument by Burkart and Steffen [16]. They view pushdown processes as 'higher-order' transition graphs. For example, the BPA process system given by A = a B A + c and B = b B A + c is viewed as a system where the A process does an a transition followed by a B transition, understood as a recursive call to B, and returns to its initial state (if B terminates), or does a c to terminate. Now, if we are interested in a particular formula ϕ, each transition, including the 'higher-order' transitions, is viewed as a predicate transformer on the subformulae of ϕ: assuming that some subformula hold at the terminal state of the process, which formulae hold at the initial state? Obviously there are only finitely many possibilities, and the result can be calculated by an approximant-style procedure. If one now plugs into the A transformer the formulae that are true at a real terminal state, one obtains the formulae true of A.

Further detail on all these results can be found in the chapter by Burkart et al. later in this Handbook [15].

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780444828309500229

LOGICISM

Jaakko Hintikka , in Philosophy of Mathematics, 2009

13 REDUCTION TO THE FIRST-ORDER LEVEL

Indeed, second-order logic can in a sense be dispensed with altogether. Even though not all mathematical reasoning can be carried out in IF first-order logic, this logic can be extended and strengthened while still remaining on the first-order level in the sense that all quantification is over individuals (particular members of the domain). By itself, IF first-order logic is equivalent to Σ ¹ ₁ fragment of second-order logic. (This is the logic of sentences which have the form of a string of second-order existential quantifiers followed by a first-order formula.) It can nevertheless be extended by adding to it a sentence-initial contradictory negation. This adds to it the strength of Π¹ ₁ second-order logic. In order to extend IF logic further, a meaning must be associated to contradictory negation also when it occurs in the scope of quantifiers. This can be done, but it involves a strongly infinitary rule which involves the possibly infinite domain of individuals as a closed totality and which is tantamount to an application of the law of excluded middle to propositions of a complexity. This complexity can be thought of as a measure of the nonelementary (infinitistic) character of the application. If no limits are imposed on this complexity, we obtain a logic which is as strong as the entire second-order logic but is itself a first-order logic in the sense of involving only quantification over individuals.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780444515551500109

Technology Supports for Acquiring Mathematics

M.J. Nathan , in International Encyclopedia of Education (Third Edition), 2010

Logo

Logo (Papert, 1980 ) is both a computer programming language and a microworld, a designed learning environment to promote mathematical reasoning and problem-solving skills through an innovative process of directing the actions of a mathematical creature called the Logo turtle. The turtle can move forward or backward, stop, and rotate to the left or right, and raise and lower its pen in response to programmed commands. Although the original turtle was a physical robot that ran along the floor or paper, in later versions it was replaced by a graphical turtle on a computer screen.

The Logo environment offers a way for the child to externalize mathematical ideas and procedures and project them onto the actions and properties of the turtle and the Logo programming language (Eisenberg, 2003). Yet, it also becomes an object-to-think-with (Resnick et al., 1996) and has been used to conceptualize many areas of mathematics, including modern algebra and group theory, computer science, cybernetics, as well as Euclidean and non-Euclidean geometry (Abelson and diSessa, 1981).

Logo has long been a tool for doing mathematics and mathematics instruction, and there is a large collection of empirical studies investigating its impact on mathematics learning, teaching, and discovery. For example, fourth graders familiar with Logo programming were better able to apply what they learned and elaborate on their procedural interpretations of geometry concepts than those taught from an inquiry-based approach (Lehrer et al., 1989). In other studies, Logo improved students' use of geometric models in other areas of mathematics, generalization and abstraction of geometric operations, and improved complex reasoning along with more general cognitive skills (Battista and Clements, 1991; Clements and Battista, 1991, 1992; Lehrer and Littlefield, 1993).

As is the case with educational technology, more generally, the effects of Logo have as much to do with the teaching and the engagement of the students, as the technology itself (Kozma, 1991, 1994; though also see Clark, 1983, 1994).

The essential ideas conveyed in Papert's (1980) original work, Mindstorms, inspired a broad range of technological designs for learning and instruction, including: StarLogo, which uses concepts of parallel computation to introduce participants to the computational and cognitive aspects of modeling complex, dynamic systems (e.g., Colella et al., 1999); and the NetLogo Project (reviewed below) at Northwestern University and The University of Texas at Austin (Wilensky, 1999; Wilensky and Stroup, 1999), which supports distributed computing.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780080448947007351

Kerala Astronomers

T.K. Puttaswamy , in Mathematical Achievements of Pre-Modern Indian Mathematicians, 2012

Govindaswamin (ad 800–850)

Govindaswamin was an astronomer and a well-known exponent of Aryabhata I School and Bhaskara I. He authored "Mahabhaskariam Bhasya," which expounded new concepts and mathematical reasoning. In this work, he has provided a set of rules to the calculation of intermediary functional values. His formula in modern notation can be written as

$f(x+nh)=f(x)+n\mathrm{\Delta }f(x)+\frac{n(n-1)}{2}[\mathrm{\Delta }f(x)-\mathrm{\Delta }f(x-h)]$

where Δ is finite difference operator. This formula is a special case up to the second order of the general Newton–Gauss formula. Govindaswamin's work has been brought to light by R.C. Gupta ("Fractional parts of Govindaswamin," "Bhasya" on the "Mahabhaskariya." Indian Journal of History of Science, Vol. 6, 1971, pages 51–59). Govindaswamin has also written another work called "Govinda krti" on astronomy and mathematics. Unfortunately, this work has been lost and yet to be traced.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123979131000132

Programs and Instructional Strategies for Students with Gifts and Talents

V.I. Daniels , M.J. McCollin , in International Encyclopedia of Education (Third Edition), 2010

Curricular and Programmatic Models

Connecting intelligence theories to curricular models requires a juxtapositioning of the theories with specific curricular models. VanTassel-Baska and Brown (2009) defined curricular models as a curriculum design and development framework that provides a systematic approach to developing an appropriate curriculum for the target population. These curricular models must include in their frameworks the ability to identify curriculum-product elements. In order for a model to be effective, it must possess differentiation, flexibility, transferability, and usability across content areas, age/grade span, and flexible grouping models. Additionally, it must delineate ways in which it responds to the particular needs of the individual with gifts. The models are descriptive and do not validate the most effective method for maximizing student development in a specific time or space. Each of the curricular models has more than 10   years of supportive research, development, and implementation undergirding its use, endurance, and attention (Coleman and Cross, 2005; VanTassel-Baska and Brown, 2009). The following are subsections that discuss these models.

The Stanley Model of Talent Identification

The Stanley model focuses on lifelong education for the individual. Model principles include: (1) utilization of assessment instruments that encourage high-level verbal and mathematical reasoning; (2) diagnostic instructional methodologies; (3) accelerated and fast-paced core content; and (4) flexible curriculum across the school environment. This content-based model is aligned with national standards, is highly sustainable, and demonstrates the benefits of acceleration for advancement.

The Renzuilli Schoolwide Enrichment Triad Model

The major principles of the Schoolwide Enrichment Triad Model (SEM) model are supported by the (1) use of interest and learning style inventories to assess inter and extracurricular abilities; (2) provision of compacting curriculum (i.e., the regular curriculum is modified by eliminating mastered content, and substituting alternative work); and (3) access to the appropriate triad level based on students' abilities, interest, and task commitment. Enrichment level 1 consists of general exploratory experiences (e.g., guest speakers, field trips, and interest centers); enrichment level 2 includes instructional strategies designed to promote thinking; and enrichment level 3 utilizes analytical activities and creative productions that support primary inquiry and thinking.

Gardner's Multiple Intelligences (MI)

The Gardner model is a core-curricula approach that employs the multidimensional concept of intelligence (Gardner, 1983). The eight types of intelligence are defined as (1) verbal/linguistic, (2) logical/mathematical, (3) visual/spatial, (4) musical/rhythmic, (5) bodily/kinesthetic, (6) interpersonal, (7) intrapersonal, and (8) naturalistic. The multiple-intelligences curricula model has been used as the base curriculum for the identification of individual differences and multidimensional evaluation.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780080448947011453

The Construct of Mathematical Resilience

Clare Lee , Sue Johnston-Wilder , in Understanding Emotions in Mathematical Thinking and Learning, 2017

Knowing How to Gain Support

Resilient learners of mathematics know that mathematics requires struggle but they also know how to access help and support in that struggle. Some learners may need to be shown successful models of mathematical thinking and reasoning. All need to be listened to because in formulating thinking to communicate ideas to others, that thinking becomes clarified (Lee, 2006). Furthermore when the "sticking point" becomes obvious, a more capable peer will be able to question the reasoning or offer targeted and appropriate support. Collaborative discourse may enable students to learn to ask themselves the right questions (Lee, 2006).

In order to work collaboratively, learners need to build up sufficient language or vocabulary so that they can use enough of the mathematics register to be able to express and explore mathematical ideas (Lee, 2006). This is not to say that they must use the "right" words but rather that they see a need to express mathematical ideas themselves and thus seek a way to do so effectively. Effective mathematics communicators can explore their own understandings and connections and support others. Mathematical resilience is based within a social constructivist domain (Vygotsky, 1978); expressing mathematical ideas and talking about mathematical learning within a mathematical community are both vital aspects of developing the resilience that allows for learning mathematics.

Digital technologies have a role to play here. Search engines furnish a process or ready-made procedure that may yield solutions to a problem, and software such as Grid Algebra or dynamic geometry programs provide a safe place to express ideas, experiment, think, and learn. The potential to make mistakes and to learn from those mistakes is high when using IT because feedback tends to be immediate and having "another go" is straightforward. The transitory nature of attempts on screen appeals to many people who suffer acute anxiety, while they build their resilience.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128022184000108

Many-Dimensional Modal Logics

In Studies in Logic and the Foundations of Mathematics, 2003

2.7 Intuitionistic logic

Intuitionistic logic is yet another type of logic which can be embedded in S4; actually, as we have already said, to provide such an embedding was the main reason for constructing S4 by Gödel (1933) and Orlov (1928).

Intuitionistic logic, and more generally intuitionism as the trend in the foundations of mathematics initiated by Brouwer (1907, 1908 ), aimed to single out and describe the principles of 'constructive' mathematical reasoning, constructive in the sense that it provides (at least) an algorithm constructing an object the existence of which is proved. Classical logic Cl, as well as all other logics having Cl as their fragment, are not constructive: using the law of the excluded middle (A10) we can establish the existence of objects by reductio ad absurdum without even giving a hint of how to find them (mathematical textbooks abound with proofs of this sort ⁹ ).

Intuitionistic propositional logic Int was first constructed syntactically by Kolmogorov (1925), Glivenko (1929) and Heyting (1930). It has the same language $L$ as Cl, and an $L$ -formula φ belongs to Int iff φ can be derived from the axioms (A1)–(A9) using MP and Subst. In other words, Int is obtained from Cl by discarding axiom (A10). (It should be noted, however, that unlike Cl, the connectives ∧, ∨, → and ⊥ are independent: they cannot be expressed via each other.)

The intended meaning of the intuitionistic connectives was explained first in terms of the proof interpretation due to Brouwer, Kolmogorov and Heyting:

•

a proof of a proposition φ ∧ ψ consists of a proof of φ and a proof of ψ;

•

a proof of φ ∨ ψ is given by presenting either a proof of φ or a proof of ψ;

•

a proof of φ → ψ is a construction which, given a proof of φ, returns a proof of ψ;

•

⊥ has no proof and a proof of ¬φ is a construction which, given a proof of φ, would return a proof of ⊥.

According to this interpretation, Int contains only those formulas that have proofs. The existence of open mathematical problems (e.g., 'P = NP?') shows that the formula p ∨ ¬p has no proof, and so cannot be accepted as an intuitionistically valid principle.

Various more formal semantics have been constructed for Int (see, e.g., Kleene 1945, Gödel 1958, Kreisel 1962, Medvedev 1962, Skvortsov 1979, Artemov 2001). Here we briefly consider three of them: the topological, the algebraic and the relational (or possible world) semantics.

Stone (1937) and Tarski (1938) discovered that Int can be interpreted in topological spaces $I$ = 〈U, $I$ 〉 by associating with each variable p an open set $D$ (p) ⊆ U, the value of p in $I$ under the valuation $D$ . The values of arbitrary $L$ -formulas in $I$ are defined inductively as follows:

$\begin{array}{ll}\hfill V(\perp )& =\varnothing ,\\ \hfill V\left(\phi \wedge \psi \right)& =V\left(\phi \right)\cap V\left(\psi \right),\\ \hfill V\left(\phi \vee \psi \right)& =V\left(\phi \right)\cup V\left(\psi \right),\\ \hfill V\left(\phi \to \psi \right)& =I(\left(U-V\left(\phi \right))\cup V\left(\psi \right)\right)\cdot \end{array}$

If $D$ (φ) = U for every valuation $D$ in $I$ , then we say that φ is valid in $I$ and write $I$ ⊨ φ. It turns out that φ ∈ Int iff φ is valid in all topological spaces iff φ is valid in $R$ ⁿ , for any n ≥ 1; see, e.g., (Rasiowa and Sikorski 1963).

A more general algebraic semantics was constructed by McKinsey and Tarski (1944, 1946). A Heyting (or pseudo-Boolean) algebra is a structure of the form

$A=〈A,{\wedge }^A,{\vee }^A,{\to }^A,0^A,1^A〉$

such that ∧ $A$ , ∨ $A$ and → $A$ are binary operations on A, 0 $A$ , 1 $A$ ∈ A, ∧ $A$ and ∨ $A$ are commutative, associative and have the absorption property (like in Boolean algebras, see Section 1.5) and for all a, b, c ∈ A,

•

c ∧ $A$ a ≤ $A$ b iff c ≤ $A$ a → $A$ b (a → $A$ b is the greatest element in the set {c ∈ A | c ∧ $A$ a ≤ $A$ b});

•

0 $A$ ≤ $A$ a ≤ $A$ 1 $A$ (0 $A$ and 1 $A$ are the least and greatest elements in $A$ respectively),

where the binary relation ≤ $A$ on A is defined by taking

$\begin{array}{ccc}a{\le }^{A}b& \text{iff}& a{\wedge }^{A}b=a\cdot \end{array}$

Note that one can also define Heyting algebras as the algebras of open elements of modal algebras for S4 (see Sections 1.5 and 2.6).

Int is sound and complete with respect to the class of all Heyting algebras; moreover, every extension of Int (closed under MP and Subst)—these extensions are known as intermediate or superintuitionistic logics—is characterized by the class of Heyting algebras validating its formulas; see, e.g., (Chagrov and Zakharyaschev 1997).

The possible world semantics for Int defined by Beth (1956) and Kripke (1965b) (see also Grzegorczyk 1964) reflects the epistemic character of intuitionistic logic, namely that it takes into account the development of knowledge.

Let us imagine that our knowledge is developing discretely, nondeterministically passing from one state to another. Being at some state of knowledge (or information) x, we can say which facts are known at x and which are not established yet. Besides, we know what states of information are possible in the future (i.e., do not contradict the knowledge at x). This does not mean, however, that we shall reach all these possible states (for instance, we can imagine now not only a course of events under which the equality P = NP will be proved, but also situations when it will remain unproved or will be refuted). It is also reasonable to assume that when passing to a new state, all the facts known at x are preserved, and some new facts can possibly be established. The propositions established at x are regarded as true at x; they will remain true at all further possible states. But a proposition which is not true at x cannot be said to be false, because it may become true at one of the subsequent states.

Possible states of information are represented as Kripke frames $F$ = 〈W, R〉 in which R is a partial order on W, i.e., R is reflexive, transitive and antisymmetric (∀x, y (xRy ∧ yRx → x = y)). A valuation $D$ in $F$ indicates which atomic propositions hold true in each state x ∈ W. Thus $D$ is a map from the set of propositional variables into the set Up $F$ of upward closed subsets of W (X ∈ Up $F$ iff ∀x ∈ X∀y ∈ W (xRy → y ∈ X)). The pair $M$ = 〈 $F$ , $D$ 〉 is called an intuitionistic (Kripke) model of the language $L$ . The truth-relation ( $M$ , x) ⊨ φ (or simply x ⊨ φ) is defined inductively as follows:

$\begin{array}{l}\begin{array}{ccc}\left(M,x\right)\models p& \text{iff}& x\in V\left(p\right);\end{array}\\ \left(M,x\right)\forall \perp ;\\ \begin{array}{ccc}\left(M,x\right)\models \psi \wedge \chi & \text{iff}& \left(M,\text{x}\right)\models \psi \text{\hspace{1em}and}\left(M,x\right)\models \chi ;\end{array}\\ \begin{array}{ccc}\left(M,x\right)\models \psi \vee \chi & \text{iff}& \left(M,x\right)\models \psi \text{\hspace{1em}or}\left(M,x\right)\models \chi ;\end{array}\\ \begin{array}{ccc}\left(M,x\right)\models \psi \to \chi & \text{iff}& \text{for\hspace{1em}all}y\in W\text{\hspace{1em}such\hspace{1em}that}xRy,\end{array}\\ \left(M,\text{y}\right)\models \psi \text{\hspace{1em}implies}\left(M,y\right)\models \chi \cdot \end{array}$

It follows from this definition that

$\begin{array}{ccc}\left(M,x\right)\models \neg \psi & \text{iff}& \text{for\hspace{1em}all}y\in W\text{\hspace{1em}such\hspace{1em}that}xRy,\left(M,y\right)\phantom{\models }⊭\psi \cdot \end{array}$

(Observe that an intuitionistic model based on the single-point frame is nothing else but a standard model for Cl.) For example, Fig. 2.8 shows an intuitionistic model refuting axiom (A10).

Figure 2.8. An intuitionistic model refuting p ∨ (p → ⊥).

Int is sound and complete with respect to the class of all intuitionistic frames. Moreover, it has the exponential fmp, and the decidability problem for Int is PSPACE-complete. (It should be noted that the problem of whether a given intuitionistic formula is satisfiable is NP-complete: it is enough to check satisfiability in single-point—i.e., classical—models.)

The constructive character of Int is reflected by the fact that it has the so-called disjunction property: for all $L$ -formulas φ and ψ,

$\begin{array}{ccc}\phi \vee \psi \in \text{Int}& \text{iff}& \phi \in \text{Int}\text{\hspace{1em}or}\psi \in \text{Int}\cdot \end{array}$

Note, however, that this property is not characteristic for Int: there are proper extensions of Int having the disjunction property.

We conclude this section with the definition of the Gödel translation ⊤ which embeds Int into S4:

•

⊤(p) = □p, p a propositional variable;

•

⊤(⊥) = □⊥;

•

⊤(φ ∧ ψ) = ⊤(φ) ∧ ⊤(ψ);

•

⊤(φ ∨ ψ) = ⊤(φ) ∨ ⊤(ψ);

•

⊤(φ → ψ) = □(⊤(φ) → ⊤(ψ)).

If we understand the S4-box as 'it is provable' then the intuitionistic connectives are transformed by ⊤ into the corresponding classical ones, but they are understood now in the context of 'provability.' One can show that for every $L$ -formula φ,

$\begin{array}{ccc}\phi \in \text{Int}& \text{iff}& \text{T}\left(\phi \right)\in \text{S}4\cdot \end{array}$

For more information about intuitionistic logic we refer the reader to (van Dalen 1986) or (Chagrov and Zakharyaschev 1997).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S0049237X03800034

An Introduction To Mathematical Reasoning Answer Key

Source: https://www.sciencedirect.com/topics/mathematics/mathematical-reasoning

Posted by: goddardpaptur.blogspot.com

Share this post