Tagged Questions

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 ...
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": ...
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$?
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 ...
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, ...
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 ...
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) ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$
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 ...
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. ... ...
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 ...