Predicate Logic - Inference Rules

Mixed Quantifiers

The order of the quantified variables matters. Assume that I(P)=less than, so that I(Pxy)=x<y:

  1. (∀x)(∃y)Pxy: This is interpreted as for all x there exists a y greater than said individual x. This is true.
  2. (∃y)(∀x)Pxy: This is interpreted as there exists a y that is greater than all x. This is false.

So:

(∀x)(∃y)Pxy≠(∃y)(∀x)Pxy

Figure 20

More examples may be useful in thinking about how to translate mixed quantifiers:

  1. (∃x)(∀y)(x+y=y) means there exists x which makes the proposition true given all y. This is true. This is true when x=0.
  2. (∀y)(∃x)(x+y=0) means that for all y, there exists an x which makes x+y=0 true. This is true. This is true when x=-y.
  3. (∀x)(∀y)(∃z)((x<y)→(x<z<y)) says that between all numbers x and y, there exists z.

A rule: (∃y)(∀x)Pxy→(∀x)(∃y)Pxy. This is because the antecedent implies a fixed value of y makes Pxy true. This implies that for all x, the fixed value of y will necessarily satisfy the truth conditions given. This relationship cannot be reversed.

Negated Existential Decomposition

Figure 21

Negated Existential Decomposition says that given ¬(∃x)Px, then you can infer (∀x)¬Px. (¬∃D)

Negated Universal Decomposition

Figure 22

Negated Universal Decomposition says that given ¬(∀x)Px, then you can infer (∃x)¬Px. (¬∀D)

Existential Elimination

Figure 23

Existential Elimination says that given (∃x)Px, an expression Q can be derived from a substitution with Pa.  (∃E)

  1. The Individuating constant ‘a’ does not occur in any premise or in an active proof (or sub proof) prior to its arbitrary introduction in the assumption Pa.
  2. The name ‘a’ does not occur in proposition Q discharged from the sub proof.

For instance, look at (∃x)Px⊢(∃y)Py:


Figure 24

Universal Elimination

Figure 25

Universal Elimination says that given (∀x)Px, then you can infer Pa. (∀E)

You must substitute a variable with one name if it is repeated within a proposition. For instance, these examples show incorrect usage:

Figure 26

Here is an example of an application of universal elimination in natural language:

Figure 27

Another example is the following (∀x)[Px→(∀y)(Qx→Wy)],Pb∧Qb⊢Wt:

Figure 28

Existential Introduction

Figure 29

Existential Introduction says that given Pa, then you can infer (∃x)Px. (∃I)

For instance:

Figure 30

Here’s an example of a proof of Pa→Qa,Pa ⊢(∃x)Qx∧(∃y)Py:

Figure 31

In n-placed predicates, it’s sufficient to replace one individual constant rather than all the names in so far that you don’t replace different names with the same variables. Some mistaken usages:

Figure 32

Universal Introduction

Figure 33

Universal Introduction says that given Pa, then you can infer (∀x)Px. (∀I)

  1. The individuating constant ‘a’ does not occur as a premise or as an assumption in an open sub proof.
  2. The name ‘a’ does not occur in the derived proposition ex:  (∀x)Pxa.
  3. Usually used in a sub proof or with a specified domain.

This seems strange because it leads to hasty generalization. However, it must be the case that prior to the derivation, the name ‘a’ can be replaced with any other name. In other words, a single case in the domain has a specific property from a general presumption. For instance, this is incorrect:

We cannot argue for (∀x)Px⊢Pa since it’s possible that v(Pa)=T ∧v((∀x)Px)=F:

Figure 34

An example could show the proof of (∀x)Px⊢(∀y)Py:

Figure 35

When the conclusion of the hypothesis you want to prove is a universally quantified proposition 

(∀x)Px, derive a substitution instance Pa such that a use of (∀I) will result in the desired conclusion.


Comments

Post a Comment

Popular posts from this blog

National Accounting - Consumption and Investment

Image
Over the course of a year, a quarter, or a month, we can look at the debits and credits that build up the entirety of an economy. National accounts looks at these debits and credits and record the transactions  While it can be the case we make more than we spend as individuals, this cannot be the case for entire economies. This is the old adage that every sale is something bought. In the context of macroeconomics we say that income over a period of time should be equal to expenditures over that period of time: Expenditures = Income For the case of this post, we will assume a hypothetical economy which only consists of domestic investment and consumption as transactions. We can define the two as follows: Consumption : Transactions that are associated with the destruction of asset values. Investment : Transactions that are associated with increasing assets values. To understand these definitions, we will look at two sets of debit and credit charts to show how these transactions are ...
Read more

Conceptual Analysis

Conceptual analysis is kind of like giving definitions: Conceptual Analysis : A description of constituent properties of a complex property or relation. Some complex property is usually built up of simpler properties. An example of a conceptual analysis is: X is a triangle = df. X is a shape with exactly three angles and straight lines in Euclidean space. This is more than a definition is picking out some properties of a property. Also, = df. means by definition. Another example: X is a bachelor = df. X is an unmarried man. Here a conceptual analysis is: Non-circular, the analysis refers to properties that aren’t the same thing as itself. It tries to include everything it intends to include and exclude what it intends to not exclude. It tries to pick out the properties that do this. (It’s not possible to have one condition without the other). Conceptual analysis helps you: Understand reality : reality contains things with properties, and conceptual analysis picks out properties...
Read more