Sets, Functions & Logic Mastery | EverExams.com
Font:

Introduction to Sets, Functions & Logic

Set theory, functions, and mathematical logic form the foundation of modern mathematics. These concepts are essential for understanding higher mathematics, computer science, and formal reasoning.

This comprehensive guide covers:

  • Set Theory – Types of sets, operations, Venn diagrams
  • Mathematical Logic – Propositions, truth tables, quantifiers
  • Functions – Types, properties, inverses
  • Algebraic Structures – Groupoids, semigroups, monoids, groups
  • Relations – Cartesian products, binary relations

Each section includes interactive diagrams, memory tips, and practical examples to help you master these concepts.

Interactive Learning Features

This guide includes interactive elements to enhance your learning:

  1. Animated Venn Diagrams – Visualize set operations
  2. Interactive Truth Tables – Understand logical operations
  3. Function Diagrams – Visual representation of functions
  4. Memory Tips – Click to reveal learning strategies
  5. Comprehensive Quiz – Test your knowledge with 50 MCQs
  6. Day/Night Mode – Study comfortably at any time
  7. Adjustable Font Size – Customize your reading experience

Use these features to make your study sessions more effective and engaging.

Learning Tip

Start with basic set concepts before moving to more advanced topics. Visualize each concept using the interactive diagrams to build intuition before memorizing definitions.

What is a Set?

A set is a well-defined collection of distinct objects. Sets are usually denoted by capital letters (A, B, C,…) and their elements by small letters (a, b, c,…).

Three Ways to Describe a Set:

  1. Descriptive Method: Described in words
    “The set of all vowels in the English alphabet”
  2. Tabular/Roster Form: Listing elements
    A = {a, e, i, o, u}
  3. Set-Builder Form: Using a property
    A = {x | x is a vowel in English alphabet}

Important Sets:

  • ℕ = {1, 2, 3, …} – Natural numbers
  • W = {0, 1, 2, 3, …} – Whole numbers
  • ℤ = {…, -2, -1, 0, 1, 2, …} – Integers
  • ℚ = {p/q | p,q ∈ ℤ, q ≠ 0} – Rational numbers
  • ℝ – Real numbers

Memory Tip

Remember: In roster form, each element is listed only once, and order doesn’t matter. {1, 2, 3} is the same as {3, 1, 2}.

Types of Sets

1. Equal Sets: Sets with exactly the same elements

A = B ⇔ ∀x (x ∈ A ⇔ x ∈ B)

2. Equivalent Sets (≈): Sets with same number of elements (same cardinality)

A ≈ B ⇔ |A| = |B|

3. Singleton Set: Set with exactly one element

A = {a}

4. Empty/Null Set (∅ or {}): Set with no elements

5. Finite Set: Set with finite number of elements

6. Infinite Set: Set with infinite number of elements

7. Subset (⊆): A ⊆ B if every element of A is in B

A ⊆ B ⇔ ∀x (x ∈ A ⇒ x ∈ B)

Note: Empty set is subset of every set. Every set is subset of itself.

Power Set & Universal Set

Power Set P(A): Set of all subsets of A

If A = {1, 2}, then P(A) = {∅, {1}, {2}, {1,2}}

Formula: If |A| = n, then |P(A)| = 2ⁿ

Number of subsets: 2ⁿ

Number of proper subsets: 2ⁿ – 1

Number of improper subsets: 1 (the set itself)

Universal Set (U): Set containing all sets under discussion

Acts as the “universe of discourse” for a particular context.

Example: If discussing sets of animals, U could be “set of all animals”

Basic Set Operations

Explore set operations with this interactive Venn diagram:

A
B

Union (A ∪ B): Elements in A OR B (or both)

A ∪ B = {x | x ∈ A ∨ x ∈ B}

Intersection (A ∩ B): Elements in A AND B

A ∩ B = {x | x ∈ A ∧ x ∈ B}

Difference (A – B): Elements in A but not in B

A – B = {x | x ∈ A ∧ x ∉ B}

Complement (A’ or Aᶜ): Elements not in A (relative to U)

