Set theory - Chapter 1: Axioms of Set Theory

1.1

Suppose (a,b)=(c,d)(a,b)=(c,d). We shall use the axiom of extensionality to prove a=ca=c and b=db=d. Suppose one of the pair contains the same elements, for instance a=ba=b. Then {{c},{c,d}}\{\{c\},\{c,d\}\} is equal to {{a}}\{\{a\}\} and so has one element. Hence {c}={c,d}\{c\}=\{c,d\} and the same argument gives c=dc=d. Finally {{a}}={{c}}\{\{a\}\}=\{\{c\}\} and a=b=c=da=b=c=d. Otherwise, the two sets have two elements. The elements of same cardinality are equal: {a}={c}\{a\}=\{c\} and {a,b}={c,d}\{a,b\}=\{c,d\}. The first equality gives a=ca=c. Using this in the second equal, we get b=db=d. Conversely, it is clear that if a=ca=c and b=db=d we have (a,b)=(c,d)(a,b)=(c,d).

1.2

Suppose that 𝒫(X)X\operatorname{\mathcal{P}}(X)\subseteq X. Since X𝒫(X)X\in\operatorname{\mathcal{P}}(X) we get XXX\in X which contradicts the axiom of regularity: S={X}S=\{X\} has no \in-minimal element. Alternative proof (using result of chapter 3): |𝒫(X)||X||\operatorname{\mathcal{P}}(X)|\leq|X| contradicts Cantor’s theorem.

1.3

Let XX be inductive and Y={xX:xX}Y=\{x\in X:x\subseteq X\}. We shall show that YY is inductive:

  1. (1)

    X\emptyset\in X and X\emptyset\subseteq X so Y\emptyset\in Y

  2. (2)

    Let yYy\in Y then yXy\in X and yXy\subseteq X. Because XX is inductive, y{y}Xy\cup\{y\}\in X. Moreover, yXy\subseteq X and {y}X\{y\}\subseteq X, hence y{y}Xy\cup\{y\}\subseteq X. Consequently, y{y}Yy\cup\{y\}\in Y.

If nn\in\mathbb{N} then for all inductive set XX, nXn\in X. By the previous result, YX={xX:xX}Y_{X}=\{x\in X:x\subseteq X\} is inductive thus nYXn\in Y_{X} and nXn\subseteq X. Hence, n{X:X is inductive}=n\subseteq\bigcap\{X:X\text{ is inductive}\}=\mathbb{N} and \mathbb{N} is transitive.

Now let nn\in\mathbb{N} and Zn={m:m<n}Z_{n}=\{m\in\mathbb{N}:m<n\}. Clearly, ZnnZ_{n}\subseteq n by definition of <<. Conversely, \mathbb{N} is transitive, nn\subseteq\mathbb{N} so nZnn\subseteq Z_{n}. Finally n=Zn={m:m<n}n=Z_{n}=\{m\in\mathbb{N}:m<n\}.

1.4

Let XX be inductive and Y={xX:x is transitive}Y=\{x\in X:x\text{ is transitive}\}. X\emptyset\in X and \emptyset is transitive so Y\emptyset\in Y. Let yYy\in Y. Since X is inductive, y{y}Xy\cup\{y\}\in X. If zy{y}z\in y\cup\{y\} then either zyz\in y or z=yz=y. In the former case, zyz\subseteq y by transitivity of yy so zy{y}z\subseteq y\cup\{y\}. In the latter case, zy{y}z\subseteq y\cup\{y\} too. Hence y{y}y\cup\{y\} is transitive and y{y}Yy\cup\{y\}\in Y. Finally, YY is inductive.

Let nn\in\mathbb{N} and XX be inductive. Then nYX={xX:x is transitive}n\in Y_{X}=\{x\in X:x\text{ is transitive}\}. Hence nn is transitive.

1.5

Let XX be inductive and Y={xX:x transitive and xx}Y=\{x\in X:x\text{ transitive and }x\notin x\}. We shall show that YY is inductive:

  1. (1)

    Y\emptyset\in Y

  2. (2)

    If yYy\in Y then as in 1.4 y{y}y\cup\{y\} is transitive. Suppose y{y}y{y}y\cup\{y\}\in y\cup\{y\}. Then y{y}yy\cup\{y\}\in y or y{y}=yy\cup\{y\}=y. Because yy is transitive, the first case implies y{y}yy\cup\{y\}\subseteq y. In any case, we get yyy\in y which is a contradiction. Hence y{y}Yy\cup\{y\}\in Y.

Now let nn\in\mathbb{N} and XX be inductive. Then nYXn\in Y_{X} so nnn\notin n. But nn+1=n{n}n\in n+1=n\cup\{n\} so nn+1n\neq n+1.

1.6

Let XX be inductive and Y={xX:x is transitive and every nonempty zxhas an-minimal element}Y=\{x\in X:x\text{ is transitive and every nonempty }z\subseteq x\text{has an}% \in\text{-minimal element}\}. We shall show that YY is inductive:

  1. (1)

    Y\emptyset\in Y

  2. (2)

    As in 1.4, if yYy\in Y is transitive, then so is y{y}y\cup\{y\}. Let zz be a nonempty subset of y{y}y\cup\{y\}. Suppose z{y}z\setminus\{y\} is nonempty and let ee one of its \in-minimal elements. Then ee is also \in-minimal in zz for otherwise yeyy\in e\in y which contradicts the axiom of regularity. If z{y}=z\setminus\{y\}=\emptyset then obviously z={y}z=\{y\} has an \in-minimal element. Finally y{y}Yy\cup\{y\}\in Y.

