#j'th

[a-googology-acount]

Extensible Buchholz's Function

I've created an extensible ordinal collapsing based on Buchholz's Function. It works by making the index/domain more flexible.

Original Definition

Buchholz's ψ is a mapping from pairs of ordinals to ordinals. The original definition of extended Buchholz's function is:

ψ(α,ν)=min{β|β∉C(α,ν)}

C(α,ν)=∪{C(α,ν,n)|n∈ℕ}

C(α,ν,0)=Ω(ν)

C(α,ν,n+1)={γ+δ,ψ(ξ,μ)|γ,δ,ξ,μ∈C(α,ν,n)∧ξ<α}

Ω(ν)={ν=0:1,ν≠0:ℵ(ν)}

Rule one states that ψ(α,ν) is the least ordinal that isn't in the set C(α,ν). Rule two states that C(α,ν) is the union of all its steps, C(α,ν,n) for all natural numbers n. Rule three states that the first (or zeroth if you're weird) step is equal to Ω(ν). Rule four states that each step consists of γ+δ for γ and δ in the previous step together with ψ(ξ,μ) where ξ and μ are also in the previous step, but ξ is limited by α. Rule five states that Ω(ν) is 1 (a set containing only 0) if ν=0 and the 1+ν'th cardinal, ℵ(ν) if it isn't.

This sort-of comes down to that ν denotes the domain of ψ(α,ν), e.g. ψ(α,0) is in the domain of the first cardinal and ψ(α,ω) is in the domain of the ω+1'th cardinal. And ψ(α,ν) is the least ordinal in the domain Ω(ν+1) that can't be made using a system consisting of the binary operator +, the constant 0 and the binary function ψ which is limited by α.

Extensible Definition

My extensible definition depends on the function T which maps classes of ordinals to classes with preorder (the binary relation < is defined in that class), this is why T in this isn't defined and this is how this definition is extensible. Examples of T are: T(α)=ω+1 for Buchholz's function and T(α)=α for extended Buchholz's function. Now, ψ is a mapping from pairs consisting of an ordinal and an element of T(On), where On denotes the class of ordinals. The new definition is:

ψ(α,ν)=min{β|β∉C(α,ν)}

C(α,ν)=∪{C(α,ν,n)|n∈ℕ}

C(α,ν,0)=Ω(ν)

C(α,ν,n+1)={γ+δ,ψ(ξ,μ)|γ,δ,ξ∈C(α,ν,n)∧μ∈T(C(α,ν,n))∧ξ<α}

Ω(ν)={∄μ∈T(On):μ<ν:1,∃μ∈T(On):μ<ν:min{ℵ(1+β)|β∈On∧∀μ<ν:μ∈C(0,μ)→Ω(μ)<ℵ(1+β)}}

Rule one, two and three are the same as in the original definition, ψ(α,ν) is the smallest ordinal not in C(α,ν), C(α,ν) is a union of all its steps and the first step of C(α,ν) is Ω(ν). The fourth rule is a little different, instead of μ being an element of C(α,ν,n) it is now defined to be an element of T(C(α,ν,n)) as the second argument of ψ must be an element of T(On). Rule five is where the largest change is, the domain of ψ(α,ν) is now defined in the following way: Ω(ν) is still one if ν is the least element of T(On) but if it isn't, then Ω(ν) is the least cardinal for which for all μ<ν which are in T(On), if μ is in C(0,μ) then Ω(μ) must be less than Ω(ν)=ℵ(1+β). The reason that I defined it as ℵ(1+β) and not as ℵ(β) is because ℵ(0) shouldn't be a possible domain. It sort of comes down that T(On) is a preordered class for which for two elements, ν and μ, of T(On), if ν<μ then Ω(ν)<Ω(μ) (as long as ν and μ can be constructed using ψ, 0, + T(α)).

Example

An example definition of T is the following:

T(α)={ν|ν⊆α²∧|ν|<ℵ(0)∧∀a∈On:(∃!b:(a,b)∈ν)∨∄b:(a,b)∈ν}

ν[a]={∃b∈On:(a,b)∈ν:b,∄b∈On:(a,b)∈ν:0}

ν<μ: ∃i∈On:ν[i]<μ[i]∧∄j>i:ν[j]>μ[j]