A’ = {x ∈ U | x ∉ A}

Visual Memory Tip

Use the Venn diagram above to visualize each operation. Union looks like both circles together. Intersection is the overlapping part. Difference is one circle minus the overlap.

Properties of Set Operations

Commutative Laws:

A ∪ B = B ∪ A
A ∩ B = B ∩ A

Associative Laws:

(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributive Laws:

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

De Morgan’s Laws:

(A ∪ B)’ = A’ ∩ B’
(A ∩ B)’ = A’ ∪ B’

Identity Laws:

A ∪ ∅ = A
A ∩ U = A

Complement Laws:

A ∪ A’ = U
A ∩ A’ = ∅

Disjoint & Overlapping Sets

Disjoint Sets: Sets with no common elements

A ∩ B = ∅

Example: A = {1, 2}, B = {3, 4} are disjoint

Overlapping Sets: Sets with some common elements

A ∩ B ≠ ∅

Example: A = {1, 2, 3}, B = {3, 4, 5} are overlapping

Important Results:

  • A – B and B – A are always disjoint
  • A – B, A ∩ B, and B – A are mutually disjoint
  • A ∪ B = (A – B) ∪ (A ∩ B) ∪ (B – A)
  • If A ⊆ B, then A – B = ∅ and B – A ≠ ∅ (unless A = B)

Mathematical Logic Basics

Proposition/Statement: A declarative sentence that is either true (T) or false (F), but not both.

Example: “2 + 2 = 4” is a proposition (True)
“x + 2 = 5” is NOT a proposition (depends on x)

Logical Connectives:

  • Negation (¬): “Not p” – Opposite truth value
  • Conjunction (∧): “p and q” – True only when both are true
  • Disjunction (∨): “p or q” – True when at least one is true
  • Implication/Conditional (→): “If p then q” – False only when p is true and q is false
  • Biconditional (↔): “p if and only if q” – True when both have same truth value

Memory Tip

For implication p→q: Remember it’s false ONLY when p is true and q is false. In all other cases (p false, or both true), it’s true. Think: “A false promise is not a lie.”

Truth Tables

Interactive truth table for basic connectives:

p q ¬p p ∧ q p ∨ q p → q p ↔ q
T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T

Related Conditionals:

  • Converse: q → p
  • Inverse: ¬p → ¬q
  • Contrapositive: ¬q → ¬p

Important: A conditional and its contrapositive are logically equivalent. Converse and inverse are logically equivalent.

Tautologies, Contradictions & Quantifiers

Tautology: A statement that is always true

Example: p ∨ ¬p (Law of Excluded Middle)

Contradiction/Absurdity: A statement that is always false

Example: p ∧ ¬p (Law of Contradiction)

Contingency: A statement that can be true or false

Most statements are contingencies

Quantifiers:

  • Universal Quantifier (∀): “For all” or “For every”
  • Existential Quantifier (∃): “There exists” or “For some”
∀x P(x) means “P(x) is true for all x”
∃x P(x) means “There exists at least one x for which P(x) is true”

Negation of Quantifiers:

¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x)

Functions & Relations

Cartesian Product: A × B = {(a, b) | a ∈ A, b ∈ B}

If |A| = m, |B| = n, then |A × B| = m × n

Relation: Any subset of A × B

R ⊆ A × B

Function: A special relation where each element of A is related to exactly one element of B

f: A → B where ∀a ∈ A, ∃! b ∈ B such that (a, b) ∈ f
Domain A
Codomain B

Types of Functions:

  • Into Function: Range ⊂ Codomain
  • Onto/Surjective: Range = Codomain
  • 1-1/Injective: Distinct elements have distinct images
  • Bijective: Both 1-1 and onto

Algebraic Structures

Groupoid: A set with a binary operation (closure property)

Semi-group: Groupoid + Associative property

Monoid: Semi-group + Identity element

Group: Monoid + Inverse for every element

Abelian Group: Group + Commutative property

Hierarchy: Groupoid ⊂ Semi-group ⊂ Monoid ⊂ Group ⊂ Abelian Group