1.7

Let XX\subseteq\mathbb{N} be a nonempty set and nXn\in X. If nX=n\cap X=\emptyset then nn is clearly a \in-minimal element of XX and we are done.

Suppose that nXn\cap X is nonempty. \mathbb{N} is inductive and its elements are transitive by exercise 1.4. The set of all mm\in\mathbb{N} such that every nonempty subset of mm has an \in-minimal element is inductive, so this set is \mathbb{N} itself. Hence the subset nXn\cap X of nn has an \in-minimal element ee. There is no xXx\in X such that xex\in e, otherwise it would belong to nXn\cap X by transitivity of nn. Finally ee is \in-minimal in XX.

1.8

Let XX be inductive and Y={xX:x=(y,x=y{y})}Y=\{x\in X:x=\emptyset\vee(\exists y,x=y\cap\{y\})\}. We shall show that YY is inductive:

  1. (1)

    Y\emptyset\in Y

  2. (2)

    If yYy\in Y then y{y}Xy\cap\{y\}\in X and consequently y{y}Yy\cap\{y\}\in Y.

Hence Y\mathbb{N}\subseteq Y and for all n0n\neq 0 there is yy such that n=y{y}n=y\cap\{y\}. We have yny\in n\in\mathbb{N} so yy\in\mathbb{N}. Finally n=y+1n=y+1.

1.9

Suppose A\mathbb{N}\neq A and let xx be \in-minimal in A\mathbb{N}\setminus A (such an element exists by exercise 1.7). 0A0\in A so x=y+1x=y+1 for some yy\in\mathbb{N}. But yAy\in A for otherwise xx would not be \in-minimal in A\mathbb{N}\setminus A. Thus x=y+1Ax=y+1\in A. A contradiction.

1.10

Let A={n:n is T-finite}A=\{n\in\mathbb{N}:n\text{ is }T-\text{finite}\}. We shall show that A=A=\mathbb{N} by induction (exercise 1.9) i.e. every set is TT-finite.

  1. (1)

    0A0\in A. If XX is an non-empty subset of 𝒫()={}\operatorname{\mathcal{P}}(\emptyset)=\{\emptyset\}, then X={}X=\{\emptyset\} and \emptyset is \subseteq-maximal in XX.

  2. (2)

    Let nAn\in A and X𝒫(n+1)X\subseteq\operatorname{\mathcal{P}}(n+1) a non-empty set. Let ee be a maximal element of the non-empty set {x{n}:xX}𝒫(n)\{x\setminus\{n\}:x\in X\}\subseteq\operatorname{\mathcal{P}}(n). If ee is maximal in 𝒫(n+1)\operatorname{\mathcal{P}}(n+1) then we are done. Otherwise, let’s show that f=e{n}f=e\cup\{n\} is maximal in 𝒫(n+1)\operatorname{\mathcal{P}}(n+1). If gfg\supseteq f then g{n}f{n}=eg\setminus\{n\}\supseteq f\setminus\{n\}=e hence g{n}=eg\setminus\{n\}=e by maximality of ee in 𝒫(n)\operatorname{\mathcal{P}}(n). Thus g=e{n}=fg=e\cap\{n\}=f.

1.11

For all nn\in\mathbb{N}, n+1=n{n}nn+1=n\cup\{n\}\subsetneq n shows that nn is not maximal. Hence 𝒫(n)\mathbb{N}\subseteq\operatorname{\mathcal{P}}(n) has no \subseteq- maximal element i.e. \mathbb{N} is TT-infinite.

1.12

Let f:Snf:S\rightarrow n be 1-1 onto. Let X𝒫(S)X\subseteq\operatorname{\mathcal{P}}(S) a nonempty set. Then Y={f(x):xX}Y=\{f(x):x\in X\} is nonempty and there exists a maximal element eYe\in Y. But x,yX,(xyf(x)f(y))\forall x,y\in X,(x\subseteq y\iff f(x)\subseteq f(y)). Hence f-1(e)f_{{-1}}(e) is \subseteq-maximal in XX and SS is TT-finite.

1.13

Let SS be infinite and X={uS:y is finite}X=\{u\subseteq S:y\text{ is finite}\}. XX is nonempty since X\emptyset\in X. Suppose XX has an \subseteq-maximal element ee. Then SeS\setminus e\neq\emptyset and there exists xSex\in S\setminus e. Then y=e{x}ey=e\cup\{x\}\supsetneq e. A contradiction. Finally, SS is TT-infinite.

1.14

Let X,pX,p be two sets and φ(u,p)\varphi(u,p) be a formula. Let F={(x,x):φ(x,p)}F=\{(x,x):\varphi(x,p)\}. By replacement, F(X)F(X) is set. x,(xF(X)(xXφ(x,p)))\forall x,(x\in F(X)\iff(x\in X\wedge\varphi(x,p))) and the separation axiom holds for φ,X,p\varphi,X,p.

1.15

  1. (1)

    For (1.8), let X,YX,Y such that xX,ux,uY\forall x\in X,\forall u\in x,u\in Y let Z={uY:xX,ux}Z=\{u\in Y:\exists x\in X,u\in x\}. Then Z=XZ=\bigcup X.

  2. (2)

    For (1.9) consider Z={uY:uX}Z=\{u\in Y:u\subseteq X\}.

  3. (3)

    For (1.10) consider Z={uY:xX,φ(x,u,p)Z=\{u\in Y:\exists x\in X,\varphi(x,u,p).

This page is W3C-compliant - Author: Frédéric WANG
Valid XHTML 1.1 Valid MathML 2.0 Valid SVG Valid CSS