A function from 
Conversely, we can call a function strongly non-even if for all 
Finding strongly non-even functions is easy, as any injective function provides a trivial example. We can make things harder for ourselves by considering only functions from 
Therefore, let’s make the following definition: Let a function 
In this paper, the set theorists Peter Komjáth and Saharon Shelah proved:
The existence of a non-even function of order 1 is equivalent to the Continuum Hypothesis (i.e., the statement that
).
Thus, if we assume that there is a non-even function of order 1, then we can conclude that 
For any
.
, 
, and 
. So, you head down to the ancient language department of your local university.
, knows what 
means, the second professor you come across, 
, knows what 
means, and the third professor you come across, 
, knows what 
. He doesn’t know what 
means, but if you told him what 
. If you told him what 
meant and what 
means.
. If you told him a method for finding out the meaning of 
and 
, there is a professor 
with the property that if you told him what 
have essentially the same knowledge, since to get the meaning of 
you only have to tell him a method for finding out the meaning of 
has the same state of knowledge as 
. This is because each can “simulate” the other. In one direction, suppose somebody told 
the meaning of 
be the free cartesian closed category over 
and 
, say that 
and 
are equivalent if there is an arrow from 
to 
and an arrow from 
. (The corresponding statements are also true with 
replaced by 
be Peano Arithmetic. Gödel’s Second Incompleteness Theorem says that no consistent theory 
extending 
can prove its own consistency. (I’ll write 
for the statement asserting 
is stronger than 
proves is true, we believe that 
proves is true. But by a similar argument, we believe that everything that 
proves is true. Where does this stop? Once we believe that everything 
be a 
-periodic function. It may or may not have a representation as a trigonometric series
as a trigonometric series is unique, if it has one. It was the consideration of this question that led Cantor to the invention of set theory.
which contains the reals and also some infinitesimals, prove that some statement holds of 
, and then use a general “transfer principle” to conclude that the same statement holds of 
.
instead of with 
, then we can get all the basic results of calculus and elementary real analysis just by working with 
, and without ever having to construct the reals.
to actually be a sequence of games 
for 
. For example, 
would be checkers played on an 
board. The problem was then to analyze the computational complexity of the function which takes 
and tells you which player has a winning strategy and what the winning strategy is. I’ll call that function the analysis function of 
-c.e.
be the set of all 
. You must correctly say for each number whether or not it is in 
. You are allowed to ask (and receive a truthful answer to) two questions of the form “Is 
is a set such that you can win that game, then 
must be decidable.)
as our model of the plane, the distance from 
to 
would not be rational, and we would not be able to rotate the point 
about the point 
or 
. The fact that I was wrong follows from a theorem of Micha Perles which is very famous in combinatorics, but which I only found out about recently.
into our universe: natural numbers are the most basic computational objects there are. (Notation: I’ll use 
to refer to 
from 
to 
? Since we want to admit only computable things, we should let 
denotes the partial function from 
th Turing machine. Given 
, it is possible that the computation 
never halts; in that case, I’ll write 
and say that 
is undefined. If it does halt, I’ll write 
and say that 
is defined. If it halts, then it yields an output 
. To indicate what it is, I’ll write 
or 
.)
should equal 
. What should 
equal? At this point, there is a slight subtlety: It’s not simply the set of computable functions from 
to 
.
be the set of 
such that, for all 
, 
are such that for all 
, 
, then 
.
, except that there are now two places where we should take into account that we consider 
equivalent if for all 
, 
: We’ll let 
be the set of 
are equivalent in the aforementioned sense, 
are defined and equivalent in the aforementioned sense.
and so on; these sets are called the sets of hereditarily computable functions.
small squares. With Player A starting, they take turns choosing a square and eating it together with all squares above and to the right. The catch is that the square at the lower left-hand corner is poisonous, and the player who is forced to eat it loses.
chocolate bar:
board, Player B wins (since Player A must eat the poison piece on his first move). But for any other board, Player A has a winning strategy.
boards, but on 
boards, where 
and 
are arbitrary ordinals. The game still makes sense just as before, and will always end in finite time, but Player A no longer wins all of the time (there will no longer be a top right-hand corner square if either 
or 
is a limit ordinal).
of sets, there should be a set 
which has as its members all and only those sets 
, and then you can derive a contradiction from both 
and 
.
too big to be a set. But you also end up throwing out many sets which you might want to have: for example, the set of all sets, the set of all groups, etc.
denote the class of expressions generated by
.
in 
is identically zero is undecidable. This means as well that the problem of deciding whether or not two expressions 
are always equal is also undecidable, since this is equivalent to deciding if 
is identically zero.
to 
if the 
if the 
functions from 
computer programs. But that is nonconstructive, and the two examples I gave above seem a bit like they’re cheating since their definitions refer to the concept of computability. Is there a natural example of an uncomputable function that does not refer to computability?
is a differential 
-form 
satisfying two conditions:
is non-degenerate, i.e. for each 
and tangent vector 
based at 
, if 
for all tangent vectors 
based at 
is the zero vector;
.
is just an assignment of a number in 
to each pair of vectors, in such a way that the assignment is linear in each vector in the pair. A bilinear form is called non-degenerate if the only thing that pairs to zero with every single vector is the zero vector. A 
is a collection 
of skew-symmetric bilinear forms, one for each tangent space of 
. Saying that 
is an integrability condition. I had never thought of it this way, but I probably will from now on.
):
,” “
,” the logical connectives “and,” “or,” “not”, function symbols 
, 
, constants 
, 
, and variables 
” (denoted “
”) and “there exists infinitely many 
”) instead of “
” and “
”, then we do have an algorithm for deciding whether a quasi-arithmetic statement is true or not!
(it’s arbitrary: it doesn’t have to be continuous or anything).
.
of his function on every input except the one you specified
of Bob’s secret function on the number 
have nothing to do with the value of 
on input 
in Step 2 with uniform probability from 
, the axiom of choice implies that you have a strategy such that, whatever 
(the first uncountable ordinal), you will have no money.
to 
and that we have a program which computes it. (Ignore for now exactly what it means to “compute” a real-valued function of the reals. Suffice it to say that almost every natural continuous function you come across is computable). If we want to compute 
, say to within an accuracy of 
, how would we do it, and would we need any further information about 
in order to do it?
for some large 
. For example, 
might be 0 for all 
, but 
and 
so that its definite integral is arbitrarily close to 1.
there is a 
such that whenever 
, 
. If we could compute a function 
such for all 
, whenever 
, 
, then we could compute the definite integral of 
to within 0.001, then choose 
and we can take 
, since 
.
?” is: a function 
witnessing 
into disjoint non-trivial circles. (Here “non-trivial” means “not a point.”) Winkler gives a very clever solution which is purely geometric.
, if 
has characteristic 0, so each of the axioms 
(where 
is a prime) is true in 
. But a proof can only use finitely many axioms. Therefore, there must be some 
that is not used in the proof. One can then show that there would be a polynomial function which is injective but not surjective from 
to 
, where 
is a finite field of characteristic 
is a finite set.
