5
$\begingroup$

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

$\endgroup$
5
  • $\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, 2015 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, 2015 at 13:51
  • $\begingroup$ What precise formal language are you using? $\endgroup$
    – Carl Mummert
    Jan 2, 2015 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, 2015 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, 2015 at 15:59

4 Answers 4

Reset to default
3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Not only hard; it's impossible. $\endgroup$
    – Carl Mummert
    Jan 2, 2015 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$
    – hmakholm left over Monica
    Jan 2, 2015 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, 2015 at 16:07
2
$\begingroup$

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$.

$\endgroup$
1
  • 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$
    – hmakholm left over Monica
    Jan 2, 2015 at 16:15
1
$\begingroup$

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.

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .