2
votes
1answer
168 views

Is there research on the notion of co-accessibility?

I want to start off with a disclaimer that I am only a mathematical amateur. Please forgive me for ignorance or any non-standard nomenclature I use here :) Let's start off with some context. Let X ...
9
votes
0answers
258 views

Various definitions of recursion from ordinal machines

Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...
26
votes
3answers
2k views

“Simpler” statements equivalent to Con(PA) or Con(ZFC)?

Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...
4
votes
1answer
344 views

Injections to binary sequences that preserve order

Suppose we have a countable set S with a total order. Can we give an injection from S to the set of finite binary sequences that end in all zeros that preserves the ordering? The order on binary ...
10
votes
1answer
461 views

I am searching for the name of a partition (if it already exists)

I derived this definition by searching for a representation of a family of sets. I am quite sure that someone should have thought to this before, because it seems to be quite straightforward given a ...
11
votes
6answers
1k views

Uses of bisimulation outside of computer science.

Bisimulation is one of the most important ideas of theoretical computer science. I was wondering whether bisimilarity is used/known outside of computer science/modal logic? I am aware that it ...
2
votes
1answer
2k views

What is a universal function?

This question stems from Dick Lipton's recent blog post on the Axiom of Choice. I asked there but got no takers. I promise I'm not an inept Googler, but I couldn't find a satisfactory answer. I ...