Lecture_7 Undecidability

Logic Lecture, week 7: Relations1. Describing RelationsSatisfaction is a relation between objects (things in the world) and predicates (linguistic expressions. Predicates have places: 1-place predicate, 2-place predicate, n-place predicate. Condition on satisfaction of a 1-place predicate:(1) a satisfies the 1-place predicate ‘Fx’ iff FaExample: Bush satisfies the predicate ‘x won th e 2004 US presidential election’. A 1-place predicate expresses a property: Bush has the property of having won the 2004 US presidential election.Predicates with more than one place express relations. A 2-place predicate expresses a binary relation. A 2-place predicate is satisfied by an ordered pair (a 3-place predicate is satisfied by an ordered triple, a 4-place predicate is satisfied by an ordered 4-tuple, an n-place predicate is satisfied by an ordered n-tuple)Example: the ordered pair <Bush, Brown> satisfies the 2-place predicate ‘x is more powerful than y’.NB With ordered pairs, order matters: their order reflects the direction of the relation. E.g. the ordered pair <Brown, Bush> does not satisfy the predicate: ‘x is more powerful than y’. Describing relations:(a) A relation is expressed by a predicate. The predicate is satisfied by the set of n-tuples that define the relation.(b) We define a relation in a domain as the set of ordered n-tuples that satisfy it in that domain.E.g. ‘x is more powerful than y’, D = {Bush, Brown, Sarkozy}: {<Bush, Brown>, <Bush, Sarkozy>, <Brown, Sarkozy>}.In this context, the individuals Bush, Brown, and Sarkozy are called the terms of the ordered pairs.In general, we write an ordered n-tuple: <T1, T2, …, T n>, where T1, T2, …, T n are the terms of the n-tuple.When we describe a relation by giving the set of ordered n-tuples of individuals that satisfy it, we described it extensionally: if two predicates are satisfied by the same ordered pairs, i.e. if the relations that they express are coextensive, they express the same relation.2. Formalising the Properties of Binary RelationsReflexive: ∀x RxxIrreflexive: ∀x ⌝RxxNon-Reflexive: [⌝∀x Rxx ∧⌝∀x ⌝Rxx]; equivalently: [∃x Rxx ∧∃x ⌝Rxx]Symmetric: ∀x∀y [Rxy → Ryx]Asymmetric: ∀x∀y [Rxy →⌝Ryx]Non-Symmetric: [⌝∀x∀y [Rxy → Ryx] ∧⌝∀x∀y [Rxy →⌝ Ryx]];Equivalently: ∃x∃y [Rxy ∧ Ryx] ∧∃x∃y [Rxy ∧⌝Ryx]Transitive: ∀x∀y∀z [[Rxy ∧ Ryz] → Rxz]Intransitive: ∀x∀y∀z [[Rxy ∧Ryz] →⌝Rxz]Non-Transitive: [⌝∀x∀y∀z [[Rxy ∧ Ryx] → Rxz ]∧⌝∀x∀y∀z [[Rxy ∧Ryz] →⌝Rxz]];Equivalently: [∃x∃y∃z [[Rxy ∧ Ryz] ∧ Rxz] ∧∃x∃y∃z [[Rxy ∧ Ryz] ∧⌝Rxz]] Connected: ∀x∀y [⌝x=y → [Rxy ∨ Ryx]]Not Connected: ∃x∃y [⌝x=y ∧⌝[Rxy ∨ Ryx]]Emptiness:A relation is empty when no ordered n-tuple satisfies it.Empty relation: ⌝∃x∃y Rxy (∀x∀x ⌝Rxy)Empty domain: ⌝∃x x = x (∀x ⌝x = x)If the domain is empty, then a relation defined over that domain is empty; but not conversely: there can be empty relations in a non-empty domain.3. Representing Relations With a GraphWe represent a domain as a circle, the dots in the circle represent individuals, i.e. the elements of the domain. We picture the relations (if any) that hold between the individuals of the domain by drawing arrows, between the dots (individuals). Such a representation of a relation (circle, dots, arrows) is a graph of that relation.Suppose that we have the binary relation R defined over the domain D = {a, b, c}.(i) We represent to fact that R contains the ordered pair <a, b> by drawing a single arrow between a and b.(ii) We represent the fact that R contains the two ordered pairs <a, b> and <b, a> by drawing a double arrow between a and b.(iii) We represent the fact that R contains the ordered pair <a, a>, by drawing a loop from a to a.A loop from a to a is a double arrow from a to a.(iv) We represent the fact that R contains the ordered pairs <a, b>, <b, c>, <a, c> by first drawing an arrow from a to b and an arrow from b to c, and then also an arrow directly from a to c. Hodges expresses this idea in terms of the idea of a broken journey: you can break the journey of the arrows from a to b and b to c by going directly from a to c. In this case the broken journey has a shortcut, which is represented by the arrow from a to c.We can apply this apparatus to the description of the properties of binary relations. Take R in a suitable domain:Reflexivity: R is reflexive iff every dot in the graph has a loop attached to it.Irreflexivity: R is irreflexive iff no dot in the graph has a loop attached to it.Non-Reflexive: R is non-reflexive iff some dots have a loop attached to them and some do not. Symmetric: R is symmetric iff every arrow in the graph is double.Asymmetric: R is asymmetric iff no arrow in the graph is double.Non-Symmetric: R is non-symmetric iff some arrows are double and some are not double. Transitive: R is transitive iff every broken journey in the graph has a shortcut.Intransitive: R is intransitive iff no broken journey in the graph has a shortcut.Non-Transitive: R is non-transitive iff some broken journeys have a shortcut and some do not. Connected: R is connected iff every two dots on the graph are connected by an arrow.Non-connected: some dots on the graph are not connected with an arrow to any other dot. Empty relation: R is empty iff there are no arrows in the graph.Empty domain: D is empty iff there are no dots in the graph.4. Emptiness and Symmetry vs Asymmetry, Transitivity vs Intransitivity, Reflexivity vs IrreflexivityIf a binary relation Rxy is empty, it is both symmetric and asymmetric and it is both transitive and intransitive; that is to say:⌝∃x∃y Rxy ├ ∀x∀y [Rxy → Ryx]⌝∃x∃y Rxy ├ ∀x∀y [Rxy →⌝Ryx⌝∃x∃y Rxy ├ ∀x∀y∀z [[Rxy ∧ Ryz] → Rxz]⌝∃x∃y Rxy ├ ∀x∀y∀z [[Rxy ∧Ryz] →⌝Rxz]If Rxy is empty, it is irreflexive (⌝∃x∃y Rxy ├ ∀x ⌝Rxx), but it is not also reflexive: ⌝∃x∃y Rxy ╞ ∀x Rxx is an incorrect sequent if the domain is nonempty.Counter-example: Domain {Bush, Brown} Interpretation: x is married to yIf the domain over which a binary relation Rxy is defined is empty(which entails that R is empty), then Rxy is both reflexive and irreflexive, both symmetric and asymmetric, both transitive and intransitive:⌝∃x x = x ├ ∀x Rxx⌝∃x x = x ├ ∀⌝Rxx⌝∃x∃y x = x ├ ∀x∀y [Rxy → Ryx]⌝∃x∃y x = x ├ ∀x∀y [Rxy →⌝Ryx⌝∃x∃y x = x ├ ∀x∀y∀z [[Rxy ∧ Ryz] → Rxz]⌝∃x∃y x = x ├ ∀x∀y∀z [[Rxy ∧Ryz] →⌝Rxz]In general, a relation is both transitive and intransitive if there are no broken journeys (∀x∀y∀z ⌝[[Rxy ∧Ryz])If the domain is nonempty, and Rxy is reflexive then it cannot be asymmetric (if the domain is nonempty and the only arrows on the graph are loops, Rxy is symmetric and transitive).5. Equivalence relationIf a relation is reflexive, symmetric and transitive, it is an equivalence relation.One important equivalence relation is the relation of identity. But there are other equivalence relations: every sameness predicate (‘same height as’, ‘same colour as’, ‘same degree as’, etc.) expresses an equivalence relation.Equivalence relations partition the domain into equivalence classes, i.e. subsets of the domain: equivalence classes are classes of things that are related to one another by an equivalence relation.That is to say, the domain is such that, for each of its parts, there is no arrow from a dot in that part to a dot in another part. And since the relation is reflexive, symmetric and transitive, every dot in a part is connected by a double arrow to every other dot in that part. (NB There is a mistake in Hodges’ graph on p. 155)Consider a domain of 5 people, the relation Rxy defined over that domain is: x is of the same gender as y. Suppose that there are 3 women and 2 men – the domain is partitioned into two equivalence classes: the class of women that contains 3 people, and the class of men that contains 2 people.Consider again a domain of 7 things, the relation Rxy defined over that domain is: x is of the same height as y. Suppose that 4 things are three meters high, 2 things are two meters high, and 1 thing is one metre high – the domain is partitioned into three equivalence classes: a class of 4 things, a class of two things and a class of 1 thing (singleton).。

Questions on mini-lectures in Unit 7Mini-lecture 11. How is “making an argument” defined in academic texts?Making an argument which means expressing a point of view on a subject and supporting it with evidence, is often the main aim of academic writing.2. What does a hierarchy1of arguments mean?This is the thread that holds the text together, where most of the material is directed.3. What is a counter-argument2?An academic text also needs to present the opposing argument, which is called the counter argument.4. What are the three models of structuring an argument? What are the components for each model?(1) the classical or aristotelian model(introduction, statement of background, proposition, proof, refutation, conclusion)(2) the toulmin model(claim, ground, warrant, backing, qualifier, rebuttal)(3) the rogerian model(introduction, summary of opposing views, statement of understanding, statement of your position, statement of benefits)5. What are the strengths of the three models?The toulmin model is preferred when the argument is mainly based on logic. Whereas in dealing with emotional or psychological arguments, the rogerian model is often applied.Mini-lecture 2Two types of reasoning are explained in the video: inductive3and deductive4.1. What is the process of inductive reasoning like? Can you think of an example from your own life? Inductive arguments are such that the truth of their premises. When reasoning inductively, a person starts with a specific statement in order to make a projection to a general conclusion.2. What is the most common form of inductive reasoning? Again, think of an example of your own. The most common form of inductive reasoning is the generalization.3. What is the process of inductive reasoning like? Can you think of an example from your own life? The most common form of inductive reasoning is the generalization.4. What is a fallacy5in an argument?Fallacies are defects that weaken these arguments.5. Three types of common fallacies are mentioned: the “straw man” fallacy, false cause and weak analogy. Think of examples of each fallacy.(1) the “straw man” fallacy: the arguer sets up a weak version of the opponent’s position and tries to score points by knocking it down(2) false cause: assumes that because B comes after A, A caused B(3) weak analogy: the two things that are being compared aren’t really relevant1(formal) a system that ideas or beliefs can be arranged into 层次体系2an argument against another argument 反例3using particular facts and examples to form general rules and principles 归纳的4using knowledge about things that are generally true in order to think about and understand particular situations or problems 演绎的5a false idea that many people believe is true 谬误Mini-lecture 31. What are the three main types of evidence discussed in the video?Fact, judgment, and testimony.2. What are some of the typical expressions which introduce these types of evidence?(1) fact: "for example", "in a similar case"(2) judgment: "A leads to B", "A stems from B", "A gives rise to B"(3) testimony: "state", "argue", "stress"Mini-lecture 41. What are the components in a simplified Toulmin model? Explain briefly."Since x(grounds)…then y(claim)…because z(warrant)."The claim is a statement of opinion that the author is asking his or her audience to accept as true. The grounds are the facts, the data, the reasoning upon which the claim is based.The warrant is that which links the grounds to the claim.2. What are the three types of rhetorical appeals? Explain briefly.(1) logos: appeal to reason, relies on logic, depends on the use of inductive or deductive reasoning(2) ethos: (ethical appeal) based on the character, credibility, or reliability of the writer(3) pathos: (emotional appeal) appeals to an audience's needs, values, and emotional sensibilities Mini-lecture 51. When is informal language often used?In conversation and discussion.2. What are the linguistic features of informal language?It is very personal and self-expressive, and because of that, it often includes slang and colloquialisms, and it is often used in narratives.3. When is formal language often used?Academic English is often said to be "formal". (college writing, university writing, academic journals) 4. Why is it necessary to distinguish between surface and deep formality?It is argued that the deep part is the most important one, and surface formality inherits its stylistic features from the deep version.5. What are the linguistic features of surface formality?Surface formality mainly refers to the language features of formality with deep formality.(1) Sentences structures are complete, complex and varied.(2) Longer sentences are likely to be more prevalent in formal writing.(3) No contractions should be used to simplify words.(4) Abbreviations are usually spelt out in full, and the only exceptions are when the acronym is better known than its full name.(5) A limited range of emotions are shown and emotive punctuation, is avoided, unless they are being cited from another source.(6) The formal writer is disconnected from the topic and does not use the first person or the second person point of view.。