Examples:

  • (ℤ, +) is an abelian group
  • (ℕ, +) is a semi-group (not a group – no inverses)
  • (ℝ, ×) is a monoid (not a group – 0 has no inverse)
  • (ℝ\{0}, ×) is an abelian group
  • (ℤₙ, +) is a finite abelian group

Memory Tip

Remember the hierarchy using the acronym “GSM-GA”: Groupoid, Semi-group, Monoid, Group, Abelian Group. Each adds one more property: Closure → Associativity → Identity → Inverses → Commutativity.

Important Results

Properties of Groups:

  • Identity element is unique
  • Inverse of each element is unique
  • Left identity = Right identity
  • Left inverse = Right inverse
  • Cancellation laws hold
  • (a⁻¹)⁻¹ = a
  • (ab)⁻¹ = b⁻¹a⁻¹

Special Groups:

  • ℤₙ = {0, 1, 2, …, n-1} is a group under addition modulo n
  • U(n) = {k ∈ ℤₙ | gcd(k, n) = 1} is a group under multiplication modulo n
  • Sₙ (symmetric group) is a non-abelian group for n ≥ 3

Function Composition:

If f: A → B and g: B → C, then g∘f: A → C

Function composition is associative but not commutative.

Sets, Functions & Logic Quiz

Questions 1/50
Correct 0
Time
30:00
Question 1 of 50
Loading question…

Quiz Results

You have completed the Sets, Functions & Logic Quiz

0/50
0%
Correct Answers
0
Incorrect Answers
0
Time Taken
0:00
Percentage
0%

Answer Key

Study Guidelines for Students

Follow these guidelines to effectively master Sets, Functions, and Logic:

1. Study Strategy

  • Start with definitions: Master the precise definitions of sets, relations, functions
  • Visualize concepts: Use Venn diagrams for sets, arrow diagrams for functions
  • Practice with examples: Work through examples for each type of set/function
  • Connect concepts: See how set operations relate to logical operations

2. Memory Techniques

  • Use visual memory: Associate each set operation with its Venn diagram
  • Create mnemonics: For truth tables (e.g., “Implies is false only when T→F”)
  • Make summary charts: Create comparison tables for different types of sets/functions
  • Use flashcards: For definitions, properties, and formulas

3. Problem-Solving Tips

  • Draw diagrams: Always sketch Venn diagrams for set problems
  • Use truth tables: For complex logical statements
  • Check conditions: Verify all conditions for groups/algebraic structures
  • Work systematically: Follow step-by-step approaches for proofs

4. Common Pitfalls to Avoid

  • Don’t confuse ∈ (element of) with ⊆ (subset of)
  • Remember that ∅ is different from {∅} (the set containing empty set)
  • For functions, check that each input has exactly one output
  • In logic, remember that p→q is true when p is false (vacuous truth)
  • Don’t assume all groups are commutative (only abelian groups are)

5. Exam Preparation

  • Practice with the quiz: Take it multiple times until you get 100%
  • Review incorrect answers: Understand why each mistake was made
  • Create concept maps: Show relationships between different topics
  • Time yourself: Practice solving problems within time limits

6. Recommended Study Schedule

  • Week 1: Basic Set Theory & Operations (3-4 hours)
  • Week 2: Relations & Functions (3-4 hours)
  • Week 3: Mathematical Logic (3-4 hours)
  • Week 4: Algebraic Structures (4-5 hours)
  • Week 5: Review & Practice Tests (5-6 hours)

Additional Resources

To further enhance your understanding:

  • Textbooks: “Discrete Mathematics and Its Applications” by Rosen, “A Book of Set Theory” by Pinter
  • Online platforms: Coursera’s “Introduction to Mathematical Thinking”, edX’s “Discrete Mathematics”
  • Practice websites: Brilliant.org for logic puzzles, Wolfram Alpha for set operations
  • YouTube channels: Numberphile, 3Blue1Brown, TrevTutor for discrete math

Remember: Mathematics is not a spectator sport. Work through problems actively, draw diagrams, and explain concepts in your own words to solidify your understanding.