I've been having trouble working through Machover's text Set theory, Logic and Their Limitations - specifically problem 5.14 on pg 161. Which is as below
- Construct a sentence $\alpha$ containing only logical symbols (that is no function symbols and no predicate symbols other than =) such that $\alpha$ holds in a structure U iff the domain U of U has:
(i) Least $3$ members.
(ii) At most $3$ members.
(iii) Exactly $3$ members.
How would I then in another part for each of the above sentences prove that the valuation satisfies the sentence just in the case where it satisfies the condition?
i) Least $3$ members: $$\exists_{x_1}\exists_{x_2}\exists_{x_3}(x_1\in U\land x_2\in U\land x_3\in U\land x_1\neq x_2\land x_1\neq x_3\land x_2\neq x_3)$$
ii) At most $3$ members: $$\forall_{x_1}\forall_{x_2}\forall_{x_3}\forall_{x_4}((x_1\in U\land x_2\in U\land x_3\in U\land x_4\in U)$$ $$\to(x_1=x_2\lor x_1=x_3\lor x_1=x_4\lor x_2=x_3\lor x_2=x_4\lor x_3=x_4))$$
iii) Exactly $3$ members: $$\exists_{x_1}\exists_{x_2}\exists_{x_3}\forall_{x_4}((x_1\neq x_2\land x_1\neq x_3\land x_2\neq x_3)$$ $$\land(x_4\in U\leftrightarrow(x_4=x_1\lor x_4=x_2\lor x_4=x_3)))$$
In general we have:
$\text{Let n $\in\mathbb{N}$, at least $n$ element in $U$ we can denote as }\exists^{\ge n}x,x \in U \text{ that if and only if :}$ \begin{align} &\hspace{2ex}\exists_{x_1}\dots \exists_{x_n} \text{ s.t.}\underbrace{(x_1 \in U\wedge\dots\wedge x_n \in U)}_{\text{$x_1\dots x_n$ in $U$}} \wedge\underbrace{(x_1\neq x_2\land\dots\land x_1\neq x_n)\wedge\dots\wedge(x_{n-1}\neq x_n)}_{\text{$x_1\dots x_n$ are distinct}}\\ &\equiv\underset{i=1}{\overset{n}{\exists}}x_i,(\bigwedge_{i=1}^n x_i \in U)\wedge(\bigwedge_{i=1}^{n-1}(\bigwedge_{j=i+1}^nx_i\neq x_j))\\ \end{align} At most $n$ as $\exists^{\le n}x,x \in U, \text{ if and only if :}$ \begin{align} &\hspace{3ex}\exists^{<n+1}x,x \in U\equiv\neg(\exists^{\ge n+1}x,x \in U)\\ &\equiv\underset{i=1}{\overset{n+1}{\forall}}x_i,(\bigvee_{i=1}^{n+1} x_i \not\in U)\vee(\bigvee_{i=1}^n(\bigvee_{j=i+1}^{n+1}x_i=x_j))\\ \end{align}
Exactly $n$ as $\exists^{!n}x,x \in U\text{ if and only if :}$ \begin{align} &\hspace{3ex}\exists^{\ge n}x,x\in U\wedge\exists^{\le n}x,x\in U\equiv\exists^{\ge n}x,x \in U\wedge\neg(\exists^{\ge n+1}x,x\in U)\\ &\equiv\underset{i=1}{\overset{n}{\exists}}x_i\forall_{x_{n+1}}~(x_{n+1} \in U\leftrightarrow(\bigvee_{i=1}^nx_i=x_{n+1}))\wedge\bigwedge_{i=1}^{n-1}(\bigwedge_{j=i+1}^nx_i\neq x_j)\\ \end{align}