Flashcards in Chapter 2: Definitions Deck (11)

Loading flashcards...

1

## Definition 2.1. The set of propositions, denoted by L0,

###
The set of propositions, denoted by L0, is defined inductively as follows:

1) Every primitive proposition is a proposition, i.e. if P ∈ LP

0, then P ∈ L0.

2) If α is a proposition, then so is (¬α).

3) If α, β are propositions, then so is (α ⇒ β).

2

## Definition 2.2. valuation

###
A valuation is a function v : L0 → {0, 1}, satisfying the following conditions:

1) For α ∈ L0, v(¬α) = 1 if v(α) = 0, while v(¬α) = 0 if v(α) = 1, i.e. v(¬α) = 1 − v(α).

2) If α, β ∈ L0, then v(α ⇒ β) = 0 if v(α) = 1 and v(β) = 0, while v(α ⇒ β) = 1 otherwise

3

## Definition 2.7. Model

###
If, for a valuation v, v(α) = 1 for a proposition α ∈ L0,

then we say that α is true in/for v, or that v is a model of α.

If, for a set of propositions S and a valuation v, v(α) = 1 for all α ∈ S, then we say that v is a model of S.

4

## Definition 2.8. tautology

### If a proposition α ∈ L0 satisfies v(α) = 1 for every possible valuation v, then we say that α is a tautology, and write |= α.

5

## Definition 2.9. semantically equivalent

### If, for two propositions α, β ∈ L0, it is the case that v(α) = v(β) for every possible valuation v, then we say that the propositions α and β are semantically equivalent.

6

## Definition 2.18. semantically implies

###
Consider a subset S of the set L0 of all propositions, and a proposition α ∈ L0.

Then, we say that S semantically implies or entails α, and write

S |= α if, for every valuation v such that v(s) = 1 for all s ∈ S, we also have v(α) = 1.

7

##
Definition 2.25.

proof

###
Let S be a subset of L0, i.e. S ⊂ L0, and let α be a proposition, i.e. α ∈ L0. Then, a proof of α from S is a finite, ordered sequence of propositions (or lines), t1, t2, · · · , tn say, such that tn is the proposition α, and, such that, for each proposition ti, 1 ≤ i ≤ n:

a) ti is an (occurrence of an) axiom, or

b) ti is a proposition in S (we call such a proposition a hypothesis), or

c) ti is a proposition that can be deduced by modus ponens from two preceding propositions: ti is some proposition β, and, for some j, k < i, tj is some proposition α and tk is the proposition α ⇒ β.

8

## Definition 2.26.syntactically implies

###
Consider a subset S of the set of all propositions L0, and a proposition α ∈ L0.

Then, we say that S syntactically implies or proves α, and write S |- αif there exists a proof of α from S (S being a set of hypotheses in this case).

9

## Definition 2.27. theory

###
f there exists a proof of a proposition α ∈ L0 that uses no hypotheses, but perhaps only occurrences of the three given axioms and modus ponens,

then we say that α is a theorem, i.e.

α ∈ L0 is a theorem if ∅ |- α.

In such a case, we may also write |- α.

10

## Definition 2.37. consistent

###
Consider a set of propositions, S (S ⊂ L0).

The set S is consistent if there does not exist a proposition α such that S |- α and S |- (¬α). If there exists a proposition α such that S |- α and S |- (¬α), we say that the set S is inconsistent.

11