1.0 Sets, functions and proof language

Sets and quantifiers

A set is determined by its elements. $A\subseteq B$ means every element of $A$ belongs to $B$; equality means both inclusions. The union $A\cup B$ contains elements in at least one set, while the intersection $A\cap B$ contains elements in both. Relative to a fixed universe $X$, the complement is $A^c=X\setminus A$. The difference $A\setminus B$ contains elements of $A$ not in $B$.

The negation of “for every $x$, there exists $y$ with property $P(x,y)$” is “there exists $x$ such that for every $y$, $P(x,y)$ fails.” The order matters: one $y$ working for every $x$ is stronger than being allowed a different $y$ for each $x$. Analysis definitions such as uniform continuity and uniform convergence depend on precisely this distinction.

Theorem

De Morgan's laws

For subsets of a fixed universe, $(A\cup B)^c=A^c\cap B^c$ and $(A\cap B)^c=A^c\cup B^c$.

Proof

Element-by-element proof

An element $x$ belongs to $(A\cup B)^c$ exactly when it is not in $A$ and not in $B$, which is exactly membership in $A^c\cap B^c$. The second identity follows similarly, replacing “not both” with “at least one not.” Each equivalence establishes both inclusions.

Worked example

A quantifier trap

For every real $x$ there exists a real $y$ with $y>x$: take $y=x+1$. But there is no single real $y$ greater than every real $x$: if there were, taking $x=y+1$ gives a contradiction. Changing quantifier order changes the assertion.

Functions, images and inverse images

A function $f:X\to Y$ assigns each $x\in X$ exactly one element $f(x)\in Y$. It is injective if equal outputs imply equal inputs, surjective onto $Y$ if every $y\in Y$ has a preimage, and bijective if both hold. A bijection has an inverse function $f^{-1}:Y\to X$.

For $A\subseteq X$, the image is $f(A)=\{f(x):x\in A\}$. For $B\subseteq Y$, the inverse image is $f^{-1}(B)=\{x\in X:f(x)\in B\}$. This inverse-image notation makes sense for every function, even when an inverse function does not exist.

Theorem

Inverse images preserve unions and intersections

For $B,C\subseteq Y$, $f^{-1}(B\cup C)=f^{-1}(B)\cup f^{-1}(C)$ and $f^{-1}(B\cap C)=f^{-1}(B)\cap f^{-1}(C)$. Images always satisfy $f(A\cup D)=f(A)\cup f(D)$, but only $f(A\cap D)\subseteq f(A)\cap f(D)$ in general.

Proof

Membership tracks the logic

For example, $x\in f^{-1}(B\cap C)$ if and only if $f(x)\in B$ and $f(x)\in C$, which is equivalent to $x\in f^{-1}(B)\cap f^{-1}(C)$. For image intersections, every output from $A\cap D$ belongs to each image, but the same output may arise from two different inputs, one in each set, even if no input belongs to both.

Worked example

Image of an intersection can be smaller

Let $f:\mathbb R\to\mathbb R$ be $f(x)=x^2$, $A=\{-1\}$, and $D=\{1\}$. Then $A\cap D=\varnothing$ and $f(A\cap D)=\varnothing$, but $f(A)\cap f(D)=\{1\}$. Noninjectivity creates the discrepancy.

Countability

A set is countable if it is finite or can be put in bijection with $\mathbb N$; some authors use “countable” to mean countably infinite, so state the convention. The integers are countable by listing $0,1,-1,2,-2,\ldots$. The rational numbers are countable: enumerate integer numerator and positive denominator pairs in diagonals and omit repetitions. In contrast, $\mathbb R$ is uncountable; a diagonal argument constructs a decimal in $(0,1)$ different from every entry in any proposed list, taking care to choose digits such as $1$ or $2$ to avoid ambiguous trailing-nine representations.

Method comparison

Prove set equality by double inclusion or a chain of equivalent membership statements. To disprove a universal assertion, give one explicit counterexample. For inverse images, translate membership through the function; do not assume it is an inverse function. To negate a quantified limit statement, reverse each quantifier and negate the final inequality carefully.

Practice

1. Prove $A\subseteq B$ if and only if $A\cap B=A$.
2. Negate “for every $\varepsilon>0$ there exists $N$ such that for all $n\ge N$, $|x_n-L|<\varepsilon$.”
3. For $f(x)=x^2$ on $\mathbb R$, find $f^{-1}([1,4])$.
4. Give two disjoint sets whose images under the same function intersect.

Full solutions

1. If $A\subseteq B$, exactly the elements of $A$ lie in both, so $A\cap B=A$. Conversely, if $A\cap B=A$, every $x\in A$ is in the intersection and hence belongs to $B$.
2. There exists $\varepsilon_0>0$ such that for every $N$ there exists $n\ge N$ with $|x_n-L|\ge\varepsilon_0$.
3. $1\le x^2\le4$ holds exactly on $[-2,-1]\cup[1,2]$.
4. Take $A=\{-1\}$, $B=\{1\}$ and $f(x)=x^2$. The sets are disjoint but both images are $\{1\}$.

Synthesis

Set membership and quantifier order are the grammar of analysis. Images, inverse images and counterexamples make that grammar concrete; precise quantification becomes essential when comparing pointwise and uniform statements.