T.7 · Образы множеств, отношения эквивалентности и логическое отрицание

Подготовка к GRE для бакалавров. Локальные цели в рамках пересмотренного диапазона ETS; это оригинальное обучение, а не официальный тест или предиктор баллов.

Предварительные требования: операции над множествами, кванторы, функции и элементарные доказательства.

• Доказать тождества образов и различать включение и равенство
• Проверить рефлексивность, симметричность и транзитивность на конкретных примерах
• Отрицать импликации и высказывания с кванторами, не меняя их scope (область действия)

прообраз: Множество всех входных значений, образы которых принадлежат заданному целевому множеству.

отношение эквивалентности: Отношение, которое является рефлексивным, симметричным и транзитивным.

Для f:X→Y и A⊆X образ f(A) состоит из всех значений f(a), где a∈A. Точка принадлежит f(A∪B) тогда и только тогда, когда она происходит из A или B, следовательно f(A∪B)=f(A)∪f(B). Если A⊆B, то f(A)⊆f(B). Для пересечения автоматически верно лишь f(A∩B)⊆f(A)∩f(B): одно и то же значение может получаться из разных аргументов. Возьмите f(x)=x², A={−1}, B={1}; левый образ пуст, а правое пересечение равно {1}.

Прообразы ведут себя иначе. Для C⊆Y через f⁻¹(C) здесь обозначается множество всех входных значений, отображаемых в C, даже если у f нет обратной функции. Принадлежность двум прообразам означает, что один и тот же вход отображается в оба целевых множества. Следовательно, прообразы сохраняют объединения, пересечения и дополнения относительно заявленной области определения и кодомена. Не переносите теоремы о прообразах на образы. Если f инъективна, то пересечения образов становятся равными, поскольку одинаковые значения вынуждают наличие общего аргумента.

Отношение R на X рефлексивно, если xRx для каждого x, симметрично, если xRy влечет yRx, и транзитивно, если xRy и yRz влекут xRz. Все три свойства вместе образуют отношение эквивалентности; его классы разбивают X. На целых числах отношение xRy, при котором x и y имеют одинаковый остаток от деления на четыре, дает четыре класса. Отношение |x−y|≤1 рефлексивно и симметрично, но не транзитивно: 0R1 и 1R2, в то время как 0 не находится в отношении с 2. Проверки одной-двух диаграмм или свойств недостаточно.

Импликация P⇒Q ложна тогда и только тогда, когда P истинно, а Q ложно. Следовательно, отрицание P⇒(Q∧R) есть P∧(¬Q∨¬R), а не ¬P⇒(¬Q∧¬R). Отрицание «для каждого x выполняется свойство A» дает «существует x, для которого A не выполняется»; отрицание «существует x» дает «для каждого x не выполняется». Контрпример опровергает универсальное утверждение, тогда как примеры не могут его доказать. При индивидуальном отрицании кванторы сохраняют порядок: ¬(∀x∃y S(x,y)) равносильно ∃x∀y ¬S(x,y).

Пусть f отображает как a, так и b в метку L. При A={a}, B={b} имеем f(A∩B)=∅, но f(A)∩f(B)={L}. Для отношения xRy, заданного условием x=y или x=−y на множестве R, рефлексивность и симметрия следуют непосредственно из определения, а два изменения знака все равно дают z=±x, что доказывает транзитивность. Классы включают {x,−x}, где {0} — одноэлементное множество (синглетон). Ложное утверждение «каждый сохраненный файл имеет хеш» означает, что существует хотя бы один сохраненный файл без хеша; это не означает, что у всех файлов нет хешей.

f⁻¹(C) может означать прообраз множества без наличия обратной функции. Рефлексивное и симметричное отношение все еще может не быть транзитивным. Отрицайте все высказывание целиком перед упрощением его частей.

Докажите $f(A\cap B)\subseteq f(A)\cap f(B)$. Приведите пример строгого включения. При каком дополнительном предположении о f равенство будет выполняться для любых A и B?

Разобранное решение

Если $y=f(x)$ для $x\in A\cap B$, то x принадлежит каждому множеству, поэтому y принадлежит каждому образу. Для демонстрации строгого неравенства отобразим различные a,b в один и тот же c и возьмём $A=\{a\}$, $B=\{b\}$. Левый образ пуст, а правое пересечение равно $\{c\}$. Если f инъективна и $y=f(a)=f(b)$ с $a\in A,b\in B$, то инъективность даёт a=b в пересечении, доказывая обратное включение. Обратное следует из примера с синглетом: равенство для всех пар влечёт инъективность.

На множествах целых чисел определим $aRb$, когда $a-b$ делится на 4. Докажите, что это отношение эквивалентности, и опишите каждый класс. Отрицание: «Для каждого целого n существует целое m, большее n, не обладающее свойством P».

Проверка после выполнения

Рефлексивность использует $a-a=0$; симметрия — отрицание кратного четырём; транзитивность — сумму двух таких кратных. Классы — четыре вычета по модулю четырёх; класс числа a равен $a+4\mathbb Z$. Отрицание гласит: существует целое n, такое что каждое целое m, большее n, не обладает свойством P. Эквивалентно $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$. Это не утверждает, что P не выполняется ни для одного целого, и не означает, что m ≤ n для всех m.