0

I can't find a statement of the well-ordering principle that is an if-then statement that uses as much mathematical symbolic notation as possible. I want the if-then statement to involve an inequality, subset notation, invoke the natural numbers, use for all $\forall$ and $\exists$there exists.

I also want to write the if-then statement as a contrapositive which I can do if I'm given the implication statement.

2 Answers2

1

$$(\forall S\subset\mathbb{N}):(S=\emptyset\vee(\exists x\in S)(\forall y\in S):x\leqslant y)$$

José Carlos Santos
  • 427,504
  • shouldn't S be non-empty? –  Jun 11 '17 at 18:07
  • @brittany No, the point is "either $S$ is empty or it has a least element." (There are of course other ways to express it, e.g. "If $S$ is nonempty then it has a least element.") – Noah Schweber Jun 11 '17 at 18:07
  • Does there exists an S $\subset$ $\mathbb{N}$ in your statement that is not equal to $\mathbb{N}$? For example the set S does not contain all the elements of N. Card $S$<= Card$\mathbb{N}$ or S={1,2,3,4,5} $\neq$ $\mathbb{N}$? –  Jun 11 '17 at 18:16
  • @brittany Sure. Every subset $S$ of $\mathbb N$ fulfills the condition of my statement. Do you disagree? – José Carlos Santos Jun 11 '17 at 18:18
0

Whoops, this is the induction principle. Still, this might be helpful to the OP (and of course they're equivalent), so I'll leave it up.

$$\forall S[S\subseteq \mathbb{N}\wedge 0\in S\wedge\forall n(n\in\mathbb{N}\wedge n\in S\implies n+1\in S)\implies S=\mathbb{N}].$$

In case you haven't seen this symbol before, "$\wedge$" is the logical symbol for "and." think of it as being like set intersection: $x\in A\cap B$ iff $x\in A\wedge x\in B$.

Translation: "For every set $S$, if $S$ is a set of natural numbers which contains $0$ and contains $n+1$ whenever it contains $n$, then $S$ is all of $\mathbb{N}$."

Note that this isn't strictly a conditional: it has the form "$\forall(\implies)$," not just "$\implies$." Similarly, the "contrapositive" will have a "$\forall$" on the outside - really, what you'll be doing is taking the contrapositive of the inside of the expression above.

Often, though, the "$\forall S$" is left out; what we get then isn't strictly a sentence, since it has a free variable (namely, $S$), but we often conflate a formula $\varphi(x_1, ..., x_n)$ with some free variables with the sentence $\forall x_1...\forall x_n(\varphi(x_1, ..., x_n))$ when no confusion will arise (but this is an abuse of notation).

Noah Schweber
  • 245,398