/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 17 Show that if there is an injecti... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 4: Problem 17

Show that if there is an injective function \(g: B \rightarrow A,\) and \(B\) is non-enumerable, then so is \(A\). Do this by showing how you can use \(g\) to turn an enumeration of \(A\) into one of \(B\).

Short Answer

Expert verified
The proof shows that if there exists an injective function from B to A and B is non-enumerable, then A must also be non-enumerable. This result is derived by attempting to construct a bijective function from the natural numbers to A, which leads to a contradiction if A is considered enumerable.

Step by step solution

01

Understanding the concept

In this proof, we will use the basic properties of injective functions and non-enumerable sets. Firstly, a non-enumerable set is a set that cannot be listed or enumerated, meaning that it does not have a listing of its elements that is both complete and countable. Secondly, an injective function (or one-to-one function) is a function with the property that no two different inputs will produce the same output.
02

Constructing the proof

Let's assume on the contrary that A is enumerable. So, there exists a bijective function \(f: \mathbb{N} \rightarrow A\). Now, we can define a new function \(h: \mathbb{N} \rightarrow B\) by \(h(n) = g^{-1}(f(n))\), where \(g^{-1}\) is the inverse of \(g\). This function is well-defined because for every element in A, there is a unique corresponding element in B (by the definition of an injective function).
03

Reaching the Contradiction

According to the definition of \(h\), it is clear that it is a bijective function from \(\mathbb{N}\) to \(B\). Consequently, it seems like we've just managed to enumerate the set B, which contradicts our initial assumption that B is non-enumerable. So, the assumption that A is enumerable must be false. Therefore, if there is an injective function from B to A, and B is non-enumerable, then A is also non-enumerable. This completes our proof.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Show that a set \(A\) is enumerable iff either \(A=\varnothing\) or there is a surjection \(f: \mathbb{N} \rightarrow A\). Show that \(A\) is enumerable iff there is an injection \(g: A \rightarrow \mathbb{N}\)

Show that the set of all sets of pairs of positive integers is nonenumerable by a reduction argument.

Recall from your introductory logic course that each possible truth table expresses a truth function. In other words, the truth functions are all functions from \(\mathbb{B}^{k} \rightarrow \mathbb{B}\) for some \(k\). Prove that the set of all truth functions is enumerable.

Define an enumeration of the square numbers \(1,4,9,16, \ldots\)

Show that if \(A\) and \(B\) are enumerable, so is \(A \cup B\). To do this, suppose there are surjective functions \(f: \mathbb{Z}^{+} \rightarrow A\) and \(g: \mathbb{Z}^{+} \rightarrow B,\) and define a surjective function \(h: \mathbb{Z}^{+} \rightarrow A \cup B\) and prove that it is surjective. Also consider the cases where \(A\) or \(B=\varnothing\).
See all solutions

Recommended explanations on Math Textbooks

Logic and Functions

Read Explanation

Statistics

Read Explanation

Discrete Mathematics

Read Explanation

Calculus

Read Explanation

Decision Maths

Read Explanation

Pure Maths

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.