Help me Prove that such a set does NOT exist

In summary, the conversation discusses the theory of Robinson Arithmetic (Q) and the concept of a nice theory, which is consistent, p.r. adequate, and extends Q. The fixed-point lemma states that for any nice theory T and formula φ, there is a sentence σ such that T proves σ if and only if φ holds for "σ." The conversation then introduces the set gn(X) which contains the Godel numbers of all formulas in X, denoted by "φ." The task at hand is to prove that there is no decidable set R that contains all Godel numbers of formulas in Q and also contains the Godel numbers of all formulas in Q that are negated.
  • #1
norman95
6
1
  1. Let Q denote the theory of Robinson Arithmetic. A theory T is nice iff T is consistent, is p.r. adequate and extends Q. The fixed-point lemma states that for all nice theories T, for any formula φ, there is a sentence σ such that
    T ⊢σ↔φ("σ") Given a set of formulas X, let gn(X) = {"φ" | φ ∈ X} be the set of Godel numbers of formulas in X. (Quotation mark denote Godel numbers.) Prove that there is no decidable set R such that gn(Q) ⊆ R and gn({σ | ¬σ ∈ Q}) ⊆ R.

Please help guys, I've been really sick for the last two week and missed all the relevant material, and now this is due tonight!
 
Physics news on Phys.org
  • #2
This is what I have so far, but I have no idea if it's anywhere close to correct and I have like 4 chapters of my textbook that I need to cover the relevant materiel. My intuition is that either I have to show some sort of overlap between R and R-completment, or that I have to show that the decideability of R entails the decideability of Q (which is a contradiction).
 

Attachments

  • Scan.jpeg
    Scan.jpeg
    65.5 KB · Views: 442

FAQ: Help me Prove that such a set does NOT exist

Can you provide evidence or proof that a set does not exist?

Yes, as a scientist, proving the non-existence of something is just as important as proving its existence. To prove that a set does not exist, we can use logical reasoning, mathematical principles, and empirical evidence. We can also use the concept of a null set, which is a set that contains no elements, to demonstrate that a set does not exist.

Why is it important to prove that a set does not exist?

Proving that a set does not exist is important because it allows us to clarify and refine our understanding of the world. It also helps us avoid making false assumptions or conclusions based on a non-existent set. Additionally, disproving the existence of a set can lead to new discoveries and advancements in the field of science.

Is it possible for a set to exist and not exist at the same time?

No, it is not possible for a set to exist and not exist at the same time. This concept is known as the law of non-contradiction, which states that something cannot be both true and false at the same time. Therefore, if a set does not exist, it cannot exist simultaneously.

What are some common methods scientists use to prove that a set does not exist?

Scientists may use various methods to prove that a set does not exist, including logical reasoning, mathematical proofs, experiments, and observations. They may also use the principle of falsifiability, which states that a scientific theory must be testable and can be proven false through evidence or experimentation.

Can the non-existence of a set be proven definitively?

Yes, in most cases, the non-existence of a set can be proven definitively. However, there may be some situations where the non-existence of a set is difficult to prove due to lack of evidence or limitations in our current understanding. In these cases, scientists may continue to gather more evidence and refine their methods to definitively prove or disprove the existence of a set.

Similar threads

Proving intersection of finitely many open sets is open
Replies
1
Views
2K
Prove Zorn's Lemma is equivalent to the following statement
Replies
2
Views
2K
Proof by Induction of shortest suffix of concatenated string
Replies
1
Views
1K
I May I use set theory to define the number of solutions of polynomials?
Replies
13
Views
2K
Abstract math, sets and logic proof
Replies
2
Views
2K
Proving Compact Set Exists with m(E)=c
Replies
11
Views
2K
I solving a proof dealing with the set of irrational numbers.
Replies
1
Views
1K
How to prove a set belongs to Borel sigma-algebra?
Replies
7
Views
6K
Proving Countable Infinite Accumulation Points in a Set
Replies
5
Views
6K
Proving a is Supremum of Set E
Replies
18
Views
4K

Hot Threads

Recent Insights

Back
Top