Proving ∃x(P(x) → ∀y(P(y))): An Exercise in Logic

In summary, the task at hand is to prove the statement ∃x(P(x) → ∀y(P(y))) and the most common approach is to use a proof by contradiction. Some have attempted to solve it but are unsure if their proof is correct.
  • #1
Syrus
214
0

Homework Statement



Prove ∃x(P(x) → ∀y(P(y))).

Homework Equations





The Attempt at a Solution



∃x(P(x) → ∀y(P(y))) is equivalent to ∃x(¬P(x) ∨ ∀y(P(y))).



This exercise is found in a section on "proofs involving disjunctions." I have tried many different ways to solve this and have a feeling I am not approaching it the right way. Perhaps I am not considering clever enough exhaustive cases? Can anyone direct me in the proper way to begin?
 
Physics news on Phys.org
  • #2
This is an exercise from "How to prove it" right?:biggrin:

I'm having troubles with this one too.

I've tried a proof by contradiction, i think i proved it but I'm not so sure.
 

1. What does the statement "∃x(P(x) → ∀y(P(y)))" mean?

This statement is a logical expression that translates to "There exists an x such that if P(x) is true, then for all y, P(y) is also true." In other words, there is at least one element x for which the statement P(x) implies that P(y) is true for all elements y.

2. Can you provide an example of this statement?

One example of this statement could be "There exists a number x such that if x is even, then all numbers y are even." In this case, the statement is true because x can be any even number and the implication holds true for all y.

3. How do you prove this statement?

To prove this statement, you need to use the rules of logic and set theory to show that there exists an x that satisfies the given condition. This can be done by assuming that P(x) is true and using logical deductions to show that ∀y(P(y)) is also true.

4. What is the significance of proving this statement?

In logic and mathematics, proving statements like this one helps to establish the validity and truth of certain assumptions. It also allows for the development of new theorems and theories based on these proven statements.

5. Can this statement be false?

Yes, this statement can be false if there does not exist an x that satisfies the given condition. For example, if we change the statement to "∃x(P(x) → ∀y(Q(y)))", where Q(y) is the statement "y is a prime number," then the statement becomes false because there is no x for which P(x) implies that all numbers y are prime.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
594
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
806
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
Back
Top