Proof by contradiction and function

[MeConfused]

Homework Statement

Problem 1
Assuming that the people in D and C all have KTP (Citizen ID in my country) IDs, let:

D = {x |x is the KTP ID of a student in your Basic Calculus class},

C = {y |y is the KTP ID of the biological father/mother of a student in your Basic Calculus class},

and f : D ->C be the function that relates a student in your Basic Calculus class to his/her

biological father and mother.

1. It is clear that f does not exist. Why?

2. You can fix C such that f exists. Express your fix formally using the set-builder notation,

and then, formally define f!Problem 2
Proof by contradiction that if p^2 is an odd number, then p is an odd number too, profided
p is an element of integer numbers

Homework Equations

The Attempt at a Solution

Problem 1
1. Because a case can occur when both the student's father and mother are in the list as there is no rule that say it can't, if that occur, then f is not a function as it fails the vertical line test

2.D= {x|x is the KTP ID of a student in calculus class}
C= {y|y is the KTP ID of either a student's father or mother}
f(x)= KTP number of a student's father or mother

I've submitted these answers to my lecturer and have been told that both were wrong. Number 2 is wrong my way of fixing it does not uphold the required relationship

Problem 2
I've followed like they did here http://proofsfromthebook.com/2014/09/28/odd-and-square/. I thought it's proof by contraposition and told by my lecturer that it was.

 

[Fredrik]

I don't think you have defined C clearly enough. (What does "father/mother" mean?). I'm guessing that you mean that C contains the KTP ID's of all the fathers, the KTP ID's of all the mothers, and nothing else.

The question about f doesn't entirely make sense. It doesn't make sense to say that f is some specific function, and then say that f doesn't exist. If it doesn't exist, then it isn't a function. But I guess it's clear enough that what they're asking you to do is to explain why the statement that's supposed to define f is inadequate. I wouldn't say that your answer is wrong, but it can be improved somewhat. If Charlie's parents are Alice and Bob, then what does the definition say that f(Charlie) is? Is it an element of D?

Your attempt to change the definitions of C and f doesn't work because you haven't made it clear what exactly the elements of C are, or what each f(x) is.

One of the most basic results in logic is that $A\Rightarrow B$ is equivalent to $\lnot B\Rightarrow\lnot A$. The latter statement is called the contrapositive of the former. So if you want to prove "p² odd ⇒ p odd", you can do it by proving its contrapositive.

An alternative approach is to start with the statement "suppose that p² is odd", and then try to prove that p is odd. You can use a proof by contradiction to do this. It would be best to explain what you're going to do: "We're going to prove that p is odd by deriving a falsehood from the assumption that it's not. So suppose that p is not odd". This approach is more complicated, but perhaps more deserving of the label "proof by contradiction".

Note that in this approach, we prove A ⇒ B by assuming A and proving B. It's B that's proved by contradiction, not the implication A ⇒ B. If you really want to prove the implication by contradiction, you have to assume that it's false. This is to assume that A is true and B is false. Then you derive a falsehood from those assumptions.

 

[HallsofIvy]

You start by saying "assuming the people in C and D" and then define C and D as sets of numbers, not people!
Problem 1 follows from the definition of "function"- what is that definition?

"Proof by contradiction" starts by assuming the conclusion is false, then finding a contradiction. Here, the conclusion is "then p is an odd number". If p in NOT an odd number, it is an even number.

 

[MeConfused]

Hi, thanks for the response. For problem 1 doesn't the problem already define the elements of D and C?

 

[HallsofIvy]

Hi, thanks for the response. For problem 1 doesn't the problem already define the elements of D and C?

Yes, but NOT as "sets of people" so you cannot talk about the "people" in sets C and D!

 

[Fredrik]

Hi, thanks for the response. For problem 1 doesn't the problem already define the elements of D and C?

The problem statement defines D clearly, but I don't think it's clear what "father/mother" means. However, the only interpretation I see is that C is the set of all the KTP IDs of all the parents of the students whose KTP IDs are included in C. If that interpretation is correct, then I would say that the problem has defined D clearly and C sufficiently clearly.

But you also said this:

2. You can fix C such that f exists. Express your fix formally using the set-builder notation,

and then, formally define f!

Doesn't this mean that you should change the definition of C before you attempt to define f?