Unit 1: Sets and Propositions

Introduction to Sets and Propositions

In the realm of mathematics and logic, sets and propositions form foundational concepts. Sets deal with the collection of objects, while propositions focus on the logical statements and their validity. This unit introduces the basic operations on sets, the principles governing logical connectives, and their applications in various domains such as computer science, mathematics, and engineering.

Sets

Definition of a Set

A set is a collection of well-defined, distinct objects, known as elements or members. Sets are commonly denoted by capital letters, and their elements are listed within curly braces. For example:

Set of natural numbers: $S = \{1, 2, 3, 4, \dots\}$
Set of vowels in the English alphabet: $V = \{a, e, i, o, u\}$

Sets can be either finite (having a specific number of elements) or infinite (endless elements). Sets can also be countable or uncountable depending on the nature of their elements.

Combinations of Sets

Several operations can be performed on sets to combine or compare them. Some of the most important operations include:

Union $A \cup B$ : The set of all elements that are in $A$ or $B$ , or both.

A \cup B = \{x : x \in A \text{ or } x \in B\}

Intersection $A \cap B$ : The set of all elements that are in both $A$ and $B$ .

A \cap B = \{x : x \in A \text{ and } x \in B\}

Difference $A - B$ : The set of all elements that are in $A$ but not in $B$ .

A - B = \{x : x \in A \text{ and } x \notin B\}

Complement $A^c$ : The set of all elements not in $A$ , typically taken from a universal set $U$ .
$A^c = \{x : x \notin A\}$

Venn Diagrams

A Venn diagram is a graphical way to represent sets and their relationships. Circles represent sets, and overlapping regions represent intersections between sets. Below is an example of a Venn diagram representing two sets, $A$ and $B$ :

+------------+
|            |
|   +-----+  |
|   |     |  |   Region of intersection \(A \cap B\)
|   +-----+  |
|            |
+------------+

Venn diagrams are useful in visualizing operations like union, intersection, and difference.

Finite and Infinite Sets

Finite sets have a specific number of elements. For example, the set of days in a week: $D = \{Monday, Tuesday, \dots, Sunday\}$ .
Infinite sets do not have a fixed number of elements. For example, the set of all natural numbers: $N = \{1, 2, 3, \dots\}$ .

Countable and Uncountable Sets

Countable sets can be listed in a sequence, meaning there is a one-to-one correspondence with the natural numbers. For example, the set of even numbers $E = \{2, 4, 6, \dots\}$ .
Uncountable sets cannot be listed in such a sequence. For example, the set of real numbers between 0 and 1 is uncountable.

Multisets

A multiset allows for multiple occurrences of its elements. Unlike sets, where each element appears only once, a multiset permits repetition.

For example:

$A = \{1, 1, 2, 3\}$ is a multiset where the element $1$ appears twice.

Principle of Inclusion and Exclusion

The principle of inclusion and exclusion is a formula used to find the number of elements in the union of multiple sets by adding and subtracting the sizes of individual and intersecting sets.

For two sets, $A$ and $B$ , the formula is:

|A \cup B| = |A| + |B| - |A \cap B|

For three sets, $A$ , $B$ , and $C$ , the formula is:

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

Mathematical Induction

Mathematical induction is a method of proof used to establish the truth of an infinite number of cases. It consists of two steps:

Base case: Prove that the statement is true for an initial value usually $n = 0$ or $n = 1$ .
Inductive step: Prove that if the statement is true for some arbitrary case $n = k$ , then it is true for $n = k+1$ .

For example, to prove the formula for the sum of the first $n$ natural numbers:

S = 1 + 2 + \dots + n = \frac{n(n+1)}{2}

Base case: For $n = 1$ , the sum is $1$ , and the formula gives $frac{1(1+1)}{2} = 1$ , so the base case holds.
Inductive step: Assume it holds for $n = k$ , i.e., $S_k = \frac{k(k+1)}{2}$ . Now prove for $n = k+1$ :

S\_{k+1} = S_k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}

Propositions

Definition of Propositions

A proposition is a declarative statement that is either true or false, but not both. Examples include:

"The sky is blue" (True).
"2 + 2 = 5" (False).

Logical Connectives

Logical connectives are symbols that combine propositions to form more complex logical expressions. The most common connectives are:

Negation $\neg p$ : The opposite of proposition $p$ . If $p$ is true, $\neg p$ is false, and vice versa.

Example: If $p$ is "It is raining," $\neg p$ is "It is not raining."
Conjunction $p \land q$ : True if both $p$ and $q$ are true.

Example: "It is raining and it is cold."
Disjunction $p \lor q$ : True if at least one of $p$ or $q$ is true.

Example: "It is raining or it is sunny."
Implication $p \rightarrow q$ : True unless $p$ is true and $q$ is false.

Example: "If it rains, the ground will be wet."
Biconditional $p \leftrightarrow q$ : True if $p and$ q$ are either both true or both false.

Example: "The light is on if and only if the switch is up."

Conditional and Biconditional Propositions

Conditional proposition $p \rightarrow q$ : This statement asserts that if $p$ is true, then $q$ must also be true.

Example: "If it is raining, then the ground is wet."
Biconditional proposition $p \leftrightarrow q$ : This statement asserts that $p$ is true if and only if $q$ is true.

Example: "The light is on if and only if the switch is up."

Logical Equivalence

Two propositions are logically equivalent if they have the same truth value in all possible situations. Logical equivalence can be verified using truth tables.

For example, the propositions $p \rightarrow q$ and $\neg p \lor q$ are logically equivalent.

Validity of Arguments using Truth Tables

A truth table helps determine the truth value of compound propositions for all possible combinations of truth values of the individual propositions.

Example:

$p$	$q$	$p \rightarrow q$	$\neg p \lor q$
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

Since the columns for $p \rightarrow q$ and $\neg p \lor q$ are the same, the

two propositions are logically equivalent.

Predicates and Quantifiers

Predicates are statements that contain variables and become propositions when the variables are specified.

Example: "x is greater than 5" is a predicate.
Quantifiers are symbols used to express the extent to which a predicate applies to a set of elements.
- Universal quantifier $\forall$ : "For all" or "for every."
- Existential quantifier $\exists$ : "There exists" or "for some."

Normal Forms

Logical expressions can be simplified into normal forms, which include:

Conjunctive Normal Form (CNF): A conjunction of disjunctions.
Disjunctive Normal Form (DNF): A disjunction of conjunctions.

Applications of Sets and Propositions

Computer Science: Sets are used in databases, search algorithms, and artificial intelligence. Propositions form the basis of Boolean logic in circuit design and programming.
Mathematics: Sets and propositions are fundamental in various areas like number theory, topology, and analysis.
Logic and Reasoning: Propositions are crucial in formal proofs, argument validation, and logical reasoning.

By mastering sets and propositions, we build a foundation for more advanced mathematical and computational concepts.

Introduction Unit-02