Logic and Induction Flashcards

Vocabulary flashcards covering core concepts of logic, connectives, quantifiers, sets, and mathematical induction from Lecture 1.

Axiom

A statement assumed to be true without proof, serving as a foundation for further reasoning.

Definition

A formal description of a mathematical concept or term.

Theorem

A mathematical result derived logically from earier statements, such as axioms, definitions, and other theorems.

Proof

A logical derivation of a theorem from axioms, definitions, and previously established theorems.

Odd Integer

An integer $x$ for which there exists an integer $n$ such that $x = 2n + 1$.

Negation

A logical connective denoted by $\neg P$, representing the statement 'not $P$'.

Conjunction

A logical connective denoted by $P \land Q$, representing the statement '$P$ and $Q$'.

Disjunction

A logical connective denoted by $P \lor Q$, representing the statement '$P$ or $Q$'.

Implication

A logical connective denoted by $P \Rightarrow Q$, representing the statement 'if $P$, then $Q$'.

Equivalence

A logical connective denoted by $P \Leftrightarrow Q$, representing the statement '$P$ if and only if $Q$'.

Logical Equivalence

The property of two logical formulas having identical truth tables.

Set

A collection of objects, where the individual objects are called its elements.

Universal Quantifier

The symbol $\forall$, which translates to 'for all'.

Existential Quantifier

The symbol $\exists$, which translates to 'there exists'.

Principle of Mathematical Induction

A proof method establishing that a statement holds for all natural numbers by showing it is true for $n = 1$ (base step) and proving that if it holds for $n$, it also holds for $n + 1$ (induction step).

Induction Hypothesis

The assumption made within a proof by induction that the statement $P(n)$ holds for a given natural number $n$.

Russell's Paradox

A logical paradox considering the set $S = \{K : K \text{ is a set and } K \notin K\}$, showing that assuming $S$ exists leads to a contradiction ($S \in S \Leftrightarrow S \notin S$), proving that not all collections are valid sets.