Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Limitation of size: "For any class $C$, a set $x$ such that $x=C$ exists if and only if there is no bijection between $C$ and the class $V$ of all sets."

In Von Neumann–Bernays–Gödel set theory how could you state the axiom of limitation of size in first-order logic similarly to the axioms stated in first-order logic on the Wikipedia page?

I understand what a bijection is but I don't understand how you would refer to them in first-order logic (without just using a predicate).

Is there an answer using only predicates of equivalence and set/class membership?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

First let us define some encodings:

  1. $\langle x,y\rangle = \{\{x\},\{x,y\}\}$ is an ordered pair.
  2. $R$ is a relation if and only if $\forall z\in R$ there are $x,y$ such that $z=\langle x,y\rangle$.
  3. $f$ is a function if and only if it is a relation and for every two pairs $\langle x,y\rangle\in f$ and $\langle a,b\rangle\in f$ if $x=a$ then $y=b$.
  4. $Dom(f)$ is the collection of all $x$ such that there is $y$ for which $\langle x,y\rangle\in f$, similarly we define $Rng(f)$.

Now we can say that $f$ is a function from class $X$ to the class $Y$ by specifying that $f$ is a function, its domain is exactly $X$ and its range is a subclass of $Y$.

To say that $f$ is also a bijection we say that every $y\in Y$ appears in the range of $f$ and that if $a\neq b$, and $\langle a,u\rangle,\langle b,v\rangle$ are both in $f$ then $u\neq v$ (if you think of $u=f(a)$ it is simply the condition $a\neq b\rightarrow f(a)\neq f(b)$).

Now to write that a class $C$ is a set if and only if there is no bijection from $C$ onto the universe it is simply to write the following formula:

For all $C$, $\exists D: C\in D$ if and only if for all $f$ which is a function, whose domain is $C$ there is some $x$ such that $x\notin Rng(f)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.