In this way, T(α) is defined to be the set of all ν which are transfinitary arrays for which ν is a finite subset of α² (the set of all pairs of elements of α) for which there doesn't exists two pairs in it with the same first element. The first element of a pair in ν denotes index and the second element denotes the value e.g. {(1,2),(ω,4)} is an array with 2 as first element and 4 as ω-th element. Two arrays can be compared in the following way: if there exists an index, i, for which i'th element of ν is smaller than the i'th element of μ and there doesn't exists an index, j, larger than for which the j'th element of ν is greater than the j'th element of μ then ν<μ. The equality ψ(α,{(0,ν)})=ψ(α,ν) holds where the left ψ is the extensible Buchholz's function with the T defined above and the right ψ is the normal extended Buchholz's function. I think that this extension of Buchholz's ψ is stronger than Rathjen's ψ.

System Of Fundamental Sequences

No OCF or ordinal notation is fully complete without a system of fundamental sequences! So, here's one:

D(0)=1

D(n+1)={γ+δ,ψ(α,ν)|γ,δ,α∈D(n),ν∈T(D(n))}

α[n]=max{β∈D(n+k)|β<α}+1 for k=min{m|α∈D(k)}

With this definition, the cofinality of each ordinal is ω. The first rule states that the first step consists of only 0. The second rule states that for any step, D(n), the next step, D(n+1), consists of all in T(D(n)) and γ+δ and ψ(α,ν) for γ, δ and α in D(n) and ν in T(D(n)). The third rule states that the n'th element of the fundamental sequence of α is the maximum ordinal β for which β is less than α and is in the n+k'th step where k is the least step number for which α is an element of that step.

[dailyprogrammer]

[2019-01-25] Challenge #373 [Hard] Embeddable trees

Today's challenge requires an understanding of trees in the sense of graph theory. If you're not familiar with the concept, read up on Wikipedia or some other resource before diving in.

Today we're dealing with unlabeled, rooted trees. We'll need to be able to represent fairly large trees. I'll use a representation I just made up (but you can use anything you want that's understandable):

A leaf node is represented by the string "()".

A non-leaf node is represented by "(", followed by the representations of its children concatenated together, followed by ")".

A tree's representation is the same as that of its root node.

For instance, if a node has two children, one with representation (), and one with representation (()()), then that node's representation is ( + () + (()()) + ) = (()(()())). This image illustrates the following example trees:

((()))

(()())

((())(()))

((((()()))(()))((((()()))))((())(())(())))

In this image, I've colored some of the nodes so you can more easily see which parentheses correspond to which nodes, but the colors are not significant: the nodes are actually unlabeled.

Warmup 1: equal trees

The ordering of child nodes is unimportant. Two trees are equal if you can rearrange the children of each one to produce the same representation. This image shows the following pairs of equal trees:

((())()) = (()(()))

((()((())()))(())) = ((())(()(()(()))))

Given representations of two trees, determine whether the two trees are equal.

equal("((()((())()))(()))", "((())(()(()(()))))") => true equal("((()))", "(()())") => false equal("(((()())())()())", "(((()())()())())") => false

It's easy to make a mistake, so I highly recommend checking yourself before submitting your answer! Here's a list of 200 randomly-generated pairs of trees, one pair on each line, separated by a space. For how many pairs is the first tree equal to the second?

Warmup 2: embeddable trees

One tree is homeomorphically embeddable into another - which we write as <= - if it's possible to label the trees' nodes such that:

Every label is unique within each tree.

Every label in the first tree appears in the second tree.

If two nodes appear in the first tree with labels X and Y, and their lowest common ancestor is labeled Z in the first tree, then nodes X and Y in the second tree must also have Z as their lowest common ancestor.

This image shows a few examples:

(()) <= (()())

(()()) <= (((())()))

(()()()) is not embeddable in ((()())()). The image shows one incorrect attempt to label them: in the first graph, B and C have a lowest common ancestor of A, but in the second graph, B and C's lowest common ancestor is the unlabeled node.

(()(()())) <= (((((())()))())((()()))). There are several different valid labelings in this case. The image shows one.

Given representations of two trees, determine whether the first is embeddable in the second.

embeddable("(())", "(()())") => true embeddable("(()()())", "((()())())") => false

It's easy to make a mistake, so I highly recommend checking yourself before submitting your answer! Here's a list of 200 randomly-generated pairs of trees, one pair on each line, separated by a space. For how many pairs is the first embeddable into the second?

Challenge: embeddable tree list

Generate a list of trees as long as possible such that:

The first tree has no more than 4 nodes, the second has no more than 5, the third has no more than 6, etc.

No tree in the list is embeddable into a tree that appears later in the list. That is, there is no pair of indices i and j such that i < j and the i'th tree <= the j'th tree.

[altascharacters]

J’TH

Universe: Fantasy verse

Age: ???

Gender: Male

Occupation: Witchdoctor

Personality: Socially awkward, chill

Bio: J’th lives in a swamp with his many monstrous pets. He is considered the guardian of the swamp by locals, who also come to him for medicines and spells.