Lecture 16: Recursively Defined Sets & Structural Induction

CSE 311: Foundations of Computing

Lecture 16: Recursively Defined Sets & Structural Induction

Last class: Recursive Definition of Sets

Recursive definition of set S ? Basis Step: 0 S ? Recursive Step: If x S, then x + 2 S ? Exclusion Rule: Every element in S follows from the basis step and a finite number of recursive steps.

S={even natural numbers}

We need the exclusion rule because otherwise

S= would satisfy the other two parts. However,

we won't always write it down on these slides.

Last class: Recursive Definitions of Sets

Basis: 6 S, 15 S Recursive: If x,y S, then x+y S

S={6,12,15,18,21,...}

Basis: [1, 1, 0] S, [0, 1, 1] S Recursive: If [x, y, z] S, then [x, y, z] S for any

If [x1, y1, z1] S and [x2, y2, z2] S, then [x1 + x2, y1 + y2, z1 + z2] S. S={plane in 3 spanned by [1,1,0] and [0,1,1]}

Number of form 3n for n 0: Basis: 1 S Recursive: If x S, then 3x S.

Recursive Definitions of Sets: General Form

Recursive definition

? Basis step: Some specific elements are in S

? Recursive step: Given some existing named

elements in S some new objects constructed from these named elements are also in S. ? Exclusion rule: Every element in S follows from

the basis step and a finite number of recursive steps

Strings

? An alphabet is any finite set of characters

? The set * of strings over the alphabet is defined by ? Basis: ( is the empty string w/ no chars) ? Recursive: if *, , then *

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download