Set Proofs

Elements of sets

Many types of theorems can be expressed as questions about the relationship between sets. Sometimes it’s a question of membership.

Theorem: For any natural numbers \(a\) and \(b\) there exist integers \(k\) and \(l\) such that \[ \gcd(a,b)=ak+bl. \]

Theorem: Let \(a\) and \(b\) be natural numbers, and let \(A=\{ax+by:x,y\in\mathbb{Z}\}\). Then \(\gcd(a,b)\in A\).

More examples

General situation: \(A=\{x\in S: P(x)\hbox{\rm\ is true}\}\). Then \[ x\in A \Leftrightarrow (x\in S)\wedge P(x). \]

Let \(A=\{3x+2: x\in\mathbb{Z}\}\). Then \(14\in A\).
Let \(A=\{3x+2: x\in\mathbb{Z}\}\). If \(x\equiv 2\pmod{3}\), then \(x\in A\).

More examples

Let \(B\) be the set of \(X\in\mathcal{P}(\mathbb{N})\) such that, for all \(x\in X\) and \(y\in X\), \(|x-y|<2\).

Is \(\{-1,2\}\in B\)? Is \(\{0,1\}\)?