Is it possible to write '$f$ is NOT a bijection' with quantifiers only, and without using "$\neg$"? What is the negation of "$\exists$!"?

  • $\begingroup$ "... and without using?" is confusing, unless you mean not using question marks. Did you forget to finish your sentence? $\endgroup$ – Thomas Andrews Jan 2 '15 at 13:39
  • $\begingroup$ To negate injectivity we need $x$ and $y$ different with the same image. How to say different without using $\lnot$? What is the language that you're working in? $\endgroup$ – Henno Brandsma Jan 2 '15 at 13:51
  • $\begingroup$ What precise formal language are you using? $\endgroup$ – Carl Mummert Jan 2 '15 at 15:49
  • $\begingroup$ I have no idea, I am taking an introduction course called formal mathematical reasoning and logic. I didn't even know there are different formal languages? In the question in my syllabus they state not to use $\neg$ but $\neq$ you can use, so the solution Makholm suggested seems correct. $\endgroup$ – Michael Angelo Jan 2 '15 at 15:55
  • $\begingroup$ In most presentations, $\not =$ is not actually in the language, it is an abbreviation for a formula that includes $\lnot$. So this is a somewhat idiosyncratic problem, apparently. $\endgroup$ – Carl Mummert Jan 2 '15 at 15:59

For $f:X \to Y$ we can write something like $$ \bigl(\exists x_1,x_2\in X:f(x_1)=f(x_2)\land x_1\ne x_2\bigr) \lor \bigl(\exists y\in Y:\forall x\in X:f(x)\ne y\bigr)$$

But it seems to be hard to avoid the negations implicit in the $\ne$s.

  • 1
    $\begingroup$ Not only hard; it's impossible. $\endgroup$ – Carl Mummert Jan 2 '15 at 15:55
  • $\begingroup$ @CarlMummert: That's my gut feeling too, but it seems to be tricky to pin down exactly which constraints on the problem will make it impossible. At least, it seems, we have access to the connectives $\land$ and $\lor$, and they are monotone, which could point the way to a proof of the necessity of using $\neg$ somewhere. But if we're working in set theory, then $f(x_1)=f(x_2)$ is an abbreviation for something more primitive, and how much do we need to express that? If we need to accept $\to$ or $\leftrightarrow$, we could disguise $x\ne y$ as $(x=y)\to(x\in x)$, for example. $\endgroup$ – Henning Makholm Jan 2 '15 at 16:06
  • $\begingroup$ I have a solution in my answer, at least for pure FOL. Unfortunately, the OP is not able to clarify the precise formal language. But all we need, as I point out there, is a way to get two distinct elements. $\endgroup$ – Carl Mummert Jan 2 '15 at 16:07

Assume that the formal language only has $=$, $f$, variables, and quantifiers. Then there is no formula of the type requested in the question.

Suppose that $\phi$ is a formula that does not include $\lnot$. I claim that, in a structure with only one element, $\phi$ must be true. But every function from that model to itself is a bijection, so no $\phi$ can express "$f$ is not a bijection" in all models.

To prove that such a formula $\phi$ is true a model with only one element, we just have to consider all the cases, where we only consider formulas that do not include $\lnot$.

  • Every substitution instance of the formula $x = y$ will be true, because there is only one element. Every atomic formula is a substitution instance of $x=y$.

  • Every expression of the form $\psi \land \theta$, $\psi \lor \theta$, or $\psi \Rightarrow \theta$ will be true when $\psi$ and $\theta$ are both true

  • Every quantified expression $(\exists x)\psi$ of $(\forall x)\psi$ will be true, because every substitution instance of $\psi$ will be true.

Once we exclude models with only one element, the question has a postive answer. $(\forall x)(\forall y)(x = y)$ is then a suitable replacement for $\bot$. an identically false formula. And then $\lnot \theta$ is $\theta \Rightarrow \bot$ as usual, so we can express negation without using $\lnot$.

  • 1
    $\begingroup$ This works, within the assumptions set out at the start of the answer. I don't think a language as restricted as this would be my first choice for formalizing the problem, though -- it feels poor to talk about functions being bijective without being able to speak explicitly about domains and codomains. (Though I acknowledge that we can ask whether a function symbol in FOL stands for a bijection between the universe and itself). $\endgroup$ – Henning Makholm Jan 2 '15 at 16:15

Hint: The expression $$\exists ! x \, P(x)$$ is shorthand for $$\exists x \, P(x) \; \land \forall y \, \forall z \, ((P(y) \land P(z)) \implies y=z)$$ which can be negated with deMorgan's laws.

  • $\begingroup$ The negation of this still has a not sign.... $\endgroup$ – Henno Brandsma Jan 2 '15 at 14:02

$$\exists y\in Y\quad \forall x\in X:\qquad f^{-1}\bigl(\{y\}\bigr)\ne\{x\}\ .$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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