I think this is where we come in.
When we prove things by induction, we think about objects that have some sort of ordering to them, where the ability to reduce things to some smaller case allows us to understand it about all objects.
So, for example, in the natural numbers, we can do induction by reducing a case n to n-1, and thus reduce everything into the initial, empty, case of 0, so that knowing it is true for 0 means that it is true for all bigger numbers.
And maybe you've seen what's called "strong induction", where instead of just knowing it for 0 and for n-1, you assume you know it for every natural number m less than n. It is a neat exercise to show that this is the same thing.
Now, ideally, we would like to know what kind of things we can do induction on. And this notion of "reducing cases" perhaps, gives us a hint as to how we want to encode the notion of induction formally.
One of my previous posts shows how we can write out theories. So you might want to say something like "If it can always be reduced to just knowing the smaller cases, then you know it for everything."
So we put in the axioms of ordering so that we have a foundation that gives us a notion of "smaller case".
And perhaps with some rearranging you might say "for any given predicate, it being true for all cases less than n means it works for n, then it must work for all cases."
And you notice, perhaps, that there are two "foralls" going on, for all cases and for all predicates. In order to distinguish these, we will make two kinds of variables. In our language, capital letters will be predicates variables, and lowercase letters will be the actual objects.
Notably, having variables be predicates makes this a 'second-order' sentence. This might not be relevant, but by the compactness of the stone-topology of first order theories on all possible structures, this is not possible to encode in first order.
We will make the language just include a "<", with arity 2, some capital letter variables for predicates, and lowercase for objects, and write out our theory:
First, we want to specify the notion of an ordering, our "wishlist" for how we want to talk about big and small, which is:
1: Nothing is smaller than itself
2: , if something is smaller than something else, it is not bigger
3: If something is smaller than something else, it's also smaller than everything bigger.
∀a∀b∀c (a<b)∧(b<c) ⇒ (a<c)
4: Things are either the same, bigger, or smaller than each other.
∀a∀b (a ≠ b) ⇒ (a<b)∨(b<a)
Notably, this doesn't quite get 'all' the things we want to talk about, and later I will generalize to posets.
But for now, we also need to add in the induction axiom, the thing that makes this a well-ordering. The notion that for every thing you want to prove P, if you know that it is true that the smaller cases (y<x ⇒ P(y)) allow you to prove the current case (y<x ⇒ P(y) ⇒ P(x)), then you always know its true (P(x)).
5: You can do Induction on this ordering.
∀P (∀x (∀y y<x ⇒ P(y)) ⇒ P(x)) ⇒ ∀x P(x)
I recommend you spend some time convincing yourself this lines up for the natural numbers. Convince yourself that this does include the proof of 0, and the inductive step.
You can also check that the standard ordering and presentation of the Real Numbers does not work for induction, since you can have examples like "P(x) := x≤0", where in every instance where it is true for every number less than this, it is true for that number. So you might have to do something strange with the Reals, and so maybe it is beneficial to better understand "orderings where induction works" better. So we'll give these a name: "Well-orderings".
PART 2: EQUIVALENT NOTIONS
TFAE: (The following are all equivalent)
① Induction works. (∀P (∀x (∀y y<x ⇒ P(y)) ⇒ P(x)) ⇒ ∀x P(x))
② There are no infinite strictly descending sequences.
③ Every nonempty class in a well ordering has a minimum.
You can show it the following way.
Let Q be the statement "If a strictly descending sequence contains x, then it must be finite."
Applying Q to the inductive axiom, (∀x (∀y y<x ⇒ Q(y)) ⇒ Q(x)) ⇒ ∀x Q(x)
Take a free x, and assume it is true for all y less than x, (∀y y<x ⇒ Q(y)) and assume that a strictly descending sequence contains x. By the sequence being strictly descending, the next element must then contain some y<x, and by hypothesis, Q(y), so since the sequence contains y, it must be finite, therefore Q(x).
Since this fulfills the condition (∀x (∀y y<x ⇒ Q(y)) ⇒ Q(x)), by the application of Q to the inductive axiom, ∀x Q(x), therefore, if a sequence contains any element at all, it must be finite.
Corollary: Finite linear orders are all well-ordered, since they cannot have an infinite descending sequence.
We will prove this by contrapositive.
Assume some nonempty class Q has no minimum. Then choose some m₀ in Q. By Q having no minimum, m₀ is not the minimum, therefore you can choose another element. m₁ which is less than that. But you can again choose an m₂ which is less than even that. And an m₃. You can keep on doing this forever, since at no point there is a minimum. This is an infinitely descending sequence, so by contra-positive, we are done.
Corollary: You can take a minimum of a nonempty well ordering by taking the class P(x) := True, and finding its minimum.
Assume ③. Then there are two cases, the ordering is empty and the ordering is not. If there are no elements in the ordering, then ① holds vacously. Otherwise, let P be a class, and assume now that the first part of the inductive condition works on P: ∀x (∀y y<x ⇒ P(y)) ⇒ P(x)). Now all we have to do is show ∀x P(x).
Take the inverse of P, ¬P(x). If it contains some x', then by nonempty it must contain some x := min(¬P), but the condition ∀x (∀y y<x ⇒ P(y)) ⇒ P(x)) holds, and P is true for every element y less than x, implying it is true for x, and thus x is not the minimum, which is a contradiction. Therefore, ¬P is empty, so P must contain the entire well-ordering. Hence ∀x P(x).
It maybe makes sense to imagine these against the example of the natural numbers, but I recommend figuring out a few other well-orderings.
PART 3: OTHER WELL ORDERINGS
Let's find some more well-orderings! We already know the natural numbers are well ordered. What about the natural numbers, along with just an extra element, (let's call it ω), which is greater than all of them. Is that well-ordered?
What if we add another element? Let's call it ω+1, such that it is greater than all the other elements so far?
This video for example, may give you some insight on some more well-orderings, and some infinite well-orderings. Chess games with mate-in-infinity that must end in a finite amount of moves.
Some exercises, if you are willing:
(1) Which ones of these are well-orderings?
Under the usual ordering:
{1-1/n-1/(nm) : n, m >0 ∈ℕ}
Dictionary Ordering (Ordered by first different value).
The set of all functions ℕ→ℕ
The same functions, but restricted to the ones that map to 0 on all but a finite subset of the domain. (Only a finite amount of nonzero outputs).
A bit of playing around might give you a sense of the structure of well-orderings.
(2) Prove that every subset of a well-ordering is a well-ordering.
(3) Prove that you can always make a new well-ordering by adding an element which is "after" all the elements so far.
(4) An initial segment is a subset of a well-ordering such that every element in the well ordering is either in the initial segment or is an upper bound to it. Prove that every initial segment is a well ordering, and prove that the set of all initial segments of a well-ordering are well-ordered by inclusion.
(5) If you have a sequence wₙ such that each wₙ is well ordered and wₙ<wₙ₊₁ (Is an initial segment), then the union of all wₙ forms well-ordering (What about uncountable cases?)
PART 4: INDUCTIVE FUNCTIONS
It turns out we can also use inductions to construct functions! If we make a function where knowing what its output is for everything less than it tells you what its output is now, then, you can consider in what situations you know the value of it. So consider Q being the class of elements that the function f is defined on, then, plugging Q into induction, the "inductive definition" clears out the condition:
∀x (∀y y<x ⇒ Q(y)) ⇒ Q(x)
Therefore the function is defined everywhere.
This kind of function is also called "recursive".
An isomorphism is a bijective function that preserves all the structures we care about.
In groups, for example, it sends the identity to the identity, it takes products of elements to the products of the image of the elements, and inverses to inverses, therefore, as far as groups are concerned, they are the same thing.
Similarly, we can have isomorphisms of well-orderings, which in this case, are bijective functions that preserve the ordering.
For example, sending each element (n, m) in ℕ×ℕ to {1-1/n-1/(nm) : n, m >0 ∈ℕ} via the very function {1-1/(n+1)-1/((n+2)(m+n+1))} is an isomorphism.
In a same way, 2ⁿ is an isomorphism between ℕ and {2ⁿ : n∈ℕ}.
From here, it becomes relevant to show the following:
Every subset of a well ordering is isomorphic to an initial segment of itself.
For any pair of well-orderings α and β, then α is isomorphic to an initial segment of β, or β is isomorphic to an initial segment of α.
Proof:
We will prove 2, but 1 is an easy corollary.
Consider the following recursively defined function f from α to β.
f(x) = min {b∈β | ∄a∈α , f(a)=b}
There are two cases, this function is well defined, or this function is not well-defined.
Let a<b and say that f(b)<f(a). Let y=f(b). If since y<f(a), then some c less than a must have mapped to y, f(c)=y, but c<a<b, so c<b, so f(b), which is the minimum non-chosen element, cannot be y. Contradiction, so a<b means that f(a)<f(b) or f(a)=f(b). But if f(a)=f(b), then y must have been unchosen by the time we reached b, which means a couldn't have mapped to it, therefore a<b implies f(a)<f(b), therefore this preserves order.
The image of this is an initial segment, because let's say there's some element x that is not an upper bound and not in the image of f, then there is some minimum a such that f(a)>x, by properties of well-orderings. Then in that case, f(a) must equal the minimum of all the unchosen elements, which must include x, and therefore the solution must be less than or equal to x, not more.
Therefore, since it is injective, it is bijective to its image, and its image is an initial segment, making it an isomorphism to the initial segment, so α is isomorphic to an initial segment of β. Notably, this accounts for α is isomorphic to β, as the initial segment is just everything.
The other case is if the function is not defined everywhere. This can only happen if there is not a minimum left. Choose the minimum element it is not defined for, and take the set of all elements less than it. This is an initial segment, and by definition of minimum, it must all be in the image of f. This must be the complete image, as if it hits something above this, then it would be skipping some x, which we already showed it wasn't doing. By the same arguments, this is an isomorphism, therefore:
β is isomorphic to an initial segment of α.
This induces an ordering on all the well-orders, up to isomorphism. Using "β is isomorphic to an initial segment of α" as "β is less than or equal to α". Define "equals" as being isomorphic to, and less than as being less than or equal, but not equal.
You can show this is transitive, by following the isomorphism. The proof above shows the trichotomy law. Everything is isomorphic to itself by the identity, getting the reflexivity property, and if two things are isomorphic to initial segments of each other, they must be isomorphic to each other, as the map between them works the same both ways. Fully proving this is a good exercise.
If you consider that there's a "cannonical" ordering of all the possible well-orderings, you might decide to name a cannonical element for every possible well-ordering.
This is us! The ordinals. The canonical representation for every possible well-ordering.
You can show that we form a well-order: Consider any set of us, and pick one of us, and look at the well ordering of initial segments. Then you can consider only those of us less than it, and map them into the initial segments via the isomorphism. There must be a minimum, as the initial segments form a well-ordering, so you can trace it back via the isomorphism to the minimum ordinal.
So, how can you get this to "work" on the reals?
It turns out just doing "infinitesmals" doesn't quite give a well ordering. You can always trick it with open or closed sets in weird ways. For example, x<5. For any element that is less than five, it is still less when you add an infinitesmal, and yet at some point it does cross and become five, and then more. If you idea is that if you can show that you have a limiting sequence to it that is all true then it must be true, you can fool it with x≥5.
So you have to somehow leverage something to get that sweet finite cases. Maybe you can show that if its true at some point, then it must be true for a small region around that point, and then you can do the limiting sequence proof. If something is true at every limiting sequence, then you can always find one that limits towards the supremum, and realise that it must be included, and therefore an open set around it must, so it cannot be a supremum. You can similarly get everything greater than an element in the set, doing something like induction. This generally follows from compactness! Every infinite cover has a finite subcover. Therefore the solution to these is an open set of the form (a, inf), or (-inf, inf), or just (inf, inf) for when they don't happen at all.
There we go! Sorry for taking so long!
discoholicmusic
pixelskylines
tangentwithtanner
blakekathryn
turnnoffyourmind
baratheonpilled
andulkaphoto
jacobvanloon
kianamaiart
