1.2 Basic definitions and notation

Additive combinatorics blends number theory and combinatorics, focusing on the structure of sets under addition. This field explores how sets grow when combined and studies patterns in sumsets, laying the groundwork for understanding additive properties of integers and finite fields.

Basic definitions and notation are crucial in additive combinatorics. We'll cover essential concepts like sets, subsets, and their properties, as well as key operations like sumsets and difference sets. These fundamentals will help us tackle more complex problems in the field.

Essential terms in additive combinatorics

Sets, subsets, and their properties

• A set is a well-defined collection of distinct objects
• A subset is a set that is contained within another set
• The cardinality of a set refers to the number of elements in the set, denoted by $|A|$ for a set $A$
• The complement of a set $A$, denoted $A^c$, is the set of all elements in the universal set that are not in $A$
• The symmetric difference of two sets $A$ and $B$, denoted $A \triangle B$, is the set of elements that are in either $A$ or $B$, but not in both

Sums and differences of sets

• The sum of two sets $A$ and $B$, denoted $A + B$, is the set of all elements that can be expressed as the sum of an element from $A$ and an element from $B$
• The h-fold sum of a set $A$, denoted $hA$, is the set of all elements that can be expressed as the sum of $h$ elements from $A$
• The difference set of a set $A$, denoted $A - A$, is the set of all differences between pairs of elements in $A$
  • For example, if $A = \{1, 2, 3\}$, then $A - A = \{-2, -1, 0, 1, 2\}$

Mathematical notation in additive combinatorics

Set builder and interval notation

• Set builder notation, such as $\{x \in A : P(x)\}$, represents the set of all elements $x$ in $A$ that satisfy the condition $P(x)$
  • For example, $\{x \in \mathbb{N} : x \text{ is even}\}$ represents the set of all even natural numbers
• Interval notation, such as $[a, b]$ or $(a, b)$, represents the set of all real numbers between $a$ and $b$, inclusive or exclusive of the endpoints, respectively
  • For example, $[0, 1]$ represents the set of all real numbers between 0 and 1, including 0 and 1

Set operations and products

• The union of two sets $A$ and $B$, denoted $A \cup B$, is the set of all elements that are in either $A$ or $B$, or both
• The intersection of two sets $A$ and $B$, denoted $A \cap B$, is the set of all elements that are in both $A$ and $B$
• The Cartesian product of two sets $A$ and $B$, denoted $A \times B$, is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$
• The power set of a set $A$, denoted $\mathcal{P}(A)$, is the set of all subsets of $A$, including the empty set and $A$ itself

Types of sets and their properties

Finite and infinite sets

• A finite set is a set with a finite number of elements, while an infinite set has an infinite number of elements
  • For example, the set of natural numbers $\mathbb{N}$ is an infinite set, while the set $\{1, 2, 3\}$ is a finite set
• Countable sets are infinite sets that can be put into a one-to-one correspondence with the natural numbers, while uncountable sets cannot
  • The set of rational numbers $\mathbb{Q}$ is countable, while the set of real numbers $\mathbb{R}$ is uncountable

Structured sets and their axioms

• Structured sets, such as groups, rings, and fields, have additional properties and operations defined on them that satisfy certain axioms
• A group is a set with a binary operation that satisfies the group axioms: closure, associativity, identity, and inverses
  • For example, the set of integers $\mathbb{Z}$ under addition forms a group
• A ring is a set with two binary operations (addition and multiplication) that satisfy the ring axioms, which include the group axioms for addition and distributivity of multiplication over addition
  • For example, the set of integers $\mathbb{Z}$ under addition and multiplication forms a ring
• A field is a ring in which every non-zero element has a multiplicative inverse
  • For example, the set of real numbers $\mathbb{R}$ under addition and multiplication forms a field

Set addition in additive combinatorics

Definition and properties of set addition

• Set addition is a fundamental operation in additive combinatorics that combines elements from two or more sets to create a new set
• The sum set $A + B$ contains all possible sums of elements from $A$ and $B$, i.e., $\{a + b : a \in A, b \in B\}$
• Set addition is commutative ($A + B = B + A$) and associative ($(A + B) + C = A + (B + C)$)

h-fold sums and repeated sums

• The h-fold sum of a set $A$, denoted $hA$, is the set of all possible sums of $h$ elements from $A$, i.e., $\{a_1 + a_2 + ... + a_h : a_i \in A \text{ for all } i\}$
  • For example, if $A = \{1, 2\}$, then $2A = \{2, 3, 4\}$
• The repeated sum of a set $A$, denoted $A + A + ... + A$ ($h$ times), is equal to the h-fold sum $hA$
• Set addition is used to study the additive structure of sets and to prove important results in additive combinatorics, such as the Cauchy-Davenport theorem and Freiman's theorem