4
votes
1answer
75 views

The “converse” of $P\rightarrow(Q\rightarrow R)$

As everyone know, even when reading mathematics books, a paragraph written in natural language contains much more information than just its purely logical translation. For my next tutor session, I am ...
2
votes
1answer
43 views

Non-isomorpic uncountable dense linear orderings (a textbook example)

We know that two countable dense open orderings are isomorphic, and we know that this is generally not true for uncountable structures. Now I quote from the textbook, that is "Model-Theoretic Logics": ...
4
votes
3answers
229 views

Does Gödel's Completeness Theorem still hold even if the set of variables is finite?

Let $L$ be a first order language with a finite set of variables. Let $T$ be a consistent set of formulas of $L$. Does it follow that there exists a model for $T$?
1
vote
1answer
88 views

Example of two finitely isomorphic structures (or $\omega$-isomorphic) that are not partially isomorphic?

One can define several maps between given structures in order to portray similarities or differences. The concept of isomorphism displays a deep structural overlapping, while for instance an ...
4
votes
3answers
136 views

Peculiar examples to the Stone Representation Theorem

The Stone Representation theorem states that every Boolean algebra is isomorphic to a field of sets. That is, a Boolean algebra whose elements are sets, and sums, products, negation are union, ...
0
votes
3answers
124 views

Can a premise imply contradictory statements?

Can a premise imply contradictory statements? Can two contradictory premises imply the same conclusion? Determine the answers to these questions by doing the following. Prove or disprove: the ...
2
votes
4answers
73 views

Mixing and Distributing Qualifiers ($\forall x$, $\exists x$)

Context I'm having trouble understanding the limited situations in which qualifiers can be distributed. I am given that the rules are: $$\forall x\left[P(x)\land Q(x)\right]\equiv\forall xP(x) ...
2
votes
4answers
131 views

Boolean prime ideal theorem and the axiom of choice

The Boolean prime ideal theorem is strictly stronger than ZF, and strictly weaker than ZFC. I'm looking for nice examples (like the existence of non-measurable set) that request at least that theorem ...
1
vote
1answer
66 views

Counterexample for the logical argument

Give a counter example to show the argument is not valid by using formulas from a particular structure interpreting the language. $\forall x\exists y (r_1xy)$ $\forall y \exists x (r_2xy)$ then, ...
2
votes
2answers
244 views

How to prove if something is false or true?

I'm a bit stuck at a task i'm working on here. Here is the task: Show statement "If $(P \rightarrow Q)$ and $(Q \rightarrow R)$ is true, then $(P \rightarrow R)$ is true by a counter ...
20
votes
7answers
484 views

Illustrative examples of a phenomenon in the logic of mathematical induction

It is said (and I myself have said) that in some cases the easiest way to prove a statement by mathematical induction is to prove a stronger statement by mathematical induction, because then one has a ...
4
votes
2answers
155 views

Counterexample in propositional logic

There is this lemma: Let $\Sigma\subset \textrm{Prop}(A)$ and $p, q \in \textrm{Prop}(A)$. Then $\Sigma\models p \implies \Sigma\models p\vee q$. I can't figure out a counterexample for the opposite ...
6
votes
1answer
106 views

How we can understand one category is small

"A category is said to be small if its objects form a set." Now one question is in my mind and that is although we know lots of sets and always working with them, but how we can show a class of ...
3
votes
1answer
156 views

Tarski-Vaught test for $\preceq$ reduction

The Tarski-Vaught test for $\preceq$ states that given a structure $\mathfrak{B}$ and $A\subseteq B$ then $A$ is the underlying set of an elementary substructure of $\mathfrak{B}$ iff for all formulas ...
4
votes
4answers
300 views

Examples of partial functions outside recursive function theory?

My math background is very narrow. I've mostly read logic, recursive function theory, and set theory. In recursive function theory one studies partial functions on the set of natural numbers. Are ...
1
vote
2answers
302 views

predicate logic - counterexample $(A \models \phi \implies A \models \psi) \implies A \models \phi \rightarrow \psi$

It's predicate logic and I need to find a counterexample to disprove the follwowing claim $(A \models \phi \implies A \models \psi) \implies A \models \phi \rightarrow \psi$
4
votes
1answer
150 views

Are there simple counterexamples to a strengthening of omitting types theorem

The famous Ehrenfeucht's omitting types theorem states that for any countable set of nonisolated types (without parameters), there is a (countable) model such that it does not realize any of them. A ...
2
votes
4answers
153 views

What's an example on Interpretability?

From wikipedia: In mathematical logic, interpretability is a relation between formal theories that expresses the possibility of interpreting or translating one into the other. ... ...
3
votes
1answer
121 views

Automorphisms of elementary extensions

I think this is probably a very simple question, but I've been puzzling over it for a while and can't seem to get anywhere. Suppose $M$ is a structure, $\alpha$ is an automorphism of $M$, and $N$ is ...
27
votes
5answers
2k views

An example of an easy to understand undecidable problem

I am looking for an undecidable problem that I could give as an easy example in a presentation to the general public. I mean easy in the sense that the mathematics behind it can be described, well, ...
4
votes
0answers
224 views

Interesting applications of the cofinite topology?

Background: I'm doing some expository writing on intuitionistic logic and I have been toying with the idea of demonstrating its applicability via models where the denotations are taken from a Heyting ...