In order to meaningfully discuss incompleteness, you need to read a textbook in mathematical logic. Without such background, your notions and terminology are not comprehensible.

(1) By 'alphabet' in this context we mean the set of symbols of the formal language. The concern is not with the number of alphabets, but rather with the cardinality of the set of symbols. This is very relevant to mathematical logic and Godel-Rosser specifically.

(2) it appears, as in other threads, that this poster is not familiar with the actual subject matter of the discussion. It is a continual curiosity when a person insists on posting opinions on a technical subject of which he or she has not read even the first page in an introductory textbook.

Note: I make use of some of the sharpenings of certain notions and specifics that came after Godel's original paper.

(1) Godel-Rosser pertains to systems that are recursively axiomatized. A recursively axiomatized system allows an algorithm for checking whether a purported proof is indeed a proof in the system. Systems with languages having uncountably many symbols are not generally recursively axiomatized. That is why uncountable languages are not generally entertained for the purpose of the theorem.

(2) It is not desired to have a system that proves "everything", since then it would prove contradictions. And the main concern with Godel-Rosser is with theories that prove only arithmetic truths, not "everything".

(3) The rest of what the poster writes is not recognizable to me as sensical commentary on mathematical logic.

Replying to MU:

In common, pervasive usage in mathematics, as I mentioned, a formula

T = S

is true (or satisfied) if and only if 'T' and 'S' refer to the same object.

The reason you are not familiar with that fact is that you are not familiar with rigorous mathematics and especially as mathematics is treated in mathematical logic.
— GrandMinnow — jgill

(1) There is nothing incorrect in what you quoted.

(2) Since not just Wikipedia (which itself is not a reliable source on mathematics and certain other subjects) mentions a usage that distinguishes between an 'identity' and a 'conditional equation', fair enough, I should not have allowed an impression that I claim that such usage does not exist, and I was incorrect to dispute that some people use that basis of distinction. But from a brief perusal on the Internet, I see that that usage is found mainly in high school level algebra texts (and "college" level that is seen in the examples to be really review of high school level). It is often wise to be wary of high school level explanations and terminology that need to be made rigorous and even corrected by rigorous mathematical treatments (for a salient example, the definition of 'function'). Meanwhile, I have never seen that rubric mentioned by Wikipedia used in rigorous mathematics at upper division and early graduate level, including the basic ordinary subjects: mathematical logic, set theory, abstract algebra, analysis or topology. In such subjects, the notion of an equation is as I have mentioned it, and it is at least implicit in texts that include introductions recognizing the logical and set theoretical foundations. I can't claim to a certainty that the rubric is not found anywhere in serious mathematics, but I am skeptical that it is.

(3) The distinction that Wikipedia mentioned is different from the example you gave. You gave an example of a true statement with no variables versus an equation with variables that is not true on all values for the variables. The Wikipedia article refers to a distinction between formulas that are true for all values for the variables versus formulas that are true only for certain values for the variables.

The distinction you mentioned is correctly given a precise explanation in my previous posts. For the Wikipedia sense, we can somewhat expand to make explicit the distinction between:

Valid formulas. Formulas are valid if and only if they are true (or satisfied) in all structures/variable_assignments.

and

Formulas that are not validities. Those include those that are true in some structures/variable_assignments and those that are logically false as they are not true in any structure/variable_assignment.

No, the left side does not represent an operation. The left side represents the value of an operation with an operand pair.

The value of the operation + applied to the operand pair <2 2> is 4. Thus the equation 2+2=4 is true.

That's the way it works in mathematics. Your philosophy about things does not refute mathematics. Meanwhile, if you wish to continue to ignore how mathematics actually works and instead insist on your philosophy, then you would do better to present a systematic development of the subject with your alternative premises, definitions, and notations listed, and not continue to post disinformation about mathematics you know nothing about.

if the very same thing is referred to on the right and the left, use of the '=' is valid. That is because a thing cannot be unequal to itself. But since there are many instance when the right and the left refer to something different, we cannot conclude that '=' signifies identity. — Metaphysician Undercover

You're confused. If the left and the right refer to the same thing, then the formula is true (or satisfied). And when the left and the right refer to different things, then formula is false (or not satisfied. The fact that we can write a false identity formula doesn't vitiate that.

0 = 0 is a true equation.

0 = 1 is a false equation.

That doesn't contradict identity principles.

n common, pervasive usage in mathematics, as I mentioned, a formula

T = S

