Help with a proof in my discrete math summer class

In summary, to prove the set equality A = B, we must show that if x is in A, then x is in B, and if x is in B, then x is in A. By definition of A and B, x must be a perfect square and a square root of an integer, respectively. Through algebraic manipulation, we can show that the two sets are equivalent. Therefore, A = B.
  • #1
CapnCornbread
3
0

Homework Statement



Let A be the set of all integers x such that x is = k2 for some integer k
Let B be the set of all integers x such that the square root of x, SQRT(x), is an integer
Give a formal proof that A = B. Remember you must prove two things: (1) if x is in A, then x is in B, AND (2) if x is in B, then x is in A


Homework Equations





3. Why I am so useless
I am taking an online discrete math class as a prerequisite for my major. The prof is a nice enough person, but the extent of help that he provides on questions that I have asked is "read the book". Which I have...and it didn't help me in this case. If someone could point me in the right direction of how to get this proof underway, I would appreciate it.
 
Physics news on Phys.org
  • #2
CapnCornbread said:

Homework Statement



Let A be the set of all integers x such that x is = k2 for some integer k
Let B be the set of all integers x such that the square root of x, SQRT(x), is an integer
Give a formal proof that A = B. Remember you must prove two things: (1) if x is in A, then x is in B, AND (2) if x is in B, then x is in A

Since this is your first post, here's a couple of useful hints.

You don't mean what you wrote for A. What you have written would mean A was the even integers. You should write it as k^2 or, better, use the X2 key above your edit window. So A = {x: x is an k2 for some integer k} which we might more informally call the perfect squares. And B is, informally, the integers that are square roots of other integers.

First you might argue that both sets only contain positive integers. Now suppose x is in A. Can you make an argument that it is in B? Then you have to do the other way.
 
  • #3
Welcome to PF!

Hi CapnCornbread! Welcome to PF! :wink:

Show us your attempt at (1) first. :smile:
 
  • #4
OK, I was thinking I could do something like this:
To prove this example of set equality, we need to undertake two steps: first, show that if x is in A then X is in B, and second, show that if x is in B then X is in A.
First, Assume x ∈A. Then by definition of A, x = k2 for some integer k. Thus by algebra, x = k2 = SQRT(k) * SQRT(k). Therefore x ∈B.
Next, Assume x ∈B. Then by definition of B, SQRT(x) for some integer k. Thus by algebra, x = SQRT(k) = k2. Therefore x ∈A.
We have shown that both A⊆B and B⊆A, therefore A = B.
 
  • #5
CapnCornbread said:
OK, I was thinking I could do something like this:
To prove this example of set equality, we need to undertake two steps: first, show that if x is in A then X is in B, and second, show that if x is in B then X is in A.
First, Assume x ∈A. Then by definition of A, x = k2 for some integer k. Thus by algebra, x = k2 = SQRT(k) * SQRT(k). Therefore x ∈B.

You really need to use the X2 icon. You are close, but your equality
k2=SQRT(k) * SQRT(k) isn't true because the left and right sides aren't equal. Think about it a little more.

Next, Assume x ∈B. Then by definition of B, SQRT(x) for some integer k. Thus by algebra, x = SQRT(k) = k2. Therefore x ∈A.
We have shown that both A⊆B and B⊆A, therefore A = B.

Again, sqrt(k) ≠ k2. Do you need that?
 
  • #6
With revisions:
Assume x ∈A. Then by definition of A, x = k2 for some integer k. Thus by algebra,
x = k2 = k * k. Therefore x ∈B.
Assume x ∈B. Then by definition of B, SQRT(x) for some integer k. Thus by algebra, x = SQRT(k) * SQRT(k) = k. Therefore x ∈A.
We have shown that both A⊆B and B⊆A, therefore A = B.
 

1. What is discrete math?

Discrete math is a branch of mathematics that deals with objects that can only take on distinct, separated values. It includes topics such as set theory, logic, graph theory, and combinatorics.

2. Why is discrete math important?

Discrete math is important because it provides the foundation for many areas of computer science, including algorithms, data structures, and cryptography. It also has applications in fields such as physics, engineering, economics, and biology.

3. How do I approach a proof in discrete math?

To approach a proof in discrete math, it is important to first understand the definitions and concepts involved. Then, carefully read and analyze the problem, identify any given information and what needs to be proven, and try to think of a logical approach or strategy to solve it. Don't be afraid to use diagrams or examples to aid your understanding.

4. What are some common proof techniques used in discrete math?

Some common proof techniques used in discrete math include mathematical induction, direct proof, contrapositive proof, proof by contradiction, and proof by cases. It is important to be familiar with these techniques and know when to apply them in different problems.

5. How can I improve my skills in discrete math proofs?

The best way to improve your skills in discrete math proofs is through practice. Start with simple problems and gradually work your way up to more complex ones. Also, make sure to understand the underlying concepts and definitions, and seek help from your instructor or classmates if you are stuck on a problem.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
24
Views
672
  • Calculus and Beyond Homework Help
Replies
9
Views
981
  • Calculus and Beyond Homework Help
Replies
3
Views
3K
  • Calculus and Beyond Homework Help
Replies
10
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
857
  • Calculus and Beyond Homework Help
Replies
3
Views
466
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Back
Top