给定函数$f:A\rightarrow B$，如何机械判定命题等价于满射定义？

Absolutely—you can definitely use systematic logical simplification to verify if a candidate proposition is equivalent to the definition of an onto (surjective) function. This method is rigorous, straightforward, and relies on applying standard logical equivalence rules to transform the candidate into a form that directly matches (or contradicts) the official onto definition.

How to Do It: Step-by-Step #

Here's a reliable process to follow:

• Start with your candidate proposition (like the partial one you mentioned starting with $\neg \exists x \in A, \forall...$).
• Apply logical equivalence rules one at a time—focus on quantifier negation, De Morgan's laws, double negation, and any other relevant rules.
• Keep simplifying until you reach a form that's either identical to the onto definition, its negation, or a clearly non-equivalent statement.
• Compare the final simplified form to the textbook onto definition:
  $$\forall y\in B, \exists x\in A, f(x) = y$$

Example Walkthrough #

Let's take a common candidate proposition that's equivalent to onto, and simplify it to prove the equivalence:
Suppose the candidate is:
$$\neg \exists y \in B, \forall x \in A, f(x) \neq y$$

1. Apply quantifier negation: $\neg \exists y$ converts to $\forall y$, and we push the negation inward to the next quantifier:
   $$\forall y \in B, \neg \forall x \in A, f(x) \neq y$$
2. Negate the universal quantifier: $\neg \forall x P(x)$ is equivalent to $\exists x \neg P(x)$, so:
   $$\forall y \in B, \exists x \in A, \neg (f(x) \neq y)$$
3. Double negation: $\neg (f(x) \neq y)$ simplifies directly to $f(x) = y$, leaving us with:
   $$\forall y\in B, \exists x\in A, f(x) = y$$
   Which is exactly the textbook definition of an onto function—so we've confirmed equivalence.

Key Logical Rules to Memorize #

These are the workhorses for simplifying quantifier-based propositions:

• Quantifier negation:
  • $\neg \forall x P(x) \equiv \exists x \neg P(x)$ ("It's not true for all x that P(x)" means "There exists some x where P(x) is false")
  • $\neg \exists x P(x) \equiv \forall x \neg P(x)$ ("There's no x where P(x) is true" means "For all x, P(x) is false")
• Double negation: $\neg \neg P \equiv P$ (Straightforward—two negatives cancel out)
• De Morgan's laws for logical operators: $\neg (P \land Q) \equiv \neg P \lor \neg Q$ and $\neg (P \lor Q) \equiv \neg P \land \neg Q$ (Useful if your candidate includes AND/OR)

Pro Tips #

• Work step-by-step: Write down each transformation explicitly to avoid mixing up quantifier scopes or making negation errors.
• Reverse the process if stuck: If simplifying the candidate isn't working, try starting from the onto definition and transforming it to see if you can reach the candidate proposition.
• Watch quantifier scope: Make sure negations apply to the entire quantifier and its predicate—don't accidentally negate only part of the statement.

内容的提问来源于stack exchange，提问作者Philip Kuo