is true (or satisfied) if and only if 'T' and 'S' refer to the same object.
— GrandMinnow

This is a false statement. It is very evident from the common use of mathematics, and even your example of "free variables", that the right and left side usually do not signify the very same thing. — Metaphysician Undercover

You don't know anything about it. You've never read a single page in a textbook on the subject. What I wrote is correct. You may have your own philosophy about things, but when you make claims about what happens in mathematics, you are prone to be flat out wrong and posting disinformation.

The left and the right may refer to the same thing or to different things, but the equation is TRUE if and only if the left and right refer to the same thing; and the equation is FALSE if and only if the left and right refer to different things.

the law of identity is violated in mathematical usage — Metaphysician Undercover

No, the laws of identity are not violated in mathematics, no matter what we take the ontological status of the referents to be. Or, please state precisely a mathematical text in which you find violation of the laws of identity. I mean a specific piece of mathematical writing; not just something that you imagine someone has meant somewhere or another.

your formula just begs the question. You assume that a number is an object, therefore '=' means identity. But of course, as I've already demonstrated, '=' is not actually used that way. So your question begging premise is actually false. — Metaphysician Undercover

What specific formula are you referring to? A formula is just a formula and it's not an argument, while question begging refers to arguments, so a formula itself is not question begging. And the rest of what you wrote there is double-talk ignorant of the subject of actual mathematics. The remedy for you is to get a book on beginning symbolic logic then on mathematical logic.

show me how T and S necessarily refer to the exact same object — Metaphysician Undercover

I didn't say that they necessarily refer to the same object. I said the formula is satisfied when they refer to the same object.

The fixed semantics for '=' is given in the method of structures for languages in mathematical logic. If you are not familiar with that method and subject matter, then you won't follow what I'm saying here.

asserting that the '=' means that they refer to the exact same object, because we already know that this is not true in the common usage of '=' in equations. — Metaphysician Undercover

In common, pervasive usage in mathematics, as I mentioned, a formula

T = S

is true (or satisfied) if and only if 'T' and 'S' refer to the same object.

The reason you are not familiar with that fact is that you are not familiar with rigorous mathematics and especially as mathematics is treated in mathematical logic.

In the vast ordinary sense in mathematics, an equation (an identity statement) is a formula of the form:

T=S

where 'T' and 'S' are terms.

The equations mentioned differ in that one has no free variables and the other has occurrences of free variables. One of them happens to be satisfied in all structures, while the other is satisfied in some structures and assignments for the variables but not in others.

It's as simple as that. There are no "angels on pins" involved.

Points to make clear:

(1) Ordinary mathematics, formally and informally, uses the law of identity. This is the use of first order logic with identity (sometimes called 'identity theory') that has the built-in semantics:

If 'T' and 'S' are terms then

T = S

is true if and only if 'T' and 'S' stand for the same object.

Said another way:

T = S

is true if and only if the denotation of 'T' is identical with the denotation of 'S'.

Said another way:

In any interpretation of a language, '=' maps to the identity relation on the domain.

Moreover, for proofs, identity theory is axiomatized by an axiom schema.

This is the very precise sense of the identity.

(2) Leibniz's law is taken as either the principle of the indiscernibility of indenticals (if x and y are identical then x and y share all properties) or as the conjunction of two principles - the principle of the identity of indiscernibles (if x and y share all properties, then x and y are identical) and the aforementioned principle of the indiscernibility of indenticals.

Identity theory, hence mathematics, adheres to both principles:

* If T = S, then T and S have all the same properties.

This is the indiscerbility of identicals and is expressible formally in a first order schema:

For any formula F,

x=y -> (Fx <-> Fy)

* If T and S have all the same properties, then T=S.

This is not expressible in a first order schema unless the number of non-logical constants in the language is finite. However, even if the number of logical constants is infinite, the principle is still upheld by the semantics of identity theory.

(3) Formulations of set theory may be based on first order logic with identity (so '=' is taken as primitive). And this holds even if you take out the axiom of extensionality. The axiom of extensionality is needed to prevent urelements, but it does not contradict identity theory, rather it is an addition to identity theory.

So there are three ways to handle identity and have extensionality in set theory:

1. '=' is primitive from identity theory, so we have:

theorem: x=y -> Az((zex <-> zey) & (xez <-> yez))

and we add the axiom of extensionality:

axiom: Az(zex <-> zey) -> x=y

2, dispense with identity theory and stipulate:

definition: x=y <-> (zex <-> zey)

axiom: x=y -> Az(zex -> zey)

3. dispense with identity theory and stipulate:

definition: x=y <-> Az(zex <-> zey)

axiom: Az(zex <-> zey) -> Az(xez -> yez)

In all three cases, we have the same set of theorems and the identity of indiscernibles and the indiscernibility of identicals. So we have Leibniz's principles to exact specification. Both syntactically and semantically.

(3) It was claimed that '=' has two different senses, for example:

2=2

vs,

2x=x+3

But those aren't different senses of '='. Rather they are examples of the difference between a formula with no free variables and a formula with at least one free variable. The first is true and the second is true or false depending on what value is assigned to the free variable 'x'. That doesn't entail that '=' has two different senses. It's a matter of understanding variables here, not any supposed difference (there is not one) in the meaning of '='.

set theory (if it is consistent [...]) does not prove the existence of a model of set theory.
— GrandMinnow

No, that's not right. Set theory is consistent if and only if there's a model. That's Gödel's completeness theorem. — fishfry

No, it is right. Yes, set theory is consistent if and only if there is a model of set theory. But if set theory is consistent then set theory itself doesn't prove that it has a model;. That's Godel's 2nd Incompleteness Theorem.

I think he made a typo and actually meant 'between the natural numbers and the computable numbers'.

No that's not right.There are a countably infinity of Turing machines hence a countable infinity of computable numbers, hence a bijection between the natural numbers and the noncomputable numbers. — fishfry

You mean there is a bijection between the naturals and the computable reals. And I didn't claim otherwise. I only pointed out the incoherence of a particular poster's argument.

I don't suggest that you suggested that the set of noncomputable reals is countable.

Meanwhile, I changed my post above to pertain to definability rather than computability, It's not a problem to show in set theory that the set of computable reals is countable, but there are issues in showing the countability of the set of definable reals, as mentioned in the article you linked to. I tried to sketch a sense in which the notion of definability can be used without such contradictions as 'the least undefinable ordinal' that was mentioned in that article.

I changed this post greatly:

So to make the argument work that there are only countably many definable real numbers, maybe something like this in a set theoretic meta-theory for set theory:

Let 'Rx' be the set theory formula 'x is a real number'. Let M be any model of set theory such that any subset S of the universe of M satisfies 's is countable' if and only if S is countable. Let D (the set of definable reals) be the subset of the universe of M by D = {d | there exists a formula F of set theory such that (E!x(Fx & Rx) is a theorem of set theory & d satisfies Fx and d satisfies Rx). Then D is countable.

your assertion that there is no definable list of noncomputable reals — fishfry

I didn't make that assertion. I only commented on the poster's particular argument. (I later edited 'definable' to 'defined', but in either case, my comment pertained only to the poster's own argument.)

Anyway, there is no list (no enumeration) of the the set of uncomputable reals, since the set of uncomputable reals is uncountable.

/

That thread you linked to includes an argument that uses 'least undefinable ordinal' to throw shade on the "naive" notion of definability. But one would not claim that 'definabie' itself is a predicate in the theory. I only mentioned a certain syntactical fact - regarding formulas of a certain form. I wouldn't say in set theory itself, about set theory, that there exists a definable something or other. To even speak of that "something' is to speak of an object that exists per a set theoretic model, but indeed, as we well know, set theory (if it is consistent, which I take as a "background" assumption) does not prove the existence of a model of set theory. (Though, I'm not expert enough to defend against possible other complications in the matter.)

The negative statement was deliberately chosen. Of course, it is equivalent to saying that there does exist a definable uncomputable real.

Suppose the following is the complete list of computable irrational numbers between e and pi — TheMadFool

Right from the start of your argument, the merely ostensive (and not specified by actual mathematical description) list you gave is either actually not defined or it's finite. It ends with a certain value, yet doesn't specify how to squeeze in a countably infinite number of values in between the first and the last.

There are proofs that there exist definable uncomputable reals, but you haven't given such a proof.

Using 'infinity' as a noun in the context of cardinality is incorrect and supposed refutations of set theoretic notions of cardinality by using 'infinity' as a noun are fallacious.

In the context of set theoretic cardinality, there is no object named 'infinity'. Rather, there is the adjective 'is infinite'. So expressions like '1/infinity', et. al are meaningless, and supposed arguments based on such usage are fallacious.

(This does not contradict that there are things such as the extended real number system in which there are points of positive infinity and negative infinity and arithmetic on them, since that is a different context from set theoretic cardinality.)

Moreover, set theory does not assert that there is a set that is equal to a proper subset of itself. Indeed, it is a trivial theorem that there is no set S such that S is equal to a proper subset of S. That does not contradict however that there are sets that have a 1-1 function from the set onto a proper subset of itself. Having a 1-1 function between sets (of which we say 'the sets have a bijection' or 'the sets are equinumerous') is plainly distinct from the fact that the sets are not equal, not identical, not having all the properties of each other.

If any of a number of articles (e.g. https://medium.com/cantors-paradise/uncomputable-numbers-ee528830d295) on the Internet are correct, then it is not the case that there does not exist a definable uncomputable real number. I am not versed in all the details, but it does seem to be settled mathematics.

(By 'there exists a definable uncomputable real number' in this context, I mean the ordinary mathematical sense:

There exists a formula F such that

E!x(Fx & x is an uncomputable real number)

is a theorem of set theory.)

But I said ONTO ITSELF.
— GrandMinnow

Where? Those words are clearly not in your post. Am I missing other posts of yours perhaps? — fishfry

Clearly there is a problem with the manner in which you are reading. My very first sentence in this thread:

"One doesn't have to provide much argument that the following claim onto itself is not self-contradictory."

And you even quoted me saying that.

/

And I don't know why you say that Wiki claims a subtle difference between separation and specification. The Wikipedia (which I don't rely on as authoritative in mathematics anyway; for example see the wildly incorrect article on the rule of existential instantiation) article says they are the same. Nor, as I mentioned, do I know why you even mention the matter.

Would you please slow down. You're swinging your arms around wildly.

I didn't refute my own point. I never claimed that a demonstration of the consistency of ExAy yex would be faithful to ordinary concepts of set. Go back and read exactly what I posted: I said that it doesn't take much to show that "There exists a set such that every set is a member of it" is not self-contradictory; I did not claim that showing that fact would adhere to ordinary concepts of set.

And you say that I fail to provide context, when I just spent my time tying out for you the context per this thread.

You said "There exists a set such that every set is a member of it" — fishfry

No I did NOT. I said the sentence is not self-contradictory. I did not say or even suggest that it is true or even compatible with ordinary concepts of set. Really, it is becoming egregious of you that you're putting words in my mouth even after I just asked you not to do that.

I'm not picking up on your remarks about NF, because I don't need recourse to NF to support my own remarks.

/

Angle brackets, indicate ordered pair, as is ordinary notation. Also, incorrectly, you put the question about the meaning of angle brackets within my own quote.

/

To recap:

(1) ExAy yex

is consistent. And it takes little argument to see that it is consistent. And I did not claim such an argument would use only our ordinary concept of set. And I did not claim ExAy yex. And indeed I pointed out that ExAy yex contradicts separation (which, goes without saying, is part of our ordinary concept of set).

(2) The point of mentioning (1) in the context of this thread was described in a previous post.

All that said, please slow down and read exactly what I post at exact face value. That will avoid time wasting squabbles about who said what about what.

There is nothing cryptic in what I wrote and it is not false without further explanation.

And I did not say that there is a universal set. I said that "there is a universal set" is not onto itself a contradiction.

And I didn't claim that I said something I didn't say:

You QUOTED me saying that a universal set contradicts:

(2) For any property and for any set, there is the subset of that set with the members of the subset being those with said property.

And (2) IS the axiom schema of separation.

So surely I did mention that it contradicts the axiom schema of separation.

/

If someone says to me that his concept of set demands that there is a set of all sets, but he has not made fully clear what else is in his concept of sets, then I say "Fine, it is not onto itself contradictory that there is a set of all sets, but you will incur contradiction once you add certain other principles to your concept, such as the subset principle (which is given more explicitly as separation)."

That it doesn't take much argument to see that "There exists a U such that everything is a member of U" is not BY ITSELF contradictory, we just need to show a model M.

Let M be the model for the language with the 2-place relation 'e' as follows:

The universe of M is {0}, and e is interpreted as {<0 0>}.

The reason I didn't pedantically spell out that argument is that it takes but a nanosecond of reflection to see that yes, of course, "ExAy yex" has models.

Granted, that doesn't capture an ordinary concept of sets, but I am at first allowing, for sake of argument, that one my have whatever concept of set one may wish to have. And toward that end, I am mentioning that "there is a universal set" is not ONTO ITSELF a contradiction.

The point in the context of this thread is that we find someone who claims that there is a universal set, and I wish to emphasize that explaining what is wrong with that claim may be best understood as a two step process: First, being as generous as possible to the person that he may have any concept of set he wishes to have, we recognize that, ONTO ITSELF, "there is a universal set" is not self-contradictory, then Second, mention however that "there is a universal set" does contradict other plain and well agreed upon aspects of sets, such as separation.

/

Whatever Wiki may say, 'the axiom schema of separation' and "the axiom schema of specification" are two names for the same schema, as I mentioned that schema previously. And I don't know what difference it makes for my comments, as I specifically used only "axiom schema of separation" anyway.

Of course it contradicts the axiom of regularity.

But I said ONTO ITSELF.

The formula

ExAy yex

is not a contradiction. It is consistent. Trivially, it has a model.

However, indeed it is in contradiction with certain axioms of set theory, as I mentioned in particular it contradicts the axiom schema of separation.

One doesn't have to provide much argument that the following claim onto itself is not self-contradictory:

(1) There exists a set such that every set is a member of it.

However, it does contradict the claim that:

(2) For any property and for any set, there is the subset of that set with the members of the subset being those with said property.

You can have (1) or you can have (2), but you can't have both. That is the basic upshot of Russell's paradox applied to sets.

consider the hypothetical possibility that all these famous philosophers after Russell, were wrong, and I'm right — Philosopher19

Consider the actual reality (not just a hypothetical possibility) that the mathematicians thoroughly studied the subject matter down to its finest details and understand its rigorous axiomatization, including that set theoretic proofs are machine checkable, while on the other hand, it appears you have not read the first page in a textbook on mathematical logic or set theory.

Yes, and even more simply, no atomic formula or its negation is provable in pure FOL.

It seems to me that birthdays celebrate the fact that the person was born. The person is closer to death every day, not just on their birthday. I see no paradox in celebrating that a person was born, even though the person will die.

"FOL is syntactically complete."

That is incorrect. It is not the case that for every formula, either FOL proves the formula or FOL proves the negation of the formula.

"a list of statements is closed under derivations if that list of statements contains every statement which is derivable from it"

I would put it this way: A set of formulas is closed under deduction if and only if every formula derivable from the set is a member of the set. A theory is a set of sentences closed under deduction.

/

"the claim that a contradiction is false in every model doesn't make sense to me"

A contradiction is false in every model. In any given model (for a given language), every sentence (of the language) is exactly one: true or false. So a contradiction (of the language) is always false in any model (of the language).

"A contradiction is not false. A contradiction is a pair of syntactic derivations, one of some statement P and the other of not-P."

No, a contradiction is any formula of the form P & ~P (or, more broadly any formula that is equivalent in pure FOL to P & ~P).

The completeness theorem, as applied to Q in particular, is that for first order logic, if a formula F is entailed by a set of formulas Gamma, then there is a proof of F from Gamma. In other words, if Gamma symantically entails F, then Gamma syntactically proves F.

The incompleteness theorem, as applied to Q in particular, is that there are formulas in the language of Q such that neither the formula nor its negation is a theorem of Q. That is purely syntactical. It does not require mentioning any semantic notion, though, of course, we can go on to observe many corollaries about semantics, such as that there are formulas that are true in the standard model for Q that are not theorems of Q.

In any case, there is no need for explanation of why the Completeness theorem applied to Q does not conflict with the Incompleteness theorem applied to Q. It's just that the word 'completeness' is used in two different senses in the nicknames of the theorems.

Russell's paradox applies not only to the element relation, and not just to set theory, but to any 2-place relation whatsoever and to logic in general.

Let R be any 2-place relation. It is a theorem of logic that:

There does not exist an x such that for all y, y R-relates to x if and only if y does not R-relate to itself. Symbolically:

~ExAy(Ryx <-> ~Ryy)

In particular, where R is the membership relation, there does not exist a set x such that for all y, y is a member of x if and only if y is not a member of itself. Symbolically:

~ExAy(y in x <-> ~ y in y)

Proof is simple:

Suppose, toward a contradiction, that there is an x such that for all y, y R-relates to x if and only if y does not R-relate to itself. Then x itself R-relates to x if and only if x does not R-relate to x, which is a contradiction. Symbolically:

Suppose ExAy(Ryx <-> ~Ryy). Then Rxx <-> ~Rxx, which is a contradiction.

For set theory:

Suppose ExAy(y in x <-> ~ y in x). Then x in x <-> ~ x in x, which is a contraction.

Thus trying to deny Russell's paradox by appealing to one's personal notion of the concept of 'sets' fails, since the structure of the contradiction does not rely on any concept of set. The principle that there is no set of all sets that are members of themselves is an instance of Russell's paradox, but, as I've shown, that principle does not rely on the any particular concept of 'sets'.

This is witnessed by Russell himself where he explains the paradox by reference to an arbitrary 2-place relation such as 'shaves'. It matters not whether the relation is 'is a member of', 'shaves', 'loves', or 'billwingadoobadoodles'. Seeking to dispute Russell's paradox by recourse of arguing over the concept of 'set' misses the point and is ill-conceived.

However, it is a correct that there is no 'set of all sets' is a corollary from Russell's paradox that DOES depend on a set theoretic notion that is expressed by the Axiom Schema of Separation which says that for any any formula F, and set s, there is the set y whose members are all and only those members of s such that F holds of y. Symbolically:

AxEyAz(z in y <-> (z in x & Fz))

From that axiom we derive that there is not a set of which all sets are members. Symbolically:

~EsAy y in x

Proof is simple:

Let F be the formula '~ z in z'. Suppose, toward a contradiction, that EsAy y in x. By the Axiom Schema of Separation we have EyAz(z in y <-> (z in s & ~ z in z)). So y in y <-> (y in s & ~ y in y). But, by the supposition that Ay y in s, we derive y in y <-> ~ y in y.

So one can deny that there is no set of all sets only by denying that for any property expressible by a formula and for any set, there is the subset of the set whose members are all and only those in the set and having said property.

The explanations are both correct and clear.

I said it's basic combinatorics. I have no opinion on what you know about it otherwise.

I have offered you several explanations. Those explanations depend on knowing what a function from a set into a set is. And even if one does not have familiarity with the von Neumann ordinals (which is the standard set theoretic explication of natural numbers), I even explicitly listed the set of functions concerned. I have also mentioned that you can take any sets with two members and the definition works. And I gave you the standard inductive definition also. And I've given you a search term on the Internet where you can see this approach. There is no lack of clarity.

This wasn't very helpful. — SophistiCat

It is exactly correct, precisely clear, and states exactly how it works in terms of von Neumann ordinals or even using any sets. And

x^0 = 1
x^(y+1) =( x^y)*x

is also utterly clear.

you still have one number (in this case, one set) in the domain and one number (one set) in the codomain — SophistiCat

Wrong. As Nagase so clearly and generously explained. 2, as a von Neumann ordinal, is a set with two members. And as I explained, it does not even depend on 2 itself being a von Neumann ordinal, or having itself 2 members, as we could take any set with 2 members. So (1) von Neumann ordinals are the usual means for an exact set theoretic mathematical formulation, and (2) we could also use any sets, and (3) I also gave you the inductive definition, which is the standard definition, that is equivalent with using von Neumann ordinals.

This is basic finite combinatorics. You can read about it not just in many a textbook on the subject, but even online by doing an Internet search on 'exponentiation'.

set-theoretical representatives of the natural numbers — Nagase

To add to that comment, we note that it works with any sets, not just von Neumann ordinals.

Take any set S that has x number of elements and any set T that has y number of elements. Then x^y is the number of functions from T into S.

And, for natural numbers, this is equivalent to the inductive definition:

x^0 = 1
x^(y+1) =( x^y)*x

four functions — SophistiCat

{f | f is a function & domain(f) = 2 & range(f) is a subset of 2}

=

{
{<0 0> <1 0>}
{<0 0> <1 1>}
{<0 1> <1 0>}
{<0 1> <1 1>}
}

which is a set having 4 members.

/

The context of the discussion did not include consideration of exponents other than natural numbers. Of course, with exponents other than natural numbers, the definition must be expanded.

the number of functions from 2 into 2 is 1 — SophistiCat

The number of functions from 2 into 2 is 4.

What do you mean by that? — SophistiCat

x^y = the cardinality of {f | f is a function & domain(f) = y & range(f) is a subset of x}.

If 2 has the exponent 0, the answer can be 2 or 0 — Gregory

2^0 = 1

The number of functions from 0 into 2 is 1.

Or, for natural numbers, we have the inductive definition:

x^0 = 1
x^(n+1) = (x^n)*x

x^y may be defined as the number of functions from y into x.

The empty function is the only function from 0 into x, so the number of functions from 0 into x is 1, so x^0 = 1.